QHash vs QList. Один уродует порядок, другой тормозит..., Нужен быстрый доступ, но без сортировки объектов Опции

[demon051]

Всем привет!
Попал вот в неприятное...

В общем гружу из таблицы БД данные. Каждая строка превращается в объект в памяти. Надо куда-то сохранять.
Почитал доку по QHash, там написано что он не сортирует заносимые в него данные.
Ага, на...
В итоге оказалось, что он не сортирует, но раскидывает в каком-то удобном ему порядке, возможно, для осуществления быстрого поиска по ключу.
А мне надо, чтобы порядок был тот самый, в котором я загружаю (order by - в sql-запросе).

Ну я подозревал по предыдущему опыту, что c QList будет доступ к данным тормознее, но оказалось, что жутко тормознее.
Фактически для поиска нужного объекта в QList надо каждый раз всё перебирать. Соответственно, чем больше объектов и чем глубже лежит нужный, тем всё хуже и хуже скорость

Чешу репу, думаю что делать... чтобы получить не сортированный порядок объектов с возможностью быстрого поиска нужного.
Ищется по уникальному Id, который в QHash использовался в качестве ключа. А в QLict - перебор со сравнением для каждого Id.

Help me!!! Please!!!

[Sokoloff]

Чешу репу, думаю что делать... чтобы получить не сортированный порядок объектов с возможностью быстрого поиска нужного.
Ищется по уникальному Id, который в QHash использовался в качестве ключа. А в QLict - перебор со сравнением для каждого Id.

А что такое "не сортированный порядок объектов"? Ведь не совсем не сортированный, иначе и QHash подошел бы. Если нужно сортированное по ID, то можно взять QMap, он чуть медленнее чем QHash, но отсортирован по ключу.
Если это не подходит, то можно сделать свой класс, он хранит объекты в QList/QVector, но еще хранит пары ID->номер строки в QHash. Или, если объекты хранятся как указатели, можно хранить указатель на один объект и в QList и в QHash.

[Алексей1153]

если память не жалко, а скорость поиска не очень критична, то подойдёт контейнер
QMap<ТВОЙ_UID,ТВОЙ_item>

если хочется остаться на QHash (он обеспечивает быстрый поиск и более экономно обращается с памятью), то для поддержания сортировки нужно параллельно вести индекс типа QMap<ТВОЙ_UID,char> . Второй тип (char) в шаблоне ничего здесь не делает (хотя, можешь его занять чем-то полезным). Автоматическая сортировка по ключу, уникальность ключа. В итоге, для перебора по-порядку, нужно бежать по индексу, брать ключ и по ключу вытаскивать элемент из хеш-таблицы


Сообщение отредактировал Алексей1153 - 15.6.2018, 7:18

[demon051]

Чешу репу, думаю что делать... чтобы получить не сортированный порядок объектов с возможностью быстрого поиска нужного.
Ищется по уникальному Id, который в QHash использовался в качестве ключа. А в QLict - перебор со сравнением для каждого Id.

А что такое "не сортированный порядок объектов"? Ведь не совсем не сортированный, иначе и QHash подошел бы. Если нужно сортированное по ID, то можно взять QMap, он чуть медленнее чем QHash, но отсортирован по ключу.
Если это не подходит, то можно сделать свой класс, он хранит объекты в QList/QVector, но еще хранит пары ID->номер строки в QHash. Или, если объекты хранятся как указатели, можно хранить указатель на один объект и в QList и в QHash.

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

[Алексей1153]

demon051, то есть, ты сортируешь по параметру "порядок загрузки". В этом случае идеально подходит QVector



а QList - вообще бесполезный, на мой взгляд, контейнер для хранения больших объёмов данных.

Сообщение отредактировал Алексей1153 - 15.6.2018, 9:58

[Sokoloff]

хотя в доке прямым текстом указано, что хэш не сортирует

Это не совсем так
When iterating over a QMap, the items are always sorted by key. With QHash, the items are arbitrarily ordered.
http://doc.qt.io/qt-5/qhash.html
Это надо понимать так, для ускорения мы хэшируем ключи, и храним значения в порядке который дает максимальную скорость поиска по этим хэшам. Для человека это выглядит как произвольный/случайный порядок.
QMap просто сохраняет отсортировано по ключам. И потом ищем по ним, возможно что-то вроде бинарного поиска. Но это несколько медленнее чем поиск по хэшам.

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

Подход зависит от того как ты хранишь данные. Если хранишь указатели, то все проще.
Я бы написал класс DataStorage внутри у него QVector. Также класс умеет создавать индекс для поиска, индекс это QHash<ID, yourRowData*>. Т.е. данные не дублируются, но указатели на данные храняться и в порядке добавления, и удобно для быстрого поиска.
У класса есть методы:
* addRow - добавляет указатели и в вектор и в индекс
* deleteRow - удаляет из обоих
* count - кол-во строк
* row(int) - возвращает строку по номеру, использует вектор
* search(ID) - возвращает строку по ID, использует QHash

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

demon051, то есть, ты сортируешь по параметру "порядок загрузки". В этом случае идеально подходит QVector
а QList - вообще бесполезный, на мой взгляд, контейнер для хранения больших объёмов данных.

Это зависит от способа хранения, если demon051 хранит указатели, да еще и доступается по номеру строки, то вектор. А если хранит сами данные по значению, да еще и данных много, то для QVector-а может не хватить памяти одним куском.