Могу ли я предварительно загрузить карту STL без выполнения картой каких-либо поворотов?

#c #stl #map

#c #stl #словарь

Вопрос:

Я отсортировал данные, поступающие из базы данных, для инициализации карты STL. Позже внутри карты будет изменено только 5% данных.

Как я понимаю, для каждой вставки будут накладные расходы на вращения. Возможно ли обойти накладные расходы для отсортированных данных? например, есть ли возможность пропустить поворот и другой алгоритм STL для создания сбалансированного дерева с отсортированными данными?

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

1. О каком объеме данных мы говорим?

2. Независимо от того, O(db access) > O(std::map inserts) .

3. Вы уверены, что STL map — лучшая структура данных для манипулирования вашими данными? Если входные данные уже отсортированы, vector или deque может быть лучше (с бинарным поиском для доступа к определенному элементу).

Ответ №1:

Я полагаю, вас интересует только эффективная загрузка исходных отсортированных данных?

Стандартный конструктор map :: map (InputIterator первый, InputIterator последний), кажется, делает все правильно.

«Для конструктора iterator, линейное расстояние между итераторами (копирование конструкций), если элементы уже отсортированы в соответствии с comp. Для несортированных последовательностей, линейно-рифмованных (N * logN) на этом расстоянии (сортировка, копирование конструкций).»

Ответ №2:

http://www.sgi.com/tech/stl/Map.html

Я думаю, что map (InputIterator f, InputIterator l) может вам помочь, но я не знаю, учитывает ли это сортируемые данные :/

1. Я нажал на эту ссылку и копнул глубже и обнаружил, что «Конструктор range и конструктор range с compare в общем случае равны O(N * log(N)), где N — размер диапазона. Однако они линейны по N, если диапазон уже отсортирован с помощью value_comp(). »

Ответ №3:

Я не верю, что у вас есть какие-либо гарантии относительно фактической структуры данных, используемой под капотом для карты STL. Кроме того, учтите, что порядок, в котором вы вставляете данные (вы заявляете, что они отсортированы), может оказать негативное влияние на производительность, если карта не выполняла поворотов! Конечно, вращения подразумевают, что используется самобалансирующееся дерево, а не список пропусков, дерево сплайсов или любая другая структура данных, выбранная автором библиотеки.

Вероятно, время, затраченное на извлечение данных из базы данных, затмит время, затраченное на добавление отсортированных данных на карту. Возможной оптимизацией было бы НЕ извлекать данные в отсортированном порядке. Карта не будет заботиться о сортировке.

Ответ №4:

std::map::insert(iterator, pair) Функция имеет амортизированную постоянную стоимость, если входные данные отсортированы. Чтение всего набора данных означает, что вы получаете O (N). (Обратите внимание, что эта программа имеет правильную семантику независимо от того, отсортированы ли входные данные.)

 #include <map>
#include <iostream>
int main() {
 std::map<int, int> m;
 int a, b;
 for(std::map<int,int>::iterator it = m.begin();
     std::cin >> a >> b;
     it = m.insert(it, std::pair<int,int>(a,b))) {
  /* nothing */
 }
}

Ответ №5:

Если вам необходимо использовать карту, рассмотрите возможность использования контейнеров на основе политики gcc, если это возможно. Они намного быстрее, чем STL.

http://gcc.gnu.org/onlinedocs/libstdc /ext/pb_ds/interface.html