вставка QVector в другой QVector |
Здравствуйте, гость ( Вход | Регистрация )
вставка QVector в другой QVector |
Авварон |
15.2.2013, 10:10
Сообщение
#31
|
Студент Группа: Участник Сообщений: 99 Регистрация: 26.4.2009 Пользователь №: 709 Спасибо сказали: 14 раз(а) Репутация: 0 |
Iron Bug
Вы зря считаете, что никто Qt не оптимизировал Я лично гонял бенчмарки на маке по просьбе человека, к-ый занимался оптимизацией строк (там вообще весьма забавно, скорость работы строк рассчитывается на "наиболее частые юзкейзы" - читай подгоняют код под определенные последовательности строк). Для стд же контейнеров оптимизация если даже и проводится в большем количестве, но проводится она _разными_ людьми, реализующим _разные_ имплементации в компиляторах. Соответственно то, что оптимизировали в одном компилере, может не быть оптимизировано в другом (что и является главной причиной для меня не использовать stl контейнеры - я хочу делать оценки о производительности не привязываясь к компилятору, а только лишь к самому алгоритму) От слов к делу - будьте добры, погоняйте этот http://mtgs.clan.su/stlvsqt.zip бенчмарк на вашем компуторе. Он не совсем "честный", так как использует QString, базированную на корове, а не wstring, так как кутешные контейнеры оптимизированы на использование Qt типов. В случае wstring результаты чуть другие (некоторые вещи, например deep copy QList'а будут сильно медленнее, чем копия QVector'a или std::vector, а аппенд std::vector'а в 2 раза быстрее аппенда qt; остальные же операции у qt по-прежнему быстрее). Поправьте, если я где налажал в бенчмарке. Вот мои результаты (OX X 10.8, Apple clang 4.1 (llvm 3.1)) Раскрывающийся текст
Вкратце (больше значит быстрее, больше либо равно значит чуть быстрее, но вообще цифры сравнимы) для QString Append: QList > std::vector >= QVector Prepend: QList > QVector > std::vector InsertMiddle: QList >= QVector > std::vector InsertRandom: QVector > QList > std::vector DeepCopy: std::vector == QList >= QVector для std::wstring Append: std::vector > QVector >= QList Prepend: QList > std::vector >= QVector InsertMiddle: QList > QVector == std::vector InsertRandom: std::vector >= QVector > QList DeepCopy: std::vector == QVector > QList (тут кулист почему-то ОЧЕНЬ медленный) Сообщение отредактировал Авварон - 15.2.2013, 10:50 |
|
|
Алексей1153 |
15.2.2013, 11:16
Сообщение
#32
|
фрилансер Группа: Участник Сообщений: 2941 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: 34 |
Авварон,
Да, эта программа подпадает под мое понимание "одной формочки". Что у нее там внутри крутится, не могу сказать в первой программе крутится несколько потоков - - чтение с порта со скоростью 115200 бод непрерывно (объектов, присылающих сообщения со всего города - порядка 3 тысяч на пульт, каждый да пришлёт чего-нибудь - тестовые сигналы, охранные сигналы, учитывай ещё повторы для радиоканала и с ретрансляторов - но одинаковые сообщения я отбрасываю по тайм-фильтру), обработка и сохранение этого всего в БД , ответ прибору (ок-транспорт), так как без ответа "ок" он будет повторять сообщение. Заметь, что БД - не шустрик MySQL, а откровенный тормоз на FireBird 1.5 . Мне приходится большую часть данных хранить в озу, а это - журнал событий для оператора(до 5 лимонов сообщений , загруженных из БД) , около поллимона сообщений железных - для настройщиков (кольцевой буфер) - приём по TCP и UDP сообщений, ретранслированных с других машин - отправка писем и SMS (модем подключен к компу) - работа в сети с другими рабочими местами (операторов несколько) - обработка текущих состояний объектов, охранных алгоритм и контроль всяческих периодов - пропадание, тестовые, задержка на вход, проверка расписания объекта - составление отчётов, статистика и прочее ВСЁ ЭТО обязано работать на машине чуть сильнее средней, причём работать без выключения месяцами. во второй программе таких ужасов нет, но все диалоги построены из XML файла с применением нелюбимого тобой STL . В момент переключений приборов создание и разрушение объектов (в том числе и объектов GUI системы) идёт очень интенсивно У меня нет утечек, чесна чесна! ) Про профилировщик я ничего не мог сказать - я ими не пользовался ни разу. Фриланс - это движение вперёд и уход от стереотипов , вливайся free-lance.ru по скорости работы Qt ничем не уступает MFC или WinAPI Приведённые тесты лично мне ни о чём не говорят Append: QList > std::vector >= QVector Prepend: QList > QVector > std::vector InsertMiddle: QList >= QVector > std::vector InsertRandom: QVector > QList > std::vector DeepCopy: std::vector == QList >= QVector - всеми этими операциями я пользуюсь редко. А у вектора резервирование памяти учитывал ? Или без него ? опять же, если нужен ассоциативный массив, всё равно городить надо. А тут раз - и есть готовый std::map к слову, из всех контейнеров мне хватает std::vector std::set std::multiset std::map std::multimap остальное не требуется |
|
|
Авварон |
15.2.2013, 11:31
Сообщение
#33
|
Студент Группа: Участник Сообщений: 99 Регистрация: 26.4.2009 Пользователь №: 709 Спасибо сказали: 14 раз(а) Репутация: 0 |
Цифры вы можете приводить сколько угодно, но если вам не приходилось использовать профилировщик, то, видимо либо вы всегда пишите оптимальные алгоритмы сразу (в чем я сомневаюсь, так как это просто невозможно), либо данных всё-таки не так много. Я не представляю, как можно писать без профилировщика, Qt - достаточно сложный фреймворк и сложно понять - это тормозит их код или мой или их комбинация.
Для вектора память не резервировал, так как тестировал основной юзкейз вектора - добавление неизвестного кол-ва эл-тов. Кроме того, вектор выделяет память с большим запасом и на большом количестве итераций, которые делает бенчмарк расходы на реалок выровняются. Про ассоциативный массив - в Qt есть и они, вы не поверите Плюс кутешники используют скип-лист вместо черно-красного дерева в стд, который в каких-то случаях лучше, в каких-то хуже. Кто знает, может QMap вам подойдет лучше |
|
|
Алексей1153 |
15.2.2013, 11:58
Сообщение
#34
|
фрилансер Группа: Участник Сообщений: 2941 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: 34 |
если вам не приходилось использовать профилировщик, то, видимо либо вы всегда пишите оптимальные алгоритмы сразу (в чем я сомневаюсь, так как это просто невозможно) опыт сказывается Лично я раньше по-всякому куролесил. В старые проекты без волосодыбления невозможно заглядывать. И запускать тоже их смешно Для вектора память не резервировал, так как тестировал основной юзкейз вектора - добавление неизвестного кол-ва эл-тов. Кроме того, вектор выделяет память с большим запасом и на большом количестве итераций, он автоматом резервирует capacity вдвое больше от последнего, если памяти не хватает. При этом происходит "тяжёлая вещь" - переаллокация. То есть, для 1024 элемента, если их вставлять по одному, произойдёт около 10 переаллокаций. Чаще всего размер вектора можно предсказать заранее и reserve его в Qt есть и они, вы не поверите я в курсе. Тут ещё такой момент присутствует - захочется мне использовать некий отлаженный алгоритм из Qt-проекта применить в проекте другого типа, я просто скопипастю его и всё. А с Qt-контейнерами придётся возиться переделывать, а потом тестить топикстартер __ilya__ - Последнее посещение: 11.2.2013, 14:22 вот порадуется, какой вброс совершил |
|
|
lanz |
15.2.2013, 11:59
Сообщение
#35
|
Старейший участник Группа: Участник Сообщений: 690 Регистрация: 28.12.2012 Пользователь №: 3660 Спасибо сказали: 113 раз(а) Репутация: 8 |
Цитата Every C++ programmer is a showoff |
|
|
Алексей1153 |
15.2.2013, 12:03
Сообщение
#36
|
фрилансер Группа: Участник Сообщений: 2941 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: 34 |
lanz, ну давай, начинай ))
|
|
|
Авварон |
15.2.2013, 12:20
Сообщение
#37
|
Студент Группа: Участник Сообщений: 99 Регистрация: 26.4.2009 Пользователь №: 709 Спасибо сказали: 14 раз(а) Репутация: 0 |
он автоматом резервирует capacity вдвое больше от последнего, если памяти не хватает. При этом происходит "тяжёлая вещь" - переаллокация. То есть, для 1024 элемента, если их вставлять по одному, произойдёт около 10 переаллокаций. Чаще всего размер вектора можно предсказать заранее и reserve его При этом количество переаллокаций уменьшается логарифмически при увеличении кол-ва эл-тов. А при бенчмарке 4096 итераций - это минимум. То, что вы предлагаете - это как тестить map, вставляя в него эл-ты так, чтобы он оставался идеально сбалансированным Ну и аппенд - это лишь одна из операций (самая быстрая у вектора), а вот вставки в середину/начало вы никаким преалоком не улучшите. |
|
|
Алексей1153 |
15.2.2013, 12:31
Сообщение
#38
|
фрилансер Группа: Участник Сообщений: 2941 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: 34 |
То, что вы предлагаете а что я предлагаю ? map, вставляя в него эл-ты так, чтобы он оставался идеально сбалансированным алгоритм сортировки std::map работает всегда одинаково (впрочем, как и у QMap), повлиять на эту работу без предиката невозможно. Поэтому непонятна фраза про "так,чтобы он оставался". И как можно сравнивать вектор и мап, непонятно ) Мы же про вектор говорим вроде а вот вставки в середину/начало вы никаким преалоком не улучшите. копирование и сдвиг произойдёт гораздо быстрее, чем переаллокация. Несоизмеримо сначала можно применить метод вставки как есть. Когда наш алгоритм уже работает, начинаем смотреть на его время работы и придумывать грабли, если это вообще потребовалось |
|
|
Авварон |
15.2.2013, 14:27
Сообщение
#39
|
Студент Группа: Участник Сообщений: 99 Регистрация: 26.4.2009 Пользователь №: 709 Спасибо сказали: 14 раз(а) Репутация: 0 |
алгоритм сортировки std::map работает всегда одинаково (впрочем, как и у QMap), повлиять на эту работу без предиката невозможно. Поэтому непонятна фраза про "так,чтобы он оставался". И как можно сравнивать вектор и мап, непонятно ) Мы же про вектор говорим вроде Для черно-красного дерева действтительно нет разницы, так как оно остается сбалансированным. А вот QMap вроде как не имеет этого свойства и при "специально" подобранных элементах можно получить линейную скорость поиска (хотя тут могу быть и не прав, не разбираюсь в скип-листах). Но вы правы, давайте продолжим рассматривать вектор копирование и сдвиг произойдёт гораздо быстрее, чем переаллокация. Несоизмеримо Я прогнал тест с преаллоцированным размером на 10^9 элементов, результаты еще интереснее: при добавлении в конец - std::vector в 4 раза быстрее, чем QVector и чуть-чуть опережает QList при вставке в случайное место - std::vector хуже на порядок (0.0023 для QList, 0.0024 для QVector, 0.023 (в десять раз медленнее!) для std::vector), при вставке в начало - std::vector на 3 (!) порядка (!) хуже QList'а , на 1 порядок хуже, чем QVector Правда, следует понимать, что эти цифры возможны благодаря тому, что QList/QVector "знают" о том, что QString (и другие Qt классы) используют Корову, и можно применять memmove вместо копирующего/мувающего конструкторов. Скорее всего, при использовании обычных классов или структур std:: типы будут быстрее; однако ничто не мешает переписать свою структуру на Корову или тупо использовать указатель. Сообщение отредактировал Авварон - 15.2.2013, 17:22 |
|
|
Алексей1153 |
15.2.2013, 18:19
Сообщение
#40
|
фрилансер Группа: Участник Сообщений: 2941 Регистрация: 19.6.2010 Из: Обливион Пользователь №: 1822 Спасибо сказали: 215 раз(а) Репутация: 34 |
|
|
|
Текстовая версия | Сейчас: 29.11.2024, 15:32 |