Почему добавление в список плохо?
Я недавно начал изучать Scala, и я столкнулся с :: (cons) функция, которая добавляется в список.
В книге "Программирование в Scala" говорится, что нет функции добавления, потому что добавление в список имеет производительность o (n), тогда как предварительное добавление имеет производительность o(1).
Что-то мне кажется неправильным в этом утверждении.
Разве производительность не зависит от реализации? Разве нельзя просто реализовать список с прямыми и обратными ссылками и сохранить первый и последний элемент в контейнере?
Второй вопрос, который я полагаю, это то, что я должен делать, когда у меня есть список, скажем, 1,2,3, и я хочу добавить 4 в конце?
5 ответов
Ключ в том, что x :: somelist не мутирует somelist, но вместо этого создает новый список, который содержит х, а затем все элементы somelist, Это можно сделать за O(1) раз, потому что вам нужно только установить somelist как преемник x во вновь созданном, односвязном списке.
Если вместо этого использовались двусвязные списки, x также должен быть установлен в качестве предшественника somelistголова, которая изменила бы somelist, Так что, если мы хотим быть в состоянии сделать :: в O(1) без изменения исходного списка мы можем использовать только односвязные списки.
Что касается второго вопроса: вы можете использовать ::: объединить одноэлементный список до конца вашего списка. Это операция O(n).
List(1,2,3) ::: List(4)
Другие ответы дали хорошие объяснения этому явлению. Если вы добавляете много элементов в список в подпрограмме или создаете список, добавляя элементы, функциональная идиома состоит в том, чтобы создать список в обратном порядке, располагая элементы в начале списка, а затем поменяйте местами в конце. Это дает вам производительность O(n) вместо O(n²).
Поскольку вопрос только что обновился, стоит отметить, что здесь все изменилось.
В сегодняшней Scala вы можете просто использовать xs :+ x добавить элемент в конце любой последовательной коллекции. (Существует также x +: xs готовиться. Мнемоника многих операций по сбору Scala 2.8+ заключается в том, что цвет рядом с коллекцией.)
Это будет O (n) со связанной реализацией по умолчаниюListили жеSeq, но если вы используете Vector или же IndexedSeqЭто будет эффективно постоянное время. в Scala Vector вероятно, самая полезная спискообразная коллекция Scala - в отличие от Java Vectorчто в основном бесполезно в наши дни.
Если вы работаете в Scala 2.8 или выше, ознакомление с коллекциями абсолютно необходимо прочитать.
Предварительное добавление выполняется быстрее, потому что требуется только две операции:
- Создать новый узел списка
- Пусть этот новый узел указывает на существующий список
Для добавления требуется больше операций, потому что вам нужно перейти к концу списка, поскольку у вас есть только указатель на заголовок.
Я никогда не программировал в Scala раньше, но вы можете попробовать List Buffer
На большинстве функциональных языков видна структура данных с односвязными списками, поскольку это удобный неизменяемый тип коллекции. Когда вы говорите "список" на функциональном языке, это обычно то, что вы имеете в виду (односвязный список, обычно неизменный). Для такого типа append - это O(n), а cons - это O(1).