Почему «списки» Scala реализованы в виде связанных списков

Question

Я всегда думал, что преимущество связанных списков состоит в том, что вы можете добавлять или удалять элементы (особенно не в конце) без необходимости копировать много элементов благодаря красоте указателей.

Однако ScalaList является неизменным (по крайней мере по умолчанию).В чем преимущество наличия неизменного связанного списка (поскольку есть определенные недостатки, например, отсутствие доступа к элементу O (1).)

Спасибо!

Answer 1

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

def listlen[A](xs: List[A], already: Int = 0): Int = xs match {
  case Nil => already
  case x :: rest => listlen(rest, already+1)
}

Конечно, списки уже знают, как получить их длину; это всего лишь пример. Дело в том, что вы отрываете голову, а затем делаете что-то еще с хвостом - таким образом работает много полезных вещей.

Поскольку списки неизменны , мы можем сделать что-то еще - мы можем потратить столько времени, сколько мы хотим, чтобы оценить остальную часть нашего списка! Мы не должны закончить за один раз; мы уверены, что это никогда не изменится. Это было бы не так, если бы список был изменчивым - либо нам нужно заблокировать список, чтобы никто другой не видел его, либо нам нужно сделать защитную копию всего этого на случай, если кто-то может поменять его.

Теперь, если вам действительно нужен изменяемый список, есть mutable.LinkedList, у которого есть хорошие свойства вставки, о которых вы говорите. Но это не дает вам элегантной рекурсии с душевным спокойствием, которую дают вам неизменные списки.

(Обратите внимание, что вы могли бы сделать это с неизменной структурой на основе массива, но возможное преимущество коллекции с каждым обернутым элементом состоит в том, что вам не нужно сохранять или копировать весь массив только потому, что вам нужен несколько элементов с конца; если ранние элементы в списке больше не указаны, они могут быть удалены мусором.)

Answer 2

Структурное разделение. Если вы выполняете функцию более высокого порядка (отображение, сложение и т. Д.) В списке, вы возвращаете новый экземпляр списка, который разделяет указатели предыдущего списка.

Даниэль Спивак на прошлой неделе сделал замечательную презентацию о функциональных структурах данных в NE Scala. Смотрите здесь: http://www.nescala.org/2011/

Answer 3

Однако, список Scala неизменен (по крайней мере, по умолчанию). В чем преимущество наличия неизменного связного списка

Я немного опоздал на вечеринку здесь, но я чувствовал, что есть важный момент, который никто не сделал:

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

Тот факт, что вы можете создавать новые, более крупные, но все еще неизменяемые списки с постоянной операцией и с небольшим объемом памяти (только стоимость одного узла), является, я подозреваю, значительной частью причин, по которым данные структура была выбрана.

Answer 4

scala.List - псевдоним для scala.collection.immutable.List. Это всего лишь одна из многих конкретных реализаций коллекций.

Если вы работаете с фоном Java, приравнивайте java.util.List к scala.collection.mutable.Buffer, а не scala.List.

Обзор структуры библиотеки коллекций можно найти в Обзор коллекций Scala 2.8. . Здесь вы найдете много других конкретных реализаций (как изменяемых, так и неизменных).

Answer 5

Пока я почти не представляю, как реализована scala. Однако следует избегать LinkedLists.

Они неэффективны на современном оборудовании из-за их обхода, каждый узел практически приводит к потере кэша. Промахи в кеше - вот что влияет на производительность в наше время.