Data.Vector заменяет Data.Sequence? - PullRequest
Новая
       17

Data.Vector заменяет Data.Sequence?

20 голосов
/ 04 ноября 2011

Я был большим поклонником Data.Sequence .Но поскольку я изучал Data.Vector , кажется, что он может делать все, что может Data.Sequence, но лучше, плюс он может делать больше вещей.Должны ли мы осудить Data.Sequence и проповедовать Data.Vector?Есть ли веские причины для использования Data.Sequence over Data.Vector?

Ответы [ 2 ]

36 голосов
/ 04 ноября 2011

Ни одна из этих структур данных не может заменить другую; Data.Sequence и Data.Vector фактически находятся на диаметрально противоположных концах структур данных, доступных для представления последовательностей.

  • Data.Vector - это непрерывный массив элементов. Это означает небольшой объем памяти и O (1) поиск, но ужасная мутация, конкатенация и копирование (O (n) каждый). (Мутация может быть O (1), если вы отбросите постоянство.)
  • Data.Sequence, с другой стороны, является чисто функциональным деревом. Это означает более высокое использование памяти и меньшую локальность, но оно поддерживает быстрый доступ и мутацию O (log n) и потрясающую конкатенацию O (log (min (n1, n2))) и копирование.

Выбор структуры данных действительно зависит от поставленной здесь задачи.

  • Обработка больших потоков элементов линейным способом или с произвольным поиском лучше всего делать с помощью Data.Vector.
  • Если вам нужно много раз разделить, объединить и изменить элементы, используйте Data.Sequence.
1 голос
/ 04 ноября 2011

Совместное использование префикса похоже на то, что Seq лучше, чем Vector.snoc на Vector - это O (n).

...