OberonCore https://forum.oberoncore.ru/ |
|
Компрометация цикла Дейкстры https://forum.oberoncore.ru/viewtopic.php?f=86&t=3776 |
Страница 1 из 2 |
Автор: | Сергей Губанов [ Четверг, 19 Январь, 2012 17:25 ] |
Заголовок сообщения: | Компрометация цикла Дейкстры |
(модератор) Исходное решение с помощью ЦД, см: viewtopic.php?f=82&t=3770 Изначально я написал процедуру на C#, а затем перевёл на Компонентный Паскаль. Версия на C#: Код: public static void MultiFind2 (byte[] s, int begin, int end, int wordCount, byte[][] words, int[] lens, out int word, out int pos) Ваш вариант на C# выглядит так: { int w, j; word = -1; pos = -1; while (begin < end) { w = 0; while (w < wordCount) { if ((begin + lens[w] <= end) && (s[begin] == words[w][0])) { j = 1; while ((j < lens[w]) && (s[begin + j] == words[w][j])) { j++; } if (j == lens[w]) { word = w; pos = begin; w = wordCount; begin = end; } } w++; } begin++; } } Код: public static void MultiFind (byte[] s, int beg, int end, int wordCount, byte[][] words, int[] lens, out int word, out int pos) Я сравнил производительность C# вариантов на 64 разрядной системе (i7 2600K). Мой вариант быстрее вашего:{ int i = beg; int w = 0; int wlen = lens[0]; int j = 0; while (true) { if ((i + j < end) && (j < wlen) && (s[i + j] == words[w][j])) { j++; } else if ((i + j < end) && (j < wlen) && (w < wordCount - 1)) { w++; wlen = lens[w]; j = 0; } else if ((i + j < end) && (j < wlen)) { i++; w = 0; wlen = lens[0]; j = 0; } else { break; } } if (j == wlen) { word = w; pos = i; } else { word = -1; pos = -1; } } Длина текста 100'000'000. Количество слов 10. Быстрее на 52% Длина текста 10'000'000. Количество слов 100. Быстрее на 52% Длина текста 1'000'000. Количество слов 1'000. Быстрее на 42% Длина текста 100'000. Количество слов 10'000. Быстрее на 13% Длина текста 10'000. Количество слов 100'000. Быстрее на 7% Длина текста 1'000. Количество слов 1'000'000. Быстрее на 6.9% Во всех вариантах искомых слов в тексте не было (худший случай). Мой вариант содержит оптимизацию предполагающую, что искомые слова имеют длину больше либо равную единице. |
Автор: | Сергей Губанов [ Четверг, 19 Январь, 2012 19:17 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Удалось ещё больше ускорить программу. Надо вместо IF (begin + lens[w] <= end) & (source[begin] = words[w][0]) THEN написать наоборот: IF (source[begin] = words[w][0]) & (begin + lens[w] <= end) THEN то есть сначала проверить совпадение первой буквы (в случае равномерного распределения с большей вероятностью буквы окажутся не равны чем равны). Вариант на C# Код: public static void MultiFind (byte[] s, int begin, int end, int wordCount, byte[][] words, int[] lens, out int word, out int pos) { int w, j; word = -1; pos = -1; while (begin < end) { w = 0; while (w < wordCount) { if ((s[begin] == words[w][0]) && (begin + lens[w] <= end)) { j = 1; while ((j < lens[w]) && (s[begin + j] == words[w][j])) { j++; } if (j == lens[w]) { word = w; pos = begin; w = wordCount; begin = end; } } w++; } begin++; } } Работает до 2-х раз быстрее исходного варианта по "Дейкстре" в лучшем случае (текст очень длинный, а искомых слов мало) и на 30% быстрее в худшем случае (текст короткий, а искомых слов очень много). |
Автор: | alexus [ Четверг, 19 Январь, 2012 20:25 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Сергей Губанов писал(а): Работает до 2-х раз быстрее исходного варианта по "Дейкстре" в лучшем случае (текст очень длинный, а искомых слов мало) и на 30% быстрее в худшем случае (текст короткий, а искомых слов очень много). Браво!
|
Автор: | Евгений Темиргалеев [ Четверг, 19 Январь, 2012 20:41 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Сергей Губанов писал(а): Я сравнил производительность C# вариантов на 64 разрядной системе (i7 2600K). Мой вариант быстрее вашего Ваш вариант --- оптимизация, о которой думают потом. И возможен он тут, т.к. вычислительная сложность самих веток сопоставима со сложностью охран. Но так будет не во всех задачах.
|
Автор: | Info21 [ Четверг, 19 Январь, 2012 21:40 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
alexus писал(а): Сергей Губанов писал(а): Работает до 2-х раз быстрее исходного варианта по "Дейкстре" в лучшем случае (текст очень длинный, а искомых слов мало) и на 30% быстрее в худшем случае (текст короткий, а искомых слов очень много). Браво! |
Автор: | Peter Almazov [ Четверг, 19 Январь, 2012 22:22 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Сергей Губанов писал(а): Удалось ещё больше ускорить программу. Можете еще ускорить, т.к. в самом внутреннем цикле есть лишняя индексация words[w], где w внутри цикла не меняется.А вообще, если нужна скорость, так есть готовые алгоритмы. Ахо-Корасик тот же. |
Автор: | Info21 [ Пятница, 20 Январь, 2012 00:06 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Peter Almazov писал(а): если нужна скорость, так есть готовые алгоритмы. Ахо-Корасик тот же. Там случайно не ЦД?
|
Автор: | Peter Almazov [ Пятница, 20 Январь, 2012 08:06 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Ну, вообще-то, на такие вопросы обычно отвечают: используйте Google. Там нет ЦД, более того, я почти уверен, что ЦД как средство ликвидации вложенности вообще не используется ни в одном справочнике алгоритмов. Если это только не учебник. Ибо за повторную проверку условия автора закидают помидорами. Т.к люди ожидают оптимизации. Не преждевременной, а Just In Time |
Автор: | alexus [ Пятница, 20 Январь, 2012 08:37 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Сергей Губанов писал(а): Илья Ермаков писал(а): Алгоритм 1. Мультипоиск. В последовательности байт найти первое вхождение какого-либо из искомых слов. Длина текста 100'000'000. Количество слов 10. Быстрее на 52% Длина текста 10'000'000. Количество слов 100. Быстрее на 52% Длина текста 1'000'000. Количество слов 1'000. Быстрее на 42% Длина текста 100'000. Количество слов 10'000. Быстрее на 13% Длина текста 10'000. Количество слов 100'000. Быстрее на 7% Длина текста 1'000. Количество слов 1'000'000. Быстрее на 6.9% 1. Отсортировать слова в словаре, например, с помощью быстрой сортировки (затраты времени ~ N*log(N), где N - количество слов в словаре); 2. Для каждого слова текста: 3. Найти вхождение в словаре, например, с помощью бинарного поиска (затраты времени ~ M*log(N), где M - количество слов в тексте); Очевидно, что сортировка выполняется один раз, а каждый поиск даст экономию (при обычном сканировании словаря затраты времени в среднем составят ~ M*N/2). Примечание: Во всех приведённых формулах "затраты времени" считаются пропорциональными количеству операций сравнения. |
Автор: | Madzi [ Пятница, 20 Январь, 2012 08:46 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Можно ещё ускорить, если хешировать словарь и хранить его в красно-чёрном дереве. |
Автор: | Илья Ермаков [ Пятница, 20 Январь, 2012 08:48 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Кстати, сфера применения нашего алгоритма мультипоиска достаточно очевидна из второго алгоритма: разбор всяких потоков данных. Т.е. ясно ограничение на длину и количество искомых слов. Грешно тут переделывать под оптимизацию Вообще, я сейчас придерживаюсь принципа оптимизации, для нагруженных приложений: определяющей является работа с памятью (в широком смысле, например, форматы данных и проч.), а не заоптимизированное программирование алгоритмов. Какой-нибудь XML там, где он не нужен, может съедать до 70% маш. времени. Если же XML приходит извне и неизбежен, то при простом формате избегание использования общих парсеров типа DOM, замусоривающих память динамическими объектами, даёт тоже приличный эффект. И так по всей программе: перестать в каком-нибудь месте "мусорить" и нагружать сборщик - значительно более приличная оптимизация, чем перестановка буков в алгоритме. (При использовании КП есть много путей повышения эффективности. В отличие от Java, где вы даже строчку не заведёте без выделения дин. памяти. Теперь, конечно, есть JIT-оптимизаторы, перекидывающие эту работу обратно на стек... но ну её в качель, всю эту чунгу-чангу ). К тому же алгоритм оптимизировать можно всегда "задним числом", а вот переделать работу с памятью без глубокой переделки часто нельзя. |
Автор: | alexus [ Пятница, 20 Январь, 2012 09:09 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Илья Ермаков писал(а): Кстати, сфера применения нашего алгоритма мультипоиска достаточно очевидна из второго алгоритма: разбор всяких потоков данных. Т.е. ясно ограничение на длину и количество искомых слов. Кстати, забыл отметить, что подход/алгоритм, предложенный в предыдущем моём сообщении, позволяет выполнять параллельный поиск (в отличие от цикла Дейкстры), что может оказаться полезным в нынешних реалиях.Илья Ермаков писал(а): Грешно тут переделывать под оптимизацию Это Вам виднее... Лишь бы потом у студентов не возникало проблем при столкновении с реальной жизнью. Не лучше ли "нафталиновые" алгоритмы (типа "цикла Дейкстры") оставить на самостоятельное освоение тем студентам, которым интересно?
|
Автор: | Илья Ермаков [ Пятница, 20 Январь, 2012 09:16 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
alexus писал(а): 2. Для каждого слова текста: Здесь путаница. В моём алгоритме "слово" - это "подпоследовательность". Таким образом понятие "слово текста" не имеет смысла. |
Автор: | Info21 [ Пятница, 20 Январь, 2012 11:21 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Peter Almazov писал(а): Ну, вообще-то, на такие вопросы обычно отвечают: используйте Google. Мой вопрос был в значительной степени риторическим.Там нет ЦД, более того, я почти уверен, что ЦД ... "используйте Гугл" можно ответить на многие вопросы, но мы же обращаемся к коллегам. |
Автор: | Info21 [ Пятница, 20 Январь, 2012 11:24 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Плюс ко всему есть понятие evolvability. "Оптимизированные" алгоритмы эволюции не выдерживают. |
Автор: | Сергей Губанов [ Пятница, 20 Январь, 2012 11:51 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Евгений Темиргалеев писал(а): Ваш вариант --- оптимизация, о которой думают потом. Если бы забота была о предельной ясности, а не об оптимизации, то эти линейные поиски были бы вынесены в отдельные процедуры.viewtopic.php?p=69699#p69699 Илья Ермаков писал(а): я вообще всегда стараюсь их выкидывать в отдельные процедуры, чтобы нормально понималось. Представьте, насколько упадёт быстродействие в Вашем-моём варианте, если я его структурирую по процедурам, как "душа просит". Я вчера первым делом написал эти три линейных поиска в трёх процедурах. Замедлилось примерно на 40% по сравнению с вашим "ЦД" или, значит, примерно раза в три по сравнению с моим конечным вариантом. Это цена предельной ясности.Peter Almazov писал(а): Можете еще ускорить, т.к. в самом внутреннем цикле есть лишняя индексация words[w], где w внутри цикла не меняется. Я так поначалу и сделал, но к своему удивлению оказался не прав. Оказывается индексация words[w][j] на современных процессорах и компиляторах работает даже быстрее чем сначала закэшировать byte[] tmp = words[w]; а потом использовать tmp[j]. Возможно в 32-разрядном Блэкбоксе такая оптимизация и окажется полезной, но в 64-разрядном C# она точно оказывается вредной. alexus писал(а): При больших словарях (от 100 слов) целесообразно использовать другой алгоритм решения: 1. Отсортировать слова в словаре Я тоже так подумал когда вчера с работы домой ехал. Наверное можно даже отсортировать просто по первой букве. Составить таблицу, что слова начинающиеся на букву t лежат в диапазоне range[t].begin .. range[t].end.alexus писал(а): Кстати, забыл отметить, что подход/алгоритм, предложенный в предыдущем моём сообщении, позволяет выполнять параллельный поиск (в отличие от цикла Дейкстры) +1
|
Автор: | Валерий Лаптев [ Пятница, 20 Январь, 2012 12:03 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Евгений Темиргалеев писал(а): Сергей Губанов писал(а): Я сравнил производительность C# вариантов на 64 разрядной системе (i7 2600K). Мой вариант быстрее вашего Ваш вариант --- оптимизация, о которой думают потом. И возможен он тут, т.к. вычислительная сложность самих веток сопоставима со сложностью охран. Но так будет не во всех задачах.ИМХО ЦД ЕСТЕСТВЕННО параллелится на многоядерном процессоре: каждая ветка - для отдельного ядра. (модератор) разделённое сообщение: viewtopic.php?p=69711#p69711 |
Автор: | Сергей Губанов [ Пятница, 20 Январь, 2012 12:47 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Валерий Лаптев писал(а): И кстати, о параллельности. ИМХО ЦД ЕСТЕСТВЕННО параллелится на многоядерном процессоре: каждая ветка - для отдельного ядра. Ы-ы-ы?!!
|
Автор: | alexus [ Пятница, 20 Январь, 2012 13:22 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Илья Ермаков писал(а): alexus писал(а): 2. Для каждого слова текста: Здесь путаница. В моём алгоритме "слово" - это "подпоследовательность". Таким образом понятие "слово текста" не имеет смысла. (модератор) удалена часть сообщения с цитатами и ответом на удалённое сообщение другого участника |
Автор: | Сергей Губанов [ Пятница, 20 Январь, 2012 21:07 ] |
Заголовок сообщения: | Re: Пара примеров на цикл Дейкстры |
Удалось ещё больше ускорить, да ещё и вынести один линейный поиск в отдельную процедуру. Вспомогательная процедура: Код: PROCEDURE EQ (IN s: ARRAY OF BYTE; begin, end: INTEGER; IN word: ARRAY OF BYTE; length: INTEGER): BOOLEAN; Основная процедура: VAR i: INTEGER; BEGIN i := 0; IF begin + length <= end THEN WHILE (i < length) & (s[begin + i] = word[i]) DO INC(i) END END; RETURN (i = length) END EQ; Код: PROCEDURE MultiFind* (IN s: ARRAY OF BYTE; begin, end, wordCount: INTEGER; IN words: ARRAY OF ARRAY OF BYTE; IN lens: ARRAY OF INTEGER; OUT word, pos: INTEGER); VAR w: INTEGER; sb: BYTE; h: ARRAY 64*1024 OF BYTE; BEGIN word := -1; pos := -1; w := 0; WHILE w < wordCount DO h[w] := words[w][0]; INC(w) (* засасываем в кэш процессора первые буквы слов *) END; WHILE begin < end DO sb := s[begin]; w := 0; WHILE (w < wordCount) & ~((h[w] = sb) & EQ(s, begin, end, words[w], lens[w])) DO INC(w) END; IF w < wordCount THEN word := w; pos := begin; begin := end END; INC(begin) END END MultiFind; ускорение в 2.93 раз при wordCount = 100, sourceLength = 100'000'000 ускорение в 3.35 раз при wordCount = 1'000, sourceLength = 10'000'000 ускорение в 3.56 раз при wordCount = 10'000, sourceLength = 1'000'000 ускорение в 4.73 раз при wordCount = 100'000 sourceLength = 100'000 1) Основной вклад в ускорение вносит запоминание первых букв слов в отдельном массивчике. Чтобы они лежали в одном месте непрерывной памяти, а не были разбросаны по далёким местам двумерного массива. 2) Так как слова сравниваются редко (много вариантов отсекается сразу по первой букве), то код сравнения слов можно вынести в отдельную процедуру без потери эффективности. В главной процедуре остаётся всего два вложенных цикла. 3) Кэширование sb := s[begin]; не принципиально, ускоряет на чуть-чуть, но я всё же не удержался и добавил и его тоже. Производительность измерял в 64-разрядной системе на C# на машине с процессором i7 2600K, память 1600 MHz. Затем программу на C# переписал на Компонентном Паскале. Программу на Компонентном Паскале в 32-разрядном Блэкбоксе не испытывал, так что под Блэкбоксом результаты могут быть иными. |
Страница 1 из 2 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |