Forth
http://fforum.winglion.ru/

Задача - выбор пробела
http://fforum.winglion.ru/viewtopic.php?f=19&t=2698
Страница 4 из 4

Автор:  вопрос [ Сб фев 05, 2011 00:09 ]
Заголовок сообщения:  Re: Задача - выбор пробела

chess писал(а):
вопрос писал(а):
Нет, всё-таки меньше и при сноровке - значительно, но в другом направлени

Вот по решению задачки я бы этого не сказал. А наработать алгоритмы перебора вариантов и в Форте можно, если понадобится.
Я не вижу что можно привнести из Пролога в Форт полезного, как впрочем и из других языков. :)

Нет, ну надо сохранять обьективность.
решение на форте было неправильным, пока не было проверено на Прологе, решение на котором было написано с первого раза и выдавало и правильные и неправильные варианты и путь поиска можно было, если бы хотелось и в любую сторону модифицировать и т.д. Более того, оно ещё и по скорости было сравнимо с первым форт-решением (и даже (что не может быть) превосходило) :)

Я всё жду пояснений, что именно сохраняет время в последнем :shuffle;

Автор:  chess [ Сб фев 05, 2011 10:06 ]
Заголовок сообщения:  Re: Задача - выбор пробела

вопрос писал(а):
Нет, ну надо сохранять обьективность.решение на форте было неправильным, пока не было проверено на Прологе, решение на котором было написано с первого раза и выдавало и правильные и неправильные варианты и путь поиска можно было, если бы хотелось и в любую сторону модифицировать и т.д. Более того, оно ещё и по скорости было сравнимо с первым форт-решением (и даже (что не может быть) превосходило)

Просто я реализовал алгоритм Antender'a - он оказался неверным. После того как я это понял
уже проанализировав этот алгоритм я перешел к тупому перебору( вообщем это всегда неинтересный вариант). Ну конечно перебор может быть тоже разным. С отсечениями, например.
Кроме того внутри перебора могут существовать процедуры, которые могут быть реализованы
с разной степенью эффективности. Вот эти два момента - отсечение и повышение эффективности
были проделаны, причем второе не до конца.
Отсечение - счет максимума пар при убирании очередного разделителя заканчивается после того как текущее насчитанное значение числа пар
превысит текущий минимум максимума для уже пройденных разделителей. Если прерывания счета пар не произошло, то текущий минимум заменяется на только что посчитанный.
Эффективность - обнуление таблицы для подсчета числа пар делается только по позициям
имеющихся пар, а не по всем 16384 позициям.
Недоделано - проход по парам при обнулении таблицы ведется по парам исходной строки, а
надо только однократно по разным парам этой строки, проход по разделителям также идет по исходной строке, а надо по однократно по разным разделителям.
А вообще-то я нашел алгоритм сводящий перебор к минимуму. Будет время - реализую.
Пролог на такое не способен :D

Автор:  chess [ Вт фев 08, 2011 21:47 ]
Заголовок сообщения:  Re: Задача - выбор пробела

chess писал(а):
Будет время - реализую.


Код:
M: aDO ( a u -- ) D=A A=@P @P+D DO ;
: space ( a u -- )   u!  a!
0x100 ad] 0 nd! 0x100 ad1] 0x100 asd] 0. d! n! 0x100 asdm] 0 nm!
0x40000   ap] 0x20000  asp] 0. p! m! 0. max! t! 0 maxg!
sd( a u  aDO 1 I C@ ad + C! LOOP ad 0x100 aDO I C@ IF I ad - ad1 nd + C! nd 1+ is nd THEN LOOP )
noBL?( is t t 0xFF AND d <> t 0xFF00 AND 8 RSHIFT d <> AND )
ap0( asp m aDO 0 I W@ 4 * ap + ! 2 +LOOP )
emd( aDO I C@ EMIT SPACE LOOP )
maxBL( 0 is max ap0 a u 1- aDO I W@ noBL? IF t 4 * ap + DUP 1+! @ max MAX is max THEN LOOP )
a u 1- aDO I W@ is p p 4 * ap + @ 0= IF p asp m + W! m 2+ is m  THEN
           p 4 * ap + DUP 1+! @ max MAX is max LOOP max is maxg
asp m  aDO I W@ 4 * ap + @ maxg =
IF   asdm nm + C@ 0= IF I C@ asdm nm + C! I 1+ C@ asdm nm + 1+ C! nm 2+ is nm THEN
ELSE asd  n  + C@ 0= IF I C@ asd  n  + C! I 1+ C@ asd  n  + 1+ C! n  2+ is n  THEN THEN 2 +LOOP
asd C@ is d maxBL max maxg = IF sd ( ad1 nd emd ) ELSE ( asdm nm emd ) THEN ;

T: str 23241214542365432175326526432561 ;
str space
STARTLOG
: test 100000 0 DO str space LOOP ;
REQUIRE .elapsed   G:/spf/devel/~af/lib/elapse.f
time-reset test .elapsed

лог
Код:
Elapsed time: 00:00:00:141
Ok

( 1.41 мкс )
пс. На малых длинах строки алгоритм не сильно ускоряет по сравнению с перебором.

Автор:  вопрос [ Вт фев 08, 2011 21:49 ]
Заголовок сообщения:  Re: Задача - выбор пробела

Такой хороший результат нужно снабдить комментарием для надёжности :)
:hey;
и, если это нетрудно - у всех разные компьютеры, нельзя ли скорость или указывать компьютер или в относительных единицах.

Автор:  chess [ Вт фев 08, 2011 21:52 ]
Заголовок сообщения:  Re: Задача - выбор пробела

chess писал(а):
и, если это нетрудно - у всех разные компьютеры, нельзя ли скорость или указывать компьютер или в относительных единицах.

Результат не показательный - вх.строка короткая. Всего в 4 раза быстрее переборного варианта.

Страница 4 из 4 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/