Russian Qt Forum

Пишу программку для хитроумных расчетов над большими массивами данных (показания приборов, считанные за большой интервал времени). Т.е., одна-несколько колонок и до десятков или даже сотен тысяч строк. Хотел бы спросить совета у более опытных людей: как лучше организовать такие данные ? Колеблюсь между списком колонок в виде списка векторов типа QVector и списком списков типа QList.
В литературе пишут, что QVector экономней расходует память, но тормозно работает с операциями типа добавления и вставки новых элементов, в особенности, когда вектор уже состоит из большого количества элементов.
Про QList пишут, что операции вставки/добавления выполняются быстро, но QList якобы кушает гораздо больше памяти.
Также хотел бы спросить: может вообще для хранения и работы с огромными массивами чисел с плавающей точкой используется какая-нибудь совсем другая организация данных и какие-то специфические приемы ?

Пишут вообще-то правильно, но все же лучше смотреть в исходники. Напр

QList съедает на 4 байта больше - для каждого элемента (или 8 в 64-бит), т.е. размер адреса
Поэтому выбор между QList и QVector определяется размером элемента. Если элемент QString, то QList подойдет лучше

По нынешним временам размер "сотни миллионов элементов"  не считается "огромным", а о "сотнях тысяч" уже давно забыли. Прикиньте размер. Если в рамках 1 Gb, то беспокоиться нечего

Спасибо за ответ !
Применю QList. Скорость в моем случае важнее, чем плюс 4 байта к каждому элементу.

   Не знаю как в твоем случае, может оно тебе и не нужно, но если например, используются таблицы как эксель, то в таком случае применяется действительно другой прием. Дело в том, что даже если ячейка ничего не хранит, под неё все-равно нужно отвести память необходимую для размещения указателя. Если взять пустую таблицу эксель, то получается внушительный объем памяти. Поэтому применяют хеширование, чтобы память выделялась под ячейки, которые содержат данные. Если в твоем случае это не требуется (последовательное заполнение ячеек), то можно обойтись списком или вектором.

Может и не совсем верно, но вектор можно представить как обертку над обычным массивом, содержащий объекты, а список как обертку над массивом указателей на эти объекты. И теперь можно представить, как в каждом случае происходит вставка/удаление элемента и перераспределение памяти.

А откуда известен размер  QString? Уверен, что если рассматривать этот класс как POD и применить sizeof(QString), то получится очень даже не большой размер, т.к. скорее-всего это обертка над с-строкой (указатель + возможно инт под размер).

это не обертка над си строкой, строка там юникодовская (массив шортов - кучаров). Кроме того применяется механизм дата-шаринга. Но в целом, данных там не так много

А я почему-то уверен, что sizeof(QString) вернет размер указателя. Там вся петрушка в куче лежит.

Что такое POD?

американская рок-группа из города Сан-Диего, Калифорния.  ;D
Ну или для тех кто немного занимается программированием http://forum.sources.ru/index.php?showtopic=150319

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


    Кстати, не первый раз вижу этот пост, и не все совсем так. Например, в книге Рихтера Windows via C++ от 2009г., указанный товарищ приводит кучу примеров, в которых он пишет классы, которые являются потомками POD структур, причем активно использует конструкторы и методы (хоть не виртуальные). Далее в такую "расширенную структуру" сохраняет что хочет и передает ее адрес обычной вынь-апи ф-ии, которая рассматривает ее как базовый класс (т.е. как базовую POD структуру). С точки зрения С++ и той статьи, такое делать вроде бы нельзя. Пытался уяснить на мсдн форуме, никто ничего толкового не ответил. Книга под грифом микрософт пресс. Хотя наследование можно было заменить вложением и вопросы бы не возникали  как там компилятор по стандарту должен разместить в памяти объект.

Ладно, давайте подробно. sizeof(QString) = 4 (32 бит). Для таких размеров (<= sizeof(void *)) QList оптимизирован: данные хранятся как массив указателей, вызов new не происходит. Это занимает столько же памяти что и QVector, но операции вставки/удаления намного быстрее, т.к можно обойтись memmove вместо конструкторов копирования.

Ну и конечно никакая QString не обертка над с-строкой :)

Ну да 1 байт. Внутри класса QString определена структура struct Data, в которой определены все необходимые члены, а в самом классе QString имеется лишь указатель на эту структуру, ну а размер указателя уже платформой определяется. Таким образом вопрос, о том что размер QString большой не стоит, что я с самого начало говорил. А вообще шаблончик нужно взять на заметку - можно любые объекты делать размером в 1 байт (для стека).

Почему один байт?
Не один байт.  :)

Сам удивляюсь.

Да, и виртуальных методов я не увидел.

И чего пишет?

1.

2 Alex_cs_gsp
Этот перец может делать как считает нужным. Истина одна - это библия стандарт ISO C++.

А так?  ;)

C++ (Qt)
int main(int argc, char *argv[])
{
 
    QApplication app(argc, argv);
 
    QLabel lbl;
    lbl.setNum((int)sizeof( QString ));
    lbl.show();
 
   return app.exec();
}
 

4
Ну и как так?  ???Объект меньше весит?

Что как так?
Указатель на твоей платформе занимает 4 байта, а не один.

А, ну-да я неправильно сайзоф использовал, бывает. Просто день независимости отмечал.
http://msdn.microsoft.com/en-us/library/4s7x1k91(VS.71).aspx (http://msdn.microsoft.com/en-us/library/4s7x1k91(VS.71).aspx) Для объекта возвращает 1 как и написано.

Вот некогда проверять. Остальные Qt объекты также содержат по указателю, а все данные-члены по нему находятся???

Для какого объекта и где написано?
Такая запись вообще не корректна:

C++ (Qt)
sizeof( QString() )
 

и поэтому компилятор выдает предупреждение.

Я ж говорю неправильно, а написано у меня выше в посту.  :)

   По большому счету, вектор и список отличаются только тем, что у вектора элементы располагаются в памяти последовательно друг за другом (в виде линейного массива), а у списка - где угодно, и лишь указатели на элементы представляют собой линейный массив. Операции добавления в конец массива одинаково эффективны для обоих шаблонов (если не требуется перераспределения памяти, для вектора можно предусмотреть это заранее резервированием). Операции вставки эффективнее у списка только за счет того, что перемещается массив указателей, а не сами элементы. Для данных небольшого размера вектор, думается, будет эффективнее (не требуется операция разыменования указателей).
  Если предполагается интенсивная работа с операциями вставки/удаления внутри этих последовательностей, то оба шаблона не подходят для этого.
  На мой взгляд, чтобы сделать выбор, нужно сначала определиться с данными и перечнем операций над ними.

Так и есть, но это совсем не так просто как кажется  :)  Напр. добавление в конец для QList намного быстрее. Для QList можно спокойно брать адрес элемента т.к. он не изменится даже при вставках/удалениях. А для вектора нет. QList лихо добавляет в начало, для вектора это тяжелая операция. С др. стороны нет способа уменьшить размер массива указателей в QList и это может быть проблемой. Ну и как ни крути QList расходует памяти больше. И не только на указатель. Наверное Вам не составит труда пояснить на что же еще?  :)

  Это намеки на перераспределение памяти при ее заполнении для вектора? Есть такая тема. Но для нашего случая (известного количества измерений) есть операция резервирования. Кстати, для списка, кажется, нет такой? Т.е. массив указателей перераспределяется по алгоритму, заложенному разработчиком класса?
   Добавить в список элемент и где-то хранить его адрес? Сомнительное преимущество. Хотя имеет место быть.
   Поясните, за счет чего. И не путаете ли Вы простой список со связным списком?
  По той информации, которой я располагаю, не могу. Может, все же раскроете секрет?

Не путаю - см. исходник QList (напр метод prepend)

Я могу подсказать: здесь изучение исходников никак не поможет, там только + 4 байта. Но все же это не так, больше памяти расходуется, иногда намного больше (почти вдвое). Думайте, причина очень простая, Вы ее давно знаете  :)

Подсказка супер - исключаем действие не смотреть исходники. Зачем в школу играться, и так времени мало :( Если можешь скажи, всем интересно.

Большое спасибо общественности за обсуждение моего вопроса ! На днях определюсь со структурой своих данных. Почитаю еще только... :)

Посмотрите еще книги:
  Николай Джосьютис. C++ Стандартная библиотека. Для профессионалов.
  Бьерн Страуструп. Язык программирования C++. Специальное издание.
Думаю, это будет полезнее, чем ковыряться в исходниках даже такой хорошей штуки, как Qt. Средства стандартной библиотеки эффективнее любых других по определению...

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

Мое личное мнение: эффективнее тот инструмент который программист лучше знает, понимает и применяет с толком. Огромное количество "говнокода" связано именно с STL и совсем не потому что он плох. Свалиться в изучение const iterator и.т.п очень легко, ведь это выглядит довольно круто  :) Дальше все идет по накатанной дорожке "знаю что давать на вход - получу такой-то результат". А как это работает? А чего стоит удобство использования? А есть ли лучшее решение? Увы, в большинстве случаев STL-щику очень не нравится когда разговор заходит об этом  :)

Так что рекомендовать STL надо осторожно

Но тем не менее STL есть везде, где есть стандартный С++ компилятор, и она работает.

Ну что "есть" везде - на то она и включена в стандарт. А вот используется/применяется далеко не везде. Напр. когда-то приходилось заниматься 3ds, так в ихнем SDK никакой STL почему-то не наблюдалось. Да и Qt использует "мелкие вкралления STL" - не более того  :)

А насчет "работает" - так то на нормальной платформе/компиляторе. А на MSVC удовольствие ниже среднего

тем более что реализации stl могут отличаться от компилера к компилеру

тут еще про сложность алгоритмов еще кажется не говорили. для QList сложность O(1). так что с точки зрения производительности лучче использовать QList чем QVector. QVector еще удобнее (спорный момент) тем, что с его элементами можно работать как с обычным массивом в С, например передавать в функции в виде обычных С массивов.

Да, а для QVector по твоему какая сложность? Удобный/неудобный это диван или кресло может быть, тут нужно подходит или не подходит.

Не О(1), а Amort О(1) и это при вставке в начало. Во всех остальных операциях контейнеры равны.

Чем вставка в начало QList отличается от вставки в начало QVector?

тем что у кулиста есть область спереди, а у вектора - нет

Немного про структуру контейнеров можно почитать здесь: http://doc.trolltech.com/qq/qq19-containers.html

А чё в кувекторе не сделали? Одну лишнюю переменную хранящую сдвиг пожалели, вместо нулевых указателей для кулиста?

вектор - это вектор, просто массив с динамической длинной.
кулист - это список, то есть структура, ориентированная на аппенд/препенд/инсерт

Да, c QList так не получится. Но с др. стороны QVector (по крайней мере на некоторых платформах) не перешагнет через барьер 1Gb, а QList пожалуйста

От лукавого это все. Если нужно писать выскопроизводительный код, например серверный или для автоматизированных систем, то это уже не для Qt. Для пользовательских программ учет времени, которое затрачивается на разыменование указателя нет смысла учитывать.

чем же скорость работы Qt в плане контейнеров меньше того же буста? Другое дело, что таскать Qt и не использовать многие фичи оттуда, которые в таких приложениях не нужны, смысла нет

Ну как бы это разне контейнеры, с разной логикой размещения данных. Если бы ты сходил по моей ссылке выше, то понял бы разницу между этими контейнерами. Конкретный контейнер служит для конкретных целей. "Слепить" функционал всех контейнеров в один имхо как-то неочень.

Хаачу хранить  инты и вставлять их в начало контейнера и работать как с масивом. Какой контейнер? Кулист - памяти в два раза больше. Так почему бы не сделать в кувекторе вставку в начало?

Как уже обсуждалось в этой теме, для таких типов QList оптимизирован и не требует больше памяти. Но нет способа работать с QList как с "С" массивом, он для этого не предназначен. Вставка в начало QVector - ну "гипотетчески" возможна, но, на мой взгляд, противоречит природе vector (QVector). Как должны вести себя методы resize, reserve,capacity если мы хотим (втихаря) резервировать место внвчале?

Не знаю. Может reserve_front(), reserve_back()  :D ;D :D Проблема надуманная, но все-таки это сделать можно.

Ну чего ж надуманная если решать это придется?  :)  Никто не мешает сделать свой класс на основе QVector если вопрос о вставке в начало стоит остро

Размышляя...

Дело хорошее, но "(unsigned) long" замените - он 8 байт на одних платформах и 4 байт на до.

Зачем? Вектор он и есть вектор. Если нужно другое поведение, стоит взглянуть на другие контейнеры или пересмотреть логику программы.

Да не нужно мне, просто разговор зашел, почему не сделали, если можно.