Как быстро прибегнуть к списку только с одним измененным значением?

Question

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

Какой алгоритм сортировки или «трюки» можно использовать для очень быстрого сортировки этого списка, учитывая, что он выпадает из сортировки только по одному элементу за раз?

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

Я использую Scala для этого, но любые общие советы или указатели были бы полезными.

Answer 1

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

Answer 2

Перемещение несортированный элемент влево или вправо в списке кажется оптимальным решением

Answer 3

Если список отсортирован, вы можете просто удалить элемент, который вы собираетесь изменить из списка, и после его изменения, вы могли бы «двоично-вставить» его, нет? Это займет в среднем количество шагов log (n).

Если вы можете, переключитесь с массива на java.util.TreeMap: как удаление, так и вставка будут выполняться в режиме log (n): это будет быстрее, чем ваш O (1) доступ + O (n) вставка решения с использованием массива.

Answer 4

Удалите один предмет и снова добавьте его в правильное положение. IF Вы делаете только один элемент, ваш максимальный период времени равен N.

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

Answer 5

В зависимости от того, будет ли новое значение больше или меньше предыдущего, вы можете «раздуть» его на месте.

псевдо-код будет выглядеть примерно так:

if new value larger than old value 
    then if new value is larger than next value in collection 
     then swap the value with the next value 
     iterate until value is not larger than next value 
else if new value is smaller than previous value in collection 
    then swap the value with the previous value 
    iterate until value is not smaller than the previous value 

Конечно, лучше всего было бы использовать бинарный поиск.

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

Например, предположим, что эта коллекция:

a b c d e f g h i j 
10 20 30 40 50 60 70 80 90 100 

Затем вы хотите, чтобы изменить значение дзета элемента от 60 до 95.

Сначала вы выяснить, где она должна быть.Использование двоичного поиска, мы обнаружили, что это должно быть между 90 и 100:

a b c d e f g h i j 
10 20 30 40 50 60 70 80 90 100 
           ^
            +- here 

Затем вы переносите элементы из текущего положения вниз один элемент, например:

a b c d e f g h i j 
10 20 30 40 50 60 70 80 90 100 <-- from this 
10 20 30 40 50 70 80 90 ?? 100 <-- to this 

И тогда вы сохраните значение в ?? пространство, которое дает этому образованию

a b c d e g h i f j 
10 20 30 40 50 70 80 90 95 100 

Answer 6

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

Для более крупных списков вы можете получить обновления O (log (n)), используя отсортированную структуру данных O (log (n)) (деревья AVL/RB, списки Skip-Lists, деревья сегментов и т. Д.). Простая реализация может включать удаление обновляемого элемента, изменение значения и повторное его вставку. Многие популярные языки имеют некоторую сортированную структуру данных в своей библиотеке (например, TreeMap/TreeSet в Java, multiset/multimap в STL), или вы можете легко найти бесплатную реализацию для своего языка.

Answer 7

Для массива вставка элемента в правильное положение будет O (n), поскольку вам нужно скопировать элементы массива, чтобы освободить место для дополнительного элемента. Вы можете найти индекс, который нужно вставить, выполнив binary search (O (log n)) или linear search (O (n)). Какой бы выбор вы ни выбрали, алгоритмом в целом будет O (n).

Единственный способ сделать это очень быстро - использовать структуру данных, которая лучше подходит для этой ситуации: a binary search tree. Вставка будет равна O (log n), если дерево остается сбалансированным (используйте self-balancing binary search tree, чтобы убедиться в этом, или надейтесь, что ваши данные не будут вставлены в очень регулярном порядке, чтобы приблизиться к O (log n).)

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