C ++ std :: map создание занимает слишком много времени?

Question

ОБНОВЛЕНО:

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

        std::map<long, int> myMap;

        for (int i = 0; i < myVector.size(); ++i)
        {
            const Type& theType = myVector[i];
            myMap[theType.key] = i;
        }

Когда я ищу карту, результаты остальной части программы намного быстрее.Однако остальным узким местом является создание самой карты (для вставки в нее около 1500 элементов в среднем требуется около 0,8 миллисекунды).Мне нужно найти способ сократить это время.Я просто вставляю long как ключ и int как значение.Я не понимаю, почему это занимает так много времени.

Еще одна идея, которая у меня была, - создать копию вектора (не может коснуться оригинала) и каким-то образом выполнить более быструю сортировку, чем std ::сортировать (сортировка занимает слишком много времени).

Редактировать:

Извините всех.Я хотел сказать, что я создаю std :: map, где ключ long, а значение int.Длинное значение - это ключевое значение структуры, а int - это индекс соответствующего элемента в векторе.

Кроме того, я сделал еще одну отладку и понял, что вектор вообще не отсортирован.Это совершенно случайно.Так что делать что-то вроде stable_sort не получится.

ДРУГОЕ ОБНОВЛЕНИЕ:

Спасибо всем за ответы.В итоге я создал вектор пар (std :: vector из std :: pair (long, int)).Затем я отсортировал вектор по длинному значению.Я создал собственный компаратор, который смотрел только на первую часть пары.Затем я использовал lower_bound для поиска пары.Вот как я все это сделал:

  typedef std::pair<long,int> Key2VectorIndexPairT;
  typedef std::vector<Key2VectorIndexPairT> Key2VectorIndexPairVectorT;

  bool Key2VectorIndexPairComparator(const Key2VectorIndexPairT& pair1, const Key2VectorIndexPairT& pair2)
  {
      return pair1.first < pair2.first;
  }

  ...

  Key2VectorIndexPairVectorT sortedVector;
  sortedVector.reserve(originalVector.capacity());

  // Assume "original" vector contains unsorted elements.
  for (int i = 0; i < originalVector.size(); ++i)
  {
      const TheStruct& theStruct = originalVector[i];
      sortedVector.insert(Key2VectorIndexPairT(theStruct.key, i));
  }

  std::sort(sortedVector.begin(), sortedVector.end(), Key2VectorIndexPairComparator);

  ...

  const long keyToSearchFor = 20;

  const Key2VectorIndexPairVectorT::const_iterator cItorKey2VectorIndexPairVector = std::lower_bound(sortedVector.begin(), sortedVector.end(), Key2VectorIndexPairT(keyToSearchFor, 0 /* Provide dummy index value for search */), Key2VectorIndexPairComparator);

  if (cItorKey2VectorIndexPairVector->first == keyToSearchFor)
  {
      const int vectorIndex = cItorKey2VectorIndexPairVector->second;
      const TheStruct& theStruct = originalVector[vectorIndex];

      // Now do whatever you want...
  }
  else
  {
      // Could not find element...
  }

Это принесло мне скромный прирост производительности.Раньше общее время моих вычислений составляло 3,75 миллисекунды, а теперь оно сократилось до 2,5 миллисекунд.

Answer 1

И std :: map, и std :: set построены на двоичном дереве, поэтому при добавлении элементов происходит динамическое распределение памяти.Если ваша карта в значительной степени статична (то есть инициализируется один раз в начале, а затем редко или никогда не добавляет или удаляет новые элементы), вам, вероятно, будет лучше использовать отсортированный вектор и std :: lower_bound для поиска элементов с помощью бинарного поиска.

Answer 2

Карты занимают много времени по двум причинам

• Вам необходимо выделить много памяти для хранения данных
• Для сортировки необходимо выполнить O (n lg n) сравнений.

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

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

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

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

Answer 3

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

Очевидно, что профилирование может помочь вам точно определить проблему.

Я бы предложил в качестве общей идеи простоскопируйте нужные данные long / int в другой вектор и, поскольку вы сказали, что они почти отсортированы, используйте для этого команду stable_sort, чтобы завершить упорядочивание.Затем используйте lower_bound, чтобы найти элементы в отсортированном векторе.

Answer 4

Создание карты может быть узким местом в производительности (в том смысле, что это занимает измеримое время), если вы создаете большую карту и копируете в нее большие куски данных.Вы также используете очевидный (но неоптимальный) способ вставки элементов в std :: map - если вы используете что-то вроде:

myMap.insert(std::make_pair(theType.key, theType));

, это должно улучшить скорость вставки, но это приведет кнебольшое изменение в поведении, если вы встретите дубликаты ключей - использование insert приведет к удалению значений дубликатов ключей, тогда как при использовании вашего метода последний элемент с дубликатом ключа будет вставлен в карту.

IТакже следует избегать создания копии данных (например, путем сохранения указателя на них), если ваши результаты профилирования определяют, что копирование элемента является дорогостоящим.Но для этого вам придется профилировать код, предположения IME, как правило, ошибочны ...

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

Answer 5

Если ключи сплошные и короткие, возможно, вместо этого попробуйте std::hash_map. Со страницы MSDN на hash_map Class :

Основным преимуществом хеширования перед сортировкой является большая эффективность; успешное хеширование выполняет вставки, удаления и находит в постоянное среднее время по сравнению со временем, пропорциональным логарифм количества элементов в контейнере для сортировки методы.

Answer 6

std :: find - это линейное сканирование (должно быть, поскольку оно работает с несортированными данными).Если вы можете сортировать (std :: sort гарантирует поведение n log (n)) данных, тогда вы можете использовать std :: binary_search для получения запросов log (n).Но, как отмечают другие, проблема может быть в копировании.

Answer 7

Спасибо всем за ответы. В итоге я создал вектор пар (std :: vector из std :: pair (long, int)). Затем я отсортировал вектор по длинному значению. Я создал собственный компаратор, который смотрел только на первую часть пары. Затем я использовал lower_bound для поиска пары. Вот как я все это сделал:

      typedef std::pair<long,int> Key2VectorIndexPairT;
      typedef std::vector<Key2VectorIndexPairT> Key2VectorIndexPairVectorT;

      bool Key2VectorIndexPairComparator(const Key2VectorIndexPairT& pair1, const Key2VectorIndexPairT& pair2)
      {
          return pair1.first < pair2.first;
      }

      ...

      Key2VectorIndexPairVectorT sortedVector;
      sortedVector.reserve(originalVector.capacity());

      // Assume "original" vector contains unsorted elements.
      for (int i = 0; i < originalVector.size(); ++i)
      {
          const TheStruct& theStruct = originalVector[i];
          sortedVector.insert(Key2VectorIndexPairT(theStruct.key, i));
      }

      std::sort(sortedVector.begin(), sortedVector.end(), Key2VectorIndexPairComparator);

      ...

      const long keyToSearchFor = 20;

      const Key2VectorIndexPairVectorT::const_iterator cItorKey2VectorIndexPairVector = std::lower_bound(sortedVector.begin(), sortedVector.end(), Key2VectorIndexPairT(keyToSearchFor, 0 /* Provide dummy index value for search */), Key2VectorIndexPairComparator);

      if (cItorKey2VectorIndexPairVector->first == keyToSearchFor)
      {
          const int vectorIndex = cItorKey2VectorIndexPairVector->second;
          const TheStruct& theStruct = originalVector[vectorIndex];

          // Now do whatever you want...
      }
      else
      {
          // Could not find element...
      }

Это дало мне скромный прирост производительности. Раньше общее время моих вычислений составляло 3,75 миллисекунды, а сейчас оно сократилось до 2,5 миллисекунд.

Answer 8

Я думаю, у тебя есть другая проблема. Создание вектора из 1500 <long, int> пар и сортировка его по длинным значениям должно занять значительно меньше 0,8 миллисекунд (по крайней мере, если предположить, что мы говорим о достаточно современном процессоре типа настольный компьютер / сервер).

Чтобы попытаться понять, что мы должны увидеть здесь, я сделал небольшой тестовый код:

#include <vector>
#include <algorithm>
#include <time.h>
#include <iostream>

int main() {

    const int size = 1500;
    const int reps = 100;

    std::vector<std::pair<long, int> > init;
    std::vector<std::pair<long, int> > data;
    long total = 0;

    // Generate "original" array
    for (int i=0; i<size; i++)
        init.push_back(std::make_pair(rand(), i));

    clock_t start = clock();
    for (int i=0; i<reps; i++) {
        // copy the original array
        std::vector<std::pair<long, int> > data(init.begin(), init.end());
        // sort the copy
        std::sort(data.begin(), data.end());

        // use data that depends on sort to prevent it being optimized away
        total += data[10].first;
        total += data[size-10].first;
    }
    clock_t stop = clock();

    std::cout << "Ignore: " << total << "\n";

    clock_t ticks = stop - start;
    double seconds = ticks / (double)CLOCKS_PER_SEC;
    double ms = seconds * 1000.0;
    double ms_p_iter = ms / reps;

    std::cout << ms_p_iter << " ms/iteration.";
    return 0;
}

Запустив это на моей «продвинутой» (~ 5-летней) машине, я получаю время около 0,1 мс / итерация. Я ожидаю, что поиск в этом (используя std::lower_bound или std::upper_bound) будет несколько быстрее, чем поиск в std::map (поскольку данные в векторе размещаются непрерывно, мы можем ожидать лучшую локальность ссылок, что приведет к для лучшего использования кэша).

Answer 9

Вы строите копию таблицы из неработающего примера, который вы даете, а не просто ссылку.

Почему я не могу хранить ссылки на карте STL в C ++?

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

typedef vector<Type> Stuff;
Stuff myVector;
    typedef std::map<long, *Type> LookupMap;
    LookupMap myMap;
    LookupMap::iterator hint = myMap.begin();

    for (Stuff::iterator it = myVector.begin(); myVector.end() != it; ++it)
    {
        hint = myMap.insert(hint, std::make_pair(it->key, &*it));
    }

Или, возможно, отбросить вектор и просто сохранить его на карте ??

Answer 10

Поскольку ваш вектор уже частично упорядочен, вы можете вместо этого создать вспомогательный массив, ссылающийся на (индексы) элементов в вашем исходном векторе.Затем вы можете отсортировать вспомогательный массив, используя Timsort , который имеет хорошую производительность для частично отсортированных данных (таких как ваши).