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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 8 ] 
Автор Сообщение
 Заголовок сообщения: Wide Finder
СообщениеДобавлено: Сб ноя 17, 2007 12:52 
Не в сети

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Всё началось с того что некто Tim Bray в своём блоге опубликовал задачку и прямое в лоб решение на Руби. А также в целях изучения стал описывать попытки решения на Ерланге и сравнивать скорость. В результате эта задачка получила небольшой hype в программерской блогосфере, были представлены решения на многих других языках. Но вот незадача - ни одного решения на форте :)
Итак - оригинальное условие. Там есть ссылки на другие варианты решений, идеи по оптимизации, сравнения разных языков (точнее их реализаций). Тестовые данные можно взять по ссылке из WF II - http://www.tbray.org/tmp/o10k.ap (2 МБ).
Кратко говоря задача в том чтобы распарсить большой лог-файл от апача и определить 10 наиболее популярных ссылок которые попадают под заданный шаблон (регексп). Файл очень большой - несколько миллионов строк. Критерий - соответствие исходным условиям (sic!), скорость (и понятность кода). Процессор у автора 8-ядерый поэтому он призывает использовать многопоточность (что как видно по результатам даёт большой прирост в скорости). Также все топовые решения на прямую проецируют файл в память и жульничают с регекспом.
Получится ли у нас кандидат от форума который сможет составить конкцренцию чемпионам - на данный момент это решение на JoCaml?

_________________
http://forth.org.ru/~ygrek


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

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Полный текст условия :
Цитата:
Дан текстовый файл - лог запросов к различным веб-страницам. Требуется определить какие страницы пользуются наибольшей популярностью и вывести 10 первых по числу хитов. Кроме обращения к страницам в логе также есть обращения к другим файлам которые в подсчёте не участвуют. Считать надо же только те страницы запрос к которым попадает под следующее регулярное выражение (внутри кавычек) : "GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) "
\d это любая цифра
() скобки обозначают подстроку которая есть уникальный ключ-идентификатор страницы.
последовательность [^ .]+ значит "один или более любых символов кроме точки и пробела".
Остальные символы обозначают себя.
Обратите внимание на пробел в конце.


Тестовые данные можно взять по ссылке выше.
Правильный ответ на тестовые данные :
[pre]89: 2006/09/29/Dynamic-IDE
20: 2006/07/28/Open-Data
13: 2003/07/25/NotGaming
8: 2006/01/31/Data-Protection
8: 2003/09/18/NXML
8: 2003/10/16/Debbie
7: 2003/06/23/SamsPie
6: 2006/01/08/No-New-XML-Languages
6: 2005/11/03/Cars-and-Office-Suites
6: 2005/07/27/Atomic-RSS[/pre]

_________________
http://forth.org.ru/~ygrek


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

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Вот такое "в лоб" решение.
По скорости на два порядка хуже таких же "лобовых" решений на Ruby и OCaml.

Данные профайлера показывают что 99.9% процентов времени тратится на сопоставление регэкспа со строкой.
Отсюда есть варианты -
1) оптимизировать движок RE что делать надо в любом случае впрочем
2) заменить RE частично простым поиском и сопоставлять только небольшую часть всех строк
3) заменить RE полностью небольшим заточенным конечным автоматом
После этого надо смотреть на другие оптимизации.

<pre>\ $Id: q1.f 43 2007-11-18 15:37:20Z ygrek $

\ REQUIRE .AllStatistic ~pinka/lib/tools/profiler.f
REQUIRE re_match? ~ygrek/lib/re/ext.f
REQUIRE FileLines=> ~ygrek/lib/filelines.f
REQUIRE HASH!N ~pinka/lib/hash-table.f
REQUIRE Enterly ~pinka/lib/queue_pr.f

: HASH-INC { a u h -- }
a u h HASH@N NOT IF 0 THEN
1+
a u h HASH!N ;

0 VALUE h

: re RE" .*GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) .*" ;

: (parse) ( a u -- ) FileLines=> DUP STR@ re re_match? IF \1 h HASH-INC THEN ;

0 VALUE q

: sort h LAMBDA{ DROP SWAP NEGATE q Enterly } for-hash ;
: show h LAMBDA{ ROT . TYPE CR } for-hash ;

: do
big-hash TO h
(parse)
\ show
New-Queue TO q
sort
10 0 DO q LeaveLow IF ASCIIZ> TYPE CR THEN LOOP
q Del-Queue
h del-hash ;

:NONAME S" input.ap" do BYE ; MAINX !
S" q1.exe" SAVE BYE</pre>

_________________
http://forth.org.ru/~ygrek


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

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Использование простого линейного поиска "GET /ongoing/When/" в строке и применение регэкспа только для успешного совпадения сокращает разрыв с (лобовым) решением на Ruby до 1-го порядка (т.е. в 10 раз). И это при том что для Руби пускается скрипт, а не готовый бинарник.
Мораль - в обработке строк spf безоговорочно сливает ruby.

_________________
http://forth.org.ru/~ygrek


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

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Дальнейшие попытки ускорить приводят к результату - 3.15 сек проти 0.85
Даже это очень плохо, тем более если сравнить код "на глаз".
<pre>
\ $Id: q1.f 54 2007-12-08 17:14:16Z ygrek $

\ REQUIRE .AllStatistic ~pinka/lib/tools/profiler.f
REQUIRE re_match? ~ygrek/lib/re/ext.f
REQUIRE FileLines=> ~ygrek/lib/filelines.f
REQUIRE HASH!N ~pinka/lib/hash-table.f
REQUIRE Enterly ~pinka/lib/queue_pr.f
REQUIRE NOT ~profit/lib/logic.f

: HASH-INC { a u h -- }
a u h HASH@N NOT IF 0 THEN
1+
a u h HASH!N ;

0 VALUE h

: numbers? ( a u -- a1 u1 -1 | 0 )
DUP 16 &lt; IF 2DROP FALSE EXIT THEN
OVER 16 RE" \d\d\dx/\d\d\d\d/\d\d/\d\d/" re_fast_match? IF 16 /STRING TRUE ELSE 2DROP FALSE THEN ;

: SEARCH-END DUP >R SEARCH IF R> /STRING TRUE ELSE RDROP FALSE THEN ;

: space-no-dot ( a u -- a -1 | 0 )
BOUNDS ?DO
I C@ [CHAR] . = IF UNLOOP FALSE EXIT THEN
I C@ BL = IF I UNLOOP TRUE EXIT THEN
LOOP
FALSE ;

: line-matched? ( a u -- 0 | a u -1 )
S" GET /ongoing/When/" SEARCH-END NOT IF 2DROP FALSE EXIT THEN
numbers? NOT IF FALSE EXIT THEN
OVER 11 CHARS - >R
space-no-dot NOT IF RDROP FALSE ELSE R@ - R> SWAP TRUE THEN ;

: (parse) ( a u -- ) FileLines=> DUP STR@ line-matched? IF h HASH-INC THEN ;

0 VALUE q

: sort h LAMBDA{ DROP SWAP NEGATE q Enterly } for-hash ;
: show h LAMBDA{ ROT . TYPE CR } for-hash ;

: do
big-hash TO h
(parse)
\ show
New-Queue TO q
sort
10 0 DO q LeaveLow IF ASCIIZ> TYPE CR THEN LOOP
q Del-Queue
h del-hash ;

:NONAME S" input.ap" do BYE ; MAINX !
\ S" q1.exe" SAVE BYE

~af/lib/elapse.f

time-reset
S" input.ap" do
.elapsed</pre>

<pre>
counts = {}
counts.default = 0

ARGF.each_line do |line|
if line =~ %r{GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) }
counts[$1] += 1
end
end

keys_by_count = counts.keys.sort { |a, b| counts[b] &lt;=> counts[a] }
keys_by_count[0 .. 9].each do |key|
puts "#{counts[key]}: #{key}"
end</pre>

_________________
http://forth.org.ru/~ygrek


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб дек 08, 2007 23:45 
На глаз сравнивать (вид и размер исходника) справедливо только когда базы одного уровня.
Использование BREGEXP.DLL (~ac\lib\string\bregexp\bregexp.f) и fix-refill.f без ухищрений дает результат в 2.3 раз быстрей, чем вариант от 08, 2007 20:30. А он, похоже, компилит регексп каждый раз.
По большому счету, дело не столько в строках (оптимизации маш-кода), сколько в алгоритмах. Например, поиск подстроки — есть быстрые алгоритмы типа B-M (Boyer-Moore) поиска, и др., которые не реализованы в наших либах.


Вернуться к началу
  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Сб дек 08, 2007 23:52 
Не в сети

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
Развитие истории.
Рувим обратил внимание на нерациональное использование FileLines=> которое для каждой строки файла выделяет и уничтожает динамическую строку. Замена на INCLUDED-LINES-WITH (с подключением ~pinka/spf/fix-refill.f) даёт большой прирост в скорости.
Также Рувим предложил своё решение с помощью bregexp.dll (и обёртки ~ac/lib/string/bregexp/bregexp.f).
Результаты (на o200k.ap) :
wide-finder-ruv2.f : 0.65s
q1.f (r66) : 0.85s
Я отказался от ручной симуляции регекспа как в коде выше т.к. это очень некрасиво (но даёт прирост до 0.45s!)

Вообщем лобовое решение на ruby догнали и перегнали :)

Следующий барьер - лобовое решение на ocaml - 0.28s

wide-finder-ruv2.f
<pre>
\ 08.Dec.2007 Sat 21:54
\ original wide-finder-ygrek.f by ~ygrek

REQUIRE CORE_OF_REFILL ~pinka/spf/fix-refill.f \ patch for accept and refill
REQUIRE INCLUDED-LINES-WITH ~pinka/lib/ext/include.f

REQUIRE re_match? ~ygrek/lib/re/ext.f
REQUIRE HASH!N ~pinka/lib/hash-table.f
REQUIRE Enterly ~pinka/lib/queue_pr.f

REQUIRE BregexpGetMatch ~ac\lib\string\bregexp\bregexp.f

\ REQUIRE .AllStatistic ~pinka/lib/tools/profiler.f
REQUIRE .elapsed ~af/lib/elapse.f

: HASH-INC { a u h -- }
a u h HASH@N NOT IF 0 THEN
1+
a u h HASH!N
;

0 VALUE h

: re S" /GET \/ongoing\/When\/\d\d\dx\/(\d\d\d\d\/\d\d\/\d\d\/[^ .]+) /" ;

: (parse1) ( -- ) SOURCE re BregexpGetMatch DUP 0= IF DROP EXIT THEN 2 = IF 2DROP h HASH-INC EXIT THEN ABORT ;

: +(parse1) ( -- ) SOURCE S" GET /ongoing/When/" SEARCH IF h HASH-INC EXIT THEN 2DROP ;

: (parse) ( a u -- ) ['] (parse1) INCLUDED-LINES-WITH ;

0 VALUE q

: sort h LAMBDA{ DROP SWAP NEGATE q Enterly } for-hash ;
: show h LAMBDA{ ROT . TYPE CR } for-hash ;

: do
big-hash TO h
(parse)
\ show
New-Queue TO q
sort
10 0 DO q LeaveLow IF ASCIIZ> TYPE CR THEN LOOP
q Del-Queue
h del-hash
;

\ S" o10k.ap" do .AllStatistic BYE

time-reset
S" input.ap" do
.elapsed</pre>

q1.f (r66)
<pre>
\ $Id: q1.f 66 2007-12-08 19:37:46Z ygrek $

\ REQUIRE .AllStatistic ~pinka/lib/tools/profiler.f
REQUIRE re_match? ~ygrek/lib/re/ext.f
REQUIRE HASH!N ~pinka/lib/hash-table.f
REQUIRE Enterly ~pinka/lib/queue_pr.f
REQUIRE NOT ~profit/lib/logic.f
REQUIRE CORE_OF_REFILL ~pinka/spf/fix-refill.f
REQUIRE INCLUDE-LINES-WITH ~pinka/lib/ext/include.f
REQUIRE .elapsed ~af/lib/elapse.f

: HASH-INC { a u h -- }
a u h HASH@N NOT IF 0 THEN
1+
a u h HASH!N ;

0 VALUE h

: SEARCH-END ( a u -- a1 u1 ? ) DUP >R SEARCH IF R> /STRING TRUE ELSE RDROP FALSE THEN ;

: line-matched? ( a u -- 0 | a u -1 )
S" GET /ongoing/When/" SEARCH-END NOT IF 2DROP FALSE EXIT THEN
OVER >R
RE" \d\d\dx/\d\d\d\d/\d\d/\d\d/[^ .]+ " re_sub ?DUP IF 1- R> SWAP 5 /STRING TRUE ELSE RDROP FALSE THEN
;

: (parse) ( a u -- ) LAMBDA{ SOURCE line-matched? IF h HASH-INC THEN } INCLUDED-LINES-WITH ;

0 VALUE q

: sort h LAMBDA{ DROP SWAP NEGATE q Enterly } for-hash ;
: show h LAMBDA{ ROT . TYPE CR } for-hash ;

: do
big-hash TO h
(parse)
\ show
New-Queue TO q
sort
10 0 DO q LeaveLow IF ASCIIZ> TYPE CR THEN LOOP
q Del-Queue
h del-hash ;

\ :NONAME S" input.ap" do BYE ; MAINX ! S" q1.exe" SAVE BYE

time-reset
S" input.ap" do
.elapsed</pre>

_________________
http://forth.org.ru/~ygrek


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

Зарегистрирован: Чт май 04, 2006 18:18
Сообщения: 456
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
r118 = r66 + отображение файла в память.
Даёт ускорение в полтора раза.
На файле с миллионом строк :
q1.f (r66) - 3.15s
q1.f (r118) - 2.40s
ruv2.f - 2.65s
wf.ml - 1.15s
original.rb - 4.45s

<pre>
\ $Id: q1.f 118 2008-01-25 10:31:02Z ygrek $

\ REQUIRE .AllStatistic ~pinka/lib/tools/profiler.f
\ profile off

REQUIRE re_match? ~ygrek/lib/re/ext.f
REQUIRE HASH!N ~pinka/lib/hash-table.f
REQUIRE Enterly ~pinka/lib/queue_pr.f
REQUIRE NOT ~profit/lib/logic.f
REQUIRE CORE_OF_REFILL ~pinka/spf/fix-refill.f
REQUIRE INCLUDE-LINES-WITH ~pinka/lib/ext/include.f
REQUIRE .elapsed ~af/lib/elapse.f
REQUIRE OPEN-FILE-MAP ~ygrek/lib/win/mapfile.f

: HASH-INC { a u h -- }
a u h HASH@N NOT IF 0 THEN
1+
a u h HASH!N ;

0 VALUE h

: SEARCH-END ( a u -- a1 u1 ? ) DUP >R SEARCH IF R> /STRING TRUE ELSE RDROP FALSE THEN ;

: line-matched? ( a u -- 0 | a u -1 )
OVER >R
RE" \d\d\dx/\d\d\d\d/\d\d/\d\d/[^ .]+ " re_sub ?DUP IF 1- R> SWAP 5 /STRING TRUE ELSE RDROP FALSE THEN
;

: test line-matched? IF h HASH-INC THEN ;

CREATE \CR 0x0A C,
: STRCR \CR 1 ;

: scan
BEGIN
S" GET /ongoing/When/" SEARCH-END
WHILE
2DUP test
STRCR SEARCH IF 1 /STRING ELSE 2DROP 0 0 THEN
REPEAT
2DROP ;

: (parse) ( a u -- ) OPEN-FILE-MAP IF DUP MAPPED@ scan CLOSE-FILE-MAP ELSE DROP THEN ;

0 VALUE q

: sort h LAMBDA{ DROP SWAP NEGATE q Enterly } for-hash ;
: show h LAMBDA{ ROT . TYPE CR } for-hash ;

: do
big-hash TO h
(parse)
\ show
New-Queue TO q
sort
10 0 DO q LeaveLow IF ASCIIZ> TYPE CR THEN LOOP
q Del-Queue
h del-hash ;

\ :NONAME S" input.ap" do BYE ; MAINX ! S" q1.exe" SAVE BYE

\ ResetProfiles
time-reset
S" input.ap" do
.elapsed
</pre>

_________________
http://forth.org.ru/~ygrek


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

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


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

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


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

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