Оценка скорости / использования памяти для различных структур данных
Я пытаюсь решить, какую структуру данных использовать для следующего.
Допустим, у меня есть около 10 миллионов ключей, которые содержат указатели на уникальные объекты, содержащие некоторые данные.
Ключи UUID представляют собой 16-байтовые двоичные массивы. UUID генерируются с использованием генератора случайных чисел хорошего качества.
Я думал о следующем, но хотел бы знать, какие плюсы и минусы с точки зрения скорости и потребления памяти будут для каждого. Некоторые справедливые оценки, лучший / худший / средний случай на 64-битной платформе были бы хорошими.
Мне нужно иметь возможность вставлять практически неограниченное количество предметов.
Двоичное дерево хеш-таблиц Radix Tree (на основе битов или 2-битный многоканальный)
Мне нужно выполнить следующие операции: вставить, удалить, найти
Мне нравится идея основополагающего дерева, но оно оказывается трудным для реализации, и я не нашел подходящей реализации, которую можно было бы включить в коммерческий продукт.
4 ответа
- Вы не заботитесь о заказе
- Ваш ключ уже случайный
- 10 миллионов предметов
Краткий ответ
Хеш-таблица, вероятно, будет лучшим для вашего случая.
скорость
Хеш-таблица (std::unordered_map) будет O(1), если хеширование постоянное. В вашем случае O(1) выполняется, потому что вам даже не нужно хэшировать - достаточно просто использовать младшие 32 бита случайного UUID. Стоимость поиска будет аналогична одной или двум указателям.
Бинарное дерево (std::map) будет O(log2 n), поэтому для 10 миллионов элементов у вас будет 24 сравнения и 24 потенциальных пропуска кэша. Даже при n = 4000 он будет использовать 12 сравнений, поэтому он очень быстро станет значительно хуже, чем хеш-таблица.
Основное дерево будет O(k), поэтому у вас будет максимум k сравнений и k потенциальных пропусков кэша. Очень маловероятно, что основополагающее дерево будет таким же быстрым, как хеш-таблица. В худшем случае (при условии k = несколько разумных 16 для дерева с 256 путями) он будет работать лучше, чем двоичное дерево, но гораздо хуже, чем хеш-таблица.
Так что, если скорость является главным приоритетом, используйте хеш-таблицу.
накладные расходы
Типичная хеш-таблица будет содержать около 1–3 указателей накладных расходов на элемент, если они заполнены. Если не заполнен, вы, вероятно, будете тратить 1 указатель пространства на пустой слот. Вы должны быть в состоянии поддерживать его почти полным, но при этом быть быстрее, чем двоичное дерево, потому что у вас очень случайный ключ, но для максимально возможной скорости вы, конечно, захотите дать ему достаточно места. Для 10 миллионов элементов на 32-разрядной машине ожидайте 38–114 МБ служебных данных для полной таблицы. Для наполовину заполненного стола ожидайте 76–153MiB.
Красно-черное дерево, самое распространенное std::map реализация, будет иметь 3 указателя + 1 бул на элемент. Некоторые реализации используют выравнивание указателей для объединения bool с одним из указателей. В зависимости от реализаций и степени заполнения хеш-таблицы, красно-черное дерево может иметь немного меньшие накладные расходы. Ожидайте 114–153MiB.
Основное дерево будет иметь 1 указатель на элемент и 1 указатель на пустой слот. К сожалению, я думаю, что такие большие случайные ключи приведут к тому, что у вас будет очень много пустых слотов к краю дерева, поэтому он, вероятно, будет использовать больше памяти, чем любой из перечисленных выше. Уменьшение k может снизить эти издержки, но также снизит производительность.
Если важны минимальные издержки, используйте хэш-таблицу или двоичное дерево. Если это приоритет, используйте полную хеш-таблицу.
Обратите внимание, что std::unordered_map не позволяет вам контролировать, когда он изменит размер, поэтому получить один полный будет сложно. Boost Intrusive имеет очень хороший unordered_map реализация, которая позволит вам непосредственно контролировать это и многое другое.
Я только что сделал быстрый расчет, и я думаю, что вы можете быть в порядке со стандартным деревом 10 миллионов ключей - разумное число. При сбалансированном дереве это будет глубина только 23 узлов для проверки. С основополагающим деревом у вас фактически есть длина ключа 128 битов для проверки.
Ваш ключ также может быть представлен и сравнительно дешево. Используйте кортеж (boost или 0x) из двух 64-битных значений, чтобы получить тот же 128-битный ключ. Порядка кортежа будет достаточно для использования на карте. Копирование ключей, таким образом, дешево, как и сравнение. Сравнение целых чисел как есть, вероятно, дешевле, чем маскирование и сравнение на основе битов для поиска по глубине.
Так что в этом случае карта, скорее всего, будет работать нормально.
* Я бы избежал unordered_map здесь, поскольку UUID, как правило, структурированные данные. Это означает, что стандартная процедура хеширования (для хэш-карты) может быть очень плохой по производительности. *
Обновить:
Поскольку вы используете случайные UUID, хеширование может быть просто нормальным, хотя такие большие хеш-таблицы имеют значительные накладные расходы памяти, чтобы оставаться эффективными.
Кроме того, учитывая совершенно случайные UUID, основание, скорее всего, будет иметь такую же балансировку, что и дерево (поскольку распределение ключей абсолютно равномерное). Таким образом, вы не можете сохранить даже шаги и все равно понести накладные расходы на битовые операции. Но существует так много способов специализироваться и оптимизировать основополагающее дерево, что трудно точно сказать, может ли оно быть быстрее или всегда медленнее.
Я бы попробовал std::map или же std::unordered_map первый.
У них было много умных людей, которые развивали и совершенствовали их в течение многих лет.
Есть ли причина, по которой вы не можете использовать std::map или же std::unordered_map?
Основное дерево IMO не сложно реализовать. Тем не менее, простой хэш-таблицы будет достаточно. Просто выделите массив из 2^16 списков объектов и используйте первые 2 байта UUID для индексации списка, куда вставить объект. Тогда вы можете искать список примерно с 160 элементами.
Или выделите массив из 20M указателей. Чтобы сохранить объект, просто сделайте хеш UUID в диапазоне 0-20M, найдите первый свободный (NULL) указатель и сохраните его там. Поиск означает переход от значения хеша к первому значению NULL. Удаление также просто.... попробуйте прочитать http://en.wikipedia.org/wiki/Hash_function