std :: unordered_map распределение, время вставки и освобождение

Question

У меня есть приблизительно 4 миллиона значений в файле, который я хочу сохранить в контейнере для выполнения вычислений.

Ключ каждого значения состоит из 2 целых без знака Значение представляет собой структуру, содержащую 4 двойных числа.

Значения после загрузки не изменяются.

typedef pair<unsigned int, unsigned int> aa; 
struct MyRecord { double a1; double a2; double a3; double a4; }; 

class MyRecordHash{ 
public: 
    size_t operator()(const aa &k) const{ return k.first * 10000 + k.second;  } 
}; 

struct MyRecordEquals : binary_function<const aa&, aa&, bool> { 
    result_type operator()(nm lhs, nm rhs) const 
    { 
    return (lhs.first == rhs.first) && (lhs.second == rhs.second); 
    } 
};  

std::unordered_map<aa,MyRecord,MyRecordHash,MyRecordEquals> MyRecords; 

Я использую MyRecords.reserve (number_of_records) перед вставкой записей.

Проблема A: Хотя я вызываю резерв перед началом ввода данных, выделенной памяти недостаточно и перераспределяет все больше и больше памяти, когда она вставляет данные. Не следует ли выделить резервную память? Например, для 4-х записей он выделяет резерв 38.9Mb, а затем после вставок добавляет 256.5Mb.

Задача B: Процесс вставки довольно медленный. Я проверил коэффициент загрузки, и он никогда не увеличивается более чем на 0,5. Есть ли какие-либо предложения по проверке чего-либо еще? Я использую MyRecords.insert для вставки.

Проблема C: После завершения моих вычислений я вызываю MyRecords.clear(). Вместо того, чтобы мгновенно удалять содержимое, он начинает снимать запись по записи (приблизительно 3 Мбит/с). Если я не вызываю clear(), я получаю такое же поведение. Это нормально? Я проверил все предыдущие вопросы о stackoverflow, и единственное, что я нашел, это то, что это может быть связано с отладкой. Я использовал опцию -O3, но ничего не изменил.

Я использую компилятор MinGW-64 4.9.1.

Благодарим всех вас за это и за ваши предложения.

EDIT После предложено Комментарии и решения:

-Он, кажется, что нет никакого способа, чтобы освободить или предварительно выделить память STL для unordered_maps при использовании, кроме стандартных типов для ключа и данных, содержащихся , -Резервный метод, резервирует память только для хэшей. -Использование вектора <> с индексами, вычисленными из ключа значений, которые очень хорошо работали. Просто предопределяйте вектор, затем используя значение myvector.at() =, задайте значения. Деструктор по умолчанию освобождает вектор почти мгновенно (при этом значения 4 м занимают 2-3 секунды, а не 5 минут с unordered_map). -Использование памяти с вектором меньше, так как не сохраняется ключ -Random доступ к вектору кажется немного медленнее, хотя еще не профилировал код.

Еще раз спасибо за помощь.

Answer 1

Взято из комментариев ...

---

Я полагаю, я задаю вопрос (смотреть на вещи в ином свете), вы уверены, что вам нужен ассоциативный контейнер?

Если у вас есть записи, охватывающие почти все комбинации клавиш, то, возможно, вектор будет делать, если вы в порядке, потратив немного места на неиспользуемые записи. Поэтому относитесь к своим ключам как индексы в свой вектор. Это даст вам постоянный поиск времени и позволит вам выделить всю необходимую память спереди, избегая затрат нескольких распределений.

Значение этого подхода будет зависеть от распределения ключей в пространстве ключей и насколько легко их можно сопоставить с индексом массива с нулевым значением.

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

Answer 2

reserve, вероятно, выделяет пространство только для структуры хэша (вектор указателей на данные, например), а не самих данных.

Примите ваш пример вставки записей 4M. Каждая запись - 4 двойных или 4 * 8 байта. Записи 4M означают 4 * 8 * 4 = 128 Мбайт данных. Очевидно, что выделение 38,9 Мбайт резерва() недостаточно.

Answer 3

Все unordered_map::reserve делает увеличение количества ведер, так что вы не превысите максимальный коэффициент загрузки при вставке указанного количества элементов. Это тебе не поможет.

unordered_map - это контейнер на основе узлов; в результате каждая вставка представляет собой отдельное распределение. Деструкторы структуры данных тривиальны, но освобождение 4 миллионов кусков памяти довольно дорого.

Вы можете

• Используйте выборочный аллокатор, который обрабатывает ваш шаблон распределения эффективно,
• или переключиться на другую структуру данных. boost::flat_map - хороший выбор (и слегка увеличенная временная сложность вполне может быть компенсирована увеличением производительности за счет лучшей локализации данных).