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)
{
  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++;
  }
}
Ваш вариант на C# выглядит так:
Код:
public static void MultiFind (byte[] s, int beg, int end, int wordCount, byte[][] words, int[] lens, out int word, out int pos)
{
  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;
  }
}
Я сравнил производительность C# вариантов на 64 разрядной системе (i7 2600K). Мой вариант быстрее вашего:

Длина текста 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%
При больших словарях (от 100 слов) целесообразно использовать другой алгоритм решения:
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: Пара примеров на цикл Дейкстры

Валерий Лаптев писал(а):
И кстати, о параллельности. ИМХО ЦД ЕСТЕСТВЕННО параллелится на многоядерном процессоре: каждая ветка - для отдельного ядра.
Ы-ы-ы?!! :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol:

Автор:  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/