Оценка скорости / использования памяти для различных структур данных

Question

Я пытаюсь решить, какую структуру данных использовать для следующего.

Допустим, у меня есть, возможно, 10 миллионов ключей, которые содержат указатели на уникальные объекты, содержащие некоторые данные.

КлючиUUID воспринимает их как 16-байтовые двоичные массивы.UUID генерируются с использованием генератора случайных чисел хорошего качества.

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

Мне нужно иметь возможность вставлять практически неограниченное количество элементов.основанный или 2-битный многоканальный)

Мне нужны следующие операции: вставка, удаление, поиск

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

Answer 1

• Вам нет дела до заказа
• Ваш ключ уже случайный
• 10 миллионов предметов

Краткий ответ

Хеш-таблица, вероятно, подойдет для вашего случая.

Скорость

Хеш-таблица (std::unordered_map) будет O (1), если хеширование постоянное.В вашем случае O (1) выполняется, потому что вам даже не нужно хэшировать - достаточно просто использовать младшие 32 бита случайного UUID.Стоимость поиска будет аналогична одной или двум косвенным указателям.

Двоичное дерево (std::map) будет O (log ₂ n ), поэтому для 10 миллионов элементов у вас будет 24 сравнения и 24 возможных пропуска кэша.Даже для n = 4000 он будет использовать 12 сравнений, поэтому он очень быстро станет значительно хуже, чем хеш-таблица.

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

Так что, если скоростьявляется главным приоритетом, используйте хеш-таблицу.

Служебные данные

Типичная хеш-таблица будет содержать около 1–3 указателей на каждый элемент, если заполнена.Если не заполнен, вы, вероятно, будете тратить 1 указатель пространства на пустой слот.Вы должны быть в состоянии поддерживать его почти полным, но при этом быть быстрее, чем двоичное дерево, потому что у вас очень случайный ключ, но для максимально возможной скорости вы, конечно, захотите дать ему достаточно места.Для 10 миллионов элементов на 32-разрядном компьютере ожидайте 38–114 МБ служебных данных для полной таблицы.Для таблицы наполовину полной ожидайте 76–153 МБ.

Красно-черное дерево, наиболее распространенная реализация std::map, будет иметь 3 указателя + 1 бул на элемент.Некоторые реализации используют выравнивание указателей для объединения bool с одним из указателей.В зависимости от реализаций и степени заполнения хеш-таблицы, красно-черное дерево может иметь немного меньшие накладные расходы.Ожидайте 114–153MiB.

Основное дерево будет иметь 1 указатель на элемент и 1 указатель на пустой слот.К сожалению, я думаю, что такие большие случайные ключи приведут к тому, что у вас будет очень много пустых слотов к краю дерева, поэтому он, вероятно, будет использовать больше памяти, чем любой из вышеперечисленных.Уменьшение k может снизить эти издержки, но также снизит производительность.

Если важны минимальные издержки, используйте хэш-таблицу или двоичное дерево.Если это приоритет, используйте полную хеш-таблицу.

Обратите внимание, что std::unordered_map не позволяет вам контролировать, когда он изменит размер, поэтому получить одну полную будет сложно. Boost Intrusive имеет очень приятную реализацию unordered_map, которая предоставит вам прямой контроль над этим и многими другими вещами.

Answer 2

Я только что сделал быстрый расчет, и я думаю, что вы можете быть в порядке со стандартным деревом. 10 миллионов ключей - разумное число. При сбалансированном дереве это будет глубина только 23 узлов для проверки. С основополагающим деревом у вас будет длина ключа 128 бит для проверки.

Ваш ключ также может быть представлен и сравнительно дешево. Используйте кортеж (boost или 0x) из двух 64-битных значений, чтобы получить тот же 128-битный ключ. Порядка кортежа будет достаточно для использования на карте. Копирование ключей, таким образом, дешево, как и сравнение. Сравнение целых чисел как есть, вероятно, дешевле, чем маскирование и сравнение на основе битов для поиска по глубине радиуса.

Так что в этом случае карта, скорее всего, будет работать нормально.

* Я бы избежал unordered_map здесь, поскольку UUID, как правило, являются структурированными данными. Это означает, что стандартная процедура хеширования (для хэш-карты) может быть очень плохой по производительности. *

Обновление:

Поскольку вы используете случайные UUID, хэширование может быть вполне приемлемым, хотя такие большие хеш-таблицы имеют значительные накладные расходы памяти, чтобы оставаться эффективными.

Кроме того, учитывая совершенно случайные UUID, основание, скорее всего, будет иметь ту же балансировку, что и дерево (поскольку распределение ключей абсолютно равномерное). Таким образом, вы не можете сохранить даже шаги и все равно понести издержки на битовые операции. Но есть так много способов специализироваться и оптимизировать основополагающее дерево, что трудно точно сказать, может ли оно быть быстрее или всегда медленнее.

Answer 3

Сначала я бы попробовал std::map или std::unordered_map.

У них было много умных людей, которые разрабатывали и совершенствовали их в течение многих лет.

Есть ли причина, по которой вы можете 'т std::map или std::unordered_map?

Answer 4

Дерево основ IMO несложно реализовать.Однако простой хэш-таблицы будет достаточно.Просто выделите массив из 2 ^ 16 списков объектов и используйте первые 2 байта UUID для индексации списка, куда вставить объект.Затем вы можете выполнить поиск по списку примерно с 160 элементами.

Или выделить массив из 20 миллионов указателей.Чтобы сохранить объект, просто сделайте хеш-код UUID в диапазоне 0-20M, найдите первый свободный (NULL) указатель и сохраните его там.Поиск означает переход от значения хеш-функции к первому значению NULL.Удаление также просто .... попробуйте прочитать http://en.wikipedia.org/wiki/Hash_function