Ли Байрон подчеркивает это в видео, но я не могу найти часть, где он это объясняет.
https://www.youtube.com/watch?v=I7IdS-PbEgI&t=1604s
Это потому, что когда вы обновляете узел, у вас есть журнал обхода (n), чтобы добраться до узла. С неизменяемой структурой, и он должен копировать n узлов в худшем случае ... Это все, что я думаю.
Если бы вы попытались создать неизменяемый список простым способом, очевидным решением было бы скопировать весь список в новый список и заменить этот единственный элемент. Таким образом, большой список займет больше времени для копирования, верно? Результат будет как минимум O(n).
Immutable.js, с другой стороны, использует график trie (см. википедию), который позволяет повторно использовать большую часть структуры, убедившись, что существующие ссылки не изменены.
Проще говоря, вы создаете новую древовидную структуру и создаете новые ветви для измененных частей. Когда одна из ветвей не изменяется, дерево может просто ссылаться на исходную структуру вместо копирования.
Документация по immutable.js начинается с двух ссылок на длинные описания, особенно хороша ссылка на векторные попытки:
Эти структуры данных очень эффективны на современных виртуальных машинах JavaScript благодаря совместному использованию структур через пробы хэш-карт и < href="https://hypirion.com/musings/understanding-persistent-vector-pt-1" rel="nofollow noreferrer">векторные попытки, популяризированные Clojure и Scala, сводя к минимуму необходимость копирования или кешировать данные.
Если вы хотите узнать больше деталей, вы можете взглянуть на вопрос о Как реализована неизменность тоже.
