Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Ср май 23, 2018 07:04

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Обьединение упорядоченных списков.
СообщениеДобавлено: Сб мар 22, 2008 14:13 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Дано:
- область памяти начиная с адреса A содержащая N чисел (CELLS) последовательно;
- первые N1<N чисел упорядочены по возрастанию;
- следующие N2=N-N1 чисел тоже упорядочены по возрастанию;
- размеры областей могут быть в пределах: 0<N1<2^29; 0<N2<2^29.
Пример последовательности для N1=5, N2=4: 3, 9, 23, 23, 41, 21, 22, 93, 112

Требуется:
- разместить все N чисел в порядке возрастания.
Для вышеприведенного примера результат должен быть: 3, 9, 21, 22, 23, 23, 41, 93, 112

Ресурсы:
- алгоритм представить на Форте в соответствии с http://fforum.winglion.ru/viewtopic.php?p=7402#7402 ;
- не допускается применение ассемблера;
- можно использовать дополнительные области памяти (переменные, буферы, и т.д.) только фиксированного размера, независимого от N и суммарным обьемом не более 1024Кб.

Критерий оценки:
- решение должно быть более эффективным за представленный ниже пример;
- достижение максимальной скорости выполнения (на уровне алгоритма);
- использование минимальных ресурсов.

Пример тривиального решения задачи (ANSI):
Код:
\ a1 - адресс первой области, равен A
\ n1 - количество чисел в первой последовательности
\ a2 - адресс второй области, равен: a1 n1 CELLS +
\ n2 - количество числе во второй последовательности, равно N-N1
: MERGE ( a1 n1 a2 n2 )
LOCALS| N2 A2 N1 A1 |  \ используются локальные переменные для наглядности
BEGIN
  A1 @ A2 @ <  \ смотрим откуда брать минимальное число
  IF \ если оно в первой последовательности, просто его пропускаем
   A1 CELL+ TO A1 
   N1 1- TO N1
  ELSE \ если оно во второй, делаем ротацию:
   A2 @ \ читаем число из второй последовательности
   \ перемещаем остаток первой последовательности на одно число вверх:
   A1 DUP DUP CELL+ DUP TO A1 N1 CELLS MOVE
   ! \ сохраняем минимальное число в освободившееся место
   \ переходим к следующему числу второй последовательности:
   A2 CELL+ TO A2
   N2 1- TO N2
  THEN
  N1 0= N2 0= OR \ завершаем работу по исчерпанию любой последовательности
UNTIL
;

Этот вариант в худшем случае выполняет копирование N1*N2 чисел. Требуется более быстрое решение.
Желаю удачи! :)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб мар 22, 2008 15:01 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
По идее, кажется, надо искать вариант,
который выполняется быстрее, чем обыкновенный QuickSort на массиве N1+N2 чисел...
Ибо N1*N2 в большинстве случаев больше чем (N1+N2)Ln2(N1+N2)/2

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб мар 22, 2008 15:58 
Не в сети

Зарегистрирован: Вс дек 02, 2007 17:31
Сообщения: 442
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Вообще то, в данном случае нет смысла применять полноценные сортировочные алгоритмы, поскольку списки уже отсортированы. ;)
[...дальше было слишком много подсказок... :shuffle; ]


Последний раз редактировалось Forthware Вс мар 23, 2008 19:20, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб мар 22, 2008 20:23 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Если не экономить память, то алгоритм "Бери больше, кидай дальше" отработает с O(N) сравнениями и N пересылками.

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB