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

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

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

Update

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

Обновление 2

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

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

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

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

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

или

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

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

Ответы

Ответ 1

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

Edit

В вашем вопросе есть много вопросов.

Итак, какую общую структуру данных, подобную стекю, я должен написать свои методы и алгоритмы?
- Я думаю, что ответ здесь List. Это стек, и он очень быстро
Можно ли выбрать тип, который будет обеспечивать эффективность этих операций?
- В общем, вам придется полагаться на реализацию concerete. Характеристики производительности здесь http://www.scala-lang.org/docu/files/collections-api/collections_40.html
Например, я должен использовать TraversableOnce или IndexedSeq вместо List или Array? Купит ли я что-нибудь?
- Некоторые абстракции имеют характеристики производительности, некоторые другие нет. Например, IndexedSeq scaladoc говорит: "Индексированные последовательности поддерживают постоянный или близкий к постоянному времени доступ к элементу и вычисление длины". Если у вас есть параметр IndexedSeq, и кто-то передает реализацию IndexedSeq, у которой нет "почти постоянного доступа к временному элементу", тогда кто-то нарушает контракт, и это не ваша проблема.
Какова ваша подпись по умолчанию в виде списка данных?
- Seq

Ответ 2

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

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

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

Ответ 3

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

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

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

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, который имеет красиво варианты типов? для поиска проблем, с которыми вы столкнетесь, и некоторых решений.