Задача - выбор пробела

Antender

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

вопрос

Цитата:

А сколько дает Пролог по времени?

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

chess

Antender писал(а):

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

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

Antender

chess писал(а):

Antender писал(а):

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

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

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

chess

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').
А как разительно изменилось решение. Теперь все символы - разделители.

вопрос

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
что соответствует

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

вопрос писал(а):

в то же время мой алгоритм с эквилибристикой на стеке даёт
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.можно еще как минимум на порядок ускорить , но надо побольше кода писать
Похоже Прологи проигрывают Форту

вопрос

chess писал(а):

вопрос писал(а):

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

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

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

вопрос

chess писал(а):

При переходе на 'время-сберегающие' технологии код ускорился почти на 2 порядка:

Код:

Elapsed time: 00.00.00.516
 Ok

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

Ага сейчас только понял, что chess шутит: сравнивать в абсолютных цифрах время выполнения на 2 разных процессорах, один из которых 2ядерный

Просьба дальше постить только в относительных цифрах: не так трудно запустить и "чужой" код
в относительных цифрах ускоренный код chess' a превосходит мой как 4:7, т.е. 1.75

Цитата:

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

Да, на 3 порядка могут проигрывать, если использовать интерпретацию, которая текстовая

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

chess

вопрос писал(а):

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

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

Hishnik

chess писал(а):

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

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

вопрос

Хищник писал(а):

chess писал(а):

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

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

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

chess

вопрос писал(а):

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

Ну да. Пролог - это не панацея, в нем тоже работать надо.

Причем непонятно по сравнению с Фортом больше или меньше. Мне представляется, что больше.

вопрос

Цитата:

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

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

chess

вопрос писал(а):

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

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

Задача - выбор пробела

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