О правильных контейнерах, методах и алгоритмах
January 27th, 2011 Begemot Posted in Qt
Довелось мне тут недавно портировать один код, считающий dog inbreeding coefficient, с C# на С++/Qt. Код портировался легко, фактически 1 в 1, за исключением того что стеки в Qt ведут себя немного не так как в шарпе, но это решилось. Через некоторое время обнаружилось, что на больших родословных код работает непозволительно медленно, в шарповской версии, что интересно, проблем не было, пришлось оптимизировать.
Шаг первый – правильные контейнеры.
Код использовал списки, при портировании я их и заменил на QList. Но в принципе списки не самый быстрый контейнер для простых операций. Первое что я сделал заменил на QVector. Автозаменой, получил прирост в 30%.
Шаг второй – правильные методы доступа.
В поисках что бы еще улучшить, случайно наткнулся в документации на следующее
For read-only access, an alternative syntax is to use at():
at() can be faster than operator[](), because it never causes a deep copy to occur.
У нас в контейнере хранились просто int’ы, ничего более сложного, поэтому чудес я не ожидал. Но произошло чудо:)
Замена всего одной строчки в коде вида
Q_FOREACH(QList<int> pf, paths_father)
{
Q_FOREACH(QList<int> pm, paths_mother)
{
if (pf[0] != pm[0]) continue;
Дала прирост на порядок для количества путей родителей XXK на XK, и в сотню раз (!) для количества порядка 220K на 30К. Сказка.
И наконец, финальный аккорд – алгоритмы.
К сожалению, таким образом удалось улучшить только второе проблемное место. А построение путей по прежнему было медленным. Пришлось найти другой алгоритм и все переписать. Стало почти мгновенно, особенно после добавления кэширования:) Как бонус считать стало более точно, так как оригинальный алгоритм игнорировал один параметр.
В общем, правильные вещи – рулят.
February 24th, 2011 at 6:17 pm
Begemot, очень интересует твое мнение по поводу wx VS Qt сегодня, когда у тебя появился серьезный опыт работ с Qt. Хотя бы в двух словах.
February 25th, 2011 at 4:27 pm
Я тут в процессе переезда из Тая в Украину, на днях попробую обдумать и написать пост. Сейчас не до того совсем:(
February 25th, 2011 at 5:01 pm
Тайвань? Эко тебя…
February 26th, 2011 at 1:03 pm
Taй это Тайланд, а не Тайвань 🙂
http://begemotov.net/asiatravel/
February 28th, 2011 at 11:00 am
Ответил – http://begemotov.net/wxwidgets/common/qt-vs-wxwidgets-lichnyiy-opyit/
February 28th, 2011 at 5:32 pm
Спасибо.
March 1st, 2011 at 9:31 pm
А чего Q_FOREACH, а не foreach?
March 3rd, 2011 at 12:01 am
А хз, наверное потому что итерируюсь все-таки по Qt шным контейнерам
March 3rd, 2011 at 10:19 am
Не путайте for_each из и foreach из : http://doc.qt.nokia.com/4.7/qtglobal.html#foreach
March 3rd, 2011 at 10:23 am
парсер скушал написанное внутри угловых скобочек. Напишу то же самое без них.
for_each из algorithm и foreach из QtCore/QtGlobal
March 3rd, 2011 at 10:44 am
То есть вопрос почему я использую Q_FOREACH вместо Qtшного же foreach? Незнаю, что первое попалось то и взял:)
Сейчас в хелпе вижу что разницы между ними нет, причем Q_FOREACH даже наверное более предпочтителен.
March 3rd, 2011 at 10:46 am
Вопрос такой — нафига использовать Q_FOREACH, если вы не делаете no_keywords?
И foreach как минимум лучше читается.
March 3rd, 2011 at 11:17 am
Ну как я уже сказал – у меня Q_FOREACH чисто потому что первый под руку попался…
А сейчас буду высасывать из пальца аргументы почему он лучше чем foreach 🙂
1. Универсальность – будет работать даже если кто-то сунет мой код в проект с no_keywords
2. Читаемость – не спутаешь случайно (как это сделал я нескольмими ответами выше) с for_each
3. Хороший стиль – кто-то там из великих писал, что макросы должны четко выделятся, и для этого их стоит именовать заглачвными буквами
еще раз уточняю, я понимаю, что аргументы высосаны из пальца:) А какие плюсы у foreach?
March 3rd, 2011 at 1:53 pm
1) Если кто-то сунет твой код в такой проект, ему придётся переделывать over9000 всего, а автоматически зариплейсить foreach на Q_FOR_EACH не проблема.
2) Как ты спутаешь std::for_each и foreach? Почти вдвое больше символов :).
3) Но foreach — не макрос.
Плюс у foreach — человекочитаемость. Алсо, во всех проектах, что я видел, юзают foreach (это не плюс, конечно, а информация к размышлению).
March 3rd, 2011 at 2:17 pm
2. Я std:: в cpp файлах не пишу 🙂
3. А в хелпе, по твоей ссылке, написано – foreach ( variable, container ): This macro is used to implement Qt’s foreach loop.
Ну ладно убедил, в следующий раз буде писать foreach 🙂
March 3rd, 2011 at 2:28 pm
2) неужели using namespace std? в больших проектах так не делают :/
March 3rd, 2011 at 3:11 pm
В отдельных _cpp_ файлах я делаю, да и откуда у меня большие проекты, я маленький и скромный разработчик 🙂
March 3rd, 2011 at 3:13 pm
Ну не знаю, у меня даже для небольших проектов привычка выработалась всё в отдельном неймспейсе делать.