Динамический массив с O (1) удаление любого элемента
Пример, сделанный мной с использованием прокрутки (только HTML, CSS и JS, только с библиотекой jquery). При прокрутке вниз кнопка сдвигается влево.
Кроме того, я предлагаю вам, если вам нужен только этот эффект, не используйте jQuery UI, потому что он слишком тяжелый (если вы просто хотите использовать его для этого).
$(window).scroll(function(){
if ($(this).scrollTop() > 100) {
event.preventDefault();
$(".scrollToTop").css({'transform': 'translate(0px, 0px)'});
} else {
$(".scrollToTop").css({'transform': 'translate(40px, 0px)'});
}
});
Отметьте этот пример
6 ответов
Эта идея используется в перемешивании Кнута (Фишера – Йейтса) . Случайно выбранный элемент заменяется последним в массиве. Поскольку в любом случае нам нужна случайная перестановка, перестановка не имеет значения.
Итак, у этой странной / бесполезной структуры есть имя и есть ли у нее какое-то применение?
Я использовал нечто подобное при моделировании многопроцессорных систем.
В планировщик для процессов, реализованный как конечные автоматы, каждый процесс либо ожидает внешнего события, активного или завершенного. В планировщике есть массив указателей на процессы.
Первоначально каждый процесс активен, и у планировщика есть индекс последнего ожидающего и первого завершенного процесса, изначально равный нулю, и длина массива.
V-- waiting
[ A-active, B-active, C-active, D-active ]
completed --^
^- run
Чтобы перевести процесс в его следующее состояние, планировщик выполняет итерацию по массив и запускает каждый процесс по очереди. Если процесс сообщает, что он ожидает, он заменяется процессом после последнего ожидающего процесса в массиве.
V-- waiting
[ A-waiting, B-active, C-active, D-active ]
completed --^
^- run
Если он сообщает, что он завершен, это ' s заменяется процессом перед первым завершенным массивом.
V-- waiting
[ A-waiting, D-active, C-active, B-completed ]
completed --^
^- run
Таким образом, когда планировщик запускается и обрабатывает переход от активного к ожидающему или завершенному, массив становится упорядоченным со всеми ожидающими процессами в начале, всеми активными в середине и завершенными в конце.
V-- waiting
[ A-waiting, C-waiting, D-active, B-completed ]
completed --^
^- run
Либо после определенного количества итераций, либо когда больше нет активных процессов, завершенные процессы удаляются из массива и обрабатываются внешние события:
V-- waiting
[ A-waiting, C-waiting, D-completed, B-completed ]
completed --^
^- run == completed so stop
Это похоже на то, что используется замена для удаления элементов из коллекции, но он скорее удаляет элементы с обоих концов и оставляет «коллекцию» посередине.
массив становится упорядоченным со всеми ожидающими процессами в начале, всеми активными в середине и завершенными в конце. V-- waiting
[ A-waiting, C-waiting, D-active, B-completed ]
completed --^
^- run
После определенного количества итераций или когда активных процессов больше нет, завершенные процессы очищаются из массива и обрабатываются внешние события:
V-- waiting
[ A-waiting, C-waiting, D-completed, B-completed ]
completed --^
^- run == completed so stop
Это похоже на то, что он использует замену для удаления элементов из коллекции, но он удаляет элементы с обоих концов и оставляет «коллекцию» посередине .
массив становится упорядоченным со всеми ожидающими процессами в начале, всеми активными в середине и завершенными в конце. V-- waiting
[ A-waiting, C-waiting, D-active, B-completed ]
completed --^
^- run
После определенного количества итераций или когда активных процессов больше нет, завершенные процессы очищаются из массива и обрабатываются внешние события:
V-- waiting
[ A-waiting, C-waiting, D-completed, B-completed ]
completed --^
^- run == completed so stop
Это похоже на то, что он использует замену для удаления элементов из коллекции, но он удаляет элементы с обоих концов и оставляет «коллекцию» посередине .
но он скорее удаляет элементы с обоих концов и оставляет «коллекцию» посередине. но он скорее удаляет элементы с обоих концов и оставляет «коллекцию» посередине.Я помню, как раньше уже много раз использовал этот метод. Но я не знаю, как это называется.
Простой пример: в компьютерной игре вы повторяете всех «плохих парней», вычисляете их движения и т. Д. С ними может случиться одна вещь - исчезнуть (их труп закончил исчезать и теперь прозрачен на 99%). В этот момент вы удаляете его из списка, как вы это делаете, и возобновляете итератор, не увеличивая счетчик итераций.
Нечто подобное делается в двоичной куче при удалении элемента, однако есть следующий шаг заключается в поддержании правила кучи - O (log n).
Хм, этот алгоритм действительно имеет время удаления O (1)?
Это означает, что
- Поиск элемента для удаления составляет O (1)
- Поиск последнего элемент (который заменит удаленный элемент) - O (1)
- Поиск предпоследнего элемента (новый «последний» элемент) - O (1)
... что невозможно ни в одном структура данных, которую я могу придумать. Хотя двусвязный список может удовлетворить эти ограничения, если у вас уже есть указатель на элемент, который нужно удалить.
] Я не знаю, как его называть, но в некоторых случаях это лучше, чем список.[
] [] В частности, это было бы намного лучше, чем однократный или двукратный список для очень маленьких данных. Потому что вы храните все непрерывно, и на каждый элемент нет лишних указателей. [
]