std :: map и performance, пересекающиеся множества

Question

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

Я считаю, что производительность очень медленная.

Подробнее: - В одном из наборов 150000 номеров - пересечение этого набора и другого набора занимает около 300 мс в первый раз и около 5000 мс во второй раз - Я еще не выполнил никакого профилирования, но каждый раз, когда я выполняю пересечение, отрываю отладчик в malloc.c!

Итак, как я могу улучшить эту производительность? Переключиться на другую структуру данных? Как улучшить производительность выделения памяти карты?

Обновление:

1. Есть ли способ задать std :: map или boost :: unordered_map для предварительного выделения немного места?
2. Или есть какие-нибудь советы по их эффективному использованию?

Update2:

См. Быстрый контейнер C ++, такой как C # HashSet и Словарь ?

Обновление3:

Я протестировал set_intersection и получил ужасные результаты:

(set_intersection) Found 313 values in the intersection, in 11345ms
(set_intersection) Found 309 values in the intersection, in 12332ms

Код:

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.insert(value);
    }

    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() % 200000 + 1;
        random *= 10;

        int value = 1000000000 + random;
        set2.insert(value);
    }

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}

Answer 1

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

Хитрость с векторами заключается в том, что если вы не выделите память для такой задачи, как эта, она выполнит ДАЖЕ МИРНОЕ, потому что будет продолжать перераспределять память, поскольку она изменяет размеры во время шага инициализации.

Попробуйте что-то вроде этого - это будет ПУТЬ быстрее.

int runIntersectionTestAlgo() { 

vector<char> vector1; vector1.reserve(100000);
vector<char> vector2; vector2.reserve(1000);

// Create 100,000 values for set1
for ( int i = 0; i < 100000; i++ )    {
    int value = 1000000000 + i;
    set1.push_back(value);
}

sort(vector1.begin(), vector1.end());

// Create 1,000 values for set2
for ( int i = 0; i < 1000; i++ )    {
    int random = rand() % 200000 + 1;
    random *= 10;
    int value = 1000000000 + random;
    set2.push_back(value);
}

sort(vector2.begin(), vector2.end());

// Reserve at most 1,000 spots for the intersection
vector<char> intersection; intersection.reserve(min(vector1.size(),vector2.size()));
set_intersection(vector1.begin(), vector1.end(),vector2.begin(), vector2.end(),back_inserter(intersection));

return intersection.size(); 
}

Answer 2

Я не понимаю, почему вы должны использовать карту для пересечения. Как уже говорили люди, вы можете поместить наборы в std::set и затем использовать std::set_intersection().

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

Answer 3

Я бы поддержал предложение отсортировать их. Уже есть алгоритмы набора STL, которые работают в отсортированных диапазонах (например, set_intersection, set_union и т. Д.):

set_intersection

Answer 4

Не зная больше о вашей проблеме, «проверьте с хорошим профилировщиком» - лучший общий совет, который я могу дать. Помимо этого ...

Если выделение памяти является вашей проблемой, переключитесь на какой-то пул распределитель, который уменьшает количество вызовов до malloc. Boost имеет несколько пользовательских распределителей, которые должны быть совместимы с std::allocator<T>. На самом деле, вы даже можете попробовать это перед профилированием, если вы уже заметили, что примеры отладочного прерывания всегда заканчиваются на malloc.

Если ваше числовое пространство известно как плотное, вы можете переключиться на использование vector - или bitset -основной реализации, используя ваши числа в качестве индексов в векторе.

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

Answer 5

Я кое-что понял: если я присоединяю отладчик к сборкам RELEASE или DEBUG (например, нажимаю F5 в IDE), то у меня ужасные времена.

Answer 6

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

Поскольку его элементы хранятся в отсортированном виде, вставка может стоить вам O (log N), но пересечение с другим (отсортировано!) std::set может быть сделано за линейное время.

Answer 7

Пересечение с картами идет медленно, попробуйте hash_map. (однако это не предусмотрено во всех реализациях STL.

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

Answer 8

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

Ответ на обновление : Существуют возможности ускорения выделения памяти за счет предварительного резервирования пространства, например boost :: pool_alloc . Что-то вроде:

std::map<int, int, std::less<int>, boost::pool_allocator< std::pair<int const, int> > > m;

Но, честно говоря, malloc довольно хорош в том, что он делает; Я бы сделал профиль, прежде чем делать что-то слишком экстремальное.

Answer 9

Какой у вас алгоритм пересечения? Может быть, есть какие-то улучшения?

Вот альтернативный метод

Я не знаю, будет ли это быстрее или медленнее, но это может быть что-то, чтобы попробовать. Прежде чем сделать это, я также рекомендую использовать профилировщик, чтобы убедиться, что вы действительно работаете в точке доступа. Измените наборы чисел, которые вы пересекаете, чтобы использовать вместо них std::set<int>. Затем переберите наименьшее из них, просматривая каждое найденное значение. Для каждого значения в наименьшем наборе используйте метод find, чтобы увидеть, присутствует ли число в каждом из других наборов (для производительности выполните поиск от наименьшего к наибольшему).

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

Затем вместо этого сохраните пересечение в std::vector<int> - вставка с использованием push_back также очень быстрая.

Вот еще один альтернативный метод

Измените наборы чисел на std::vector<int> и используйте std::sort для сортировки от наименьшего к наибольшему. Затем используйте std::binary_search, чтобы найти значения, используя примерно тот же метод, что и выше. Это может быть быстрее, чем поиск по std::set, так как массив более плотно упакован в памяти. На самом деле, не обращайте на это внимания, вы можете просто перебрать значения в шаге блокировки, просматривая значения с тем же значением , Увеличивайте только те итераторы, которые меньше минимального значения, которое вы видели на предыдущем шаге (если значения отличались).