Загрузка набора STL с предварительно отсортированными данными, C ++ - PullRequest
Новая
       18

Загрузка набора STL с предварительно отсортированными данными, C ++

5 голосов
/ 23 марта 2011

Я работаю с C ++ в Visual Studio 2010. У меня есть набор STL, который я сохраняю в файл, когда моя программа закрывается. При следующем запуске программы я загружаю (отсортированные) данные обратно в набор. Я пытаюсь оптимизировать процесс загрузки, и у меня возникли проблемы. Я подозреваю, что проблема в частой перебалансировке, и я ищу способ избежать этого.

Сначала я сделал это без оптимизации, используя "set-> insert (const value_type & x)"

Время: ~ 5,5 минут

Затем я попытался использовать версию insert (), где вы указываете подсказку для местоположения вставки (): 

iterator insert ( iterator position, const value_type& x );

Грубо говоря, я сделал это: 

set<int> My_Set;
set<int>::iterator It;
It = My_Set.insert (0);
for (int I=1; I<1000; I++) {
   It = My_Set.insert (It, I);  //Remember the previous insertion's iterator
   }

Время: ~ 5,4 минуты

Едва ли улучшения! Я не думаю, что проблема заключается в накладных расходах при чтении из файла - комментирование insert () сокращает время до 2 секунд. Я не думаю, что проблема заключается в накладных расходах при копировании моего объекта - это объект Plain Old Data с int и char.

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

1.) Согласны ли вы с моим предположением?

2.) Есть ли способ «приостановить» перебалансировку, пока я загружаю набор, и затем перебалансировать один раз в конце? (Или ... Это даже поможет?)

3.) Есть ли более разумный способ загрузки отсортированных данных, то есть не просто переход от низшего к высшему? Возможно, чередуя мои вставки, чтобы не приходилось часто балансировать? (Пример: вставить 1, 1000, 2, 999, 3, 998, ...)

Ответы [ 3 ]

6 голосов
/ 24 марта 2011

Сколько элементов мы говорим?

Я сделал короткий тест с 10.000.000 целых чисел (подготовленных в векторе) и вставил их тремя разными способами в набор.

Подготовить ввод: 

  std::vector<int> input;
  for(int i = 0; i < 10*1000*1000; ++i) {
     input.push_back(i);
  }

Вставить в заданный элемент за элементом со вставкой:

Выпуск: 2,4 секунды / Отладка: 110,8 секунды 

  std::set<int> mySet;
  std::for_each(input.cbegin(), input.cend(), [&mySet] (int value) {
     mySet.insert(value);
  });

Вставить в набор с помощью insert(itBegin, itEnd):

Выпуск: 0,9 секунд / Отладка: 47,5 секунд 

  std::set<int> mySet;
  mySet.insert(input.cbegin(), input.cend());

  // this is also possible - same execution time:
  std::set<int> mySet(input.cbegin(), input.cend());

Таким образом, вставка может быть сильно ускорена, но даже медленный путь должен быть далек от нескольких минут.

EDIT:

Между тем я провел тест в режиме отладки - вау - я знаю производительность отладки, но это больше, чем я думал. С 50.000.000 элементов в режиме отладки происходит неправильное распределение, поэтому я обновил свой пост до 10.000.000 элементов и показал время для выпуска и отладки сборки.

Здесь можно увидеть огромные различия - в 50 раз быстрее решение.

Кроме того, быстрое решение (insert(itBegin, itEnd)) кажется линейным по отношению к количеству элементов (с предварительно отсортированными данными!). В предыдущем тесте было в пять раз больше элементов, а время вставки сократилось с 4,6 до 0,9 - примерно в пять раз.

2 голосов
/ 23 марта 2011

Вы пробовали конструктор диапазонов? 

#include <set>
#include <fstream>
#include <algorithm>
#include <iterator>

int main()
{
    std::ifstream  file("Plop");

    std::set<int>   myset;

    std::copy(std::istream_iterator<int>(file),
              std::istream_iterator<int>(),
              std::inserter(myset, myset.end()));
}

Пробовали 4 метода с [0 -> 10 000 000) элементов (отсортировано в файле): 

void t1(std::set<int>& data, std::istream& file)
{
    int x;
    while(file >> x)    {data.insert(x); }
}

void t2(std::set<int>& data, std::istream& file)
{
    int x;
    while(file >> x)    {data.insert(data.end(), x);}
}

void t3(std::set<int>& data, std::istream& file)
{
    std::set<int>::iterator it = data.begin();
    int x;
    while(file >> x)    {it = data.insert(it, x);}
}

void t4(std::set<int>& data, std::istream& file)
{
    std::copy(std::istream_iterator<int>(file),
              std::istream_iterator<int>(), 
              std::inserter(data, data.end()));
}

Время в часах ()среднее значение за 3 прогона (нормальное) и 3 прогона (-O4) 

                    Plain Data
           Normal              -O4
           =========           ========= 
t1 Result: 21057300            6748061
t2 Result:  6580081            4752549
t3 Result:  6675929            4786003
t4 Result:  8452749            6460603

Вывод 1: для отсортированных данных: 

Best:   data.insert(data.end(), <item>)  // Hint end()
Worst:  data.insert(<item>);             // No Hint

Вывод 2: Оптимизация рассчитывает.

1 голос
/ 23 марта 2011

Возможно, набор перебалансирован. Сколько предметов у вас действительно есть, что занимает 5,6 мин? Если ваш набор элементов достаточно велик, вы можете столкнуться с физическим ограничением ОЗУ и перегрузкой, или просто иметь очень плохие ошибки кэша.

Определенно нет способа отключить ребалансировку. Если бы вы могли, то множество могло бы сломать свои инварианты, что было бы плохо.

  • Получить профилировщик и профилировать свой код, а не догадываться, что занимает время.
  • Вы пробовали вставить два параметра, используя end вместо предыдущего итератора в качестве другой точки данных?
  • Вы пытались вставить вместо этого предварительно зарезервированный vector, чтобы сравнить время?
  • Можете ли вы избежать неприятностей с другим типом контейнера, таким как куча или (отсортированный) вектор?
  • Если вы можете быстро загрузить вектор, сделайте это, затем random_shuffle, затем попробуйте вставить его в набор и посмотреть, что произойдет.
...