Сравнение ЯП на примере составления "словаря"

[незваный гость]

Спасибо за программы и результаты! Программы будет интересно почитать, может быть, и кто-нибудь еще что-либо добавит.

Егор писал(а):

Сравнение пар на Питоне можно записать кратко:

Можно еще кратче и проще (и намного быстрее): делать массив пар (cnt, str) (вместо (str, cnt)), и использовать встроенное сравнение. Быстрее, даже если придется создавать дополнительный список.

[bugmaker]

Сравнение языков на примере написания raytracer: http://www.ffconsultancy.com/free/ray_t ... uages.html

[Егор]

незваный гость писал(а):

Можно еще кратче и проще (и намного быстрее): делать массив пар (cnt, str) (вместо (str, cnt)), и использовать встроенное сравнение. Быстрее, даже если придется создавать дополнительный список.

Ещё поменять знак у cnt, чтобы сортировалось по убыванию. Для небольших файлов с большим словарём время работы сократилось почти в два раза. Не думал, что окончательная сортировка пар на Питоне (с помощью переопределённой функции сравнения) была настолько долгой. Для Перла этот этап тоже долгий, но пока что оставил по-старому. На C++ встроенная сортировка пар тоже чуть быстрее, чем с помощью внешней функции сравнения, но разница не так велика. В "C++, sort" поменял, а в "C++, map" оставил по-старому.

Улучшил разбиение на слова в программах на C++ (помог вариант на Лиспе ).

Вот немножко подправленные программы и результаты сравнения:
\begin{tabular}{|l|r|r|r|r|r|r|} \cline{1-5} \textbf{Input files} & Shakespeare & Bible & Thesaurus & Ulysses \\ \cline{1-5} size (bytes) & 5582655 & 4445260 & 2801695 & 1561677 \\ \cline{1-5} n (words) & 928012 & 793877 & 197768 & 270556 \\ \cline{1-5} m (dict's size) & 23683 & 12876 & 34977 & 29127 \\ \cline{1-5}\hline \textbf{Programs} &\multicolumn{4}{|c|}{time (sec)} & bytes & lines \\ \hline C, TST & 0.25 & 0.18 & 0.13 & 0.13 & 3674 & 151 \\ \hline C, 3-way str qsort & 0.48 & 0.36 & 0.15 & 0.16 & 4518 & 176 \\ \hline C, qsort & 1.00 & 0.77 & 0.24 & 0.28 & 2599 & 98 \\ \hline CPP, map & 1.48 & 1.00 & 0.51 & 0.56 & 1930 & 73 \\ \hline CPP, sort & 4.94 & 4.08 & 1.00 & 1.31 & 2116 & 79 \\ \hline Lisp, hash & 3.71 & 3.01 & 1.69 & 1.50 & 1171 & 35 \\ \hline Perl, hash & 1.77 & 1.24 & 1.28 & 1.16 & 707 & 30 \\ \hline Perl, sort & 3.90 & 3.09 & 1.14 & 1.48 & 771 & 34 \\ \hline Python, dict & 1.39 & 1.08 & 0.61 & 0.59 & 637 & 27 \\ \hline Python, sort & 2.49 & 1.97 & 0.60 & 0.81 & 743 & 34 \\ \hline \end{tabular}
Два замечания по поводу C++.

1. Сравнительно долго работает "C++, sort".

2. Посмотрим на самые долгие операции в программах "C++, map" и "Python, dict":

++d[word];  (C++, d имеет тип map)
d[word] = d.get(word, 0) + 1 (Python, d имеет тип dict)

На C++ поиск осуществляется один раз, а на Питоне - два раза. Однако время работы примерно одинаковое.

Подозреваю, что обе странности объясняются использованием предиката "меньше". Чтобы сравнить две равных строки, достаточно один раз вызвать функцию strcmp (которая возвращает +, 0, -), но требуется аж два раза вызывать предикат "меньше".

[незваный гость]

Егор писал(а):

Питоне - два раза

1) Python'овский словарь использует hash (а не compare).
2) Я бы не рискнул утверждать определенно, что Python ищет дважды. Текстуально — да, но оптимизация (компилятором) она и в Python оптимизация.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Я пытаюсь сделать профилирование Python'а. Некоторые результаты меня уже удивили. Например, и в случае словаря, и в случае сортировки, есть вторая сортировка по частоте и алфавиту в конце. Так вот (я использовал только Шекспира), вторая сортировка в словарном алгоритме занимает примерно в два раза больше времени, чем в сортирующем. Я раздумывал над причиной, пока не понял — в словарном случае данные сильно случайны, а сортированном много правильно упорядоченных данных.

Другие результаты более предсказуемы: например, время ввода заметно превышает время вывода (просто объем перекачиваемых данных в двадцать раз больше); построение частот в случа сортировки — заметный вычислительный процесс.
Для сортировки:

 5.607s ввод и разбиение на слова
14.866s сортировка слов
 7.551s построение частот слов
 0.475s сортировка по частотам
 0.621s вывод

Для словаря:

 5.560s ввод и разбиение на слова
 9.536s построения словаря
 1.724s построение частот
 0.991s сортировка по частотам
 0.655s вывод

После сравнения ежу понятно, что оптимизировать надо построение словаря и построение частот. Понятно также, что стоит использовать словарь — он едва ли не вдвое быстрее. Оптимизировать сортировку (в сортировке) в общем нечем, там объем работы определяет время. Очевидно, что оптимизация вывода (и последней сортировки) — это ловля блох (хотя и зудит меньше).

[незваный гость]

Крохотное изменение (словарного алгоритма):

  for word in words:
    if word in d:
      d[word] += 1
    else:
      d[word] = 1

и

  pairs = [(-count, word) for (word, count) in d.iteritems()]

.iteritems() вместо .items() дает новый результат:

 5.522s ввод и разбиение на слова
 6.892s построения словаря
 1.359s построение частот
 0.974s сортировка по частотам
 0.641s вывод

[Егор]

Во как... Теперь "Python, dict" уверенно обгоняет "C++, map". Правда, речь идёт о сравнении готовых библиотечных алгоритмов, к тому же разных (хэш и бинарное дерево), но всё же никак не ожидал таких результатов.

bugmaker писал(а):

Сравнение языков на примере написания raytracer: http://www.ffconsultancy.com/free/ray_t ... uages.html

Интересно. Правда, не могу сообразить, как перенаправить вывод в OpenGL, чтобы получились сами рисунки .

[bugmaker]

Цитата:

но всё же никак не ожидал таких результатов.

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

Цитата:

Правда, не могу сообразить, как перенаправить вывод в OpenGL, чтобы получились сами рисунки

Зачем перенаправлять? Я только одну прогу пробовал, http://www.ffconsultancy.com/free/ray_t ... de/ray.cpp . gqview получившийся рисунок отлично показывает. ИМХО и с остальными так же должно быть.

[Егор]

bugmaker писал(а):

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

Меня удивило, что библиотечные STL::sort и STL::map работают медленнее, чем питоновские sort и dict. Ожидал от Питона большего торможения из-за динамической типизации.

"Ручное" выделение слов на C++ работает нормально. Небиблиотечное TST на C, которое взял почти готовым из какой-то статьи, - просто отлично (естественно, там алгоритм специально для строк).

Цитата:

Я только одну прогу пробовал, http://www.ffconsultancy.com/free/ray_t ... de/ray.cpp . gqview получившийся рисунок отлично показывает. ИМХО и с остальными так же должно быть.

Спасибо. Не сообразил, что получается обычный рисунок. (Там было какое-то упоминание OpenGL.)

[bugmaker]

Цитата:

Меня удивило, что библиотечные STL::sort и STL::map работают медленнее

STL ИМХО вообще добавлено "чтоб было", у него ещё полно недостатков.

Цитата:

Ожидал от Питона большего торможения из-за динамической типизации.

позднее связывание в с++ тоже штука небыстрая.

Цитата:

Не сообразил, что получается обычный рисунок.

man 1 file

[Егор]

В двух тестированных программах (самых быстрых) были использованы готовые реализации TST и сортировки Бентли-Сэджвика. Забыл указать источник. Там перевод статьи Бентли и Сэджвика, дополненный текстами алгоритмов на C.

Недавно Алексей Татаринов прислал оригинал и улучшенный перевод статьи Бентли и Сэджвика.