VPF::Ну Очеень медленное удаление элементо QVector

AndAnd

Дата 5.5.2008, 09:17 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 82
Регистрация: 22.7.2006

Репутация: нет
Всего: 1

проблема в следующем.
Очень долго удаляются элементы списка, но нужно работать именно с QString...
как быть?

Код


//...................
#include <QVector>
#include <QString>
#include <QTime>

//...................

QVector<QString> vect;
QTime time;
QString vr;

//засекаем время на создание списка элементов
vr = time.currentTime().toString("mm:ss.zzz");
qDebug() << str;
for(int i=0;i<200000;i++)
     vect.append("строка");
vr = time.currentTime().toString("mm:ss.zzz");
qDebug() << str;
//теперь очищаем vect и смотрим на время :)
vect.clear();
vr = time.currentTime().toString("mm:ss.zzz");
qDebug() << str;

//...................

archimed7592

Дата 5.5.2008, 09:37 (ссылка)

(нет голосов)

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

Репутация: 11
Всего: 93

Ну для начала: маленький lifehack:

Код


QString str = QLatin1String("строка");
// ...
for(...)
    vect.append(str); // добавление будет многим быстрее за счёт того, что каждый раз не будет копироваться строка.

Далее. Почему ты решил, что медленное именно удаление? Ты же замеряешь время не только удаления, но и добавления...
Далее. Сама по себе очистка вектора - операция со сложностью O(N * O(~T())), т.е. если деструктор имеет сложность O(1), то сложность становится O(N) - это достаточно быстро(быстрее просто не возможно - объекты в любом случае уничтожать придётся).
А что касается удаления поэлементо(по одному за раз) - у этой операции сложность тоже O(N) потому что вектор гарантирует data contiguity, т.е. если ты удалешь элемент из начала вектора, ему придётся переместить все N-1 элементов "влево".
Если нужно быстрое поэлементное удаление, то используй именно список(как ты обозвал вектор в своём сообщении smile

), т.е. QList(или QDeque).

--------------------

If you have an apple and I have an apple and we exchange apples then you and I will still each have one apple. But if you have an idea and I have an idea and we exchange these ideas, then each of us will have two ideas.
© George Bernard Shaw

AndAnd

Дата 5.5.2008, 10:05 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 82
Регистрация: 22.7.2006

Репутация: нет
Всего: 1

может так понятней будет

Код



uint RowCount = 180000;
     QList<QString> list;

     QTime t;
     t.start();
     for (int i=0; i<RowCount; i++)
          list.append(QString("asdf"));
     qDebug("create finished %d ms", t.elapsed());  // QList ~390ms
                                                                         // QVector ~375ms



     t.restart();
     list.clear();
     qDebug("clear finished %d ms", t.elapsed());  // QList ~21500ms
                                                                      // QVector ~21000ms

Почему удаляется в 53 раза медленнее чем создаётся? вот это не понятно...
и как можно ускорить процесс удаления...

Это сообщение отредактировал(а) AndAnd - 5.5.2008, 10:10

just_geek

Дата 5.5.2008, 10:29 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 309
Регистрация: 13.12.2007

Репутация: 7
Всего: 10

AndAnd, странные результаты, этот же кусок кода у меня выполняется

Цитата

create finished 47 ms
clear finished 31 ms

з.ы. Qt и проект скомпилен на VC++ 2008 EE, ну и проц Core2Duo 2.33 FSB 1333

Это сообщение отредактировал(а) just_geek - 5.5.2008, 10:29

archimed7592

Дата 5.5.2008, 10:32 (ссылка)

(нет голосов)

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

Репутация: 11
Всего: 93

AndAnd, не беспокойся, в релизе всё ок.

Код


//    RowCount = 18000000
//    QVector/QString("asdf")
//    create finished 5079 ms
//    clear finished 3895 ms
//    QVector/el
//    create finished 844 ms
//    clear finished 310 ms
//    QList/QString("asdf")
//    create finished 5740 ms
//    clear finished 3928 ms
//    QList/el
//    create finished 1522 ms
//    clear finished 374 ms

--------------------

AndAnd

Дата 5.5.2008, 10:54 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 82
Регистрация: 22.7.2006

Репутация: нет
Всего: 1

to archimed7592, вроде ты прав... спасибо smile

В общем, если запускать из Visual под отладчиком получаются тормоза, а если скомпилированный *.exe то мгновенно...

Это сообщение отредактировал(а) AndAnd - 5.5.2008, 11:16

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| С/С++: Кроссплатформенное программирование, Qt/Gtk+/wxWidgets \| Следующая тема »