А много элементов?

> for( int i = 0; i < list.count(); i++ )

list.at(i); //do something

у меня дежавю

Ну вот, про скорость спрашиваешь, а i++ вместо ++i пишешь...

> Ну вот, про скорость спрашиваешь, а i++ вместо ++i пишешь...

Какая разница, если там int i?

> а i++ вместо ++i пишешь...

а count() и at() вас не смущают?

std::for_each + lambda.

deja vu же

пока интересуют QList и [..], так как у них время доступа до элемента O(1)

хотеть такой QList, плакать...

Эффективность обхода всех элементов контейнеров

1. по какому критерию?
2. предполагаемый размер контейнера?

Может, ты путаешь с QLinkedList?

Пруф http://doc.qt.nokia.com/4.7/containers.html#algorithmic-complexity

1. Не понял. Нужно пройтись по всем элементам типу T в QList<T> или QVector<T>. Какую роль играет сам тип в контейнере к алгоритмам перебора контейнера? Я же всё-равно в конце-концов получу T.

2. 100-10000. Допустим, размер играет роль при foreach, который делает копию контейнера через неявное разшаривание данных. Но какая разница в размере для итераторов или for/count()?

о_О я и забыл.. спасибо, что напомнил =)

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

интересно, сколько народу уже нарвалось на незаметное:

QList<T>, insert time: O(n)

//я в шоке...

> //я в шоке...

Аналогично. Сам ведь недавно только узнал.

1. Не понял. Нужно пройтись по всем элементам типу T в QList<T> или QVector<T>. Какую роль играет сам тип в контейнере к алгоритмам перебора контейнера? Я же всё-равно в конце-концов получу T.

причём тут тип контейнера? назовите критерий эффективности, иными словами - какую реализацию Вы будете считать эффективной

размер играет роль при foreach

что такое foreach? (если что - не стоит уподобляться К.О., я всего лишь спросил какую реализацию Вы имеете в виду)

и да, вроде в своё время по итогам срача в Development пришли к мнению, что никакой разницы между использованием std::for_each, итераторов и перемещением по элементам с помощью for нет, если включено -O2

//что там в кутэ наворотили норвежские кулибины я уже боюсь комментировать

> причём тут тип контейнера?

Ни причем, вот именно.

> назовите критерий эффективности, иными словами - какую реализацию Вы будете считать эффективной

типа такого

//пускаем секундомер
for( int i = 0; i < list.count(); i++ ) 
    qDebug() << list.at(i);
//снимаем показатели секундомера, запускаем его снова
QList<T>::const_iterator i;
 for (i = list.constBegin(); i != list.constEnd(); ++i)
     qDebug() << *i;
//снимаем показатели, запускаем опять
foreach (const T &var, list)
     qDebug() << var;
//cнимаем показатели

Что быстрее - то и эффективней. Можно, конечно, провести такие тесты, но хотелось бы понять принцип доступа к каждому элементу.

> foreach

If you just want to iterate over all the items in a container in order, you can use Qt's foreach keyword. The keyword is a Qt-specific addition to the C++ language, and is implemented using the preprocessor. ... Qt automatically takes a copy of the container when it enters a foreach loop. If you modify the container as you are iterating, that won't affect the loop. (If you do not modify the container, the copy still takes place, but thanks to implicit sharing copying a container is very fast.)

Что ещё добавить?

Я для себя к такому выводу пришёл: если в конкретном случае foreach подходит (в том смысле что итераторы или счётчик не были бы удобнее), то и делать через foreach. Ведь там не полное копирование идёт.

> QList

время доступа до элемента O(1).

Qt зажигает?

> QList

время доступа до элемента O(1).

Qt зажигает?

немного не так, Qt зажигает - QList<T>, insert time: O(n)

Что быстрее - то и эффективней.

ok

Можно, конечно, провести такие тесты

не можно а нужно

#include <QtCore/QCoreApplication>
#include <QElapsedTimer>
#include <QTime>
#include <QDebug>

#include <iostream>


int main(int argc, char *argv[]) {

    int list_size = 100000000;
    long sum = 0;
    int t1 = 0, t2 = 0, t3 = 0;

    QElapsedTimer timer;
    QList<int> list;

    list.reserve(list_size);
    qsrand(QTime(0,0,0).msecsTo(QTime::currentTime()));

    for( int i = 0; i < list_size; i++ )
    {
        list.push_back(qrand()%10);
    }

    //пускаем секундомер
    timer.start();

    for(int i = 0; i < list_size; i++)
    {
        sum += list[i];
    }

    //снимаем показатели секундомера, запускаем его снова
    t1 = timer.elapsed();

    std::cout << "sum: " << sum << std::endl;

    sum = 0;

    timer.start();

    QList<int>::const_iterator i;
     for (i = list.constBegin(); i != list.constEnd(); ++i)
     {
        sum += *i;
     }

     //снимаем показатели, запускаем опять
     t2 = timer.elapsed();

     std::cout << "sum: " << sum << std::endl;
     sum = 0;

     timer.start();

    foreach (const int i, list)
    {
        sum += i;
    }

    //cнимаем показатели
    t3 = timer.elapsed();

    std::cout << "sum: " << sum << std::endl;

    std::cout << "t1: " << t1 << std::endl;
    std::cout << "t2: " << t2 << std::endl;
    std::cout << "t3: " << t3 << std::endl;

    return 0;
}

и вывод

sum: 450023333
sum: 450023333
sum: 450023333
t1: 120
t2: 80
t3: 80

хотелось бы понять принцип доступа к каждому элементу

что Вы имеете в виду?

Ну вот, про скорость спрашиваешь, а i++ вместо ++i пишешь...

А вот и нубы подтянулись...

Варианта с at() не хватает. Думаю он в первом цикле даст те же 80.

Правильно писать «кажедзо».

Не актуально уже

Это что за задача, в которой так важна скорость, но при этом допустимо использовать QList?

Варианта с at() не хватает. Думаю он в первом цикле даст те же 80.

ахаха, я схожу с ума... по странной, непонятной для меня причине, Вы правы... сейчас посмотрим

если посмотреть код то увидим, что на самом деле QList::at ничем не отличается от QList::operator[], так что скоростьне должна отличаться, однако для QList::operator[] есть ещё и вариант, в котором вызывается detach() (тот самый CoW), есть мнение что при вызове sum += list; подставляется именно он и накладные расходы именно оттуда... это явный косяк Qt

template <typename T>
inline const T &QList<T>::at(int i) const
{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::at", "index out of range");
 return reinterpret_cast<Node *>(p.at(i))->t(); }

template <typename T>
inline const T &QList<T>::operator[](int i) const
{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range");
 return reinterpret_cast<Node *>(p.at(i))->t(); }

template <typename T>
inline T &QList<T>::operator[](int i)
{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range");
  detach(); return reinterpret_cast<Node *>(p.at(i))->t(); }

//я фигею с троллей, какую они себе цель ставят - быть максимально непохожими на stl?

это явный косяк Qt

Это не косяк, а известное поведение. Потому что at() возвращает константную ссылку, а operator[] - нет, и с ее помощью список можно изменить. А для этого надо, чтобы экземпляр списка был уникальным (именно CoW). Вопросы есть?

было взять самый популярный с конца метод реализации списка и велянчить его по умолчанию...

в ml-языках, в lisp'ах в начало добавить O(1), а в конец O(n). поэтому это действительно самый популярный метод реализации.

> было взять самый популярный с конца метод реализации списка и велянчить его по умолчанию...

в ml-языках, в lisp'ах в начало добавить O(1), а в конец O(n).

простите, я что-то пропустил, тролльтехи уже позиционируют Qt как ML-like язык?

поэтому это действительно самый популярный метод реализации.

насчёт самого популярного - это Вы загнули, кроме того, посмотрев сюда, Вы можете обнаружить что:

QList<T>, Index lookup: O(1), Insertion: O(n), Prepending: Amort. O(1), Appending: Amort. O(1)

то есть добавление в конец ~O(1)

вот нафига было самый неочевидный метод реализации списков вклянчивать по-умолчанию, чтобы выпендриться?

Это не косяк, а известное поведение. Потому что at() возвращает константную ссылку, а operator[] - нет

чего? я для Вас же приводил код, смотрите ещё раз:

template <typename T>
inline const T &QList<T>::operator[](int i) const
{ Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range");
 return reinterpret_cast<Node *>(p.at(i))->t(); }

возвращается константная ссылка, не?

> возвращается константная ссылка, не?

рядом наверное должен быть:

inline T &QList<T>::operator[](int i)

а QLinkedList для тебя очевиднее будет?

> возвращается константная ссылка, не?

рядом наверное должен быть:

inline T &QList<T>::operator[](int i)

а с чего этот метод должен выбираться - данные ж не меняются, не?

> а с чего этот метод должен выбираться - данные ж не меняются, не?

оператор выбирается в зависимости от объекта( константный или нет )

а QLinkedList для тебя очевиднее будет?

конечно, это классический лист, в самой что ни на есть канонической реализации

> а с чего этот метод должен выбираться - данные ж не меняются, не?

оператор выбирается в зависимости от объекта( константный или нет )

вообще-то у Qt есть мета-компилятор, можно было бы и заоптимизировать, случай-то простой

> вообще-то у Qt есть мета-компилятор

не знаю почему они назвали его компилятором - это скорее препроцессор

> вообще-то у Qt есть мета-компилятор

не знаю почему они назвали его компилятором - это скорее препроцессор

один хрен

и, главное, чем дальше я сталкиваюсь вот с такими вещами в Qt, тем больше понимаю почему программисты на Qt испытывают трудности переходя на чистый C++

А «чистый C++» - это C++ вместе с STL? Или что-то иное?

А «чистый C++» - это C++ вместе с STL?

да, а таки почему Ви уже спг'ашиваете?

Однако...

#include <QtCore/QCoreApplication>
#include <QElapsedTimer>
#include <QTime>
#include <QDebug>

#include <iostream>


int main() {

    int list_size = 100000000;
    long sum = 0;
    int t1 = 0, t2 = 0, t3 = 0;

    QElapsedTimer timer;
    QList<int> list;

    list.reserve(list_size);
    qsrand(QTime(0,0,0).msecsTo(QTime::currentTime()));

    for( int i = 0; i < list_size; i++ )
    {
        list.push_back(qrand()%10);
    }
    
    for (int var = 0; var < 5; var++)
    {
        sum = 0;

    //пускаем секундомер
        timer.start();

        for(int i = 0; i < list_size; i++)
        {
            sum += list.at(i);
        }

    //снимаем показатели секундомера, запускаем его снова
        t1 = timer.elapsed();

    // std::cout << "sum: " << sum << std::endl;

        sum = 0;
    
        timer.start();

        QList<int>::const_iterator i;
         for (i = list.constBegin(); i != list.constEnd(); ++i)
         {
            sum += *i;
         }

     //снимаем показатели, запускаем опять
         t2 = timer.elapsed();

     // std::cout << "sum: " << sum << std::endl;
         sum = 0;

         timer.start();

        foreach (const int i, list)
        {
            sum += i;
        }

    //cнимаем показатели
        t3 = timer.elapsed();

    // std::cout << "sum: " << sum << std::endl;

        std::cout << "for :\t\t" << t1 << std::endl;
        std::cout << "iterator :\t" << t2 << std::endl;
        std::cout << "foreach :\t" << t3 << std::endl;
    }

    return 0;
}

Результат:

for :           1822
iterator :      2978
foreach :       2401
for :           1854
iterator :      3007
foreach :       2499
for :           1882
iterator :      3105
foreach :       2484
for :           1879
iterator :      3091
foreach :       2471
for :           1878
iterator :      3116
foreach :       2491

С флагом -O2

sum: 449975600
sum: 449975600
sum: 449975600
for :           264
iterator :      290
foreach :       272
sum: 449975600
sum: 449975600
sum: 449975600
for :           270
iterator :      273
foreach :       271
sum: 449975600
sum: 449975600
sum: 449975600
for :           270
iterator :      270
foreach :       290
sum: 449975600
sum: 449975600
sum: 449975600
for :           275
iterator :      305
foreach :       294
sum: 449975600
sum: 449975600
sum: 449975600
for :           270
iterator :      269
foreach :       271

for рулит и педалит, что мне и нужно было узнать.

где ж он рулит, если

for :           270
iterator :      269
foreach :       271

это единичный случай ведь, с почти несущественным разрывом.

это единичный случай ведь, с почти несущественным разрывом.

не, не, разница в 1 балл тут - чисто статистическая погрешность, я к тому что никакой разницы между различными способами обхода контейнера нет, если включено -О2 канэшна

Вообще-то есть, и даже при -O2 «for» выигрывает, как правило, около десятка миллисекунд. Однако, при ста миллионах элементов этот отрыв весьма незначителен, и им можна пренебречь, согласен.

Но если собирать без оптимизаций (а где это может понадобиться вообще?) - то «for» предпочтительней, ИМХО.

Скоро хаскель для стороннего человека станет понятнее чем С++

Скоро хаскель для стороннего человека станет понятнее чем С++

думаю что для постороннего человека и то и то останется загадкой :)