Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 23:13

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пн янв 31, 2011 19:36 
Не в сети

Зарегистрирован: Вс апр 25, 2010 11:14
Сообщения: 200
Откуда: Москва
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
А можно пояснить чем он неправилен?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пн янв 31, 2011 20:55 
Не в сети

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


Последний раз редактировалось вопрос Пн янв 31, 2011 21:13, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пн янв 31, 2011 20:57 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Antender писал(а):
А можно пояснить чем он неправилен?

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

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пн янв 31, 2011 22:16 
Не в сети

Зарегистрирован: Вс апр 25, 2010 11:14
Сообщения: 200
Откуда: Москва
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
chess писал(а):
Antender писал(а):
А можно пояснить чем он неправилен?

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


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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вт фев 01, 2011 17:57 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вт фев 01, 2011 19:04 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
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 остался незаполнен


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Ср фев 02, 2011 17:49 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
вопрос писал(а):
в то же время мой алгоритм с эквилибристикой на стеке даёт
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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Ср фев 02, 2011 18:08 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
chess писал(а):
вопрос писал(а):
Похоже Прологи проигрывают Форту :)

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

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Ср фев 02, 2011 21:59 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
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 это легко проверить, если в выражение пролога вставить предикат, который отсутствует, это будет замечено только во время исполнения, т.к. нет даже компиляции на лету


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Чт фев 03, 2011 17:52 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
вопрос писал(а):
пролог не может быть настолько же быстрым как и форт, он ведь обеспечивает логику

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

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Чт фев 03, 2011 23:42 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
chess писал(а):
Поэтому, в общем случае, корректный поиск, без доп. указаний программиста в ходе этого поиска, будет невозможен.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пт фев 04, 2011 00:49 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Хищник писал(а):
chess писал(а):
Поэтому, в общем случае, корректный поиск, без доп. указаний программиста в ходе этого поиска, будет невозможен.

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

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пт фев 04, 2011 21:27 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
вопрос писал(а):
Потребуются определённые вложения компетентного труда в организацию процесса поиска решения, т.е. внимание к процессу поиска не обойти.

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

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пт фев 04, 2011 21:38 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Цитата:
Ну да. Пролог - это не панацея, в нем тоже работать надо. Причем непонятно по сравнению с Фортом больше или меньше. Мне представляется, что больше.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пт фев 04, 2011 22:37 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
вопрос писал(а):
Нет, всё-таки меньше и при сноровке - значительно, но в другом направлени

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

_________________
С уважением, chess


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

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


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

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


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

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