Хранение в std :: map / std :: set против сортировки вектора после сохранения всех данных
- Язык: C++
Я могу выделить вектор размера n и сохранить все данные. а затем отсортируйте его с помощью sort (begin (), end ()). В противном случае я могу продолжать ставить данные на карте или наборе, которые упорядочены сами по себе, поэтому мне не нужно потом сортировать. Но в этом случае вставка элемента может быть больше затратно из-за переделок (наверное).
Итак, что является оптимальным выбором для минимального времени для широкого диапазона n (кол-во объектов)
Вам нужно его измерить. Например: что быстрее вставить случайные int и сохранить контейнер отсортированным по карте, списку или вектору? Отвечаю через 2 минуты, когда найду презентацию.
Смотрите channel9.msdn.com/Events/Build/2014/2-661 с 45:50
Ответы 2
Это зависит от ситуации.
map и set - это красно-черные деревья обычно, они должны проделать большую работу, чтобы их сбалансировать, иначе работа с ними будет очень медленной. И он не поддерживает произвольный доступ. поэтому, если вы хотите отсортировать только один раз, вы не должны их использовать.
Однако, если вы хотите продолжить вставку элементов в контейнер и поддерживать порядок, map и set займут время O(logN), а отсортированный vector будет O(N). Последний работает намного медленнее, поэтому, если вам нужен часто вставлять и удалять, вы должны использовать map или set.
"Последний намного медленнее" не на моей машине.
@Nelfeal Насколько велики данные? Что ж, «последнее намного медленнее» означает только то, что функция сложности растет намного быстрее.
Верно, но это не значит, что по умолчанию следует использовать набор вместо вектора. А на вопрос «насколько велики данные?» Обычно ответ «достаточно мал». Но, конечно, как и многое другое, это зависит от обстоятельств.
@Nelfeal Да, вы правы, но я также указал, что только «часто» операции должны использовать карту или набор. :)
Разница между 2 заметна!
Используя набор, вы получаете сложность O(log(N)) для каждого вставляемого вами элемента. Таким образом, в результате вы получите O(N log(N)), который представляет собой сложность сортировки вставкой.
Добавление всего в вектор представляет собой сложность O(1), а при сортировке это будет O(N log(N)), начиная с C++ 11 (до этого у std::sort в среднем был O(N log(N))).
После сортировки вы можете использовать binary_search, чтобы получить ту же сложность, что и в наборе.
API использования вектора в том виде, в каком он установлен, не очень удобен, хотя дает хорошие преимущества в производительности. Это, конечно, полезно только тогда, когда вы можете выполнить массовую вставку данных или когда количество поисков намного больше, чем манипуляции с контентом. Возможность алгоритма сортировки по частично отсортированному вектору, когда вам нужно будет расширить его позже. Наконец, следует отметить, что у вас нет таких же гарантий аннулирования итератора.
Итак, почему векторы лучше? Место кеширования! Вектор содержит все данные в одном блоке памяти, поэтому процессор может выполнять предварительную выборку, в то время как для набора память разбросана по месту, требующему данных для поиска следующего адреса. Это делает вектор лучшей реализацией набора, чем std :: set для больших данных, когда вы можете жить с ограничениями.
Чтобы дать вам представление о кодовой базе, над которой я работаю, у нас есть несколько реализаций наборов и карт, основанных на векторах, которые имеют свои собственные повествования для работы. (Например: без стирания или без оператора [])
Честно говоря, некоторые из них проходили так, как будто касательная проходит мимо круга: P Но я думаю, что главное в том, что хотя оба дают O (NLogN) сложность на бумажном векторе лучше из-за более организованных данных в памяти
Извините, я могу что-нибудь улучшить? Хотя это хорошее резюме!
Это вопрос о структурах данных. В
std::setилиstd::mapесть сбалансированное дерево, которое постоянно сортируется - каждая вставка / удаление стоитO(logn), что означает, что все вставки будут стоитьO(nlogn). В векторе каждая вставка будет стоить вамO(1)(в среднем, потому что она иногда должна дублироваться), в то время как каждое удаление будет стоить вамO(n), а ее сортировка будет стоить вамO(nlogn)каждый раз. Если вам нужно постоянно сортировать, я бы сказал, что вам следует использовать дерево. В противном случае это может быть аналогично использованию вектора и его сортировке в конце.