std::set::find медленней std::set::insert - C/C++

задача: в массиве найти первое повторяющееся значение.

#include <set>
#include <iostream>
#include <windows.h>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    int *arr = new int[3000000];
    for (int i = 0; i < 3000000; i++)
    {
        if (i == 1000000)
        {
            arr[i] = i - 1;
            continue;
        }
        arr[i] = i;
    }
    set<int>*uinarr = new set<int>();
    size_t set_size = 0;
    DWORD start = ::GetTickCount();
    for (int j = 0; j < 3000000; j++)
    {
        //вариант №1
        /*if (uinarr->find(arr[j]) != uinarr->end())
        {
            cout<<set_size<<"; "<<arr[j]<<endl;
            break;
        }
        uinarr->insert(arr[j]);*/
        
        //вариант №2
        uinarr->insert(arr[j]);
        if (set_size == uinarr->size())
        {
            cout<<set_size<<"; "<<arr[j]<<endl;
            break;
        }
        set_size = uinarr->size();
    }
    DWORD stop = ::GetTickCount() - start;
    cout<<"time:"<<stop<<endl;
    delete uinarr;
    delete []arr;
    system("pause");
    return 0;
}

1-й вариант ~2125 мс
2-й вариант ~1096 мс
почему 1-й вариант работает медленней?
Параллельный вопрос: как ускорить удаление std::set ? предварительное set::clear() ускорения не дает

Здравствуйте, Аноним, Вы писали:
А>1-й вариант ~2125 мс
А>2-й вариант ~1096 мс
А>почему 1-й вариант работает медленней?
Очевидно потому, что в первом варианте используется и find и insert.

А>Параллельный вопрос: как ускорить удаление std::set ? предварительное set::clear() ускорения не дает
Отказаться от использования std::set — поставленную задачу можно решить и без него.

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

B>Очевидно потому, что в первом варианте используется и find и insert.
ах тыж.. кто бы мог подумать
спасибо за открытие глаз

B>Отказаться от использования std::set — поставленную задачу можно решить и без него.
таким же объемом кода?

Здравствуйте, Аноним, Вы писали:

А>        uinarr->insert(arr[j]);
А>        if (set_size == uinarr->size())
А>        {
А>            cout<<set_size<<"; "<<arr[j]<<endl;
А>            break;
А>        }
А>        set_size = uinarr->size();

Sheetcode detected

std::set

_Pairib insert(const value_type& _Val)

возвращает пару где first — iterator на элемент, second — true\false в зависимости вставили или нет.

Здравствуйте, Аноним, Вы писали:

B>>Очевидно потому, что в первом варианте используется и find и insert.
А>ах тыж.. кто бы мог подумать
А>спасибо за открытие глаз
На здоровье.

B>>Отказаться от использования std::set — поставленную задачу можно решить и без него.
А>таким же объемом кода?

    sort(arr, arr+3000000);
    for (int j = 1; j < 3000000; j++)
    {
       if(arr[j-1] == arr[j])
       {
          cout<<j<<"; "<<arr[j]<<endl;
          break;
       }
    }

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

IRO>Здравствуйте, Аноним, Вы писали:

IRO>

А>>        uinarr->insert(arr[j]);
А>>        if (set_size == uinarr->size())
А>>        {
А>>            cout<<set_size<<"; "<<arr[j]<<endl;
А>>            break;
А>>        }
А>>        set_size = uinarr->size();
IRO>

IRO>Sheetcode detected

IRO>std::set

IRO>_Pairib insert(const value_type& _Val)

IRO>возвращает пару где first — iterator на элемент, second — true\false в зависимости вставили или нет.
IRO>

оно красивей, но по скорости сравнимо с 1-м вариантом

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

B>

B>    sort(arr, arr+3000000);
      if(adjacent_find(arr, arr+3000000) != arr+3000000)
B>    {
B>          cout<<j<<"; "<<arr[j]<<endl;
B>          break;
B>    }
B>

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

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

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

B>>

B>>    sort(arr, arr+3000000);
К>      if(adjacent_find(arr, arr+3000000) != arr+3000000)
B>>    {
B>>          cout<<j<<"; "<<arr[j]<<endl;
B>>          break;
B>>    }
B>>

К>

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

B>>>Отказаться от использования std::set — поставленную задачу можно решить и без него.
А>>таким же объемом кода?

B>

B>    sort(arr, arr+3000000);
B>    for (int j = 1; j < 3000000; j++)
B>    {
B>       if(arr[j-1] == arr[j])
B>       {
B>          cout<<j<<"; "<<arr[j]<<endl;
B>          break;
B>       }
B>    }
B>

И как этот алгоритм найдет повтор в такой последовательности?

1,2,3,2,4

З.Ы. а ведь условию не противоречит

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

B>>

B>>    sort(arr, arr+3000000);
B>>    for (int j = 1; j < 3000000; j++)
B>>    {
B>>       if(arr[j-1] == arr[j])
B>>       {
B>>          cout<<j<<"; "<<arr[j]<<endl;
B>>          break;
B>>       }
B>>    }
B>>

IRO>И как этот алгоритм найдет повтор в такой последовательности?

IRO>1,2,3,2,4

IRO>

IRO>З.Ы. а ведь условию не противоречит

Смотрим выделенный косочек

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

B>Здравствуйте, IROV.., Вы писали:

B>Смотрим выделенный косочек

1) 7, 7, 1, 2, 2

2) 2, 7, 7, 1, 2

Твой алгоритм выведет 2, а нужно 7.

Не зачет!

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

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

B>>Здравствуйте, IROV.., Вы писали:

B>>Смотрим выделенный косочек

IRO>1) 7, 7, 1, 2, 2

IRO>2) 2, 7, 7, 1, 2

IRO>Твой алгоритм выведет 2, а нужно 7.

IRO>Не зачет!

А давай спросим у топикастера — что ему больше нравиться?

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

B>А давай спросим у топикастера — что ему больше нравиться?

задача: в массиве найти первое повторяющееся значение.

Нравиться, не нравится, есть задача!

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

IRO>Нравиться, не нравится, есть задача!

Сдаюсь, недосмотрел

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

IRO>Нравиться, не нравится, есть задача!

— сращиваем массив значений с последовательностью номеров [0,1,2..]
— делаем квиксорт этого массива пар по значениям (если делать по парам значение-номер, то получим стабильный квиксорт, но это для нас необязательно)
— пробегаем по элементам, обращая внимание только на равенство значений смежных элементов, и запоминаем минимальный номер
Если квиксорт стабильный, то нам даже ещё и проще: в каждой подпоследовательности смежно-равных элементов минимальный номер — у первого в подпоследовательности.

Итого, O(n) дополнительной памяти и O(n log n) времени (две линейных операции — зип и поиск, и один квиксорт).

А можно подумать насчёт самого быстрого в мире алгоритма... Какие-нибудь отсечки в квиксорте сделать; распознавать эквивалентные элементы на стадии разбивания, и тут же получать номера; ну и т.д...

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

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

К>Здравствуйте, IROV.., Вы писали:

IRO>>Нравиться, не нравится, есть задача!

К>- сращиваем массив значений с последовательностью номеров [0,1,2..]
К>- делаем квиксорт этого массива пар по значениям (если делать по парам значение-номер, то получим стабильный квиксорт, но это для нас необязательно)
К>- пробегаем по элементам, обращая внимание только на равенство значений смежных элементов, и запоминаем минимальный номер
К>Если квиксорт стабильный, то нам даже ещё и проще: в каждой подпоследовательности смежно-равных элементов минимальный номер — у первого в подпоследовательности.

К>Итого, O(n) дополнительной памяти и O(n log n) времени (две линейных операции — зип и поиск, и один квиксорт).

К>

К>А можно подумать насчёт самого быстрого в мире алгоритма... Какие-нибудь отсечки в квиксорте сделать; распознавать эквивалентные элементы на стадии разбивания, и тут же получать номера; ну и т.д...

А чем сортировка деревом не устраивает? Стабильная в отличие от квиксорт и, возможно, неполная.

... << RSDN@Home 1.2.0 alpha 4 rev. 1144>>

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

S>А чем сортировка деревом не устраивает? Стабильная в отличие от квиксорт и, возможно, неполная.

В смысле, сортировка деревом? Пирамидальная, что ли?

sort_heap
Она вдвое медленнее средней скорости квиксорта (понятно, что если квиксорт на плохом наборе вырождается в пузырёк, то хипсорт, который не вырождается, его обгонит).
Стабильность (сохранение естественного порядка эквивалентных элементов) нам, по большому счёту, не нужна.

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

А если ты имеешь в виду сортировку в древовидных контейнерах (тот же set), то мы платим памятью и скоростью за возможность мгновенной остановки.
Тут многое зависит от характера наборов данных.
Скажем, если среди этих 12000 элементов есть 1-2 дубликата, то квиксорт+сканирование может оказаться быстрее построения дерева.
А если там 1200 дубликатов — то быстрая остановка (в алгоритме с деревом) нам очень пригодится.

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

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

К>В смысле, сортировка деревом? Пирамидальная, что ли?
Я имел в виду именно сортировку бинарным деревом с перебалансировкой (например, set).

К>sort_heap
К>Она вдвое медленнее средней скорости квиксорта (понятно, что если квиксорт на плохом наборе вырождается в пузырёк, то хипсорт, который не вырождается, его обгонит).
К>Стабильность (сохранение естественного порядка эквивалентных элементов) нам, по большому счёту, не нужна.
Стабильность — это я неправильно выразился, имел в виду устойчивость по скорости.

К>make_heap
К>Не только не упорядочивает, но даже не позволяет быстро находить эквивалентные элементы. Они оказываются раскиданы по пирамиде произвольным образом, зависящим, в том числе, от порядка заполнения.

К>А если ты имеешь в виду сортировку в древовидных контейнерах (тот же set), то мы платим памятью и скоростью за возможность мгновенной остановки.
Памятью — да, платим, хотя те же O(n). Причем можем выбирать — выделить сразу или в порядке надобности в надежде на быстрый результат. А вот насчёт скорости — это вопрос. Для quicksort время может достигать O(n^2). А дерево дайт стабильную оценку O(n log n) + сортировка прерывается при нахожденнии элемента.

К>Тут многое зависит от характера наборов данных.
К>Скажем, если среди этих 12000 элементов есть 1-2 дубликата, то квиксорт+сканирование может оказаться быстрее построения дерева.
К>А если там 1200 дубликатов — то быстрая остановка (в алгоритме с деревом) нам очень пригодится.
Согласен, но дерево выглядит предпочтительней в качестве универсального решения.

... << RSDN@Home 1.2.0 alpha 4 rev. 1144>>

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

К>>А если ты имеешь в виду сортировку в древовидных контейнерах (тот же set), то мы платим памятью и скоростью за возможность мгновенной остановки.
S>Памятью — да, платим, хотя те же O(n). Причем можем выбирать — выделить сразу или в порядке надобности в надежде на быстрый результат. А вот насчёт скорости — это вопрос. Для quicksort время может достигать O(n^2). А дерево дайт стабильную оценку O(n log n) + сортировка прерывается при нахожденнии элемента.

Вместо квиксорта возьми хипсорт — он устойчив по скорости. Хотя и вдвое медленнее квика на хорошем наборе.

Коэффициенты при асимптотике несколько разные

Как при времени, так и при скорости.
Алгоритмы с сортировкой на месте требуют массив из N индексов (который, собственно, подвергается сортировке) и хитрый доступ; либо массив из N пар (значение,индекс) — доступ быстрее, обмены дороже, памяти вдвое больше.

Каждый узел дерева — это значение, три указателя и флажок. Хороший аллокатор позволит экономно расходовать кучу, но ты его сперва ещё сделай, этот аллокатор...

К>>Тут многое зависит от характера наборов данных.
К>>Скажем, если среди этих 12000 элементов есть 1-2 дубликата, то квиксорт+сканирование может оказаться быстрее построения дерева.
К>>А если там 1200 дубликатов — то быстрая остановка (в алгоритме с деревом) нам очень пригодится.
S>Согласен, но дерево выглядит предпочтительней в качестве универсального решения.

Алюминиевая пуля?

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

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

К>Здравствуйте, IROV.., Вы писали:

IRO>>Нравиться, не нравится, есть задача!

std::inplace_merge
std::binary_search

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

скорость была на порядок меньше

З.Ы. завтра могу выложить пример

	От:	Аноним
	Дата:	19.08.09 07:02
	Оценка:

	От:	Bell
	Дата:	19.08.09 07:21
	Оценка:

	От:	Аноним
	Дата:	19.08.09 07:29
	Оценка:

	От:	IROV..
	Дата:	19.08.09 07:44
	Оценка:

	От:	Bell
	Дата:	19.08.09 07:46
	Оценка:

	От:	Кодт
	Дата:	20.08.09 11:23
	Оценка:

	От:	sokel
	Дата:	20.08.09 13:14
	Оценка:

	От:	Кодт
	Дата:	20.08.09 14:03
	Оценка:

	От:	sokel
	Дата:	20.08.09 14:37
	Оценка: