Здравствуйте, Cyberax, Вы писали:
>> Если будет время, опиши, пожалуйста, задачу, а не реализацию. Хорошо бы >> в таком виде, чтобы решение можно было набросать за пару часов. Самому >> интересно, решается ли она с помощью хаскелловской реализации STM. C>Задача простая: C>1) Дан обычный линейный однонаправленый список. C>2) Необходимо придумать механизм транзакций, чтобы можно было поменять C>элемент из середины списка, не влияя на клиентов вне транзакции. C>3) Этот механизм не должен приводить к копированию списка.
По моему скромному имху, "дан линейный однонаправленный список ..." — это не задача. Задача — это, например, перевести деньги со счета на счет.
Теперь по сути вопроса. Если дан список неизменяемых значений (целых чисел, например) — то задача некорректно поставлена, т.к. и без транзакций нельзя поменять элемент в середине списка, не скопировав элементы, ему предшествующие. Т.е., если в терминах хаскелловской реализации мы работаем с переменной типа TVar [Int] (по сути, это одна транзакционная ячейка, содержащая весь список), каждая транзакция будет вызывать копирование всего списка; правда, смысла в таких транзакциях немного. А вот если мы работаем со списком ячеек транзакционной памяти — [TVar Int] — изменение одной из ячеек в списке копирования других элементов не вызовет. Механизм придумывать не надо — он уже придуман и реализован, я уже приводил здесь ссылку на статью.
Здравствуйте, AndreiF, Вы писали:
AF>Здравствуйте, VladD2, Вы писали:
VD>>Для особо невнимательных повторяю — НЕИЗМЕНЯЕМЫЕ СТРУКТУРЫ ДАННЫХ.
AF>Вся прелесть неизменяемых данных в том, что их можно использовать в измененной копии, не так ли?
Не так. Вся прелесть их в том, что при грамотном проектировании можно порождать икрементальные не изменяемые копии.
AF> Это еще называется "неразрушающее присваивание". Например, создать новый список, приклеив новую голову к старому, и далее работать с ним. Ты уж извини, что я тебе о таких азах напоминаю.
Это ты уж извини, но ты напоминашь о них другим, а сам похоже путашся. Никаких изменений при создании одного списка из другого не происходит. Мы просто получаем две структуры данных. Просто часть одной из низ является другой. Копирование при этом не происходит. И все это именно из-за того, что струкры данных неименяемые.
AF>Ну так вот — этот подход прекрасно работает со списками, немного похуже с деревьями, а вот с графами всё совсем плохо.
Никаких проблем с деревьями (которые являются чатными случаеями графов) нет и быть не может. Циклические графы тоже можно соорудить, хотя решение будет посложнее. Циклические ссылки прийдется хранить отдельно.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2 wrote: > Никаких проблем с деревьями (которые являются чатными случаеями графов) > нет и быть не может. Циклические графы тоже можно соорудить, хотя > решение будет посложнее. Циклические ссылки прийдется хранить отдельно.
Не просто сложнее, а на Ph.d в общем случае тянет, как минимум.
Здравствуйте, VladD2, Вы писали:
VD>Не так. Вся прелесть их в том, что при грамотном проектировании можно порождать икрементальные не изменяемые копии.
Если тебе нужно получить дерево, у которого вот у этого конкретного узла на одну ветку меньше, то неважно, каким образом это достигается. Или изменением изначального дерева, или созданием копии старого — с точки зрения конечного результата это эквивалентно. Важно то, что в случае дерева создать копию одного этого узла и прицепить ее к старому дереву, как со списками, не получится. Придется копировать еще все вышестоящие узлы вверх по дереву. А это — дополнительные расходы. С графами все еще хуже.
Нужно еще пояснить, что я имею в виду?
Здравствуйте, AndreiF, Вы писали:
AF>Если тебе нужно получить дерево, у которого вот у этого конкретного узла на одну ветку меньше, то неважно, каким образом это достигается. Или изменением изначального дерева, или созданием копии старого — с точки зрения конечного результата это эквивалентно. Важно то, что в случае дерева создать копию одного этого узла и прицепить ее к старому дереву, как со списками, не получится. Придется копировать еще все вышестоящие узлы вверх по дереву. А это — дополнительные расходы. С графами все еще хуже. AF>Нужно еще пояснить, что я имею в виду?
Зачем? Твоя ошибка не в теоритических знаниях, а в их неверной интрерпретации.
Ты не учитывашь, что обычно в сбалансированном дереве очень немного уровней. А так как в "функциональном" дереве пересоздавать нужно только элементы лежащие по пути к вставляемому, то расходы получаются в пределах разумного. Да, это менее эффектино чем хэш-таблица (еще бы алгорит ведь гогарифмический), но более чем достаточно для большинства задач.
Вот могжешь поглядеть на реальную реализацию. Она используется в самом компиляторе для хранения "отркытых" (using-ами) пространств имен: http://nemerle.org/svn/nemerle/trunk/lib/tree.n
Эффекнивность более чем приемлемая.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
В любом случае это эффективнее чем копировать все и всегда.
Из других вариантов я вижу только создание аналога СУБД с версионной системой (аля Оракл/Интербэйс) в памяти. Это задача намного сложнее и менее эффективнее. Плюс без блогировок необойтись.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Ты не учитывашь, что обычно в сбалансированном дереве очень немного уровней. А так как в "функциональном" дереве пересоздавать нужно только элементы лежащие по пути к вставляемому, то расходы получаются в пределах разумного. Да, это менее эффектино чем хэш-таблица (еще бы алгорит ведь гогарифмический), но более чем достаточно для большинства задач.
Это в случае дерева всё относительно просто, и можно обойтись сравнительно небольшой потерей эффективности. Если взять граф, то в общем случае решение будет крайне неэффективным. Потому что там придется клонировать все элементы, которые прямо или косвенно имеют ссылку на копируемый узел графа. А эти элементы надо еще найти, что в случае однонаправленного графа тоже очень затратно.
Пощупал я реализацию SXM от майкрософта. Впечатления, в общем то, не самые радужные.
Мануал очень неполный и с ошибками. Особенно порадовал раздел Advanced (заголовок, и больше ничего )
Для всех типов, которые участвуют в транзакции, они создают прокси-тип с помощью эмита, которые и замещает его во всех операциях в транзакции. Прокси-тип наследуется от замещаемого типа и перехватывает все обращения к геттерам/сеттерам (точнее, там делается override). Перехватчики геттеров и сеттеров как раз и отвечают за всю магию Проблема с созданием измененной копии объекта решается имеено так, как предполагал Аноним — когда геттер возвращает ссылку на объект, то сначала происходит проверка "а не был ли этот объект изменен в транзакции", и если был, то вместо оригинального объекта подсовывается его копия.
Понятно, что это накладывает ряд ограничений на типы — доступ ко всем полям должен быть только через свойства, а все свойства должны быть виртуальными, и никак иначе. Создание объектов — только через специальную фабрику. (Было бы намного лучше и правильнее использовать IL rewriting, но автор этого почему-то не сделал) Если где-то по ошибке произойдет прямой доступ к полю вместо инкапсулирующего его свойства, то вместо измененной копии объекта код получит его старый вариант. Всё, приплыли
Например, вот такой код — это замаскированная ошибка:
[Atomic]
static void Main(string[] args)
{
XObjectFactory factory = new XObjectFactory(typeof(Test));
Test t1 = (Test)factory.Create(null, 1);
Test t2 = (Test)factory.Create(t1, 1);
XStart start = new XStart(delegate (object[] a) { Test.TestMethod(t1, t2); return null; });
XAction.ManagerType = Type.GetType(DEFAULT_MANAGER);
XAction.Run(start);
Console.WriteLine(t2.Next.Value);
}
public class Test : ICloneable
{
public Test()
{
}
public Test(Test next, int value)
{
_next = next;
_value = value;
}
private Test _next;
public virtual Test Next
{
get { return _next; }
set { _next = value; }
}
private int _value;
public virtual int Value
{
get { return _value; }
set { _value = value; }
}
public object Clone()
{
Test res = new Test(this.Next, this.Value);
return res;
}
public static void TestMethod(Test t1, Test t2)
{
t1.Value = 2;
Console.WriteLine(t2.Next._value); // <<<< ошибка здесь, вместо 2 мы получим 1
//Console.WriteLine(t2.Next.Value); // Правильно - только так!
}
}
Поскольку мало кто привык использовать само-инкапсуляцию, можно предположить, что такие ошибки будут происходить часто А отлавливать их — не очень тривиальная задача.
Текущая версия очень старая, и похоже, что работа по проекту больше не ведется.
VladD2 wrote: > C>Не просто сложнее, а на Ph.d в общем случае тянет, как минимум. > А в чем проблема?
Тут где-то пробегала ссылка на работу по функциональному представлению
графов. Я вот найти ее не могу.
> Сам граф представляем в виде функционального дерева на подобии этого: > http://nemerle.org/svn/nemerle/trunk/lib/tree.n > а циклические связи в виде коллекций внутри элементов.
Циклические связи нужно хранить в виде карты узел-связь глобально для графа.
> В любом случае это эффективнее чем копировать все и всегда.
Фига. В куче алгоритмов на графах заметно повышается сложность. Чтобы
это обойти приходится использовать другие способы (разреженные матрицы
инцидентности, разбиение графа на кластеры и т.п.) — все имеют
определенные trade-off'ы.
> Из других вариантов я вижу только создание аналога СУБД с версионной > системой (аля Оракл/Интербэйс) в памяти. Это задача намного сложнее и > менее эффективнее. Плюс без блогировок необойтись.
Я это сделал в своем проекте Для ограниченного ряда частных случаев,
но все же. Блокировки — это не самая большая проблема, гораздо хуже то,
что оверхед по памяти и скорости получается достаточно заметным.
VladD2 wrote: > Ты не учитывашь, что обычно в сбалансированном дереве очень немного > уровней. А так как в "функциональном" дереве пересоздавать нужно только > элементы лежащие по пути к вставляемому, то расходы получаются в > пределах разумного. Да, это менее эффектино чем хэш-таблица (еще бы > алгорит ведь гогарифмический), но более чем достаточно для большинства > задач.
А ты представь, что у тебя граф треугольников для поверхности в
1000х1000 точек
Здравствуйте, AndreiF, Вы писали:
AF>Это в случае дерева всё относительно просто, и можно обойтись сравнительно небольшой потерей эффективности.
Ну, что же... уже сдвиг. Недвано по твоим словам и деревья было невозможно поддерживать.
AF> Если взять граф, то в общем случае решение будет крайне неэффективным.
Согласен, с графом будет сложнее. Но для многих задач более чем приемлемо. Темболее, что сероезная работа с графами редко встречается в прикладном коде.
AF> Потому что там придется клонировать все элементы, которые прямо или косвенно имеют ссылку на копируемый узел графа.
Это не так. Но откровенно говоря мне не нинтересно обсуждение этого вопроса.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Cyberax, Вы писали:
C>А ты представь, что у тебя граф треугольников для поверхности в C>1000х1000 точек
Всегда можно найти неприемлемые условия для любого решения. Однако это не делает решение невозможным в других случаях. Данная тема интересна скорее в прикладных системах (вроде учета на предприятиях) где сложных мат-вычислений нет. И решения вполне себе приемлемы.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Cyberax, Вы писали:
C>VladD2 wrote: >> C>Не просто сложнее, а на Ph.d в общем случае тянет, как минимум. >> А в чем проблема? C>Тут где-то пробегала ссылка на работу по функциональному представлению C>графов. Я вот найти ее не могу.
z00n wrote: > C> Фига. В куче алгоритмов на графах заметно повышается сложность. > log n — обычно это терпимо, зато бесплатная персистентность.
Ты забываешь про константу, которая перед log n (C*log n) — в реальных
ситуациях она часто очень даже важна. Кроме того, для графов в тысячу
узлов "log n" уже будет минимум 10, то есть квадратичные алгоритмы будут
работать в 100 раз медленнее.
palm mute wrote: > C>Задача простая: > C>1) Дан обычный линейный однонаправленый список. > C>2) Необходимо придумать механизм транзакций, чтобы можно было поменять > C>элемент из середины списка, не влияя на клиентов вне транзакции. > C>3) Этот механизм не должен приводить к копированию списка. > По моему скромному имху, "дан линейный однонаправленный список ..." — > это не задача. Задача — это, например, перевести деньги со счета на счет.
Да без проблем. Куда грузовичком документацию по проекту подвозить?
Просто модельные примеры, где у одного объекта вычитается сумма, а к
другому добавляется — это просто детский лепет.
У меня была реальная задача версирования графа треугольников
(триангуляция большой карты высот) — я самую ее суть написал.
> Теперь по сути вопроса. Если дан список неизменяемых значений (целых > чисел, например) — то задача некорректно поставлена, т.к. и без > транзакций нельзя поменять элемент в середине списка, не скопировав > элементы, ему предшествующие.
А ты представь, что объекты — изменяемые. Так как с иммутабельными
объектами — все просто.
) 
