Лучше всего самоуравновешивающееся BST для быстрой вставки большого количества узлов
Другие решения отлично подходят для одной конструкции if / else. Тем не менее, трехмерные выражения в понимании списка, возможно, трудно читать.
Использование функции облегчает читаемость, но такое решение трудно расширить или адаптировать в рабочем процессе, где отображение является входом. Словарь может облегчить эти проблемы:
row = [None, 'This', 'is', 'a', 'filler', 'test', 'string', None]
d = {None: '', 'filler': 'manipulated'}
res = [d.get(x, x) for x in row]
print(res)
['', 'This', 'is', 'a', 'manipulated', 'test', 'string', '']
4 ответа
Красно-черный лучше, чем AVL для тяжелых вставкой приложений. Если Вы предвидите относительно универсальный поиск, то Красно-черный способ пойти. Если Вы предвидите относительно несбалансированный поиск, где позже просматриваемые элементы, более вероятно, будут просмотрены снова, Вы хотите использовать косые деревья.
Почему использование a BST вообще? Из Вашего описания словарь будет работать точно также, если не лучше.
Единственная причина использования a BST был бы то, если бы Вы хотели перечислить содержание контейнера в ключевом порядке. Это, конечно, не кажется, что Вы хотите сделать это, в этом случае пойдите для хеш-таблицы. O(1) вставка и поиск, никакое беспокойство об удалении, что могло быть лучше?
Самоуравновешивающиеся два BSTs я являюсь самым знакомым с, являются красно-черными и AVL, таким образом, я не могу сказать наверняка, если какие-либо другие решения лучше, но как я вспоминаю, красно-черный имеет более быструю вставку и более медленное извлечение по сравнению с AVL.
Таким образом, если вставка является более высоким приоритетом, чем извлечение, красно-черное, может быть лучшим решением.
[хеш-таблицы имеют] O (1) вставка и поиск
Я думаю, что это неправильно.
В первую очередь, при ограничении ключевого пространства, чтобы быть конечными, Вы могли бы сохранить элементы в массиве и сделать O (1) линейное сканирование. Или Вы могли shufflesort массив и затем делаете линейное сканирование в O (1) ожидаемое время. Когда материал конечен, материал легко O (1).
Таким образом, скажем, Ваша хеш-таблица сохранит любую произвольную строку битов; это не очень имеет значение, пока существует бесконечное множество ключей, каждый из которых конечны. Затем необходимо считать все биты любого входа запроса и вставки, еще я вставляю y0 в пустой хеш и запрос на y1, где y0 и y1 отличаются в единственной позиции двоичного разряда, на которую Вы не смотрите.
Но скажем, длины ключа не являются параметром. Если Ваша вставка и поисковое взятие O (1), в особенности хеширование берет O (1) время, что означает, что Вы только смотрите на конечную сумму вывода от хеш-функции (от которого, вероятно, будет только конечный вывод, предоставленный).
Это означает, что с конечно многими блоками, должно быть бесконечное множество строк, которые у всех есть то же значение хэш-функции. Предположим, что я вставляю много, т.е. ω (1), тех, и начинаю запрашивать. Это означает, что Ваша хеш-таблица должна возвратиться к некоторому другому O (1) механизм вставки/поиска для ответа на мои запросы. Какой, и почему не просто используют это непосредственно?