#algorithm #sorting
#алгоритм #сортировка
Вопрос:
Я ищу схему назначения ключей строкам в таблице, которая позволяла бы перемещать строки и назначать новые местоположения в таблице без необходимости перенумеровывать всю таблицу.
Что-то вроде наличия ключей 1, 2, 3, 4, затем перемещения строки «2» между 3 и 4 и последующего переименования ее в «3.5» (таким образом, в итоге получается 1, 3, 3.5, 4). Но схема должна быть «бесконечно» расширяемой (разрешающей по крайней мере несколько тысяч «случайных» перемещений строк, прежде чем обычно будет необходимо «нормализовать» ключи, и в худшем (наиболее патологическом) случае допускающей 25-50 таких перемещений).).
И созданные ключи должны быть легко отсортированы, в идеале я бы хотел, чтобы они были «естественным» образом упорядочены для запроса к базе данных (предположим, SQLite).
Есть идеи?
Комментарии:
1. Для одноразового использования я остановился на чем-то вроде схемы бедняка с плавающей запятой: используйте 64-разрядное число, выделите 20 или около того битов слева в качестве приращений целого числа, а затем управляйте правыми битами как дробью. При вставке значения между двумя другими, выберите значение на полпути между ними (т. Е. их среднее значение).
2. Это должно допускать минимум 44 вставки в наиболее патологическом случае и тысячи в «среднем» случае.
3. Просто любопытно, что бы вы ни использовали, не поддерживает значения с плавающей точкой?
Ответ №1:
Эта проблема напоминает мне проблему с нумерацией строк, когда человек писал код на BASIC. Что большинство людей сделало в этой ситуации, так это сделало обоснованное предположение о том, сколько строк может быть вставлено между двумя строками. Тогда это предположение будет расстоянием между этими строками. Итак, если вы думаете, что у вас может быть 2000 вставок между двумя элементами, тогда вы могли бы сделать так, чтобы элемент1 имел ключ 2000, а элемент2 — ключ 4000. Затем, если вы хотите поместить элемент между элементом1 или элементом2, вы либо наивно разделяете разницу (3000), либо, если у вас есть некоторая интуиция относительно того, сколько элементов будет с каждой стороны элемента 3, тогда вы могли бы немного взвесить его (например, 3500 вместо 3000).
Другой альтернативой (на самом деле это то же самое, но вы используете другую систему нумерации) является использование чисел с плавающей запятой, от которых, я полагаю, вы ускользнули. Между 1 и 2 будет 1,5. Между 1,5 и 2 будет 1,75. Между 1.5 и 1.75 будет 1.625 и т.д.
Я бы не рекомендовал использовать ключ, который является строкой. Лучше придерживаться цифровых клавиш, и, кроме того, вероятно, лучше использовать ключи целочисленного типа, а не с плавающей запятой, если вы можете помочь этому.
Комментарии:
1. Да, то, что я реализовал до сих пор, — это 64-разрядный int, первые 20 бит которого являются «целочисленной» частью, а остальные — «дробью». Таким образом, добавление в нижнюю часть списка увеличивает 19-й бит слева. Чтобы вставить между двумя строками, сделайте новый ключ средним из двух значений заключающего ключа. При необходимости схему можно расширить до 2-3 64-разрядных значений, но нет очевидного способа просто сделать ее саморасширяющейся.
2. На самом деле, это, вероятно, можно было бы сделать саморасширяющимся, используя «большой двоичный объект» для данных. Тогда порядок сортировки был бы основан на memcmp (по крайней мере, в SQLite), так что это было бы эквивалентно использованию бесконечно длинного целого числа. Автоматического расширения влево, конечно, не было бы, но если допустить, скажем, 6 байт слева от «десятичной точки», то можно было бы перечислить звезды во Вселенной.
Ответ №2:
Концептуально вы могли бы рассматривать свою таблицу как связанный список. Создайте таблицу с уникальным идентификатором, ключом и его следующим узлом и любыми другими данными, которые вы хотите. Просто вставляйте элементы последовательно, когда вам нужно поместить новый элемент между ними, просто поменяйте местами значения ключей и связанные родительские узлы. Значения ключа не будут оставаться согласованными, но именно для этого и нужен дополнительный уникальный идентификатор, и это отлично работает и для упорядочивания по ключу.
Действительно, поскольку у вас есть порядок, уже указанный ключом, вам даже не нужен «следующий узел». Ваша схема, описанная выше, должна работать нормально, если вы переименуете ключи других узлов в дополнение к тому, который вы переместили — т. Е. 2 и 3 поменяют местами значения ключей.