Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Помогите подобрать контейнер, для вставки в отсортированный 
V
    Опции темы
borisbn
Дата 14.2.2012, 15:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135
Здравствуйте.

Требуется контейнер для частой вставки элементов, причём вставляться они будут так, чтобы контейнер всегда оставался отсортированным. Я тут поэкспериментировал, и понял, что из тех, которые пришли на ум, быстрее всего вектор.
Код

const int N = 10000;

template< class container_t >
double countTime( const std::vector< typename container_t::value_type > & src, container_t & container ) {
    TimeMeasure t;
    for ( int i = 0, size = src.size(); i < size; i++ ) {
        typename container_t::iterator place = std::lower_bound( container.begin(), container.end(), src[ i ] );
        container.insert( place, src[ i ] );
    }
    return t.elapsed();
}

int main()
{
    std::list< int > list;
    std::deque< int > deque;
    std::vector< int > vector;

    std::vector< int > src;
    for ( int i = 0; i < N; i++ )
        src.push_back( rand() % N );

    std::cout << "list = " << countTime( src, list ) << " ms" << std::endl;
    std::cout << "deque = " << countTime( src, deque ) << " ms" << std::endl;
    std::cout << "vector = " << countTime( src, vector ) << " ms" << std::endl;
}

http://liveworkspace.org/code/8ed11be0bbbe...47c76ba9dca3821

рез-т у меня на компе (MSVC 2008 Release)
Цитата
list = 324 ms
deque = 211 ms
vector = 11 ms

рез-т на LWS
Цитата
list = 700 ms
deque = 40 ms
vector = 20 ms


Но, может есть что-то специализированное как раз для моего случая ? Что-нибудь бустовское ?

Спасибо.

P.S. Может подскажете ещё: почему студийный deque под release так медленнее minGW-шного, да ещё и под debug ???


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
newbee
Дата 14.2.2012, 15:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бревно
**


Профиль
Группа: Участник
Сообщений: 703
Регистрация: 24.8.2011

Репутация: 4
Всего: 19
RB-дерево попробуй. Результаты списка и очереди очень предсказуемы.


--------------------
You're face to face
With man who sold the world
PM   Вверх
borisbn
Дата 14.2.2012, 16:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135
Цитата(newbee @  14.2.2012,  15:33 Найти цитируемый пост)
RB-дерево попробуй

попробовал. добавил
Код

template< class T >double countTime( const std::vector< T > & src, std::set< T > & container ) {
    TimeMeasure t;
    for ( int i = 0, size = src.size(); i < size; i++ ) {
        container.insert( src[ i ] );
    }
    return t.elapsed();
}

http://liveworkspace.org/code/a69d6828ebcc...518bd39bdc11b9f

рез-ты на моём компе
Цитата
list = 323008 mks
deque = 211275 mks
vector = 11094 mks
set= 10991.3 ms


на LWS
Цитата
list = 700 ms
deque = 40 ms
vector = 20 ms
set= 30 ms


В общем большого преимущества не видно...
Видать, работа с вектором в (specially for newbee) библиотеке, функции которой начинаются с std::, вылизана дальше некуда.

Кто-нибудь что-нибудь подскажет ещё ?


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
newbee
Дата 14.2.2012, 16:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бревно
**


Профиль
Группа: Участник
Сообщений: 703
Регистрация: 24.8.2011

Репутация: 4
Всего: 19
Цитата(borisbn @  14.2.2012,  17:01 Найти цитируемый пост)
std::set< T > & container
std::set - это RB? Оно должно работать шустрее вектора... Теоретически. Для чистоты эксперемента попробуй вместо жалких 10к элементов использовать миллион.

Цитата(borisbn @  14.2.2012,  17:01 Найти цитируемый пост)
specially for newbee
Мммм))) К чему бы это?



--------------------
You're face to face
With man who sold the world
PM   Вверх
boostcoder
Дата 14.2.2012, 16:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110
странно... ожидал что множество будет быстрее..



--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
borisbn
Дата 14.2.2012, 16:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135
Цитата(newbee @  14.2.2012,  16:11 Найти цитируемый пост)
std::set - это RB?

ну... по-моему да.
Цитата(newbee @  14.2.2012,  16:11 Найти цитируемый пост)
Для чистоты эксперемента попробуй вместо жалких 10к элементов использовать миллион.

попробовал. у вектора 320 секунд, у сета - 321 секунда. Думаю, здесь уже играет роль выделение памяти, а не сам алгоритм...

Цитата(newbee @  14.2.2012,  16:11 Найти цитируемый пост)
Мммм))) К чему бы это?

не хочу напороться на
Цитата(newbee @  13.2.2012,  19:43 Найти цитируемый пост)
пока что ты демонстрируешь незнание вообще что такое STL

Цитата(newbee @  13.2.2012,  19:43 Найти цитируемый пост)
STL просто не предоставляет ни средств вывода, ни обощенных средств преобразования данных,

Цитата(newbee @  13.2.2012,  21:30 Найти цитируемый пост)
Я могу во второй раз предложить RTFM. Это на каждом углу написано. STD-C++ != STL.

it was a joke smile 
http://imagehost.spark-media.ru/i4/510C281...jpg/Sarcasm.jpg

Я, просто, всю жизнь считал, что раз вектор или какой нибудь алгоритм входит в стандартную (Standard) библиотеку (Library), и он - шаблонный (Template), то он входит в библиботеку STL...




--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
boostcoder
Дата 14.2.2012, 17:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110
borisbn, максимальный размер вектора известен?


--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
borisbn
Дата 14.2.2012, 17:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135
Вообще-то известно, что это - единицы тасяч. Поэтому я и остановился на векторе. Мне уже стало интересно дальше поисследовать. Просто на будущее.


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
boostcoder
Дата 14.2.2012, 17:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110
чичас. допилю.


--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
rumit7
Дата 14.2.2012, 17:31 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 71
Регистрация: 16.6.2011

Репутация: 6
Всего: 7
Цитата(borisbn @ 14.2.2012,  16:01)
Цитата(newbee @  14.2.2012,  15:33 Найти цитируемый пост)
RB-дерево попробуй

попробовал. добавил
Код

template< class T >double countTime( const std::vector< T > & src, std::set< T > & container ) {
    TimeMeasure t;
    for ( int i = 0, size = src.size(); i < size; i++ ) {
        container.insert( src[ i ] );
    }
    return t.elapsed();
}

http://liveworkspace.org/code/a69d6828ebcc...518bd39bdc11b9f

рез-ты на моём компе
Цитата
list = 323008 mks
deque = 211275 mks
vector = 11094 mks
set= 10991.3 ms


на LWS
Цитата
list = 700 ms
deque = 40 ms
vector = 20 ms
set= 30 ms


В общем большого преимущества не видно...
Видать, работа с вектором в (specially for newbee) библиотеке, функции которой начинаются с std::, вылизана дальше некуда.

Кто-нибудь что-нибудь подскажет ещё ?

А так?

Код

double countTimeHeap( const std::vector< int > & src, std::vector< int > & container )
{
    TimeMeasure t;
    for ( int i = 0, size = src.size(); i < size; i++ )
    {
        container.push_back(src[i]); 
        std::push_heap (container.begin(), container.end());
    }
    std::sort_heap (container.begin(), container.end());
    return t.elapsed();
}


http://liveworkspace.org/code/0cbb7270ae53...c9b917c20971e02

Добавлено через 8 минут и 38 секунд
Если N увеличить в 10 раз, то на моей тачке преимущество heap-версии достигает 70 раз, а в LWS порядка 10:

Цитата

deque = 3090 ms
vector = 1520 ms
set= 1510 ms
heap= 130 ms


http://liveworkspace.org/code/0b533d7ae5fd...396d48d17334786
PM MAIL   Вверх
borisbn
Дата 14.2.2012, 17:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135
Цитата(rumit7 @  14.2.2012,  17:31 Найти цитируемый пост)
А так?

а так нечестно... ты сортируешь после N вставок, а мне нужно иметь отсортированный вектор после каждой вставки.
да и потом, этот вариант ничем не отличается от

Код

template< class T >
double countTimeHeap( const std::vector< T > & src, std::vector< T > & container )
{
    TimeMeasure t;
    for ( int i = 0, size = src.size(); i < size; i++ )
    {
        container.push_back( src[i] ); 
    }
    std::sort( container.begin(), container.end() );
    return t.elapsed();
}


который, кстати, быстрее


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
rumit7
Дата 14.2.2012, 18:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 71
Регистрация: 16.6.2011

Репутация: 6
Всего: 7
Цитата(borisbn @ 14.2.2012,  17:46)
Цитата(rumit7 @  14.2.2012,  17:31 Найти цитируемый пост)
А так?

а так нечестно... ты сортируешь после N вставок, а мне нужно иметь отсортированный вектор после каждой вставки.
да и потом, этот вариант ничем не отличается от

Код

template< class T >
double countTimeHeap( const std::vector< T > & src, std::vector< T > & container )
{
    TimeMeasure t;
    for ( int i = 0, size = src.size(); i < size; i++ )
    {
        container.push_back( src[i] ); 
    }
    std::sort( container.begin(), container.end() );
    return t.elapsed();
}


который, кстати, быстрее

Вы уверены что в примере где Вы добавили std::set, это было сделано правильно? Там у Вас в LWS тип переменной set - std::vector< int >. 

И потом на мой взгляд правильнее использовать multiset. 

http://liveworkspace.org/code/836e3c80b699...5c7bda67fabca7b

Цитата

deque = 3130 ms
vector = 1530 ms
multiset= 70 ms
PM MAIL   Вверх
borisbn
Дата 14.2.2012, 18:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135
Цитата(rumit7 @  14.2.2012,  18:05 Найти цитируемый пост)
Вы уверены что в примере где Вы добавили std::set, это было сделано правильно?

господа, где здесь иконка "посыпаю себе голову пеплом и обещаю больше не пользоваться "прогрессивной" технологией копи/паст" ?

rumit7, спасибо большое, а то я уже перестал понимать, что происходит.
И, таки, да, конечно, правильно будет multiset.
Я, правда, проверил скорость обхода вектора и мультисета (тупо пройтись по всем и посчитать сумму) у вектора, ессно, быстрее, даже в 10 раз, но это ни в какое сравнение не идёт с разницей во вставке.
Цитата
vector = 1307.5 ms
multiset = 31.1316 ms
walk vector = 0.380822 ms
walk multiset = 3.42739 ms


ну, всё. rumit7, спасибо ещё раз. Закрываю

Добавлено через 9 минут и 48 секунд
Уууупсс... Забыл newbee поблагодарить. Она ж сразу сказала про Стендаля.
newbee, спасибо.

Добавлено через 11 минут и 22 секунды
boostcoder, и тебе, ессно, спасибо за то, что не верил, что я всё правильно делал smile
Цитата(boostcoder @  14.2.2012,  16:42 Найти цитируемый пост)
странно... ожидал что множество будет быстрее..

 smile 


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
boostcoder
Дата 15.2.2012, 09:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110
не. не получилось вектор ускорить...
зато unordered_multiset работает в двое быстрее multiset`а smile 
Код

#include <iostream>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <chrono>

const int N = 1000000; // million

template< class container_t >
auto countTime( const std::vector< typename container_t::value_type > & src,
   container_t & container ) -> std::chrono::microseconds
{
   auto start = std::chrono::system_clock::now();
   for ( auto idx = 0u, size = src.size(); idx < size; ++idx ) {
      container.insert( src[idx] );
   }
   return std::chrono::duration_cast<std::chrono::microseconds>(
      std::chrono::system_clock::now()-start
   );
}

template< class T >
auto countTime( const std::vector< T > & src, std::multiset< T > & container )
   -> std::chrono::microseconds
{
   auto start = std::chrono::system_clock::now();
   for ( auto idx = 0u, size = src.size(); idx < size; ++idx ) {
      container.insert( src[idx] );
   }
   return std::chrono::duration_cast<std::chrono::microseconds>(
      std::chrono::system_clock::now()-start
   );
}

int main() {
   std::multiset< int > multiset;
   std::unordered_multiset< int > unordered;

   std::vector< int > src;
   for ( int i = 0; i < N; i++ ) {
      src.push_back( rand() % N );
   }

   std::cout << "multiset  = " << countTime( src, multiset ).count() << " ms" << std::endl;
   std::cout << "unordered = " << countTime( src, unordered ).count() << " ms" << std::endl;
}


http://liveworkspace.org/code/a2a90a2c7c1b...f62eb92bde8a4bd

заодно и посмотреть как использовать chrono smile


--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
borisbn
Дата 15.2.2012, 09:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135
boostcoder, спасибо. Помнится я как-то сравнивал unordered-версии со стандартной и получил тот же рез-т. Есть одно но...У меня нет возможности использовать 0x11-й. разве что буст...

а что это за конструкция
Цитата
auto foo() -> type

?
это чем-то отличается от
Цитата
type foo()

?


--------------------
Женщины отличаются от программистов тем, что у них чары состоят из стрингов
PM MAIL Jabber   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0588 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.