 |
|
Модераторы: Daevaorn |
 
|
|
альтернатива while(1) 
| box |
|
|||
|
Опытный  Профиль Группа: Участник Сообщений: 506 Регистрация: 27.2.2007 Репутация: нет Всего: 0 |
задача в следующем:
есть основной поток что заполняет некий контейнер std::map или std::queue , заполняет очень быстро , настолько быстро насколько позволяет одно ядро . хочу реализовать ступенчатую выборку из этого контейнера , например если размер очереди меньше N то задействуем одно ядро , в случае если размер очереди N*2 то подключаем еще один поток на обработку и т.д |
|||
|
||||
Загрузка ...
| baldina |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 32 Всего: 101 |
box, погляди на стандартный примерчик. С небольшими изменениями он решит твою задачу
|
|||
|
||||
| vinter |
|
|||
 Explorer Профиль Группа: Завсегдатай Сообщений: 2735 Регистрация: 1.4.2006 Где: Н.Новгород Репутация: 13 Всего: 56 |
box, слишком общее описание. Чтобы решить задачу нормальным способом, надо знать: что за данные, откуда поступают, как потом обрабатываются и т.п. Я не зря спросил про ОС и компилятор. Решать задачу с помощью мьютексов и Ко нужно лишь тогда, когда без них никак не обойтись. Не нужно использовать примитивы когда есть конкурентные контейнеры(например эти или этот) и асинхронное программирование основанное на задачах(PPL или TBB)
|
|||
|
||||
| o2n3e |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 10 Регистрация: 19.8.2011 Репутация: -4 Всего: -5 |
Модератор: Сообщение скрыто. |
|||
|
||||
| akizelokro |
|
|||
 Крокодил Профиль Группа: Участник Сообщений: 761 Регистрация: 30.7.2007 Репутация: 1 Всего: 5 |
А вообще вы в дебри уже полезли. Первое, что std::map небыстрый контейнер.
Если уж такая критичная задача, то лучше уж unordered_map брать или вообще какой-нибудь hash. То есть сначала надо оценить примерное количество элементов, которые могут быть, затраты времени на вставку, потом смотрите, нужен ли вам поиск только или же ещё и удаление из контейнера, опять оценка времени. Из этой оценки выбираете наиболее устраивающий вид контейнера. Да и ладно. Это сообщение отредактировал(а) akizelokro - 15.10.2013, 18:51 -------------------- a = a + b; b = a - b; a = a - b; |
|||
|
||||
| Randomazer |
|
|||
 Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 20.6.2010 Репутация: нет Всего: нет |
|
|||
|
||||
| baldina |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 32 Всего: 101 |
unordered_map и есть hash |
|||
|
||||
| box |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 506 Регистрация: 27.2.2007 Репутация: нет Всего: 0 |
а поясните вчем разница в плане быстродействия между map и unordered_map . с виду такой же контейнер
|
|||
|
||||
| baldina |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 32 Всего: 101 |
map вставку/поиск за Θ(logN) делает, а unordered за Θ(1)
|
|||
|
||||
| box |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 506 Регистрация: 27.2.2007 Репутация: нет Всего: 0 |
а подробнее про алгоритм обоих можно ?
|
|||
|
||||
| box |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 506 Регистрация: 27.2.2007 Репутация: нет Всего: 0 |
за счет чего достигается такая производительность unordered_map ?
|
|||
|
||||
| baldina |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 32 Всего: 101 |
можно. хэш таблица a map обычно двоичными деревьями реализуется. например красно-черными |
|||
|
||||
| volatile |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 37 Всего: 85 |
Есть такое понятие, как наихудший случай.
Так вот у хеш, наихудший случай равен простому перебору, т.е Θ(N) впрочем вероятность попадания на такой случай, практически равна 0. (вероятность возрастает при неправильно подобранной хеш функции) у мап, теоретический наихудший случай - Θ(logN), как и среднестатистический. |
|||
|
||||
| box |
|
||||
|
Опытный Профиль Группа: Участник Сообщений: 506 Регистрация: 27.2.2007 Репутация: нет Всего: 0 |
да.... разница в производительности действительно существенная , пример заполнения
случайно сгенерированным ип адресом типа стринг
в секунду максимум уникальных вхождений:
в два раза быстрее хотя по сути функция одна и таже |
||||
|
|||||
| baldina |
|
|||
|
Эксперт Профиль Группа: Завсегдатай Сообщений: 3433 Регистрация: 5.12.2007 Где: Москва Репутация: 32 Всего: 101 |
за низкую вероятность приходится платить памятью, хорошо работает при 50% заполнении (а после 75% приближаемся к худшему случаю). btw обычно используются обозначения Θ(N) - в среднем (функция ограничена сверху и снизу) O(N) - в худшем (ограничена сверху) Ω(N) - в лучшем (ограничена снизу) Добавлено через 2 минуты и 47 секунд hash: Ω(1), Θ(1), O(N), память ~2*N map: Ω(1), Θ(logN), O(logN), память ~N*(1+2 указателя) |
|||
|
||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0644 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |