Ответ 1

@tmyklebu имеет ответ, но он никогда не попадал на линию перфорации: ответ на ваш вопрос "нет", если вы не готовы принять наименьшую длину ключа для n-1 бит для хранения n элементов.

Это означает, что общее хранилище ключей для n элементов - O (n ^ 2).

Существует теоретический аргумент "противник", который говорит, что независимо от того, какую схему для назначения ключей вы выбираете для базы данных из n элементов, я всегда могу придумать серию n-позиционных позиций ( "Переместить элемент k на позицию p." ), что заставит вас использовать ключ с n-1 битами. Или по расширению, если мы начнем с пустой базы данных, и вы дадите мне элементы для вставки, я могу выбрать последовательность позиций вставки, которые потребуют от вас использовать по крайней мере нулевые биты для первого, второго для второго и т.д. На неопределенный срок.

Edit

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

Ответ 2

Вы также можете интерпретировать опцию 3 как хранение позиций как строку неограниченной длины. Таким образом, вы не "закончите десятичные знаки" или что-нибудь в этом роде. Дайте первый элемент, скажем 'foo', положение 1. Рекурсивно разделяйте ваш юниверс на "материал, который меньше, чем foo", который получает префикс 0 и "материал, который больше, чем foo", который получает префикс 1.

Это отстой во многих отношениях, особенно в том, что для позиции объекта может потребоваться столько битов, сколько было бы сделано, как вы делали перемещения объекта.

Ответ 3

Я был очарован этим вопросом, поэтому начал работать над идеей. К сожалению, это сложно (вы, наверное, знали, что это будет), и у меня нет времени на все это. Я просто подумал, что поделюсь своим успехом.

Он основан на двусвязном списке, но с дополнительной информацией о бухгалтерии в каждом перемещенном элементе. С некоторыми умными трюками я подозреваю, что каждый из n элементов в наборе потребует меньше O (n) дополнительного пространства, даже в худшем случае, но у меня нет доказательств этого. Кроме того, потребуется дополнительное время для определения порядка просмотра.

Например, возьмите следующую начальную конфигурацию:

A  (-,B|0)
B  (A,C|0)
C  (B,D|0)
D  (C,E|0)
E  (D,-|0)

Порядок верхнего порядка выводится исключительно из метаданных, который состоит из последовательности состояний (predecessor,successor|timestamp) для каждого элемента.

При перемещении D между A и B вы нажимаете новое состояние (A,B|1) в начале своей последовательности со свежей меткой времени, которую вы получаете, увеличивая общий счетчик:

A  (-,B|0)
D  (A,B|1) (C,E|0)
B  (A,C|0)
C  (B,D|0)
E  (D,-|0)

Как вы видите, мы сохраняем старую информацию для подключения C к E.

Примерно, как вы получаете правильный порядок из метаданных:

• Вы сохраняете указатель на A.
• A соглашается, что у него нет предшественника. Поэтому вставьте A. Это приведет вас к B.
• B соглашается, что хочет быть преемником A. Поэтому вставьте B после A. Это приведет вас к C.
• C соглашается, что хочет быть преемником B. Поэтому вставьте C после B. Это приведет вас к D.
• D не согласен. Он хочет быть преемником A. Начните рекурсию, чтобы вставить ее и найти настоящего преемника:
  • D выигрывает от B, потому что он имеет более новую временную метку. Вставьте D после A. Это приведет вас к B.
  • B уже преемник D. Вернитесь в историю D, которая приведет вас к E.
  • E соглашается, что он хочет быть преемником D с отметкой времени 0. Так что верните E.
• Итак, преемник E. Вставьте E после C. Он говорит вам, что у него нет преемника. Вы закончили.

Это еще не совсем алгоритм, потому что он не охватывает все случаи. Например, когда вы перемещаете элемент вперед, а не назад. При перемещении B между D и E:

A  (-,B|0)
C  (B,D|0)
D  (C,E|0)
B  (D,E|1)(A,C|0)
E  (D,-|0)

Операция "move" - то же самое. Но алгоритм для получения правильного порядка немного отличается. Из A он будет запущен в B, который сможет получить от него реальный преемник C, но не имеет места для вставки B. Вы можете сохранить его в резерве как кандидат для вставки после D, где он в конечном итоге будет сопоставлять отметки времени с E для привилегии этой позиции.

Я написал код Angular.js на Plunker, который можно использовать в качестве отправной точки для реализации и тестирования этого алгоритма. Соответствующая функция называется findNext. Он еще ничего не делает.

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

Мне стыдно, что у меня нет времени, чтобы полностью это исправить. Это интересная проблема.

Удачи!

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

A  (-,B|0)
D  (A,B|1) (C,E|0)
B  (A,C|0)
C  (B,D|0)
E  (D,-|0)

сюда (затем переместил D между B и C):

A  (-,B|0)
B  (A,C|0)
D  (B,C|2) (C,E|0)
C  (B,D|0)
E  (D,-|0)

Мы можем отбросить конфигурацию (A,B|1), потому что A и B по-прежнему связаны сами по себе. Любое количество "несвязанных" движений может входить между ними, не изменяя этого.

Во-вторых, представьте, что в конечном итоге C и E удаляются друг от друга, поэтому конфигурация (C,E|0) может быть удалена при следующем перемещении D. Это сложнее доказать, однако.

Все это рассмотрено, я считаю, что есть хороший шанс, что для списка требуется меньше O(n+k) space (n) количество элементов в списке, k - количество операций) в худшем дело; особенно в среднем случае.

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

Ответ 4

Вы должны добавить еще одно разумное ограничение в свой список пожеланий:

• max O(log N) пробел для каждого элемента (N - общее количество элементов)

Например, решение связанного списка соответствует этому - вам нужно как минимум N возможных значений для указателя, поэтому указатель занимает пространство журнала N. Если у вас нет этого предела, тривиальное решение (растущие строки), уже упомянутое Lasse Karlsen и tmyklebu, является решением вашей проблемы, но память растет на один символ (в худшем случае) для каждой операции). Вам нужен какой-то предел, и это разумно.

Затем услышите ответ:

Нет, такого алгоритма нет.

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

• Абсолютная адресация - адрес каждого элемента задается некоторой абсолютной ссылкой (integer, float, string)
• относительная адресация - адрес каждого элемента указан относительно других элементов (например, связанный список, дерево и т.д.).

Чтобы опровергнуть существование алгоритма абсолютной адресации, легко. Просто возьмите 3 предмета, A, B, C и продолжайте перемещать последний между двумя первыми. Вы скоро исчерпаете возможные комбинации для адреса перемещенного элемента и потребуете больше бит. Вы нарушите ограничение ограниченного пространства.

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

Q.E.D.

Не увлекайтесь сложностью - он не работает

Теперь, когда мы (и вы) можем признать, что ваше желаемое решение не существует, почему вы усложняете свою жизнь сложным решением, которое не работает? Они не могут работать, как мы доказали выше. Думаю, мы здесь заблудились. Ребята здесь прилагали огромные усилия, чтобы закончить слишком сложные решения, которые даже хуже, чем предлагаемое самое простое решение:

• Гениальные рациональные числа - в его примере они вырастают на 4-6 бит, а не на 1 бит, что требуется по самому тривиальному алгоритму (описанному ниже). 9/14 имеет 4 + 4 = 8 бит, 19/21 имеет 5 + 5 = 10 бит, а итоговое число 65/84 имеет 7 + 7 = 14 бит! И если мы просто посмотрим на эти цифры, мы увидим, что 10/14 или 2/3 - намного лучшие решения. Можно легко доказать, что растущее строковое решение является непревзойденным, см. ниже.

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

Эти ребята очень умны, но, очевидно, не могут принести что-то разумное. Кто-то должен сказать им - СТОП, нет решения, и то, что вы делаете, просто не может быть лучше, чем самое тривиальное решение, которое вы боитесь предложить: -)

Вернитесь к квадрату, пройдите

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

1) Нарушить ограничение памяти

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

Решение этого - это решение, уже предложенное tmyklebu и упомянутое Лассе Карлсеном - растущие строки. Просто рассмотрите двоичные строки 0 и 1. У вас есть элементы A, B и C и перемещение C между A и B. Если между A и B нет пробела, то есть они выглядят

A  xxx0 
B  xxx1

Затем просто добавьте еще один бит для C:

A  xxx0
C  xxx01
B  xxx1

В худшем случае вам нужно 1 бит после каждой операции. Вы также можете работать с байтами, а не с битами. Затем в худшем случае вам нужно будет добавить один байт на каждые 8 ​​операций. Это все равно. И, нетрудно заметить, что это решение невозможно избить. Вы должны добавить хотя бы один бит, и вы не можете добавить меньше. Другими словами, независимо от того, как решение является сложным, оно не может быть лучше этого.

Плюсы:

• У вас есть одно обновление для каждого элемента.
• может сравнивать любые два элемента, но медленно

Минусы:

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

2) Нарушить одно измененное ограничение элемента

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

Они могут обрабатываться с 3-мя элементами, сбалансированными деревьями иногда требуется больше (когда необходимы операции с балансом), но по мере амортизации O(1) в длинном ряду операций количество модификаций на операцию является постоянным. В вашем случае я бы использовал решение дерева только в том случае, если вам нужно искать или сравнивать предметы. В противном случае решение связанных списков скалывается. Выбрасывать его только потому, что им нужны 3 операции вместо 1? C'mon:)

Плюсы:

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

Минусы:

• не может легко сравнить два элемента. Может легко сгенерировать порядок всех элементов, но с учетом двух элементов случайным образом, для сравнения их будет O(N) для списка и O(log N) для сбалансированных деревьев.
• 3 измененных элемента вместо 1 (... разрешая вам, сколько из них "con" )

3) Нарушить ограничение "без домашнего хозяйства"

Это решение с целыми числами и поплавками, которое лучше всего описано здесь Лассе Карлсен. Также сюда попадут решения из пункта 1). Ключевой вопрос уже упоминался Лассе:

Как часто будет проводиться ведение домашнего хозяйства?

Если вы будете использовать k -битные целые числа, то из оптимального состояния, когда элементы распределяются равномерно в целочисленном пространстве, ведение домашнего хозяйства должно выполняться каждые k - log N операции, в худшем случае. Затем вы можете использовать больше руд менее сложных алгоритмов, чтобы ограничить количество предметов, которые вы "домохозяйства".

Плюсы:

• оптимальное использование памяти
• быстрая работа
• может сравнивать любые два элемента
• один элемент, измененный за операцию

Минусы:

• уборка

Заключение - надежда никогда не умирает

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

Но надежда никогда не умрет. Когда я писал это, я понял, что будет ваше желаемое решение, если бы мы просто смогли спросить сервер! Разумеется, зависит от типа сервера, но на классическом SQL-сервере уже реализованы деревья/связанный список - для индексов. Сервер уже выполняет операции, такие как "переместить этот элемент до этого в дереве"!! Но сервер работает на основе данных, а не на основе нашего запроса. Если бы мы могли как-то попросить сервер сделать это без необходимости создавать извращенные, бесконечно растущие данные, это было бы вашим желаемым решением! Как я уже сказал, сервер уже делает это - решение остыло, но пока. Если вы можете написать свой собственный сервер, вы можете сделать это: -)

Ответ 5

Ваш лучший вариант - "Вариант 3", хотя "нецелое" необязательно должно быть задействовано.

"Нецелое число" может означать все, что имеет определенное определение точности, что означает:

• Целые числа (вы просто не используете 1, 2, 3 и т.д.)
• Строки (вы просто нажимаете на большее количество символов, чтобы обеспечить правильный порядок сортировки)
• Значения с плавающей запятой (добавление десятичных точек, несколько то же, что и строки)

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

Однако я думаю, что вам это не нужно.

Предположим, что вы первоначально выделили каждый 1000-й индекс для каждой строки, то есть у вас будет:

1000  A
2000  B
3000  C
4000  D
... and so on

Затем вы двигаетесь следующим образом:

• D между A и B (получает индекс 1500)
• C вверх между A и D (получает индекс 1250)
• B между A и C (получает индекс 1125)
• D между A и B (получает индекс 1062)
• C вверх между A и D (получает индекс 1031)
• B между A и C (получает индекс 1015)
• D между A и B (получает индекс 1007)
• C вверх между A и D (получает индекс 1004)
• B между A и C (получает индекс 1002)
• D между A и B (получает индекс 1001)

В этот момент список выглядит следующим образом:

1000  A
1001  D
1002  B
1004  C

Теперь, вы хотите переместить C вверх между A и D.

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

Вы можете пройти, обновив B, чтобы иметь номер 1003, пытаясь обновить минимальное количество строк, и таким образом вы получите:

1000  A
1001  C
1002  D
1003  B

но теперь, если вы хотите переместить B между A и C, вы собираетесь перенумеровать все, кроме A.

Вопрос в следующем: Насколько вероятно, что у вас есть эта патологическая последовательность событий?

Если ответ очень вероятен, тогда у вас будут проблемы, независимо от того, что вы делаете.

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

Ответ 6

Что делать, если вы сохраняете первоначальный заказ и не меняете его после сохранения его один раз, а затем сохраняете количество приращений в списке или вниз по списку?

Затем, перемещая что-то на 3 уровня, вы сохраните это действие только.

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

Вставка в первый раз:

ord1 | ord2 | value
-----+------+--------
1    | 0    | A
2    | 0    | B
3    | 0    | C
4    | 0    | D
5    | 0    | E
6    | 0    | F

Обновить порядок, переместить D до 2 уровней

ord1 | ord2 | value | ord1 + ord2
-----+------+-------+-------------
1    | 0    | A     | 1
2    | 0    | B     | 2
3    | 0    | C     | 3
4    | -2   | D     | 2
5    | 0    | E     | 5
6    | 0    | F     | 6

Порядок по ord1 + ord2

ord1 | ord2 | value | ord1 + ord2
-----+------+-------+-------------
1    | 0    | A     | 1
2    | 0    | B     | 2
4    | -2   | D     | 2
3    | 0    | C     | 3
5    | 0    | E     | 5
6    | 0    | F     | 6

Порядок по ord1 + ord2 ASC, ord2 ASC

ord1 | ord2 | value | ord1 + ord2
-----+------+-------+-------------
1    | 0    | A     | 1
4    | -2   | D     | 2
2    | 0    | B     | 2
3    | 0    | C     | 3
5    | 0    | E     | 5
6    | 0    | F     | 6

Переместить E на 4 уровня

ord1 | ord2 | value | ord1 + ord2
-----+------+-------+-------------
5    | -4   | E     | 1
1    | 0    | A     | 1
4    | -2   | D     | 2
2    | 0    | B     | 2
3    | 0    | C     | 3
6    | 0    | F     | 6

Что-то вроде относительного упорядочения, где ord1 - это абсолютный порядок, а ord2 - относительный порядок.

Наряду с тем же идеей просто сохранить историю движений и сортировку на основе этого.

Не тестировался, не пробовал, просто записал то, что я думал в этот момент, может быть, он может указать вам в каком-то направлении:)

Ответ 7

Я не уверен, если вы назовете это обман, но почему бы не создать отдельный ресурс списка страниц, который ссылается на ресурсы страницы? Если вы измените порядок страниц, вам не нужно обновлять ни одну из страниц, просто список, в котором хранится заказ, если идентификаторы.

Исходный список страниц

[ford, clarkson, captain_slow, audi, hamster, vw]

Обновить до

[ford, hamster, clarkson, captain_slow, audi, vw]

Оставьте ресурсы страницы нетронутыми.

Ответ 8

Вы всегда можете сохранить перестановку заказов отдельно как строку бит ln (num_records!)/ln (2) бит и выяснить, как преобразовать /CRUD сами, чтобы вам нужно было только обновить один бит для простых операций, если обновление 2/3 записей недостаточно для вас.

Ответ 9

Как насчет следующего очень простого алгоритма:

(допустим аналогию с номерами страниц в книге)

Если вы переместите страницу, чтобы стать "новой" страницей 3, у вас теперь есть "по крайней мере" одна страница 3, возможно, две или даже больше. Итак, какая из них "правильная" страница 3?

Решение: "самый новый". Таким образом, мы используем тот факт, что запись также имеет "обновленную дату/время", чтобы определить, кем является настоящая страница 3.

Если вам нужно представить весь список в правильном порядке, вам необходимо отсортировать его по двум клавишам: по одному для номера страницы и по одному для поля "обновленная дата/время".