сравнение скорости и памяти

Question

У меня есть миллиарды ярлыков.Эти метки содержат не более 20 целых чисел в диапазоне от 1 до 500. Мне нужно найти наличие каждого целого в каждой метке и, возможно, вставить целое в метку.У меня тоже ограничение памяти.Поэтому в некоторых случаях мне нужно удалить ярлыки, чтобы освободить память.какой из них лучше?используя vector для сохранения данных меток или unordered_set?

Answer 1

как уже намекнуло в одном из комментариев:

std::bitset займет меньше места, чем 20 целых чисел и даст O(1) add / check. Это хорошая идея, если у вас в среднем более 15 значений на ярлык или вы можете использовать дополнительное использование памяти.

если нет, я бы рекомендовал вектор по набору.

• выровнено в памяти (меньше пропусков кэша => быстрее)
• имеет меньший объем памяти
• если у вас есть массовая вставка, вы можете reserve()
• если ваш вектор отсортирован, вы можете использовать std::binary_search, чтобы иметь O(log n) lookup

Как правило: если у вас менее 50 элементов, вектор является вашим предпочтительным контейнером.

Насколько я понимаю, критическая операция - найти все метки, которые содержат определенное значение?

• Вы рассматривали возможность перевернуть структуру? Вместо хранения целых в каждый ярлык, почему бы не иметь список ссылок на ярлыки для каждого из ваши 500 значений?
• Рассматривали ли вы (не-sql) БД, чтобы избавиться от ограничений памяти?