Комментарии 9
Так, первый элемент будет иметь позицию равной 1ошибка уже здесь: а что если переместить второй элемент, разместив его перед первым? отрицательное или нулевое значение?
А что будет добавлено между «aa» и «aan»?
Между «aan» и «ab»?
Это же могло быть самой интересной частью статьи!
Так, первый элемент будет иметь позицию равной 1
Это взято просто для примера. Даже если предположить, что индексы будут расставляться с каким-то шагом, скажем, в 500(500, 1000, 1500...), то при перетягивании второго элемента на место первого, алгоритм был бы таким же, как и описанный ниже: мы бы взяли начальную позицию(для лексорангов – «ааа», для чисел пускай будет 1) и индекс первого элемента(сейчас – 500) и посчитали бы среднее((1 + 500) / 2 = 250).
А что будет добавлено между «aa» и «aan»?
Длинна первой строки меньше, чем длинна второй, поэтому их необходимо выровнять. Это можно увидеть под спойлером «Наша реализация нахождения 'средней' строки» под комментарием «Make positions equal».
После выравнивания получится две строки: «aaa» и «aan», между которыми и будет найдена средняя.
PS. Возможно не правильно понял вопрос. Начало раздела
Варианты решений
может помочь разобраться лучше
Спасибо за статью.
Скажите, пожалуйста, рассматривался ли связный список для хранения данных? И если да, то почему не подошёл?
Он позволяет за константное время добавлять/перемещать/удалять элементы. Соответственно, объем данных, отправляемых на сервер тоже константное: не зависит от старой или новой позиций элемента.
Скажите, пожалуйста, рассматривался ли связный список для хранения данных? И если да, то почему не подошёл?
Он позволяет за константное время добавлять/перемещать/удалять элементы. Соответственно, объем данных, отправляемых на сервер тоже константное: не зависит от старой или новой позиций элемента.
Нет, связный список мы не рассматривали, потому что «позиции» были более привычны.
Однако идея интересная: каждый элемент списка мог бы указывать на последующий(на id). При добавлении или удалении нам бы нужно было лишь добавить/переставить указатели на элементы. При перемещении элемента нам бы нужно было лишь обновить указатели на элементы.
Однако при перемещении пришлось бы обновить три элемента.
Вот пример:
a -> b -> c -> d ->…
Мы хотим переместить элемент c между a и b. Для этого нам бы потребовалось выполнить следующие шаги:
a x b x c x d ->… – удаляем связи элементов(х – нет связи)
a -> c -> b -> d ->… – перестраиваем связи.
Можно заметить, что помимо элемента c изменились ещё и элементы a и b – у них изменился указатель на следующий элемент. Для сохранения порядка элементов это необходимо зафиксировать в бд/на сервере.
Также сходу не могу сказать, как бы тогда пришлось подготавливать данные: сначала загрузить данные из бд, а с помощью циклов расставить их в нужном порядке(в соответствии с указателем на следующий), или рекурсивно/последовательно загружать из бд по одной?
Однако идея интересная: каждый элемент списка мог бы указывать на последующий(на id). При добавлении или удалении нам бы нужно было лишь добавить/переставить указатели на элементы. При перемещении элемента нам бы нужно было лишь обновить указатели на элементы.
Однако при перемещении пришлось бы обновить три элемента.
Вот пример:
a -> b -> c -> d ->…
Мы хотим переместить элемент c между a и b. Для этого нам бы потребовалось выполнить следующие шаги:
a x b x c x d ->… – удаляем связи элементов(х – нет связи)
a -> c -> b -> d ->… – перестраиваем связи.
Можно заметить, что помимо элемента c изменились ещё и элементы a и b – у них изменился указатель на следующий элемент. Для сохранения порядка элементов это необходимо зафиксировать в бд/на сервере.
Также сходу не могу сказать, как бы тогда пришлось подготавливать данные: сначала загрузить данные из бд, а с помощью циклов расставить их в нужном порядке(в соответствии с указателем на следующий), или рекурсивно/последовательно загружать из бд по одной?
Мне кажется, что будет эффективнее выгружать все сразу в память, а не ходить в БД за каждым элементом. Особенно, для больших списков.
Нашел такую реализацию:
https://gist.github.com/errzey/1237932
После выгрузки всего списка из БД, он перекладывается в хеш-таблицу.
Как я понимаю, сложность этой операции будет О(n) — один цикл по всем записям.
Зато затем при отображении списка поиск каждого следующего элемента будет занимать О(1).
В целом, кажется, что этот подход может иметь место, особенно на больших списках, где весь этот оверхед не будет лишним.
Подскажите пожалуйста, а как при такой схеме хранения данных получить сортированный список средствами sql от первого до последнего элемента?
В нашем случае в таблице задач есть колонка – lexorank. Соответственно, с помощью ORDER BY в SELECT запросе можно отсортировать по этой колонке.
Пример:
SELECT * from Tasks ORDER BY lexorank
При таком запросе данные будут отсортированы в порядке возрастания ранга: от первого ранга до последнего(прим. от «aaa» до «zzz»)
Пример:
SELECT * from Tasks ORDER BY lexorank
При таком запросе данные будут отсортированы в порядке возрастания ранга: от первого ранга до последнего(прим. от «aaa» до «zzz»)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Лексоранги — что это такое и как их использовать для эффективной сортировки списков