Означает ли неизменность, что огромные коллекции полностью воссоздаются при каждом изменении?

Question

В последнее время я пытаюсь заняться функциональным программированием.В частности, я был заинтересован в Clojure.Я понимаю большинство аргументов в пользу неизменности данных, но одна вещь просто не имеет смысла для меня.Предположим, у меня есть очень большая коллекция, такая как карта или массив, содержащий сотни миллионов предметов.Если я не могу изменить его, значит ли это, что каждый раз, когда я хочу добавить новый элемент, я по сути воссоздаю всю коллекцию?Это звучит как ужасная идея.Как такая ситуация обрабатывается в языках, где все неизменно?

Answer 1

В случае Clojure они не воссоздаются каждый раз.Рич Хики позаботился о том, чтобы использовать постоянные структуры данных , как он объясняет в «Эксперте-эксперту» интервью .

Вы можете думать об этом больше как о связанном списке.

class LinkedList<E> {
    E data;
    LinkedList<E> next;

    LinkedList<E> cons(E item) {
        return new LinkedList(item, this);
    }
}

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

Аналогично,даже структуры данных, такие как карты, могут делиться большими объемами своих данных, когда они отличаются лишь незначительными объемами.Это помогает уменьшить используемый размер.

Кроме того, Clojure также предоставляет временные структуры данных , которые являются изменчивыми версиями его неизменяемых коллекций, позволяя вносить многочисленные изменения в структуру данных без затраткопирования / обмена данными.