Лексоранги — что это такое и как их использовать для эффективной сортировки списков

    В этой статье я расскажу, что такое Лексоранги, как ими пользуются в Jira, и как ими воспользовались мы для эффективной сортировки списков и перетаскивания элементов в нашем мобильном приложении.



    Перетаскивание элементов в списке – популярная фича в современных приложениях, наличие которой только порадует пользователей. Однако реализуя такой функционал нужно постараться не наступить на грабли плохой оптимизации: большое количество элементов, пересчет позиции каждый раз, а если в списке ещё и несколько секций – то при перетаскивании между секциями, скорее всего, нужно реализовать дополнительную логику. Как не получить по лбу, уменьшить количество вычислений, и как нам в этом помогут лексоранги – читайте под катом.

    Обозначим проблему


    Итак, Вы решили добавить в своё приложение возможность перетаскивать элементы. Значит, нужно как-то сортировать элементы, иначе никакого смысла в перетаскивании. И что первое приходит в голову?

    Позиции


    Самые обычные ничем не примечательные позиции. Те самые числа от 1 до бесконечности(не совсем). Работать с ними просто и удобно, элементы сортируются без проблем. На первый взгляд, всё хорошо. На столько хорошо, что для большинства приложений это – то, что нужно.

    Что же тогда не так с числовой позицией?

    Проблема таится в сопутствующих операциях. Нужно внедрить элемент между вторым и третьим элементами? Смещаем всё вперёд на один начиная с третьего элемента, не забыв при этом обновить данные в БД. Выполнение такой операции единожды не выглядит сложно, однако эта операция будет выполняться довольно часто.

    Еще одна проблемная операция – обновление данных на сервере. Обновили задачу – нужно послать апдейт всех затронутых задач на сервер. Сервер в свою очередь должен разослать этот апдейт всем, кто “подписан” на список задач. Чем чаще пользователи изменяют порядок задач в списке, тем больше данных нужно послать на сервер, и тем больше данных сервер должен разослать клиентам.

    Получается, при перетягивании одной задачи мы будем не только изменять позиции у большого количества элементов, но и отсылать их на сервер, который будет после рассылать их другим пользователям.

    Вывод: хочется что-то более оптимальное

    Варианты решений


    Когда мы в компании столкнулись с подобной проблемой, первым возможным решением стал следующий алгоритм: всем элементам мы расставим какие-нибудь стандартные позиции через равные интервалы(шаги). Так, первый элемент будет иметь позицию равной 1, а второй – равной 1000. Когда пользователь захочет перетащить что-нибудь между этими двумя элементами, мы посчитаем среднюю позицию – (1000 + 1) / 2 = ~500. И так далее, и так далее.

    Чем плох этот вариант, думаю, вы догадались сразу. Мы ограничены в количестве шагов, которые можно сделать. Т.е. между 1 и 1000 – 500. Между 1 и 500 – 250. Потом 125… и в конечном итоге места не останется. Увеличение шага эту проблему не решает.

    Может воспользуемся дробными числами?

    Нет, дробные числа не исправляют проблему, а лишь оттягивают момент её появления.

    Немного подумав и погуглив, мы наткнулись на доклад о том, как в Жире (Jira) используются лексоранги (Lexorank, доклад).
    Основаны они на трёх вещах:

    1 – строки легко сортировать в алфавитном порядке
    2 – между двумя строками можно найти среднюю строку (не всегда, и это уже не так просто)
    3 – нельзя найти среднюю? Воспользуемся ведром(звучит странно, да)

    С сортировкой всё понятно, идём сразу к пункту номер 2.

    Есть в английском алфавите буквы в «a» и «c», а между ними, очевидно, «b». Но как найти эту «b» математическим путём?

    Давайте просто отнимем от кода буквы «c» код буквы «a», получим 2 («c» = 143, «a» = 141). Осталось поделить результат пополам. Получили 1. И правда, если прибавить к коду «а» единицу, мы получим код буквы «b».

    Комбинация английских букв и называется лексорангом

    Ситуации, когда между двумя строками нет места, тут так же имеют место быть, и я уже писал, что для их решения используются вёдра.

    Ведро – это метка перед рангом, выглядит так: «0|aaa». Здесь 0 – номер ведра. Когда места не остаётся, элементы перекладываются из одного ведра в другое, а метки расставляются заново с сохранением порядка. Вот и вся магия!

    Как этим воспользовались мы
    Точно не сказано (скорее, просто мы не нашли) как легко и безболезненно найти среднюю строку между двумя. Поэтому мы напряглись и придумали вот что. Сразу окунаемся в пример.

    Возьмём две строки: «aa» и «cc» и найдём между ними среднюю.

    После посимвольного вычитания как выше мы получим число 11. Но что делать дальше? Вы можете подумать, что нужно просто добавить результат к строке «aa». Тут и правда получится строка «bb», находящаяся между «аа» и «сс», однако алгоритм будет неверным, и сейчас мы с вами увидим почему.

    Давайте подумаем, на что это похоже? «aa», «cc», «11». На какую-то систему счисления. На какую? А на 26-ричную! Почему? Потому что в английском алфавите 26 букв. Вот так вот.
    Надо перевести результат, «11», из 26-ричной системы счисления в привычную нам 10-ричную.

    Формула довольно простая:

    X = y0 + y1 * size + y2 * size^2… yn * size^(n-1)

    Здесь за size обозначен «размер» системы счисления (в данном случае size = 26)
    yn – n-ное число справа

    Запомним эту формулу как, например, формула 1, она нам ещё пригодится.

    Подставляем наши числа и вот что получается: 2 + 2 * 26 = 54. Теперь мы знаем, сколько символов между строкой «аа» и «сс». Но нам нужно взять среднюю между этими двумя. Делим 54 на 2, получаем 27. Остаётся только правильно добавить к кодам «аа» наш результат.
    Как это сделать? Вначале узнаем, сколько нужно прибавить к первому (правому) символу. Для этого получим остаток от деления 27 на 26. Получится 1. Прибавляем к «а» 1 – получится буква «b».

    Теперь надо подумать, как узнать, на сколько символов надо сдвинуть второй символ.
    Тут нам поможет следующая формула:

    X = Y / size^(n-1) % size

    По этой формуле мы можем узнать, сколько нужно добавить к определённому месту(символу, задаётся с помощью n).

    Подставляем всё туда, получаем(n = 2): (27/ 26) % 26 = 1. Прибавляем. Получаем финальный результат «bb».

    Реализовать алгоритм на каком-либо ЯП не так сложно, когда точно знаешь, как он работает. Ниже я добавил реализацию алгоритма на языке Dart(приложение, в котором возникла данная проблема, написано на Flutter'е).

    Наша реализация нахождения 'средней' строки
    String getRankBetween({@required String firstRank, @required String secondRank}) {
      assert(firstRank.compareTo(secondRank) < 0, "First position must be lower than second. Got firstRank $firstRank and second rank $secondRank");
    
      /// Make positions equal
      while (firstRank.length != secondRank.length) {
        if (firstRank.length > secondRank.length)
          secondRank += "a";
        else
          firstRank += "a";
      }
    
      var firstPositionCodes = [];
      firstPositionCodes.addAll(firstRank.codeUnits);
    
      var secondPositionCodes = [];
      secondPositionCodes.addAll(secondRank.codeUnits);
    
      var difference = 0;
    
      for (int index = firstPositionCodes.length - 1; index >= 0; index--) {
        /// Codes of the elements of positions
        var firstCode = firstPositionCodes[index];
        var secondCode = secondPositionCodes[index];
    
        /// i.e. ' a < b '
        if (secondCode < firstCode) {
          /// ALPHABET_SIZE = 26 for now
          secondCode += ALPHABET_SIZE;
          secondPositionCodes[index - 1] -= 1;
        }
    
        /// formula: x = a * size^0 + b * size^1 + c * size^2
        final powRes = pow(ALPHABET_SIZE, firstRank.length - index - 1);
        difference += (secondCode - firstCode) * powRes;
      }
    
      var newElement = "";
      if (difference <= 1) {
        /// add middle char from alphabet
        newElement = firstRank +
            String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
      } else {
        difference ~/= 2;
    
        var offset = 0;
        for (int index = 0; index < firstRank.length; index++) {
          /// formula: x = difference / (size^place - 1) % size;
          /// i.e. difference = 110, size = 10, we want place 2 (middle),
          /// then x = 100 / 10^(2 - 1) % 10 = 100 / 10 % 10 = 11 % 10 = 1
          final diffInSymbols = difference ~/ pow(ALPHABET_SIZE, index) % (ALPHABET_SIZE);
    
          var newElementCode = firstRank.codeUnitAt(
              secondRank.length - index - 1) + diffInSymbols + offset;
          offset = 0;
    
          /// if newElement is greater then 'z'
          if (newElementCode > 'z'.codeUnits.first) {
            offset++;
            newElementCode -= ALPHABET_SIZE;
          }
    
          newElement += String.fromCharCode(newElementCode);
        }
    
        newElement = newElement
            .split('')
            .reversed
            .join();
      }
    
      return newElement;
    }
    


    Но это ещё не всё


    Во всяком случае, для нас это было не всё. Мы добавляли данную фичу в уже выпущенное приложение, поэтому нужна была миграция. Написать миграции для SQL проблем не составляет, а вот посчитать стандартные ранги уже не так просто. Но, зная как находится средняя строка, сделать это становится не сложно. Алгоритм будет следующий:

    • задаём начало и конец промежутка(у нас это «ааа» и «zzz» соответственно)
    • считаем, сколько комбинаций разных символов между строками, тут нам поможет формула 1
    • теперь делим то, что получилось на максимально возможное количество элементов в списке
    • итак, у нас есть шаг, есть начальная позиция, остаётся только к начальной позиции прибавить шаг, получить ранг, потом к этому рангу прибавить шаг, получить новый ранг, потом снова прибавить шаг и так далее

    Всё так же на Dart'е. параметр forNumOfTasks отвечает за то, сколько позиций вы получите. Если вы проставляете позиции для списка, где сейчас всего три элемента, нет смысла рассчитывать позиции на весь список(на 50, 100 или ещё сколько-то)

    Наша реализация нахождения 'дефолтных' рангов
    /// modify field forNumOfTasks to get certain number of positions
    List‹String› getDefaultRank({int forNumOfTasks = TASK_FOR_PROJECT_LIMIT_TOTAL}) {
    	final startPos = START_POSITION;
    	final endPos = END_POSITION;
    
    	final startCode = startPos.codeUnits.first;
    	final endCode = endPos.codeUnits.first;
    
    	final diffInOneSymb = endCode - startCode;
    
    	/// x = a + b * size + c * size^2
    	final totalDiff = diffInOneSymb + diffInOneSymb * ALPHABET_SIZE + diffInOneSymb * ALPHABET_SIZE * ALPHABET_SIZE;
    	/// '~/' – div without remainder
    	final diffForOneItem = totalDiff ~/ (TASK_FOR_PROJECT_LIMIT_TOTAL + 1);
    
    	/// x = difference / size^(place - 1) % size
    	final List‹int› diffForSymbols = [
    		diffForOneItem % ALPHABET_SIZE,
    		diffForOneItem ~/ ALPHABET_SIZE % ALPHABET_SIZE,
    		diffForOneItem ~/ (pow(ALPHABET_SIZE, 2)) % ALPHABET_SIZE
    	];
    
    	List‹String› positions = [];
    	var lastAddedElement = startPos;
    	for (int ind = 0; ind < forNumOfTasks; ind++) {
    		var offset = 0;
    		var newElement = "";
    		for (int index = 0; index < 3; index++) {
    			final diffInSymbols = diffForSymbols[index];
    
    			var newElementCode = lastAddedElement.codeUnitAt(2 - index) + diffInSymbols;
    			if (offset != 0) {
    				newElementCode += 1;
    				offset = 0;
    			}
    			/// 'z' code is 122 if 'll be needed
    			if (newElementCode > 'z'.codeUnitAt(0)) {
    				offset += 1;
    				newElementCode -= ALPHABET_SIZE;
    			}
    			final symbol = String.fromCharCode(newElementCode);
    			newElement += symbol;
    		}
    
    		/// reverse element cuz we are calculating from the end
    		newElement = newElement.split('').reversed.join();
    		positions.add(newElement);
    		lastAddedElement = newElement;
    	}
    
    	positions.sort();
    	positions.forEach((p) => print(p));
    	return positions;
    }
    
    


    Фуууух, устали? Самое сложное уже позади, осталось совсем немного!

    Нам не очень понравилась идея с вёдрами. Объективно – она хороша. Но нам не нравилась сама идея наличия алгоритма «восстановления»: закончились позиции – восстанавливайся с помощью вёдер! Так что, никаких вёдер. Однако, ранги не бесконечные, а значит что-то придумать надо.

    И мы придумали

    Если места между строками не осталось, то мы решили просто добавить к нижней границе среднюю букву английского алфавита («n»). Т.е. если мы захотим всунуть элемент между «аа» и «аb», то получится «aa», «aan» и «ab». Благодаря тому, что строки сортируются поэлементно слева-направо, удлинение строки не испортит сортировку. Зато у нас появилось место для новых элементов, и это без каких-либо алгоритмов восстановления.

    Этот кусочек кода можно найти также и в алгоритме нахождения средней строки.

    Кусочек кода с добавлением 'среднего' символа
    if (difference <= 1) {
        /// add middle char from alphabet
        newElement = firstRank +
            String.fromCharCode('a'.codeUnits.first + ALPHABET_SIZE ~/ 2);
      }
    


    Резюме


    Лексоранги показались нам отличным инструментом индексации, использование которого оптимизирует работу с БД и сервером: при изменении порядка задач необходимо обновить только одну измененную задачу.

    Делитесь своим мнением по поводу лексорангов и тем, какие у Вас мысли по поводу решения подобных задач.

    Ну и для всех читателей Хабра предлагаем оценить результат, который у нас получился. А также забрать себе полезный список “Кодекс авторов Хабра”.

    Спасибо за внимание!
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 9

      0
      Так, первый элемент будет иметь позицию равной 1
      ошибка уже здесь: а что если переместить второй элемент, разместив его перед первым? отрицательное или нулевое значение?

      А что будет добавлено между «aa» и «aan»?
      Между «aan» и «ab»?
      Это же могло быть самой интересной частью статьи!
        0
        Так, первый элемент будет иметь позицию равной 1


        Это взято просто для примера. Даже если предположить, что индексы будут расставляться с каким-то шагом, скажем, в 500(500, 1000, 1500...), то при перетягивании второго элемента на место первого, алгоритм был бы таким же, как и описанный ниже: мы бы взяли начальную позицию(для лексорангов – «ааа», для чисел пускай будет 1) и индекс первого элемента(сейчас – 500) и посчитали бы среднее((1 + 500) / 2 = 250).

        А что будет добавлено между «aa» и «aan»?


        Длинна первой строки меньше, чем длинна второй, поэтому их необходимо выровнять. Это можно увидеть под спойлером «Наша реализация нахождения 'средней' строки» под комментарием «Make positions equal».
        После выравнивания получится две строки: «aaa» и «aan», между которыми и будет найдена средняя.

        PS. Возможно не правильно понял вопрос. Начало раздела
        Варианты решений

        может помочь разобраться лучше
        0
        Спасибо за статью.

        Скажите, пожалуйста, рассматривался ли связный список для хранения данных? И если да, то почему не подошёл?

        Он позволяет за константное время добавлять/перемещать/удалять элементы. Соответственно, объем данных, отправляемых на сервер тоже константное: не зависит от старой или новой позиций элемента.
          0
          Нет, связный список мы не рассматривали, потому что «позиции» были более привычны.

          Однако идея интересная: каждый элемент списка мог бы указывать на последующий(на id). При добавлении или удалении нам бы нужно было лишь добавить/переставить указатели на элементы. При перемещении элемента нам бы нужно было лишь обновить указатели на элементы.
          Однако при перемещении пришлось бы обновить три элемента.
          Вот пример:
          a -> b -> c -> d ->…
          Мы хотим переместить элемент c между a и b. Для этого нам бы потребовалось выполнить следующие шаги:
          a x b x c x d ->… – удаляем связи элементов(х – нет связи)
          a -> c -> b -> d ->… – перестраиваем связи.
          Можно заметить, что помимо элемента c изменились ещё и элементы a и b – у них изменился указатель на следующий элемент. Для сохранения порядка элементов это необходимо зафиксировать в бд/на сервере.
          Также сходу не могу сказать, как бы тогда пришлось подготавливать данные: сначала загрузить данные из бд, а с помощью циклов расставить их в нужном порядке(в соответствии с указателем на следующий), или рекурсивно/последовательно загружать из бд по одной?
            0

            Мне кажется, что будет эффективнее выгружать все сразу в память, а не ходить в БД за каждым элементом. Особенно, для больших списков.


            Нашел такую реализацию:
            https://gist.github.com/errzey/1237932
            После выгрузки всего списка из БД, он перекладывается в хеш-таблицу.
            Как я понимаю, сложность этой операции будет О(n) — один цикл по всем записям.
            Зато затем при отображении списка поиск каждого следующего элемента будет занимать О(1).


            В целом, кажется, что этот подход может иметь место, особенно на больших списках, где весь этот оверхед не будет лишним.

            0

            Подскажите пожалуйста, а как при такой схеме хранения данных получить сортированный список средствами sql от первого до последнего элемента?

              0
              В нашем случае в таблице задач есть колонка – lexorank. Соответственно, с помощью ORDER BY в SELECT запросе можно отсортировать по этой колонке.
              Пример:
              SELECT * from Tasks ORDER BY lexorank
              При таком запросе данные будут отсортированы в порядке возрастания ранга: от первого ранга до последнего(прим. от «aaa» до «zzz»)
                0

                В таком случае, если пользователь будет часто переносить элемент в начало списка, то появятся метки вида aaaaaaaaaaa.

                  0
                  В этом и суть алгоритма: мы отказались от «восстанавливающей» части в пользу динамичности, так сказать
                  Да, метки могут достигать большой длинны, однако если пользователь перенесёт задачу с меткой «aaaaaaaaaaa» куда-нибудь, пускай, в центр, то, скорее всего, метка станет заметно меньше

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое