std:: карта и производительность, пересекающиеся множества

StackOverflow https://stackoverflow.com/questions/1056244

  •  20-08-2019
  •  | 
  •  

Вопрос

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

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

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

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

Обновить:

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

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

Видишь Быстрый контейнер C ++, подобный C # HashSet<T> и словарь<K,V>?

Обновление 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(); 
}
Это было полезно?

Решение 9

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

Другие советы

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

Хитрость с векторами заключается в том, что если вы не будете предварительно выделять память для подобной задачи, она будет работать ЕЩЕ ХУЖЕ, потому что будет перераспределять память по мере изменения ее размера на этапе инициализации.

Попробуйте что-нибудь подобное в instaed - это будет НАМНОГО быстрее.

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(); 
}

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

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

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

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

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

set_интерсекция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top