Набор STL: вставьте два миллиона заказанных номеров наиболее эффективным способом - PullRequest
Новая
       21

Набор STL: вставьте два миллиона заказанных номеров наиболее эффективным способом

2 голосов
/ 19 октября 2010

Для следующей массовой вставки, поскольку входы упорядочены, есть какие-либо (небольшие) оптимизации? 

set<int> primes;
for ( int i = 2; i <= 2000000; i++ ) {
    primes.insert(i);
}
// then follows Sieve of Eratosthenes algorithm

Новое улучшение, в два раза быстрее: 

set<int> primes;
for ( int i = 2; i <= 2000000; i++ ) {
    primes.insert(primes.end(), i);
}
// then follows Sieve of Eratosthenes algorithm

Ответы [ 4 ]

7 голосов
/ 19 октября 2010

С http://www.cplusplus.com/reference/stl/set/set/

vector<int> numbers;
for (int i=2; i<=2000000; ++i)
    numbers.push_back(i);

set<int> primes(numbers.begin(), numbers.end());

Это должно иметь сложность O (n), где, как у вас, сложность O (n * log (n)).

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

Для чего-то более чистого я бы предпочел использовать итератор подсчета Boost.Это сокращает это до: 

set<int> primes(
    boost::counting_iterator<int>(0),
    boost::counting_iterator<int>(200000));
4 голосов
/ 19 октября 2010

Если вы начинаете с полного диапазона кандидатов int с, я бы вообще не использовал set, я бы использовал vector<bool>, инициализировал бы их все до false и отмечал бы цели ( простые числа) как true как они расположены. 

vector<bool> candidates(200000);

Вы можете индексировать это, используя текущего кандидата int - 1 (диапазон кандидатов = 1..200000). Затем выполните итерацию, используя find, чтобы найти истинные значения, преобразовав в int, используя смещение против begin().

  • Общее количество выделенных памяти - 1.
  • Общее использование памяти 25000 байт (vector<bool> - особый случай, см. Комментарий @Greg Rogers) против> = 800000 для set<int>, без учета накладных расходов BTree.
  • Доступ ко всем элементам осуществляется через арифметику указателей.
4 голосов
/ 19 октября 2010

Доступна перегруженная версия метода insert, который принимает итератор в качестве первого параметра. Этот итератор используется как подсказка, т. Е. Сравнение будет начинаться с этого итератора. Таким образом, если вы передадите правильный итератор в качестве подсказки, тогда у вас должна быть очень эффективная операция вставки в набор. Смотрите здесь для деталей. Я верю в вашем случае, numbers.end() -1 будет хорошим вариантом.

2 голосов
/ 19 октября 2010

Вот несколько:

  1. реализовать пользовательский распределитель stl, который резервирует память заранее.

  2. Если вы используете векторное решение, вызовите резерв.

  3. Если вы только собираетесь реализовать использование сита (или внедрить) итератор ускоренного счета и сохранить результаты только в векторе, который вызывает резерв. *

...