OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 13 Декабрь, 2019 05:32

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Компрометация цикла Дейкстры
СообщениеДобавлено: Четверг, 19 Январь, 2012 17:25 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
(модератор) Исходное решение с помощью ЦД, см: 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%

Во всех вариантах искомых слов в тексте не было (худший случай).

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


Последний раз редактировалось Сергей Губанов Среда, 25 Январь, 2012 17:21, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Четверг, 19 Январь, 2012 19:17 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Удалось ещё больше ускорить программу.

Надо вместо

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% быстрее в худшем случае (текст короткий, а искомых слов очень много).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Четверг, 19 Январь, 2012 20:25 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Сергей Губанов писал(а):
Работает до 2-х раз быстрее исходного варианта по "Дейкстре" в лучшем случае (текст очень длинный, а искомых слов мало) и на 30% быстрее в худшем случае (текст короткий, а искомых слов очень много).
Браво!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Четверг, 19 Январь, 2012 20:41 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4539
Откуда: Россия, Орёл
Сергей Губанов писал(а):
Я сравнил производительность C# вариантов на 64 разрядной системе (i7 2600K). Мой вариант быстрее вашего
Ваш вариант --- оптимизация, о которой думают потом. И возможен он тут, т.к. вычислительная сложность самих веток сопоставима со сложностью охран. Но так будет не во всех задачах.


Последний раз редактировалось Евгений Темиргалеев Суббота, 21 Январь, 2012 07:24, всего редактировалось 1 раз.
разделение темы


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Четверг, 19 Январь, 2012 21:40 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8215
Откуда: Троицк, Москва
alexus писал(а):
Сергей Губанов писал(а):
Работает до 2-х раз быстрее исходного варианта по "Дейкстре" в лучшем случае (текст очень длинный, а искомых слов мало) и на 30% быстрее в худшем случае (текст короткий, а искомых слов очень много).
Браво!
Ну да. И ООП-ом нужно заниматься на ассемблере.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Четверг, 19 Январь, 2012 22:22 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 531
Откуда: Москва
Сергей Губанов писал(а):
Удалось ещё больше ускорить программу.
Можете еще ускорить, т.к. в самом внутреннем цикле есть лишняя индексация words[w], где w внутри цикла не меняется.
А вообще, если нужна скорость, так есть готовые алгоритмы. Ахо-Корасик тот же.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 00:06 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8215
Откуда: Троицк, Москва
Peter Almazov писал(а):
если нужна скорость, так есть готовые алгоритмы. Ахо-Корасик тот же.
Там случайно не ЦД?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 08:06 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 531
Откуда: Москва
Ну, вообще-то, на такие вопросы обычно отвечают: используйте Google.
Там нет ЦД, более того, я почти уверен, что ЦД как средство ликвидации вложенности вообще не используется ни в одном справочнике алгоритмов. Если это только не учебник.
Ибо за повторную проверку условия автора закидают помидорами. Т.к люди ожидают оптимизации. Не преждевременной, а Just In Time :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 08:37 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Сергей Губанов писал(а):
Илья Ермаков писал(а):
Алгоритм 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).
Примечание: Во всех приведённых формулах "затраты времени" считаются пропорциональными количеству операций сравнения.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 08:46 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
Можно ещё ускорить, если хешировать словарь и хранить его в красно-чёрном дереве.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 08:48 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9165
Откуда: Россия, Орёл
Кстати, сфера применения нашего алгоритма мультипоиска достаточно очевидна из второго алгоритма: разбор всяких потоков данных. Т.е. ясно ограничение на длину и количество искомых слов.
Грешно тут переделывать под оптимизацию :)

Вообще, я сейчас придерживаюсь принципа оптимизации, для нагруженных приложений: определяющей является работа с памятью (в широком смысле, например, форматы данных и проч.), а не заоптимизированное программирование алгоритмов. Какой-нибудь XML там, где он не нужен, может съедать до 70% маш. времени. Если же XML приходит извне и неизбежен, то при простом формате избегание использования общих парсеров типа DOM, замусоривающих память динамическими объектами, даёт тоже приличный эффект.
И так по всей программе: перестать в каком-нибудь месте "мусорить" и нагружать сборщик - значительно более приличная оптимизация, чем перестановка буков в алгоритме. (При использовании КП есть много путей повышения эффективности. В отличие от Java, где вы даже строчку не заведёте без выделения дин. памяти. Теперь, конечно, есть JIT-оптимизаторы, перекидывающие эту работу обратно на стек... но ну её в качель, всю эту чунгу-чангу :) ).

К тому же алгоритм оптимизировать можно всегда "задним числом", а вот переделать работу с памятью без глубокой переделки часто нельзя.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 09:09 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Илья Ермаков писал(а):
Кстати, сфера применения нашего алгоритма мультипоиска достаточно очевидна из второго алгоритма: разбор всяких потоков данных. Т.е. ясно ограничение на длину и количество искомых слов.
Кстати, забыл отметить, что подход/алгоритм, предложенный в предыдущем моём сообщении, позволяет выполнять параллельный поиск (в отличие от цикла Дейкстры), что может оказаться полезным в нынешних реалиях.
Илья Ермаков писал(а):
Грешно тут переделывать под оптимизацию :)
Это Вам виднее... Лишь бы потом у студентов не возникало проблем при столкновении с реальной жизнью. Не лучше ли "нафталиновые" алгоритмы (типа "цикла Дейкстры") оставить на самостоятельное освоение тем студентам, которым интересно?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 09:16 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9165
Откуда: Россия, Орёл
alexus писал(а):
2. Для каждого слова текста:


Здесь путаница. В моём алгоритме "слово" - это "подпоследовательность".
Таким образом понятие "слово текста" не имеет смысла.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 11:21 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8215
Откуда: Троицк, Москва
Peter Almazov писал(а):
Ну, вообще-то, на такие вопросы обычно отвечают: используйте Google.
Там нет ЦД, более того, я почти уверен, что ЦД ...
Мой вопрос был в значительной степени риторическим.

"используйте Гугл" можно ответить на многие вопросы, но мы же обращаемся к коллегам.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 11:24 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8215
Откуда: Троицк, Москва
Плюс ко всему есть понятие evolvability.
"Оптимизированные" алгоритмы эволюции не выдерживают.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 11:51 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Евгений Темиргалеев писал(а):
Ваш вариант --- оптимизация, о которой думают потом.
Если бы забота была о предельной ясности, а не об оптимизации, то эти линейные поиски были бы вынесены в отдельные процедуры.

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


Последний раз редактировалось Евгений Темиргалеев Суббота, 21 Январь, 2012 07:38, всего редактировалось 3 раз(а).
разделение темы


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 12:03 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3124
Откуда: Астрахань
Евгений Темиргалеев писал(а):
Сергей Губанов писал(а):
Я сравнил производительность C# вариантов на 64 разрядной системе (i7 2600K). Мой вариант быстрее вашего
Ваш вариант --- оптимизация, о которой думают потом. И возможен он тут, т.к. вычислительная сложность самих веток сопоставима со сложностью охран. Но так будет не во всех задачах.
И кстати, о параллельности.
ИМХО ЦД ЕСТЕСТВЕННО параллелится на многоядерном процессоре: каждая ветка - для отдельного ядра.
(модератор) разделённое сообщение: viewtopic.php?p=69711#p69711


Последний раз редактировалось Евгений Темиргалеев Суббота, 21 Январь, 2012 07:40, всего редактировалось 1 раз.
разделение темы


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 12:47 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Валерий Лаптев писал(а):
И кстати, о параллельности. ИМХО ЦД ЕСТЕСТВЕННО параллелится на многоядерном процессоре: каждая ветка - для отдельного ядра.
Ы-ы-ы?!! :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol: :lol:


Последний раз редактировалось Евгений Темиргалеев Суббота, 21 Январь, 2012 07:42, всего редактировалось 1 раз.
разделение темы


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 13:22 
Аватара пользователя

Зарегистрирован: Суббота, 27 Февраль, 2010 23:34
Сообщения: 746
Илья Ермаков писал(а):
alexus писал(а):
2. Для каждого слова текста:

Здесь путаница. В моём алгоритме "слово" - это "подпоследовательность".
Таким образом понятие "слово текста" не имеет смысла.
Дело в том, что я отвечал на сообщение Сергея Губанова. Ни Ваше сообщение, ни Ваши алгоритмы я не обсуждал.

(модератор) удалена часть сообщения с цитатами и ответом на удалённое сообщение другого участника


Последний раз редактировалось Евгений Темиргалеев Суббота, 21 Январь, 2012 08:04, всего редактировалось 2 раз(а).
вырезание пикировки участников


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Пара примеров на цикл Дейкстры
СообщениеДобавлено: Пятница, 20 Январь, 2012 21:07 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Удалось ещё больше ускорить, да ещё и вынести один линейный поиск в отдельную процедуру.

Вспомогательная процедура:
Код:
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-разрядном Блэкбоксе не испытывал, так что под Блэкбоксом результаты могут быть иными.


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

Часовой пояс: UTC + 3 часа


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

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


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

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB