Forth
http://fforum.winglion.ru/

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

Автор:  Antender [ Пн янв 31, 2011 19:36 ]
Заголовок сообщения:  Re: Задача - выбор пробела

А можно пояснить чем он неправилен?

Автор:  вопрос [ Пн янв 31, 2011 20:55 ]
Заголовок сообщения:  Re: Задача - выбор пробела

Цитата:
А сколько дает Пролог по времени?
А что, никто не пытался запустить?
Смотря какой Пролог, в некоторых есть pl2c с оптимизацией, пожалуй или внутренняя компиляция, эти довольно быстры, в частности binprolog http://progopedia.ru/implementation/binprolog/ вообще - хочу устроить гонку алгоритмов и компиляторов. для этого нужно поместить всё в цикл, в т.ч. Эйфорию? о чём просьба к Antender

Автор:  chess [ Пн янв 31, 2011 20:57 ]
Заголовок сообщения:  Re: Задача - выбор пробела

Antender писал(а):
А можно пояснить чем он неправилен?

Разделитель может входить в несколько семейств одинаковых пар.

Автор:  Antender [ Пн янв 31, 2011 22:16 ]
Заголовок сообщения:  Re: Задача - выбор пробела

chess писал(а):
Antender писал(а):
А можно пояснить чем он неправилен?

Разделитель может входить в несколько семейств одинаковых пар.


А можно объяснить популярней, пожалуйста?

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

Antender писал(а):
А можно объяснить популярней, пожалуйста?

Есть много частных случаев когда можно получить правильный результат только по исходной строке.
Но есть ситуации, когда нужна информация уже по строкам без разделителей. Общий алгоритм не вырисовывается
по той причине, что назвал в предыдущем посте. :(
Короче проще вычислить для каждого разделителя макс. количество одинаковых пар и потом
выбрать разделители, для которых этот максимум минимален. Перебор одним словом.
Чуть ускоренное, по отношению к предыдущему, решение:
Код:
M: aDO ( a u -- )  D=A A=@P @P+D DO ;   M: 4LOOP  4 +LOOP ;
: space ( a u -- ) u! a!    0x40000 ut! 0x100 ud! 4*( 4 * )
ha( ALLOCATE THROW )  ut ha at! ud 4* ha ap! ud ha ad! u ha as!
at0( at ut ERASE ) fa( FREE THROW ) 0. t! d! 0 max! u min!
d~bl( a as u MOVE as u aDO I C@ d = IF BL I C! THEN LOOP )
noBL?( is t t 0xFF AND 0x20 <> t 0xFF00 AND 0x2000 <> AND )
maxp( as u 1- aDO I W@ noBL? IF t 4* at + DUP 1+! @ max MAX is max THEN LOOP )
!mind( d~bl 0 is max at0 maxp max min 1+ < IF max d 4* ap + ! max is min THEN )
a u aDO 1 I C@ ad + C! LOOP   ad ud aDO I C@ IF I ad - is d !mind THEN LOOP
ap ud 4* aDO I @ min = IF I ap - 4 / EMIT SPACE THEN 4LOOP
at fa as fa ap fa ad fa ;
STARTLOG

T: str 23541214542365432175326526432561 ;

str space CR
log
Код:
1 2 3 4 5 6 7
Ok
ps. Прикол в том, что в исходной строке заменен всего один символ (третий с начала строки - было '2' стало '5').
А как разительно изменилось решение. Теперь все символы - разделители.

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

chess писал(а):
А сколько дает Пролог по времени?
например Pentium 4 2.7
0,00225 c SWI
0,0015 c GNU
если только не ошибся при тестировании

при этом предыдущее решение chess даёт 00.00.00.187
если для скорости закомментировать строку с выводом решения
вот так

\ решение
a u aDO 1 I C@ ad + C! LOOP
ad ud aDO I C@ IF I ad - is d d~bl maxp d 4 * ap + ! THEN LOOP \ максимумы пар для каждого разделителя
ap ud 4 * + ap DO I @ DUP 0<> IF min MIN is min ELSE DROP THEN 4 +LOOP \ найти минимум из максимумов пар
\ ap ud 4 * + ap DO I @ min = IF I ap - 4 / DUP EMIT 8 RSHIFT EMIT SPACE THEN 4 +LOOP \ вывести все решения
fa( FREE THROW ) at fa as fa ap fa ; \ освободить хип


если я правильно понял, то это
0,00187 с

в то же время мой алгоритм с эквилибристикой на стеке даёт
Elapsed time: 00:00:00:016
что соответствует :o 0,00016 с
chess писал(а):
Код:
1 2 3 4 5 6 7
Ok
ps. Прикол в том, что в исходной строке заменен всего один символ (третий с начала строки - было '2' стало '5').
А как разительно изменилось решение. Теперь все символы - разделители.

действительно
Цитата:
SOLUTIONS
--------------------
For symbol 1 pair 5 4 found 3 times

For symbol 6 pair 5 4 found 3 times

For symbol 5 pair 3 2 found 3 times

For symbol 2 pair 5 4 found 3 times

For symbol 3 pair 5 4 found 3 times

For symbol 4 pair 3 2 found 3 times

For symbol 7 pair 5 4 found 3 times



NO SOLUTIONS
--------------------

кусок NO SOLUTIONS остался незаполнен

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

вопрос писал(а):
в то же время мой алгоритм с эквилибристикой на стеке даёт
Elapsed time: 00:00:00:016
что соответствует 0,00016 с

При переходе на 'время-сберегающие' технологии код ускорился почти на 2 порядка:
Код:
M: aDO ( a u -- ) D=A A=@P @P+D DO ; \ addr len aDO эквивалентно addr+len addr DO
: space ( a u -- ) u! a! 0x40000 ut!  0x100 ud! 0 t! 0 d! 0 max! u min!
0x40000 at] 0x400 ap] 0x100 ad]
noBL?( is t t 0xFF AND d <> t 0xFF00 AND 8 RSHIFT d <> AND )
maxp( 0 is max  a u 1- aDO 0 I W@ 4 * at + ! LOOP  a u 1-
      aDO I W@ noBL? IF t 4 * at + DUP 1+! @ max MAX is max THEN LOOP max )
a u aDO 1 I C@ ad + C! LOOP
ad ud aDO I C@ IF I ad - is d maxp d 4 * ap + ! THEN LOOP
ap ud 4 * aDO I @ DUP 0<> IF min MIN is min ELSE DROP THEN 4 +LOOP
ap ud 4 * aDO I @ min = IF I ap - 4 / DROP
\ EMIT SPACE
THEN 4 +LOOP  ;

STARTLOG

T: str 23541214542365432175326526432561 ;
str space CR
test: 100000 0 DO str space LOOP ;

REQUIRE .elapsed   G:/spf/devel/~af/lib/elapse.f
time-reset test .elapsed CR

log
Код:
Elapsed time: 00.00.00.516
Ok

Ps. 1.( 0.00000516 --> 5,16 мкс на Core2Duo 3 Ггц )
2.можно еще как минимум на порядок ускорить , но надо побольше кода писать
Похоже Прологи проигрывают Форту :)

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

chess писал(а):
вопрос писал(а):
Похоже Прологи проигрывают Форту :)

А прокомментировать, что именно тут время сберегающее?

пролог не может быть настолько же быстрым как и форт, он ведь обеспечивает логику

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

chess писал(а):
При переходе на 'время-сберегающие' технологии код ускорился почти на 2 порядка:
Код:
Elapsed time: 00.00.00.516
Ok

Ps. 1.( 0.00000516 --> 5,16 мкс на Core2Duo 3 Ггц )
2.можно еще как минимум на порядок ускорить , но надо побольше кода писать
Похоже Прологи проигрывают Форту :)
Ага сейчас только понял, что chess шутит: сравнивать в абсолютных цифрах время выполнения на 2 разных процессорах, один из которых 2ядерный 8) :D
Просьба дальше постить только в относительных цифрах: не так трудно запустить и "чужой" код
в относительных цифрах ускоренный код chess' a превосходит мой как 4:7, т.е. 1.75

Цитата:
Похоже Прологи проигрывают Форту :)

Да, на 3 порядка могут проигрывать, если использовать интерпретацию, которая текстовая :D это легко проверить, если в выражение пролога вставить предикат, который отсутствует, это будет замечено только во время исполнения, т.к. нет даже компиляции на лету

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

вопрос писал(а):
пролог не может быть настолько же быстрым как и форт, он ведь обеспечивает логику

Кстати о Прологе.
Я так понял, что в Прологе реализован механизм поиска, находящий решения логических операторов.
Этот механизм требует много времени из-за своей сложности.
(!)Но всех ситуаций заранее не предусмотришь(аксиома!) - кстати, это один из краеугольных камней Форта.
Поэтому, в общем случае, корректный поиск, без доп. указаний программиста в ходе этого поиска, будет невозможен.
Программист при этом должен понимать в каком состоянии Пролог находится и в чем причина каждого конкретного 'затыка'
процесса лог. вывода.
Вот это уже далеко от первоначального лозунга Пролога - освободить программиста от вникания в сам процесс лог. вывода.
Из-за недопонимания фразы(!) как-раз и погорели японцы с их эвм 5 поколения.

Автор:  Hishnik [ Чт фев 03, 2011 23:42 ]
Заголовок сообщения:  Re: Задача - выбор пробела

chess писал(а):
Поэтому, в общем случае, корректный поиск, без доп. указаний программиста в ходе этого поиска, будет невозможен.

Фразу насчет корректного поиска и указаний программиста не понял. Не перебором же Пролог работает - используется метод резолюций.

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

Хищник писал(а):
chess писал(а):
Поэтому, в общем случае, корректный поиск, без доп. указаний программиста в ходе этого поиска, будет невозможен.

Фразу насчет корректного поиска и указаний программиста не понял. Не перебором же Пролог работает - используется метод резолюций.

Я думаю, что chess словил с другой стороны то, что я говорил в неоконченной статье про
декларативное программирование: нельзя ждать что будет просто задана задача и найдено решение. Потребуются определённые вложения компетентного труда в организацию процесса поиска решения, т.е. внимание к процессу поиска не обойти.

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

вопрос писал(а):
Потребуются определённые вложения компетентного труда в организацию процесса поиска решения, т.е. внимание к процессу поиска не обойти.

Ну да. Пролог - это не панацея, в нем тоже работать надо. :o Причем непонятно по сравнению с Фортом больше или меньше. Мне представляется, что больше.

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

Цитата:
Ну да. Пролог - это не панацея, в нем тоже работать надо. Причем непонятно по сравнению с Фортом больше или меньше. Мне представляется, что больше.

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

Автор:  chess [ Пт фев 04, 2011 22:37 ]
Заголовок сообщения:  Re: Задача - выбор пробела

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

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

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