моя модель либы как раз отличается от твоей тем, что она содержит много спец. функций, которые занимаются тока тем, чем их наделили - поэтому запросы строятся под конкретную задачу. у тебя универсальнее, у меня (должно быть) - быстрее kvf77, PHP Club форумы |
Насчет скорости - вполне можно сравнить. У меня там есть автоматические тесты, можно их переделать и запустить на твоем классе.
Насчет универсальности - она не на пустом месте возникла. Исходная задача состояла в том, что для увеличения скорости обновления дерева при перемещении нескольких узлов, можно было бы обновлять дерево одним запросом. При обновлении нескольикими запросами может оказаться, что одни и те же узлы дерева обновляются несколько раз; при обновлении одним запросом они обновляются один раз - за счет этого и достигается ускорение. А так же (возможно, даже, в основном) за счет того, что индексы очень часто не используются и поэтому осуществляется проход по всему дереву. При обновлении несколькими запросами осуществляется несколько проходов.
Процедура построения запроса для переноса нескольких узлов - это довольно сложная процедура, как бы мы ни фиксировали переносимые узлы. Единственное отличие при переносе в разных направлениях (братьями, детьми, справа, слева и т.п.) состоит в том, что нужно пересчитывать дерево на разных интервалах. Определение этих интервалов - задача несравнимо более простая, чем определение пересечения интервалов: как дерево нужно было пересчитать после перемещения первой вершины и как его нужно пересчитать, если при этом переместить еще и вторую вершину. Универсальность возникла исключительно в связи с простотой задачи определения интервалов пересчета для каждого конкретного варианта перемещения.
~~~~~ 2 Сен 2005, 16:03 ~~~~~
да, я о том же - вот я как раз создал библиотеку, где каждая функция делает тока одно (максимум 2) дела. Соответственно, рассчеты запросов произведены заранее - функции подставляют в них лишь нужные данные. Это позволяет работать много быстрее, мне кажется. Вот щас выложу новую версию - если есть желание - глянь на функцию ChangePositionAll - там 4 заранее подготовленных запроса. Да, мы увеличили несколько код класса, зато скорость по идее должна также возрасти значительно, поскольку функции надо лишь выбрать нужный запрос и подставить в него данные, не требующие особых вычислений. Я пошел в своей либе по этому пути. kvf77, PHP Club форумы |
Я уже видел классы, в которых перемещение делается таким способом. Я сам с этого начинал. Собственно, все с этого начинают. Большинство на этом и заканчивают.
Насколько я понял, особенность твоей либы - не в возможности перемещения (в той или иной мере это позволяют делать практически все известные мне библиотеки для работы с деревьями), а в том, что она поддерживает несколько разных баз данных.
О скорости мы не можем ничего говорить, пока у нас нет экспериментов. Мне кажется (да, собственно, об этом и в документации по MySQL написано), что основной тормоз возникает при обращении к винчестеру. Операции построения запроса на обновление дерева не обращаются к винчестеру, хоть они реализованы как у тебя (специально для конкретных типов перемещения и для перемещения одной вершины), хоть - как у меня (универсально и с возможностью перемещения нескольких вершин). Если речь идет об одной вершине, то виртуально я могу предположить, что по времени отличие будет не слишком большое. На современных машинах, тем более с учетом того, что операция перемещения выполняется крайне редко - это вообще просто никакое время.
Если же речь идет о перемещении большого количества вершин, то тут другое дело - у меня уже есть некоторые экспериментальные данные. И эти эксперименты показывают, что при перемещении одним запросом небольшого количества вершин мы получаем значительное ускорение. При перемещении же большого числа вершин выгоднее обновлять дерево не одним запросом, а несколькими запросами - каждый запрос для перемещения нескольких вершин. Это связано с тем, что время работы разработанного мной алгоритма построения sql-запроса для перемещения нескольких вершин одним запросом зависит от количества интервалов, на которых следует произвести пересчет.
На вскидку (очень приблизительно, мог некоторые важные детали не учесть) я мог бы предложить формулу типа
T=O(n^2),
где
n - это количество интервалов
Количество интервалов целиком и полностью зависит от того, при какой стркутуре дерева какие вершины куда мы перемещаем. В лучшем случае (когда перемещаются смежные братья в одном направлении) это будет два интервала для любого количества вершин. В среднем случае (когда перемещаемые вершины не являются детьми-родителями друг друга) количество интервалов оценивается по формуле
n=O(2*x),
где
х - это количество перемещаемых вершин,
в худшем случае (когда каждая следующая перемещаемая вершина в исходном дереве является родителем предыдущей перемещенной вершины) количество интервалов можно оценить по формуле
n=O(x^2)
