Должен ли я использовать List [A] или Seq [A] или что-то еще?

Question

Я писал класс, который содержал несколько функционально-esque методов.Сначала я написал их, используя List в качестве параметров и возвращаемых типов.Тогда я подумал: «Эй, ты также можешь использовать более общий тип!»поэтому я заменил списки на Seq, надеясь, что когда-нибудь смогу ускорить свои вещи, передав им что-то, кроме списков.

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

Обновление

Я постараюсь быть более точным: учитываязнать, какие операции вы используете, например, реверсирование, .tail, прямой доступ к элементу или для понимания.Могу ли я выбрать тип, который будет обеспечивать эффективность этих операций?

Обновление 2

Я хорошо знаю производительность конкретных структур данных для различных задач.Что я не знаю, так это то, какая структура данных может выглядеть как подкласс некоторого супертипа.

Например, я должен использовать TraversableOnce или IndexedSeq вместо List или Array?Это мне что-нибудь купит?

Дополнительный вопрос

Что такое ваша подпись по умолчанию в виде списка в структуре данных?Вы пишете

def a(b: List[A]): List[A] 

или

def a(b: TraversableOnce[A]): TraversableOnce[A]

Можете ли вы объяснить, почему?

Answer 1

List является реализацией по умолчанию LinearSeq, которая, в свою очередь, является реализацией по умолчанию Seq, которая, в свою очередь, является реализацией по умолчанию Iterable, которая, в свою очередь, является реализацией по умолчанию Traversable .

См. Диаграммы здесь и выберите наиболее общий тип в соответствии с вашими требованиями.

---

---

Этот документ также может помочь.

Answer 2

Я думаю, в общем, вы должны использовать Seq для ваших параметров и разрабатывать свои методы для эффективной работы с List. Таким образом, ваши методы будут работать нормально с большинством Seq реализаций, и вам не придется конвертировать ваши seqs перед использованием ваших методов.

Редактировать

Ваш вопрос содержит много вопросов.

1. Так для какой структуры данных общего назначения я должен написать свои методы и алгоритмы?
   • Я думаю, что ответ здесь List. Это стек, и он очень быстрый
2. Могу ли я выбрать тип, который повысит эффективность этих операций?
   • В общем случае вам придется полагаться на конкретную реализацию. Характеристики производительности приведены здесь http://www.scala -lang.org / document / files / collection-api / collection_40.html
3. Например, я должен использовать TraversableOnce или IndexedSeq вместо List или Array? Это купит мне что-нибудь?
   • Некоторые абстракции имеют определенные характеристики производительности, другие нет. Например, IndexedSeq scaladoc говорит: «Индексированные последовательности поддерживают постоянный или почти постоянный доступ к элементам и вычисление длины». Если у вас есть параметр IndexedSeq, и кто-то передает реализацию IndexedSeq, которая не имеет «доступа к элементу с почти постоянным временем», то этот кто-то нарушает контракт, и это не ваша проблема.
4. Какая ваша сигнатура структуры данных по умолчанию в виде списка?

Answer 3

Дополнительную информацию о библиотеке коллекций см. В статье Scala 2.8 Collections API .

Если вы имеете в виду конкретные операции, обратите внимание, в частности, на раздел Характеристики производительности .

Относительно выбора дизайна относительно того, использовать ли определенный тип более общей черты, я бы сказал, что это зависит от того, что вы делаете в реализации. Например, если метод принимает список, он может рассчитывать на быстрое добавление и может использовать это в своей реализации. Поэтому принятие более общей черты может иметь нежелательные результаты производительности. Кроме того, вам придется беспокоиться о том, какой тип вы получите.

scala> def a[A](t:TraversableOnce[A]): TraversableOnce[A] = t
a: [A](t: TraversableOnce[A])TraversableOnce[A]

scala> a(List(1,2))
res0: TraversableOnce[Int] = List(1, 2)

scala> res0.tail
<console>:8: error: value tail is not a member of TraversableOnce[Int]
       res0.tail

Если вы хотите написать что-то общее, вы, вероятно, захотите сохранить типы. См. Могу ли я "улучшить свою библиотеку" с помощью аналога TraversableLike.map, который имеет красивые варианты типов? для ознакомления с проблемами, с которыми вы столкнетесь, и некоторыми решениями.