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

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - Задача - выбор пробела
Автор Сообщение
  Заголовок сообщения:  Re: Задача - выбор пробела  Ответить с цитатой
chess писал(а):
и, если это нетрудно - у всех разные компьютеры, нельзя ли скорость или указывать компьютер или в относительных единицах.

Результат не показательный - вх.строка короткая. Всего в 4 раза быстрее переборного варианта.
Сообщение Добавлено: Вт фев 08, 2011 21:52
  Заголовок сообщения:  Re: Задача - выбор пробела  Ответить с цитатой
Такой хороший результат нужно снабдить комментарием для надёжности :)
:hey;
и, если это нетрудно - у всех разные компьютеры, нельзя ли скорость или указывать компьютер или в относительных единицах.
Сообщение Добавлено: Вт фев 08, 2011 21:49
  Заголовок сообщения:  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:47
  Заголовок сообщения:  Re: Задача - выбор пробела  Ответить с цитатой
вопрос писал(а):
Нет, ну надо сохранять обьективность.решение на форте было неправильным, пока не было проверено на Прологе, решение на котором было написано с первого раза и выдавало и правильные и неправильные варианты и путь поиска можно было, если бы хотелось и в любую сторону модифицировать и т.д. Более того, оно ещё и по скорости было сравнимо с первым форт-решением (и даже (что не может быть) превосходило)

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

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

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

Я всё жду пояснений, что именно сохраняет время в последнем :shuffle;
Сообщение Добавлено: Сб фев 05, 2011 00:09
  Заголовок сообщения:  Re: Задача - выбор пробела  Ответить с цитатой
вопрос писал(а):
Нет, всё-таки меньше и при сноровке - значительно, но в другом направлени

Вот по решению задачки я бы этого не сказал. А наработать алгоритмы перебора вариантов и в Форте можно, если понадобится.
Я не вижу что можно привнести из Пролога в Форт полезного, как впрочем и из других языков. :)
Сообщение Добавлено: Пт фев 04, 2011 22:37
  Заголовок сообщения:  Re: Задача - выбор пробела  Ответить с цитатой
Цитата:
Ну да. Пролог - это не панацея, в нем тоже работать надо. Причем непонятно по сравнению с Фортом больше или меньше. Мне представляется, что больше.

Нет, всё-таки меньше и при сноровке - значительно, но в другом направлении
Сообщение Добавлено: Пт фев 04, 2011 21:38
  Заголовок сообщения:  Re: Задача - выбор пробела  Ответить с цитатой
вопрос писал(а):
Потребуются определённые вложения компетентного труда в организацию процесса поиска решения, т.е. внимание к процессу поиска не обойти.

Ну да. Пролог - это не панацея, в нем тоже работать надо. :o Причем непонятно по сравнению с Фортом больше или меньше. Мне представляется, что больше.
Сообщение Добавлено: Пт фев 04, 2011 21:27
  Заголовок сообщения:  Re: Задача - выбор пробела  Ответить с цитатой
Хищник писал(а):
chess писал(а):
Поэтому, в общем случае, корректный поиск, без доп. указаний программиста в ходе этого поиска, будет невозможен.

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

Я думаю, что chess словил с другой стороны то, что я говорил в неоконченной статье про
декларативное программирование: нельзя ждать что будет просто задана задача и найдено решение. Потребуются определённые вложения компетентного труда в организацию процесса поиска решения, т.е. внимание к процессу поиска не обойти.
Сообщение Добавлено: Пт фев 04, 2011 00:49
  Заголовок сообщения:  Re: Задача - выбор пробела  Ответить с цитатой
chess писал(а):
Поэтому, в общем случае, корректный поиск, без доп. указаний программиста в ходе этого поиска, будет невозможен.

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

Кстати о Прологе.
Я так понял, что в Прологе реализован механизм поиска, находящий решения логических операторов.
Этот механизм требует много времени из-за своей сложности.
(!)Но всех ситуаций заранее не предусмотришь(аксиома!) - кстати, это один из краеугольных камней Форта.
Поэтому, в общем случае, корректный поиск, без доп. указаний программиста в ходе этого поиска, будет невозможен.
Программист при этом должен понимать в каком состоянии Пролог находится и в чем причина каждого конкретного 'затыка'
процесса лог. вывода.
Вот это уже далеко от первоначального лозунга Пролога - освободить программиста от вникания в сам процесс лог. вывода.
Из-за недопонимания фразы(!) как-раз и погорели японцы с их эвм 5 поколения.
Сообщение Добавлено: Чт фев 03, 2011 17:52
  Заголовок сообщения:  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 это легко проверить, если в выражение пролога вставить предикат, который отсутствует, это будет замечено только во время исполнения, т.к. нет даже компиляции на лету
Сообщение Добавлено: Ср фев 02, 2011 21:59
  Заголовок сообщения:  Re: Задача - выбор пробела  Ответить с цитатой
chess писал(а):
вопрос писал(а):
Похоже Прологи проигрывают Форту :)

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

пролог не может быть настолько же быстрым как и форт, он ведь обеспечивает логику
Сообщение Добавлено: Ср фев 02, 2011 18:08
  Заголовок сообщения:  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 17:49
  Заголовок сообщения:  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 остался незаполнен
Сообщение Добавлено: Вт фев 01, 2011 19:04

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


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