Xpoint
   [напомнить пароль]

FLOAT в качестве индекса сортировки

Метки: [без меток]
2005-09-25 23:25:03 [обр] Алексей Пешков(0/19)[досье]

Есть упорядоченное множество (список), элементы которого решено хранить в таблице БД. Появилась идея использовать в качестве внутреннего суррогатного ключа упорядочивания значения типа FLOAT.

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

Преимущество очевидно: необходимость полной переиндексации (при превышении разрешающей способности компьютерной реализации "плавающей точки" для бесконечного множества рациональных чисел) достаточно редка.

Существуют ли причины отказаться от такого решения?

спустя 1 час [обр] Владимир Палант(27/4445)[досье]
Причины существуют и заложены они в природе чисел с плавающей запятой — их точность ограничена. С таким же успехом вы можете взять целые числа и нумеровать с шагом 256, это гарантирует вам минимум в 16 миллионов записей и 8 вставок без переиндексации. А вот с числами с плавающей запятой дать какую-либо гарантию вам будет сложно.
спустя 17 часов [обр] Robinzon(0/14)[досье]

Владимир Палант[досье]Алексей Пешков[досье]
А мне идея кажется интересной, не хватает информации о количестве максимальном знаков после запятой, ну и вообще характеристик вашего float.

8 вставок

IMHO мало, не может конкурировать с float, ибо даже для 4-х знаков после запятой имеем заметно больше 8-ми вставок. Можно увеличивать шаг, но это может уперется в overhead самого id из-за слишком большого шага.

А вот с числами с плавающей запятой дать какую-либо гарантию вам будет сложно.

Разве сложно вычислить максимальное количество вставок, зная ограничения на мантису и порядок??

спустя 14 минут [обр] Владимир Палант(27/4445)[досье]
Вычислить сложно, ограничения зависят от размера чисел. Как и количество возможных вставок. То есть, в начале таблицы (где индексы небольшие) мы сможем сделать много вставок, а в конце — возможно, что ни одной. А в среднем получается ровно то же самое, что и с обыкновенными целыми числами, битов ведь столько же. Так что лучше сразу использовать целые числа. Если 8 вставок (это минимум, максимум 2^8 = 256) недостаточно, а записей так уж много не предвидится — можно выделить больше битов под вставки. Я, кстати, для 32-битных чисел считал, а ведь можно и 64-битные использовать.
спустя 20 минут [обр] Алексей В. Иванов(3/2861)[досье]
С 64-разрядными проблема их рассчитывать/получать в языке. Тот же PHP и Perl под Win с 32-разрядными числами работает.
спустя 13 минут [обр] Robinzon(0/14)[досье]
То есть, в начале таблицы (где индексы небольшие) мы сможем сделать много вставок, а в конце — возможно, что ни одной

Туплю, наверное, но объясните pls почему?
Я исхожу из предположения что float определен как число, грубо говоря вида "XXXXX.XXXXX", т.е. количество знаков дробной части есть константа. Исходя из этого вроде бы нет разницы где делается вставка.
Хотя может возможно разница в понимании задачи. Я понял так: дан список из N элементов.
Каждому n из N ставим в соответствие некоторое число типа float - видимо через равные промежутки, т.е. шаг = (max float size)/(N-1). Ну а выгода подхода в том, что операции вставки в такой список будут дешевые.

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

спустя 36 минут [обр] Старынин Валерий(0/57)[досье]
Robinzon[досье] Нет. Сравните http://en.wikipedia.org/wiki/Floating_point и http://en.wikipedia.org/wiki/Fixed-point_arithmetic. Где-то я видел то-же описание на русском. Может, кто-то знает.
спустя 1 минуту [обр] Старынин Валерий(0/57)[досье]
спустя 1 час 21 минуту [обр] VIG(38/839)[досье]

Числа с плавающей точкой позволят лишь (и то под вопросом) отсрочить проблему, но не решить её.

Пример: в БД всего две записи, с индексами 1 и 2, и нам нужно вставить между ними еще 100 (но мы не знаем, что их будет 100 и вынуждены вставлять по одной). Первая вставленная запись будет иметь индекс 1.5, вторая — 1.75, третья — 1.875 и так далее. Очень скоро точности представления чисел с плаваюшей точкой не хватит ...

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

спустя 2 часа 16 минут [обр] Старынин Валерий(0/57)[досье]
Предлагаю: делать упорядочивание по cron'у. В момент наименьшей загрузки. Или при реальной необходимости, когда вставить нельзя. Но в последнем случае можно делат не полное, а частичное переупорядочивание.
спустя 5 минут [обр] Закиров Руслан(0/343)[досье]

Robinzon[досье] С учетом FLOAT в качестве индекса сортировки (310937) получается, что Ваш, вариант - это тоже самое, что и вариант Владимира, просто в варианте Владимира заведомо предполагается, что 8 младших бит в числе - дробная часть в вашем варианте.

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

спустя 1 час 28 минут [обр] Владимир Палант(27/4445)[досье]

Алексей В. Иванов[досье]
А с ними не обязательно работать в языке. Если уж совсем никак не получается, то можно сделать составной индекс из двух 32-битных чисел — первое "настоящий" индекс, а второе для вставок. Но вообще-то как раз в базе можно хранить 64-битное число и только в SELECT'ах разбивать его на два 32-битных, благо все нужные операции в SQL есть.

Но это не важно, а важно другое — возможность вставлять записи определяется лишь количеством битов в поле индекса. Числа с плавающей запятой лишь распределяют то же количество битов иначе, что делает их менее предсказуемыми. То есть, на самом деле они всё ещё предсказуемы, конечно, и при желании можно увеличивать индекс каждой следующей записи так, что количество возможных вставок между записями будет констатно. Но это уже далеко не тривиально, а главное — непонятно, зачем всё это.

спустя 1 час 19 минут [обр] Алексей Пешков(0/19)[досье]

Мне казалось, что применение FLOAT позволяет проще решать проблему "интеллектуального деления интервала". Теперь понял, что способ представления числа для ранжирования несущественен.

Давайте отбросим вопрос плавающих и целых чисел, и перейдем к задаче, ради которой я открыл тему:

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

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

Можно, к примеру, использовать соотношение (x[+2]-x[+1])/(x[-2]-x[-1]) как делитель интервала: если между двумя ближайшими левыми соседями в два раза больше пространства, чем между правыми, то и отрезок делим в соотношении 1:2 в пользу правого.

Можно придумать еще множество алгоритмов выделения пространства.
Может кто-то знает результаты научных работ решения этой задачи?

спустя 9 часов [обр] Robinzon(0/14)[досье]

VIG[досье]

Числа с плавающей точкой позволят лишь (и то под вопросом) отсрочить проблему, но не решить её.

It goest without saying

спустя 15 минут [обр] Robinzon(0/14)[досье]

Алексей Пешков[досье]

Можно придумать еще множество алгоритмов выделения пространства.
Может кто-то знает результаты научных работ решения этой задачи?

B-дерево не желаете попробывать? -)

А вот еще фантазия на тему - можно попробывать использовать строки вместо чисел. Как Вам такое? Гибкость практически бесконечна (ну, если CLOB'ом хранить, но индексировать тогда нельзя; впрочем не обязательно CLOB, ибо в некоторых БД можно хранить достаточно большие значения в текстовых полях). Причем тут опять-таки есть где разгуляться - можно хранить теже числа просто как строки, можно к множеству цифр еще и букв добавить и перейти например на 20-ричную систему счисления.

спустя 8 дней [обр] vvvua[досье]
А для чего, собственно, индекс? Почему не подходят индексы самой базы данных?
Просто есть индексы с возможностью задания диапазона и без нее.
Ваш способ вроде-бы дает возможность задания диапазона. А это нужно?
Есть способ реализации двусвязного списка. Добавление происходит в нужную позицию с учетом сортировки. Поиск - что-то типа бинароного поиска. Довольно быстрый.
Подобные дела изложены в Кнуте, том 3, кажется. Если надо - могу выслать электронную версию, или выложить в инет на пару дней.
спустя 4 часа 54 минуты [обр] Алексей Пешков(0/19)[досье]

Спасибо за Кнута, но, пожалуй, найду бумажного.

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

спустя 13 часов [обр] vvvua[досье]
Это какая-то научная работа? Просто это довольно сложно... Мне для нормальной работы такой проги месяц писать надо. Это только чтобы запустилось.
Если проект практический - лучше использовать встроенные индексы в базу данных.
спустя 1 час 18 минут [обр] GRAy(0/259)[досье]
vvvua[досье] Вы не поняли. Речь идёт о реализации механизма генерации значения для ключевого поля - т.е. индекса элемента в множестве, а не индексирования уже имеющегося набора.
спустя 33 минуты [обр] vvvua[досье]
Генерация идекса по данным практически всегда добавление данных последовательно с присвоением нового позиционного ключа. Так что эти механизмы эквивалентны в 80% случаев.
спустя 7 минут [обр] GRAy(0/259)[досье]
vvvua[досье] Самое важное отличие (которое собственно и мешает) первого от второго - неопределимое заранее кол-во элементов. Строя индекс - ничего не стоит заранее посчитать кол-во элементов в множестве. При генерации вы никогда не знаете, какой элемент обрабатываете - первый, второй, последний. Поэтому даже при использовании бинарного дерева, нельзя гарантировать что индекс не выродится и его не придётся перетряхивать.
спустя 1 час 58 минут [обр] vvvua[досье]
Пока не видел врождения. Запас берут большой.
Кроме того, для исключения используют сбалансированые бинарные деревья.
Муть жуткая.
спустя 1 час 17 минут [обр] GRAy(0/259)[досье]
vvvua[досье] Процесс балансировки - это и есть перетряхивание индекса.
спустя 18 часов [обр] vvvua[досье]
Я это уже не помню. Редко занимался этим.
Так как пока не понял, чем не подходят способы самой базы (кстати, какой?) перехожу в режим наблюдателя.
Powered by POEM™ Engine Copyright © 2002-2005