Почему добавление в список плохо?

Question

Я недавно начал изучать scala и натолкнулся на функцию :: (cons), которая добавляется в список.
В книге «Программирование в Scala» говорится, что нет функции добавления, потому что добавление в список имеет производительность o (n), тогда как предварительное добавление имеет производительность o (1)

Что-то мне кажется неправильным в этом утверждении.

Не зависит ли производительность от реализации? Разве нельзя просто реализовать список с прямыми и обратными ссылками и сохранить первый и последний элемент в контейнере?

Второй вопрос, который я полагаю, это то, что я должен делать, когда у меня есть список, скажем, 1,2,3, и я хочу добавить 4 в его конец?

Answer 1

Ключ в том, что x :: somelist не изменяет somelist, но вместо этого создает новый список, который содержит x, за которым следуют все элементы somelist. Это можно сделать за O (1), потому что вам нужно только установить somelist как преемник x во вновь созданном, односвязном списке.

Если бы вместо этого использовались двусвязные списки, x также должен был бы быть установлен как предшественник somelist головы, что изменило бы somelist. Поэтому, если мы хотим иметь возможность делать :: в O (1) без изменения исходного списка, мы можем использовать только односвязные списки.

Относительно второго вопроса: Вы можете использовать :::, чтобы объединить одноэлементный список до конца вашего списка. Это операция O (n).

List(1,2,3) ::: List(4)

Answer 2

Другие ответы дали хорошие объяснения этому явлению. Если вы добавляете много элементов в список в подпрограмме, или если вы создаете список, добавляя элементы, функциональная идиома состоит в том, чтобы создать список в обратном порядке, объединяя элементы на front списка, затем переверните его в конце. Это дает вам производительность O (n) вместо O (n²).

Answer 3

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

В сегодняшней Scala вы можете просто использовать xs :+ x, чтобы добавить элемент в конец любой последовательной коллекции. (Предусматривается также x +: xs. Множество многих операций сбора Scala 2.8+ заключается в том, что col on идет рядом с лекцией col .)

Это будет O ( n ) со связанной реализацией по умолчанию List или Seq, но если вы используете Vector или IndexedSeq, это будет фактически постоянное время. Scala Vector, вероятно, является самой полезной списковой коллекцией Scala - в отличие от Java Vector, который в наши дни в основном бесполезен.

Если вы работаете в Scala 2.8 или выше, введение коллекций абсолютно необходимо прочитать.

Answer 4

Предварительное добавление выполняется быстрее, поскольку требуется только две операции:

1. Создать новый узел списка
2. Пусть этот новый узел указывает на существующий список

Для добавления требуется больше операций, потому что вам нужно перейти к концу списка, поскольку у вас есть только указатель на голову.

Я никогда раньше не программировал в Scala, но вы можете попробовать List Buffer

Answer 5

Большинство функциональных языков заметно представляют структуру данных с односвязным списком, поскольку это удобный неизменяемый тип коллекции. Когда вы говорите «список» на функциональном языке, это обычно то, что вы имеете в виду (односвязный список, обычно неизменный). Для такого типа append - O (n), а cons - O (1).