Как быстро обратиться список только с одним измененным значением?
Java использует анонимные классы главным образом для подражания закрытиям или просто блокам кода. С тех пор в Python можно легко раздать методы нет никакой потребности в конструкции, столь же неуклюжей как анонимные внутренние классы:
def printStuff():
print "hello"
def doit(what):
what()
doit(printStuff)
Редактирование: я знаю, что это не то, что необходимо в этом особом случае. Я просто описал наиболее распространенное решение для Python проблемы обычно анонимными внутренними классами в Java.
7 ответов
Если список отсортирован, вы можете просто удалить элемент, который вы собираетесь изменить, из списка, а после его изменения вы можете «двоично вставить» его, нет? Это займет в среднем log (n) шагов.
Если вы можете, измените массив на java.util.TreeMap: и удаление, и вставка будут операциями log (n): что будет быстрее, чем ваш O (1) доступ + O (n) решение для повторной вставки с использованием массива.
Перемещение несортированного элемента влево или вправо в списке кажется оптимальным решением
Если список действительно большой и ожидается большое количество операций обновления, простой массив с произвольным доступом или связанный список будет слишком медленным. Если вы используете массивы / связанные списки, каждая операция обновления будет стоить O (n). Для небольших списков и / или небольшого количества обновлений этого достаточно.
Для больших списков вы можете достичь O (log (n)) обновлений, используя сортированную структуру данных O (log (n)) (AVL / RB- деревья, Skip-листы, деревья сегментов и т. д.). Простая реализация может включать удаление обновляемого элемента, изменение значения и повторную его вставку. Многие популярные языки имеют в своей библиотеке своего рода сортированную структуру данных (например, TreeMap / TreeSet в Java, multiset / multimap в STL C ++), или вы можете легко найти бесплатную реализацию для своего языка.
В зависимости от того, будет ли новое значение больше или меньше предыдущего, вы можете «пузырить» его на месте.
Псевдокод будет выглядеть примерно так:
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
Вы можете просто выполнить одну итерацию пузырьковой сортировки : начать с начала списка и повторять до тех пор, пока не найдете неупорядоченный элемент. Затем переместите его в нужном направлении, пока он не встанет на место. В худшем случае это даст вам производительность 2N.
Для массива вставка элемента в правильную позицию будет O (n), потому что вам нужно скопировать элементы массива, чтобы освободить место для дополнительного элемента. Вы можете найти индекс, в который нужно вставить, выполнив двоичный поиск (O (log n)) или линейный поиск (O (n)). Какой бы выбор вы ни выбрали, алгоритм в целом будет O (n).
Единственный способ сделать это очень быстро - это использовать структуру данных, которая лучше подходит для этой ситуации: a ] двоичное дерево поиска . Вставка будет O (log n), если дерево остается прилично сбалансированным (используйте самобалансирующееся двоичное дерево поиска , чтобы гарантировать это, или надейтесь, что ваши данные не будут вставлены в очень регулярном порядке, приближающемся к O ( журнал n).
Remove the one item, and re-add it into the correct position. IF you are only doing one item, your max run-time is N.
If you are doing more than one, you should wait till they are all done and then resort. But you'll need to tell us a lot more about your problem space. Quick is contrained by memory and other factors which you'll need to determine to pick the right algorithm.