crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

 
Ответить в данную темуНачать новую тему
> QHash vs QList. Один уродует порядок, другой тормозит..., Нужен быстрый доступ, но без сортировки объектов
demon051
  опции профиля:
сообщение 14.6.2018, 10:46
Сообщение #1


Студент
*

Группа: Участник
Сообщений: 27
Регистрация: 12.8.2014
Пользователь №: 4209

Спасибо сказали: 4 раз(а)




Репутация:   0  


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

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

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

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

Help me!!! Please!!!
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Sokoloff
  опции профиля:
сообщение 14.6.2018, 11:21
Сообщение #2


Участник
**

Группа: Участник
Сообщений: 237
Регистрация: 1.4.2009
Из: Москва
Пользователь №: 654

Спасибо сказали: 50 раз(а)




Репутация:   11  


Цитата(demon051 @ 14.6.2018, 11:46) *
Чешу репу, думаю что делать... чтобы получить не сортированный порядок объектов с возможностью быстрого поиска нужного.
Ищется по уникальному Id, который в QHash использовался в качестве ключа. А в QLict - перебор со сравнением для каждого Id.

А что такое "не сортированный порядок объектов"? Ведь не совсем не сортированный, иначе и QHash подошел бы. Если нужно сортированное по ID, то можно взять QMap, он чуть медленнее чем QHash, но отсортирован по ключу.
Если это не подходит, то можно сделать свой класс, он хранит объекты в QList/QVector, но еще хранит пары ID->номер строки в QHash. Или, если объекты хранятся как указатели, можно хранить указатель на один объект и в QList и в QHash.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 15.6.2018, 7:17
Сообщение #3


фрилансер
******

Группа: Участник
Сообщений: 2939
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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

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


Сообщение отредактировал Алексей1153 - 15.6.2018, 7:18
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
demon051
  опции профиля:
сообщение 15.6.2018, 8:51
Сообщение #4


Студент
*

Группа: Участник
Сообщений: 27
Регистрация: 12.8.2014
Пользователь №: 4209

Спасибо сказали: 4 раз(а)




Репутация:   0  


Цитата(Sokoloff @ 14.6.2018, 11:21) *
Цитата(demon051 @ 14.6.2018, 11:46) *
Чешу репу, думаю что делать... чтобы получить не сортированный порядок объектов с возможностью быстрого поиска нужного.
Ищется по уникальному Id, который в QHash использовался в качестве ключа. А в QLict - перебор со сравнением для каждого Id.

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


не сортированный - это так, как я из загрузил. а не так как захотел хэш или мап. они все сортируют по своему.
хотя в доке прямым текстом указано, что хэш не сортирует :(
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 15.6.2018, 9:57
Сообщение #5


фрилансер
******

Группа: Участник
Сообщений: 2939
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


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



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

Сообщение отредактировал Алексей1153 - 15.6.2018, 9:58
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Sokoloff
  опции профиля:
сообщение 15.6.2018, 20:08
Сообщение #6


Участник
**

Группа: Участник
Сообщений: 237
Регистрация: 1.4.2009
Из: Москва
Пользователь №: 654

Спасибо сказали: 50 раз(а)




Репутация:   11  


Цитата(demon051 @ 15.6.2018, 9:51) *
хотя в доке прямым текстом указано, что хэш не сортирует :(
Это не совсем так
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 просто сохраняет отсортировано по ключам. И потом ищем по ним, возможно что-то вроде бинарного поиска. Но это несколько медленнее чем поиск по хэшам.


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

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



Цитата(Алексей1153 @ 15.6.2018, 10:57) *
demon051, то есть, ты сортируешь по параметру "порядок загрузки". В этом случае идеально подходит QVector :)
а QList - вообще бесполезный, на мой взгляд, контейнер для хранения больших объёмов данных.
Это зависит от способа хранения, если demon051 хранит указатели, да еще и доступается по номеру строки, то вектор. А если хранит сами данные по значению, да еще и данных много, то для QVector-а может не хватить памяти одним куском.

Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

Быстрый ответОтветить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 28.3.2024, 19:39