VPF::Помогите подобрать контейнер - Форум программистов

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 ???

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

newbee

Дата 14.2.2012, 15:33 (ссылка)

(нет голосов)

Загрузка ...

Бревно

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

Репутация: 4
Всего: 19

RB-дерево попробуй. Результаты списка и очереди очень предсказуемы.

--------------------

You're face to face
With man who sold the world

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::, вылизана дальше некуда.

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

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

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

boostcoder

Дата 14.2.2012, 16:42 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

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

Репутация: 49
Всего: 110

странно... ожидал что множество будет быстрее..

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

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...

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

boostcoder

Дата 14.2.2012, 17:01 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

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

Репутация: 49
Всего: 110

borisbn, максимальный размер вектора известен?

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

borisbn

Дата 14.2.2012, 17:11 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 22
Всего: 135

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

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

boostcoder

Дата 14.2.2012, 17:19 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

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

Репутация: 49
Всего: 110

чичас. допилю.

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

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

А так?

Код


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

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();
}

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

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

rumit7

Дата 14.2.2012, 18:05 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

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

Репутация: 6
Всего: 7

Цитата(borisbn @ 14.2.2012, 17:46)

Цитата(rumit7 @ 14.2.2012, 17:31

)

А так?

Код


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

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

)

странно... ожидал что множество будет быстрее..

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

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

borisbn

Дата 15.2.2012, 09:37 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 22
Всего: 135

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

а что это за конструкция

Цитата

auto foo() -> type

?
это чем-то отличается от

Цитата

type foo()

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

boostcoder

Дата 15.2.2012, 09:50 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

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

Репутация: 49
Всего: 110

Цитата(borisbn @ 15.2.2012, 09:37

)

разве что буст

с бусте есть же: http://www.boost.org/doc/libs/1_48_0/doc/html/unordered.html

Цитата(borisbn @ 15.2.2012, 09:37

)

а что это за конструкция

это новый синтаксис. тут объясняется основное преимущество: http://en.wikipedia.org/wiki/C%2B%2B11#Alt...function_syntax
но он универсальный. можно использовать во всех случаях.

Это сообщение отредактировал(а) boostcoder - 15.2.2012, 09:54

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

mes

Дата 15.2.2012, 09:53 (ссылка)

(нет голосов)

Загрузка ...

любитель

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

Репутация: 144
Всего: 250

Цитата(borisbn @ 15.2.2012, 08:37

)

это чем-то отличается от

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

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

--------------------

http://opendots.net

borisbn

Дата 15.2.2012, 10:24 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

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

Репутация: 22
Всего: 135

ясно. в вики хороший пример

Код

template<class Lhs, class Rhs>
  auto adding_func(const Lhs &lhs, const Rhs &rhs) -> decltype(lhs+rhs) {return lhs + rhs;}

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

serghd

Дата 15.2.2012, 19:48 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

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

Репутация: нет
Всего: нет

да и тут неплохо http://en.wikipedia.org/wiki/Decltype

serghd

Дата 15.2.2012, 20:39 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

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

Репутация: нет
Всего: нет

Цитата(boostcoder @ 15.2.2012, 09:27)

не. не получилось вектор ускорить...
зато 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

boostcoder, такой вариант, наверное, "чуть" попроще для понимания будет, как Вы считаете?

Это сообщение отредактировал(а) serghd - 15.2.2012, 20:43

boostcoder

Дата 15.2.2012, 21:09 (ссылка)

(нет голосов)

Загрузка ...

pattern`щик

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

Репутация: 49
Всего: 110

лень было порядок наводить)

--------------------

компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »