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

...
Google Search
Forth-FAQ Spy Grafic

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




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

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

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

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

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


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

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

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

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


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

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

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


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

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Такой хороший результат нужно снабдить комментарием для надёжности :)
:hey;
и, если это нетрудно - у всех разные компьютеры, нельзя ли скорость или указывать компьютер или в относительных единицах.


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

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

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

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


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

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


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

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


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

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