Я должен случайным образом переставить прежде, чем вставить в набор STL?
Я должен вставить 10 миллионов строк в набор STL C++. Строки отсортированы. У меня будет патологическая проблема, если я вставлю строки в отсортированный порядок? Я должен рандомизировать сначала? Или будет G ++, реализация STL автоматически изменяет баланс для меня?
7 ответов
Единственный вопрос: действительно ли вам нужен набор ?
Если данные уже отсортированы и вам не нужно вставлять / удалять элементы после создания, появляется deque будет лучше:
- у вас будет такая же сложность big-O, используя двоичный поиск для поиска
- вы получите меньше накладных расходов на память ... и лучшую локальность кеша
На binary_search : я подозреваю, что вам нужно больше, чем ForwardIterator для двоичного поиска, думаю, этот сайт снова отключен: (
Реализация набора обычно использует красно-черное дерево, которое будет повторно сбалансировано для вас. Однако вставка может быть быстрее (а может и нет), если вы рандомизируете данные перед вставкой - единственный способ быть уверенным - это провести тест с вашей реализацией набора и конкретными данными. В любом случае время получения будет одинаковым.
http://en.wikipedia.org/wiki/Standard_Template_Library
set: «Реализовано с использованием самобалансирующегося двоичного дерева поиска».
Очень дешевое и простое решение - вставка с обоих концов ваших коллекций строк. То есть сначала добавьте «A», затем «ZZZZZ», затем «AA», затем «ZZZZY» и так далее, пока не встретитесь посередине. Это не требует больших затрат на перетасовку, но, вероятно, позволит избежать патологических случаев.
Реализация перебалансирует автоматически. Однако, учитывая, что вы знаете, что ввод отсортирован, вы можете оказать ему небольшую помощь: вы можете предоставить «подсказку», когда выполняете вставку, и в этом случае предоставление итератора для ранее вставленного элемента будет точно правильным подсказка для следующей вставки. В этом случае каждая вставка будет иметь амортизированную постоянную сложность вместо ожидаемой логарифмической сложности.
libstdc++ в g++ использует красно-черные деревья для множеств и карт.
http://en.wikipedia.org/wiki/Red-black_tree
Это самобалансирующееся дерево, и вставки всегда O(log n). Стандарт C++ также требует, чтобы все реализации обладали этой характеристикой, поэтому на практике они почти всегда являются красно-черными деревьями или чем-то очень похожим.
Так что не беспокойтесь о порядке, в котором вы размещаете элементы.