В чем разница между Seq и IndexedSeq/LinearSeq в Scala?

Question

В документации Scala Collection есть некоторые подсказки к этому вопросу:

Trait Seq имеет две субтитры LinearSeq и IndexedSeq. Они не добавляют никаких новых операций, но каждая предлагает различные характеристики производительности: линейная последовательность имеет эффективные операции заголовка и хвоста, тогда как индексированная последовательность имеет эффективные операции применения, длины и (если изменяются) обновления.

Но это не касается меня, когда использовать IndexedSeq вместо Seq? Мне нужен настоящий пример IndexedSeq или же LinearSeq где эти коллекции лучше, чем Seq,

Answer 1

Seq это супер-черта, поэтому она более общая, она имеет характеристики, общие для всех последовательностей, как линейных, так и индексированных.

Если вам интересно, какая последовательность создается Seq.apply Метод в объекте-компаньоне Seq, мы можем взглянуть на реализацию.

Имейте в виду, что если вы используете Seq.apply, вы подразумеваете, что вам просто нужен Seq и что вашему коду не важно, линейный он или индексированный

Ответ tl;dr: вы используете LinearSeq или же IndexedSeq когда вам нужно иметь определенные характеристики производительности, вы используете более общие Seq когда тебя не волнует разница

Это сопутствующий объект Seq:

object Seq extends SeqFactory[Seq] {
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Seq[A]] = ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

  def newBuilder[A]: Builder[A, Seq[A]] = immutable.Seq.newBuilder[A]
}

newBuilder[A] Метод - это то, что используется для построения Seq, как вы можете проверить в методе Seq.apply (определенном на признаке). GenericCompanion):

def apply[A](elems: A*): CC[A] = {
   if (elems.isEmpty) empty[A]
   else {
     val b = newBuilder[A]
     b ++= elems
     b.result()
   }
 }

Теперь вопрос: что делает immutable.Seq.newBuilder[A] строить? Давайте посмотрим, на этот раз на immutable.Seq сопутствующий объект:

object Seq extends SeqFactory[Seq] {
// stuff
  def newBuilder[A]: Builder[A, Seq[A]] = new mutable.ListBuffer
}

Он строит изменчивый ListBuffer! Это почему? Это потому что mutable.ListBuffer также бывает Builder[A, Seq[A]] это класс, который используется библиотекой коллекций для создания новых коллекций.

Фактическая коллекция выходных данных поступает из этой строки (как вы можете видеть выше):

b.result()

Итак, каков тип возврата ListBuffer.result()? Давайте посмотрим в ListBuffer:

// Implementation of abstract method in Builder
def result: List[A] = toList

здесь вы идете: это список.

Seq(1,2,3) возвращает List[Int] под капотом, но суть в том, что если вы используете Seq(), вам не нужно знать, какая у вас коллекция, потому что вы подразумеваете, что более абстрактного интерфейса достаточно для ваших нужд

Answer 2

Seq - это просто супер-черта IndexedSeq и LinearSeq. Seq - упорядоченный список, в отличие от Set, который обычно уникален и неупорядочен, и в отличие от Map, которая является парой ключ-значение.
Теперь идет IndexedSeq против LinearSeq.
Подклассы IndexedSeq, то есть Vector, Range, String, - это быстрый доступ на основе индекса и, как правило, быстрые обновления. Это возможно, потому что они используют подходящие для этого структуры данных, такие как внутренний массив (как в String) или дерево (на самом деле это дерево с разветвлением 32, используемое Vector... для более подробной информации, смотрите это), или Range, который представляет собой всего три числа. начало, конец, шаг.. из которого вычисления индекса просты.
В отличие от этого, все LinearSeq медленно работают на основе индексов и доступа, а обновления медленны. Обычно потому, что они имеют структуру связанного списка. Prepend быстро для всех из них, например, Queue, Stack, List..., но append общеизвестно медленен, поскольку должен идти к краю внутренней структуры связанного списка... за исключением очереди, которая использует уловку со своими проблемами. Трюк описан здесь.
В широком смысле, IndexedSeq - это структуры данных, которые имеют быстрый доступ и обновление на основе индекса, а LinearSeq - это структуры данных, которые имеют быстрое добавление.