Когда полезны строковые веса | When string weights are useful
Часто бывают случаи, когда нам нужно задать порядок на множестве объектов, у которых нет имманентного им приоритета. Например, список покупок — у абстрактного молока нет какой-то характеристики, по которой мы можем судить, что оно менее приоритетно хлеба. В таком случае объекты наделяются приоритетом снаружи, то есть, он условный. Обычно, программисты назначают тривиальный целочисленный приоритет: молоко — 1, хлеб — 2 и так далее.
Не стоит путать приоритет (вес) объекта с его идентификатором, который может быть инкрементальным целочисленным или, например, случайным UUID.
Проблема в том, что подобные множества объектов имеют свойство приобретать новые элементы, и это может доставить неудобства. Представим, что эти объекты где-то хранятся: в хешмапе (и по какой-то нелепой случайности, поле приоритета используется в вычислении хеша) или, самое неприятное, в базе данных. В какой-то момент обязательно появляется колбаса, которая чуть менее приоритетна хлеба, но более молока.
Ситуация стандартная, поведение тоже — переназначаем новые приоритеты: молоко-1, колбаса — 2, хлеб — 3. Такое переназначение может быть достаточно трудоёмким.
Часто встречаются предусмотрительные программисты, которые ожидая новых элементов, назначают приоритеты с запасом: молоко — 1, колбаса- 5, хлеб — 10. Это решение не очень элегантное, и запаса может не всегда хватить.
Другое стандартное поведение — ввести рациональные приоритеты: молоко — 1, колбаса — 1.5, хлеб — 2. Плюс такого подхода в том, что между двумя любыми элементами можно вставить сколько угодно новых. Минусы тоже есть — если заранее не подумать о рациональных приоритетах, то придётся менять тип данных столбца в базе. Ещё один плохой момент — нецелое число представляется в компьютере с округлением, что может привести к неточным расчётам.
Кстати, почему между любыми двумя рациональными числами можно вставить ещё одно? Потому что, дробная часть числа сравнивается не в числовом порядке (101>11), а в лексикографическом (0.101<0.11). Таким образом, если перейти от чисел к строкам, которые сравниваются лексикографически, то можно избавиться от проблем с возможным округлением.
Слово А меньше B в лексикографическом смысле, если либо А целиком является префиксом В, либо первый слева неравный символ у А меньше, чем у В.
Вторая часть определения даёт нам возможность сделать так, что между любыми двумя нашими словами можно было вставить третье. Для этого, последний символ любого слова должен быть таким, чтобы в алфавите присутствовали значения и больше, и меньше его. Рассмотрим небольшой алфавит из трёх элементов: =, < и >. В таком алфавите = как раз сгодится на роль последнего символа любого слова.
Представим, что у нас есть три объекта. Дадим им приоритеты:
Здесь, первая буква добавлена и для наглядности, и для практического удобства — например, это три разные категории товаров: мясное, мучное и молочное. Теперь начинаем добавлять новые объекты: менее приоритетная, чем хлеб булка — b<= (уменьшили последний символ, он получился крайний в алфавите, следовательно, добавили равно, чтобы не нарушать правило составления слов). Далее, пирожок между булкой и хлебом: берём хлеб, вычисляем приоритет меньший, получаем b<=, но такой уже присвоен булке, тогда вычисляем приоритет больше нее — b<>=. То есть алгоритм следующий: нужно вычислить приоритет больше, чем исходный — увеличиваем последний символ и добавляем средний символ алфавита, если увеличеный был крайним. Если полученный приоритет уже существует, то вычисляем приоритет меньший этого и так далее. Алгоритм для вычисления приоритета меньшего исходного аналогичен. Получаем такую картину:
Минусы этого подхода очевидны — чуть больше памяти на хранение и времени на сравнение. Минусы эти исключительно аппаратного рода, но есть мнение, что преждевременная оптимизация это корень всех зол, а удобство разработчика — благо.
На языке Raku такую генерацию можно написать следующим образом:
Объявляется функция next с тремя аргументами: изначальным словом $w и сетом уже имеющихся $set типа Set и параметром-ключом $prev, который используется, чтобы генерировать не следующее значение, а предыдущее (см. строку 12). Самые интересные строки это 4 и 5. Тут используется оператор замены s///. Берется изначальная $w, в ней ищется подстрока, которая удовлетворяет регулярному выражению между первыми косыми чертами (.$ — один символ перед концом текста) и заменяется за строку, между вторыми косыми чертами (вместо неё мы используем вычислимый блок, в котором берем нужную замену из массива). Стоит заменить, что оператор меняет исходную строку $w, вместо возвращения новой. Это позволяет использовать переменную $w в условии цикла в строке 5 (проверка, присутствует ли уже новое слово). Строки с 9 по 12 иллюстрируют использование функции.
English version