Производительность, связанная с "императивными" алгоритмами в haskell

У меня есть кое-какое обучение в семействе языков LISP, и сейчас я немного изучаю Хаскель для своего же блага. В lisp, функциональный стиль в порядке, но есть несколько случаев, когда для получения достойной производительности необходим императивный стиль, например

  • присоединять

    Добавить медленное, поскольку оно должно копировать свой первый аргумент (иногда x100 медленнее, чем версии, которые удаляются от него). Решение проблемы - переместить последний указатель первого списка в начало второго списка вместо добавления. Конечно, это разрушительная операция.

  • Сортировать

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

  • длина

    Это дорогостоящая операция в lisp, так как нужно пройти весь список, чтобы получить его длину. Это не должно быть так, afaik clojure вычисляет длину списка в логарифмическом времени. Решение часто состоит в том, чтобы вычислить длину на лету в императивном цикле.

Мой вопрос, как мы решаем эти проблемы в Haskell?

Источник

2 ответа

Решение

Как сказал Делнан, эти проблемы связаны с использованием неправильной структуры данных, такой как связанный список, когда вам нужен вектор.

Ваши конкретные операции

  • append: cons - это O(1), поэтому я подозреваю, что вы имеете в виду процесс выделения cons-ячейки, сопоставления с образцом в ячейке и возможного GC ячейки. Это довольно неизбежно, если вы не оптимизируете список, что случается в определенных ситуациях.

  • sort: я предлагаю вам взглянуть на монаду ST, которая позволяет вам использовать алгоритмы, которые требуют мутации в чистом контексте. Смотрите реализацию vsort для примера.

  • length: Конечно, единственный способ получить длину связанного списка - это просмотреть список. Если вам часто нужна длина, тогда подумайте об использовании набора, карты или вектора - все они записывают общий размер, к которому можно получить доступ в O(1).

В общем

  • Заглянуть в ST для изменчивости.
  • Используйте правильную структуру данных для правильной задачи. Узнайте, какие структуры может предложить Hackage (векторы, массивы, хэш-карты, хеш-таблицы, фильтры bloomfilters и т. Д.).
Источник

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

Как упоминают Делнан и Томас Дюбюссон, у Haskell есть все эти опции, если вы выбираете правильный тип данных.

Так что если у вас есть определенный алгоритм, который вы хотите оптимизировать, то, скорее всего, найдется способ перевести его на быструю неразрушающую версию, вариант для симуляции деструкции, обычно с мультипликативной log(n) замедление или возможность запуска ссылочно-прозрачных разрушений при аддитивном постоянном замедлении.

Для хороших примеров проблем с этим переводом посмотрите алгоритмы постоянного объединения-поиска или библиотеку функциональных графов.

Источник
Другие вопросы по тегам