Здравствуйте, Cyberax, Вы писали:
C>У меня была реальная задача версирования графа треугольников C>(триангуляция большой карты высот) — я самую ее суть написал.
>> Теперь по сути вопроса. Если дан список неизменяемых значений (целых >> чисел, например) — то задача некорректно поставлена, т.к. и без >> транзакций нельзя поменять элемент в середине списка, не скопировав >> элементы, ему предшествующие. C>А ты представь, что объекты — изменяемые. Так как с иммутабельными C>объектами — все просто.
фишка в том, что при каждом изменении может не потребоваться пересчитывать все эти данные благодаря lazy evaluation. почитай вышеупомняутый диссер Окасаки — он там развил целую теорию насчёт "амортизированной" производительности. насчёт графов я не в курсе, но скажем списки с добавлением в конец таким образом реализуются. фактически в памяти при этом сохраняется _алгоритм_ вычисления конечного списка/графа и изменение этого списка/графа, например добавление новых элементов в конец списка, не требует полного вычисления его предыдущего содержимого