Почему добавление к списку плохо?
Я смотрел бы на абстрактные тестовые классы Spring и фиктивные объекты, с которыми говорят приблизительно здесь . Они обеспечивают мощный способ автосоединить проводом Ваши управляемые объекты Spring, делающие поблочное и легче интеграционное тестирование.
4 ответа
Ключ в том, что x :: somelist не изменяет somelist , а вместо этого создает новый список, который содержит x, за которым следуют все элементы somelist . Это можно сделать за O (1) раз, потому что вам нужно только установить somelist в качестве преемника x во вновь созданном односвязном списке.
Если бы вместо этого использовались двусвязные списки, x также нужно было бы установить в качестве предшественника головы somelist , что изменило бы somelist . Поэтому, если мы хотим иметь возможность выполнять :: в O (1) без изменения исходного списка, мы можем использовать только односвязные списки.
Относительно второго вопроса: вы можете использовать ::: , чтобы присоединить одноэлементный список к концу вашего списка. Это операция O (n).
List(1,2,3) ::: List(4)
В большинстве функциональных языков заметно выделяется структура данных односвязного списка, поскольку это удобный неизменяемый тип коллекции. Когда вы говорите «список» на функциональном языке, вы обычно имеете в виду именно это (односвязный список, обычно неизменяемый). Для такого типа append имеет значение O (n), а cons - O (1).
Другие ответы дали хорошее объяснение этого явления. Если вы добавляете много элементов в список в подпрограмме или если вы создаете список, добавляя элементы, функциональная идиома состоит в том, чтобы создать список в обратном порядке, складывая элементы на передней ] списка, затем переверните его в конце. Это дает вам производительность O (n) вместо O (n²).
Предварительная обработка выполняется быстрее, потому что она требует только двух операций:
- Создание нового узла списка
- Указывает, что этот новый узел указывает на существующий список
Добавление требует большего числа операций, потому что вам нужно перейти к концу списка, поскольку у вас есть только указатель на голову.
Я никогда раньше не программировал на Scala, но вы можете попробовать List Buffer
]