О правильных контейнерах, методах и алгоритмах

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К. Сказка.

И наконец, финальный аккорд – алгоритмы.

К сожалению, таким образом удалось улучшить только второе проблемное место. А построение путей по прежнему было медленным. Пришлось найти другой алгоритм и все переписать. Стало почти мгновенно, особенно после добавления кэширования:) Как бонус считать стало более точно, так как оригинальный алгоритм игнорировал один параметр.

В общем, правильные вещи – рулят.

Related:

Posted in Qt

18 Responses to “О правильных контейнерах, методах и алгоритмах”

  1. Begemot, очень интересует твое мнение по поводу wx VS Qt сегодня, когда у тебя появился серьезный опыт работ с Qt. Хотя бы в двух словах.

  2. Я тут в процессе переезда из Тая в Украину, на днях попробую обдумать и написать пост. Сейчас не до того совсем:(

  3. Тайвань? Эко тебя…

  4. Taй это Тайланд, а не Тайвань 🙂
    http://begemotov.net/asiatravel/

  5. Спасибо.

  6. А чего Q_FOREACH, а не foreach?

  7. А хз, наверное потому что итерируюсь все-таки по Qt шным контейнерам

  8. Не путайте for_each из и foreach из : http://doc.qt.nokia.com/4.7/qtglobal.html#foreach

  9. парсер скушал написанное внутри угловых скобочек. Напишу то же самое без них.
    for_each из algorithm и foreach из QtCore/QtGlobal

  10. То есть вопрос почему я использую Q_FOREACH вместо Qtшного же foreach? Незнаю, что первое попалось то и взял:)

    Сейчас в хелпе вижу что разницы между ними нет, причем Q_FOREACH даже наверное более предпочтителен.

  11. Вопрос такой — нафига использовать Q_FOREACH, если вы не делаете no_keywords?

    И foreach как минимум лучше читается.

  12. Ну как я уже сказал – у меня Q_FOREACH чисто потому что первый под руку попался…
    А сейчас буду высасывать из пальца аргументы почему он лучше чем foreach 🙂

    1. Универсальность – будет работать даже если кто-то сунет мой код в проект с no_keywords
    2. Читаемость – не спутаешь случайно (как это сделал я нескольмими ответами выше) с for_each
    3. Хороший стиль – кто-то там из великих писал, что макросы должны четко выделятся, и для этого их стоит именовать заглачвными буквами

    еще раз уточняю, я понимаю, что аргументы высосаны из пальца:) А какие плюсы у foreach?

  13. 1) Если кто-то сунет твой код в такой проект, ему придётся переделывать over9000 всего, а автоматически зариплейсить foreach на Q_FOR_EACH не проблема.
    2) Как ты спутаешь std::for_each и foreach? Почти вдвое больше символов :).
    3) Но foreach — не макрос.

    Плюс у foreach — человекочитаемость. Алсо, во всех проектах, что я видел, юзают foreach (это не плюс, конечно, а информация к размышлению).

  14. 2. Я std:: в cpp файлах не пишу 🙂
    3. А в хелпе, по твоей ссылке, написано – foreach ( variable, container ): This macro is used to implement Qt’s foreach loop.

    Ну ладно убедил, в следующий раз буде писать foreach 🙂

  15. 2) неужели using namespace std? в больших проектах так не делают :/

  16. В отдельных _cpp_ файлах я делаю, да и откуда у меня большие проекты, я маленький и скромный разработчик 🙂

  17. Ну не знаю, у меня даже для небольших проектов привычка выработалась всё в отдельном неймспейсе делать.