#list #data-structures #haskell #performance
#Список #структуры данных #haskell #Производительность
Вопрос:
В качестве упражнения для начинающих я реализовал следующую функцию для поиска n-го элемента в списке:
elem_at (h:_) 0 = h
elem_at (_:t) n = elem_at t (n-1)
elem_at _ _ = error "Index out of bounds"
Однако, если я вызову: elem_at [1,2,3,4] 5, правильно ли, что он вернет «Индекс вне границ» только после обхода всего списка, так что последняя строка соответствует шаблону _ _ with [] 1? В более общем плане, если бы список был большим, не было бы это проблемой производительности? Может ли ghc каким-то образом оптимизировать эту ситуацию?
Ответ №1:
На самом деле, это почти канонический способ индексирования списка. Вам нужно добавить проверку на отрицательные числа
elem_at xs n | n < 0 = error "elem_at: negative index"
И вы могли бы добавить конкретное соответствие для пустого списка:
elem_at [] _ = error "elem_at: index too large"
А базовый и индуктивный регистры:
elem_at (x:_) 0 = x
elem_at (_:xs) n = elem_at xs (n-1)
и у вас есть предварительное определение индексации списка, (!!) оператор.
Немного более эффективную версию можно получить с помощью рабочей оболочки, переместив индексный тест на верхний уровень.
Комментарии:
1. Спасибо! Это имеет смысл. Но подождите … для вычисления [] _, начиная с [1,2,3,4] и 5, я должен использовать индуктивный регистр 4 раза, верно?
2. Если n слишком велико, вы попадете в базовый вариант elem_at [] _ . Это хорошо, потому что, если вы сравните n с длиной, вы в конечном итоге пройдетесь по списку один раз, чтобы получить длину, а затем снова, чтобы найти элемент.
3. @Tim ты прав. Дополнительный вопрос: хранит ли Haskell длину списка внутри, чтобы запрос к нему мог быть действительно быстрым?
4. Нет. Вы могли бы написать свой собственный список, который это делал, но тогда вы не смогли бы использовать встроенные функции, которые работают со списками. Были некоторые разговоры о преобразовании типа списка в класс типов, чтобы его можно было обобщить, но я не думаю, что с этим что-то было сделано. Кроме того, @Don Stewart было бы лучше продолжить эту мысль, поэтому я заканчиваю здесь.
5. @Frank: нет, списки — это простой рекурсивный тип,
data [a] = [] | a : [a]. Вот и все. Если ваш алгоритм зависит от индексации или определения длины, рассмотрите возможность использования пальцевых деревьев или векторов (Data.SequenceилиData.Vector).
Ответ №2:
Я считаю, что реализация на haskell примерно так же эффективна, как и обход односвязного списка на любом языке. Если бы данные хранились в другой структуре, то вы могли бы ответить на вопрос, не просматривая список.
Комментарии:
1. Моя «проблема» в том, что мне очень нравится приведенный выше код, потому что он такой краткий. Было бы идеально, если бы я больше ничего не мог написать и все еще имел очень эффективный код во время выполнения. Я написал другую версию, которая быстрее вызывает ошибку при выходе за пределы (я думаю), но это не так элегантно.
2. Если у вас статический список и вам просто нужен быстрый поиск, вы могли бы повысить эффективность, преобразовав свой список в массив. haskell.org/haskellwiki/Modern_array_libraries