Есть следующий код, состоящий из двух частей
Часть первая:

typedef std::vector< std::pair<int, int> > TVector;

// на этапе создания вектора мы знаем предварительный размер, который как правило больше реального
TVector Vector;
Vector.reserve(PrereservedAmount);;

// заполняем Vector несколькими десятками тысяч элементов (в том числе и повторяющимися) методом циклического добавления содержимого небольшого вектора
Vector.insert(some_Vector.begin(), some_Vector.end());

и вторая:

// сортируем вектор
std::sort(Vector.begin(), Vector.end());
// на выходе нужна отсортированая последовательность уникальных элементов
TVector::iterator EndOfUniqueRange = std::unique(Vector.begin(), Vector.end());

В результате регулярное добавление занимает ~15% времени выполнения, сортировка ~60%.
Какие можно предпринять шаги чтобы ускорить все это хозяйство?

спасибо

Здравствуйте, ser_gunya, Вы писали:

_>В результате регулярное добавление занимает ~15% времени выполнения, сортировка ~60%.
_>Какие можно предпринять шаги чтобы ускорить все это хозяйство?

Для однозначного ответа маловато информации, да и все равно нужно экспериментировать.
Могу привести несколько вариантов:
1. std::set вместо вектора
2. inplace_merge вместо std::sort
3. tbb::parallel_sort вместо std::sort
4. своя реализация некоторой структуры данных вместо вектора(какая именно — зависит от характера данных)
5. свяо реализация сортировки, которая может заодно и unique сделать.

Здравствуйте, Sergey Chadov, Вы писали:

SC>Для однозначного ответа маловато информации, да и все равно нужно экспериментировать.
могу дать любую информацию
SC>Могу привести несколько вариантов:
SC>1. std::set вместо вектора
сет работает дольше, как и список и очередь (при аналогичном использовании).
я даже пробовал поддерживать вектор постоянно сортированным и добавлять в него новые данные методом бинарного поиска, но все равно медленнее
все таки сортировать один раз быстрее
SC>2. inplace_merge вместо std::sort
не пользовался inplace_merge. если я правильно понял, нужно иметь две отсортированые последовательности, т.е поддерживать эти последовательности отсортированными?
SC>3. tbb::parallel_sort вместо std::sort
Я так понимаю это интеловская библиотека!?
к сожалению есть ограничение — можно использовать только буст и стл
SC>4. своя реализация некоторой структуры данных вместо вектора(какая именно — зависит от характера данных)
тип данных я привел в примере, это std::vector< std::pair<int, int> >.
если ли смысл переписывать отператор меньше для std::pair<int, int>?
SC>5. свяо реализация сортировки, которая может заодно и unique сделать.
unique занимет немного времени, главная проблема это сортировка

Здравствуйте, ser_gunya, Вы писали:


SC>>1. std::set вместо вектора
_>сет работает дольше, как и список и очередь (при аналогичном использовании).
А если скормить ему нестандартный аллокатор? например, бустовский?
Можно написать свой сет, который за счет знания конкретного типа и распределения данных будет работать быстрее.

SC>>2. inplace_merge вместо std::sort
_>не пользовался inplace_merge. если я правильно понял, нужно иметь две отсортированые последовательности, т.е поддерживать эти последовательности отсортированными?
нужно сортировать только вставляемый вектор, что модно сделать быстро, поскольку он маленького размера. Большая последовательность получится отсортированной по построению. Будет ли быстрее — фиг знает, надо проверять. Скорее всего нет, но прпробовать стоит.

SC>>3. tbb::parallel_sort вместо std::sort
_>Я так понимаю это интеловская библиотека!?
_>к сожалению есть ограничение — можно использовать только буст и стл
Можно свою написать по мотивам. Идея в том, чтобы распараллелить.

SC>>4. своя реализация некоторой структуры данных вместо вектора(какая именно — зависит от характера данных)
_>тип данных я привел в примере, это std::vector< std::pair<int, int> >.
Тип не так важен. Важно статистическое распределение данных. В литературе описываются случаи, когда перемешивание элементов массива перед сортировкой поднимало общее быстродействие

_>если ли смысл переписывать отператор меньше для std::pair<int, int>?
никакого

SC>>5. свяо реализация сортировки, которая может заодно и unique сделать.
_>unique занимет немного времени, главная проблема это сортировка
Возможно, имеет смысл поменять что-нибудь в том месте, где эти данные используются, то есть вместо сортировки использовать какой-нибудь более простой алгоритм разбиения, а досортировывать по мере необходимости.

Здравствуйте, ser_gunya, Вы писали:

_>В результате регулярное добавление занимает ~15% времени выполнения, сортировка ~60%.
_>Какие можно предпринять шаги чтобы ускорить все это хозяйство?

Ну как бы никакая сортировка принципиально не может быть быстрее O(n). Поэтому реальный способ ускориться — уменьшить количество элементов.
Первый путь к уменьшению — отбросить повторы. Как именно — смотреть надо, вначале на структуру входных данных.
Вторая идея произрастает из вопроса — а зачем надо (и надо ли? — тоже вопрос) иметь уникальную последовательность? и можно ли из входных данных придти к решению задачи без сортировки.

У меня тоже однажды была задача по выделению уникальных из порядка десятка миллионов элементов, где уникальных было на два порядка меньше. std::sort я использовать не мог по особенностям задачи. Двоичный поиск и формирование сортированного элемента работали медленно. При детальном анализа оказалось, что 95% времени занимает memmove — когда при вставке элемента сдвигается часть массива.
Решена задача была так: у меня была возможность очень быстро посчитать hash элемента. Затем, вместо одного вектора я взял N векторов. Каждый элемент по своему хэшу (hash_value % N) однозначно направлялся в один из векторов. И там уже вставка (а заодно и поиск) работала кардинально быстрее. Экспериментально было установлено, что для моего случая лучше всего иметь порядка 200 векторов и время решения задачи в целом сократилось в 10-15 раз.

Может у Вас что-то подобное?

Здравствуйте, ser_gunya, Вы писали:

_>В результате регулярное добавление занимает ~15% времени выполнения, сортировка ~60%.
_>Какие можно предпринять шаги чтобы ускорить все это хозяйство?

1. Если массив нужен не динамический то можно использовать array из boost.
2. Определить оператор <

Здравствуйте, ser_gunya, Вы писали:

SC>>1. std::set вместо вектора
_>сет работает дольше, как и список и очередь (при аналогичном использовании).
_>я даже пробовал поддерживать вектор постоянно сортированным и добавлять в него новые данные методом бинарного поиска, но все равно медленнее
_>все таки сортировать один раз быстрее

сет в качестве побочного действия неявно выполняет действия аналогичные std::sort и std::uniqe. Поэтому на выходе из сета будет то, что тебе надо.
А про ускорение сортировки — тут есть ограничение: никакая сортировка основанная на сравнениях не может быть быстрее О(n*lg n).

Хотя так как к тебя на входе числа, то можно попробовать заимплементить сортировку не основанную на сравнениях, что даст тебе порядок O(n), помидитируй на тему Counting Sort

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

Кстати, как я понимаю, есть только два разумных варианта получения вектора уникальных значений
1 — после заполнения вектора отсортировать перед вызовом std::unique
2 — в процессе заполнения вектора проверять на уникальность (что можно сделать только поддерживая вектор в сортированном состоянии, иначе будет очень медленно)

остальное все лишь производные этих двух методов, я прав?

Здравствуйте, ser_gunya, Вы писали:

_>Кстати, как я понимаю, есть только два разумных варианта получения вектора уникальных значений
_>1 — после заполнения вектора отсортировать перед вызовом std::unique
_>2 — в процессе заполнения вектора проверять на уникальность (что можно сделать только поддерживая вектор в сортированном состоянии, иначе будет очень медленно)

_>остальное все лишь производные этих двух методов, я прав?

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

Здравствуйте, ser_gunya, Вы писали:

Первая точка ускорения: заменить pair<int,int> на целочисленный тип, вмещающий в себя все реально существующие пары чисел.
Это может быть и __int64, и даже сам по себе int — если фактические диапазоны не вылезают из sqrt(INT_MAX).

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

Здравствуйте, ser_gunya, Вы писали:

_>В результате регулярное добавление занимает ~15% времени выполнения, сортировка ~60%.
_>Какие можно предпринять шаги чтобы ускорить все это хозяйство?

А почему бы Вам не использовать std::map<int, int> для того что бы всегда иметь отсортированные данные?

Для добавления каждого нового элемента потребуется О(Log(N)), где N — количество элементов внутри мэпа.
За то они всегда будут отсортированы, и всё что нужно для того что бы создать отсортированый список уникалов это — пробежаться от begin() до end() по мэпу, с проверкой двух соседних элементов на неравенство, за O(N).

скажем так...

    map<int, int> sorted_map;

    for (int i = 0; i < 10000; i++) {
        //генерируем новый элемент
        int new_val = rand(); 
        //добавляем в мэп
        sorted_map.insert(pair<int,int>(new_val, new_val)); 
        //если нужно выделить уникалов? определяется случайно...
        if (i && rand() % 100 == 0) { 
            map<int, int>::iterator it = sorted_map.begin(); 
            int prev_val = it->second; //сохраняем предидущий
            printf("%d ");
            //бежим по мэпу
            for (it++; it != sorted_map.end(); it++) { 
                //проверяем с предидущим 
                if (it->second != prev_val) { 
                    printf("%d ", it->second); //принтим уникальный элемент        
                    prev_val = it->second; //сохраняем предидущий
                }
            }
            printf("\r\n");
        }
    }