Эффективная структура данных для быстрого произвольного доступа, поиска, вставки и удаления
Ну, я лично (не так?) Использую его, когда пишу какой-то код, который, я не уверен, будет работать правильно, но пользователю не нужно знать об ошибке.
Кроме этого, я использовал его на некоторых пользовательских элементах управления, для которых вы можете определить свойство 'action' в вашей HTML-разметке, и javascript попытается выполнить это действие, например так:
try{
window['method'](args);
}catch(e){
try{
window['optionalExceptionHandler'](e, args);
}catch(e){ return; }
}
(мне нравится думать, что это лучше, чем eval() xD)
7 ответов
Я бы использовал красно-черное дерево для сопоставления ключей значениям. Это дает вам O (log (n)) для 1, 3, 4. Он также поддерживает ключи в отсортированном порядке.
Для 2 я бы использовал хеш-таблицу для сопоставления значений с ключами, что дает вам O (1 ) производительность. Он также добавляет O (1) служебных данных для обновления хеш-таблицы при добавлении и удалении ключей в красно-черном дереве.
Как насчет использования отсортированного массива с двоичным поиском?
Вставка и удаление выполняются медленно. но, учитывая тот факт, что данные представляют собой простые целые числа, их можно оптимизировать с помощью вызовов memcpy (), если вы используете C или C ++. Если вы знаете максимальный размер массива, вы даже можете избежать выделения памяти во время использования массива, так как вы можете предварительно выделить его до максимального размера.
«Лучший» подход зависит от того, сколько элементов вам нужно store и как часто вам нужно будет вставлять / удалять по сравнению с поиском. Если вы редко вставляете или удаляете отсортированный массив с доступом O (1) к значениям, безусловно, лучше, но если вы часто вставляете и удаляете что-то, двоичное дерево может быть лучше, чем массив. Для достаточно малого n массив, скорее всего, превзойдет дерево в любом случае.
Если размер хранилища вызывает беспокойство, массив также лучше, чем деревья. Деревьям также необходимо выделять память для каждого элемента, который они хранят, и накладные расходы на выделение памяти могут быть значительными, поскольку вы храните только небольшие значения (целые числа).
Вы можете профилировать, что быстрее, копирование целых чисел, если вы вставить / удалить из отсортированного массива или дерева с выделенной (де) памятью.
Как насчет карты дерева? log (n) для описанных операций.
Я не знаю, какой язык вы используете, но если это Java, вы можете использовать LinkedHashMap или аналогичная коллекция. Он обладает всеми преимуществами списка и карты, обеспечивает постоянное время для большинства операций и занимает память слона. :)
Если вы не используете Java, идея LinkedHashMap, вероятно, по-прежнему подходит для использования в качестве структуры данных для вашей проблемы.
Мне очень нравятся сбалансированные бинарные деревья. Иногда они медленнее, чем хеш-таблицы или другие структуры, но они гораздо более предсказуемы; обычно они равны O (log n) для всех операций. Я бы предложил использовать Красно-черное дерево или AVL-дерево .
Если вы работаете в .NET, то в соответствии с документами MS http://msdn.microsoft.com/en-us/library/f7fta44c.aspx
- SortedDictionary и SortedList имеют O (log n ) для извлечения
- SortedDictionary имеет O (log n ) для операций вставки и удаления, тогда как SortedList имеет O ( n ).
Они отличаются использованием памяти и скоростью вставки / удаления. SortedList использует меньше памяти, чем SortedDictionary. Если SortedList заполняется сразу из отсортированных данных, это быстрее, чем SortedDictionary. Так что это зависит от ситуации, какая из них действительно лучше для вас.
Кроме того, ваш аргумент для связанного списка недействителен, так как для вставки он может быть O (1), но вы должны пройти по списку чтобы найти точку вставки, так что на самом деле это не так.
Как добиться 2 с помощью RB-деревьев? Мы можем заставить их подсчитывать дочерние элементы при каждой операции insert/delete. Это не заставит эти операции выполняться значительно дольше. Тогда спуститься вниз по дереву, чтобы найти i-й элемент, можно за log n времени. Но я не вижу реализации этого метода ни в java, ни в stl.