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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 46 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 12, 2008 16:40 
Не в сети
Аватара пользователя

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

Похоже я все-таки не понял почему это все еще делают, в чем принципиальные трудности.

Вот оценочные прикидки ускорения поиска в моем случае.

Код:
REQUIRE METER ~CHESS\TASK\METER.F

: hash ( a u -- hash) 0 -ROT OVER + SWAP DO I C@ + LOOP ;

CREATE QWORDS 4000 ALLOT
: save1 ['] DUP QWORDS S" DUP" hash + ! ; save1

: search1 S" DUP" SFIND DROP ; \ в СПФ

: search2 QWORDS S" DUP" hash + @ ; \ с hash

search1 . CR search2 .
CR
STARTLOG
METER search1
METER search2

лог
Код:
126806 77560
744 94
Ok

Ускорение, если его по полной схеме сделать(с контролем) в среднем на 2 порядка похоже будет.
Наличие линейного поиска - нормально - страховка от повтора хэшей для имен слов,
хотя они и редки будут, зато не надо формировать сложный хэш - это будет долго,
нужен быстрый, пусть и не всегда однозначный - в этом смысл.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 12, 2008 18:12 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
chess писал(а):
Похоже я все-таки не понял почему это все еще делают, в чем принципиальные трудности.

принципиальных трудностей нет. Просто когда Черезов делала СПФ, то решил, что линейного поиска по словарю достаточно.
(в остальных русских фортах не так, по крайней мере в тех, что я видел).
А вот эксперименты ищут компромисс между сложностью реализации и скоростью поиска.

chess писал(а):
Вот оценочные прикидки ускорения поиска в моем случае.

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

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 12, 2008 23:34 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
А мне вот интересно, сколько времени занимает процесс поиска слов при загрузке текста? :shuffle;


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 13, 2008 07:17 
Не в сети

Зарегистрирован: Пн окт 15, 2007 17:24
Сообщения: 164
Откуда: Бийск
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
Хищник писал(а):
А мне вот интересно, сколько времени занимает процесс поиска слов при загрузке текста? :shuffle;

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

_________________
And so forth ...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 13, 2008 14:49 
Не в сети
Аватара пользователя

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

Это зависит от форт-системы. Вот в СПФ время поиска составляет львиную долю времени загрузки текста.
У меня в примере показано, что при словаре Forth (в данном примере это примерно 3000 слов) время на поиск слова близкого к началу словаря ( в примере это DUP ) тратится около 100000 тактов. Учитывая, что наиболее часто употребляемые слова
находятся ближе к началу словаря, нужно эту цифру умножить на количество слов в тексте программы. И если учесть, что
для большой программы словарь будет гораздо больше, то это довольно таки реальная оценка. Хотя все зависит и от программы,
если к примеру наделать слов в начале программы, а дальше использовать в основном только их, то поиск будет гораздо менее
время затратным, так как искать надо слова около вершины словаря.
Варнак писал(а):
Сколько он занимает в процессе загрузки при комиляции совершенно неважно

Ну это зависит от того как использовать транслятор. Вот меня по многим причинам устраивает технология Juice, и одним из ее существенных моментов является отсутствие исполняемых файлов программ. Там есть транслятор и исходники и запуск программы на исполнение идет после трансляции исходников - требования к скорости компиляции и поиску соответственно там очень высоки.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 13, 2008 15:20 
Не в сети

Зарегистрирован: Ср сен 13, 2006 10:06
Сообщения: 636
Откуда: Омск
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
chess писал(а):
У меня в примере показано, что при словаре Forth (в данном примере это примерно 3000 слов) время на поиск слова близкого к началу словаря ( в примере это DUP ) тратится около 100000 тактов.

Вот, о чем я тоже говорю, нужен новый алгоритм.

_________________
Меня нет, не будет и не было.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 13, 2008 16:18 
Не в сети

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

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 13, 2008 19:24 
Не в сети
Administrator
Administrator
Аватара пользователя

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

Берем мегабайт исходников. Допустим, что средняя длина слова - 5 байт (4 + пробел, ориентируясь на ! @ . , но включая и то, что будут и слова большой длины). Имеем около 200 тыс. слов, требующих поиска. Умножаем на 100 тыс. тактов. 20 000 млн. = 20 млрд. тактов, что при тактовой 2 ГГц дает 5 секунд на поиск при загрузке. Это мегабайтный (!) проект. Логотип программы на экран и progress bar...


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 13, 2008 19:56 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Хищник писал(а):
Имеем около 200 тыс. слов, требующих поиска. Умножаем на 100 тыс. тактов. 20 000 млн. = 20 млрд. тактов, что при тактовой 2 ГГц дает 5 секунд на поиск при загрузке. Это мегабайтный (!) проект. Логотип программы на экран и progress bar...

Ошибка в вашем расчете в том, что при увеличении количества слов растет время поиска для слов в начале словаря. Таким образом
при 200000 словах время поиска одного в начале словаря возрастет в 70 раз( у меня в словаре было 3000 слов), поэтому получится
5сек*70=350 сек. Это терпимо если в итоге получится exeшник, но я говорю о другой технологии запуска программ на исполнение и там
это не проходит - ждать даже минуту это плохо.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб сен 13, 2008 20:51 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
chess писал(а):
Ошибка в вашем расчете в том, что при увеличении количества слов растет время поиска для слов в начале словаря. Таким образом
при 200000 словах время поиска одного в начале словаря возрастет в 70 раз( у меня в словаре было 3000 слов), поэтому получится
5сек*70=350 сек. Это терпимо если в итоге получится exeшник, но я говорю о другой технологии запуска программ на исполнение и там
это не проходит - ждать даже минуту это плохо.

Нет, это не 200 тысяч слов в словаре, это 200 тысяч токенов (далеко не каждый из них создает новое слово). В любом случае, примерно 250 кб грузились в 486DX4-100 не более 15 секунд - это наиболее непроизводительный вариант старого компьютера в цеховой лаборатории, куда ставился проект на Форте. После загрузки каждого из ~20 файлов рисовался квадратик на прогресс баре, и никто ни слова не сказал о времени загрузки. И так понятно, что большие программы долго загружаются.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт сен 25, 2008 13:50 
Не в сети

Зарегистрирован: Ср сен 13, 2006 10:06
Сообщения: 636
Откуда: Омск
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
Тут мысль пришла, хотелось бы развить. Сделать кодофайл перемещаемым в памяти.
В СПФ например вызов словарной статьи из словарной статьи выглядит так:
Код:
CALL [CFA]

А если сделать так? Что, при условии вершина кодофайла в ESI. И вершина стека данных не в EAX, а в EBX.
Код:
MOV EAX,[CFA]
ADD EAX,ESI
CALL EAX

или если ESI указатель на адрес где хранится начало кодофайла:
Код:
MOV EAX,[CFA]
CALL [EAX+ESI]

_________________
Меня нет, не будет и не было.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт сен 25, 2008 21:38 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Pretorian писал(а):
Тут мысль пришла, хотелось бы развить. Сделать кодофайл перемещаемым в памяти.

вопрос только в одном, зачем?

Pretorian писал(а):
А если сделать так?

это приличная потеря производительности.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 26, 2008 05:46 
Не в сети

Зарегистрирован: Ср сен 13, 2006 10:06
Сообщения: 636
Откуда: Омск
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
mOleg писал(а):
Pretorian писал(а):
Тут мысль пришла, хотелось бы развить. Сделать кодофайл перемещаемым в памяти.

вопрос только в одном, зачем?

Pretorian писал(а):
А если сделать так?

это приличная потеря производительности.

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

_________________
Меня нет, не будет и не было.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 26, 2008 18:31 
Не в сети
Administrator
Administrator
Аватара пользователя

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

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн сен 29, 2008 09:21 
Не в сети

Зарегистрирован: Ср сен 13, 2006 10:06
Сообщения: 636
Откуда: Омск
Благодарил (а): 0 раз.
Поблагодарили: 3 раз.
Хищник писал(а):
В PC для этого существует аппаратный механизм трансляции страниц, и там можно кусок кода размещать всегда с одного и того же адреса.

И как это поможет например для DOS?

_________________
Меня нет, не будет и не было.


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

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


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

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


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

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