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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

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

Затем вы хотите изменить значение элемента f с 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 4

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

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

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

Answer 5

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

Answer 6

Удалите один элемент и снова добавьте его в правильное положение. ЕСЛИ вы делаете только один элемент, максимальное время выполнения равно N.

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

Answer 7

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