QHash vs QList. Один уродует порядок, другой тормозит...

[demon051]

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

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

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

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

Help me!!! Please!!!

[darkelf]

Не пользовался QHash и QList, но, думаю, можно попробовать их совместить, например сделать общий свой QHashList, который будет внутри иметь оба объекта  - и QHash и QList. В обоих объектах будут храниться ссылки (адреса) те самые объекты в памяти, которые надо куда-то сохранять. Тогда, через QList можно обеспечить их последовательный перебор, а через QHash - поиск по ключу.

[demon051]

Не пользовался QHash и QList, но, думаю, можно попробовать их совместить, например сделать общий свой QHashList, который будет внутри иметь оба объекта  - и QHash и QList. В обоих объектах будут храниться ссылки (адреса) те самые объекты в памяти, которые надо куда-то сохранять. Тогда, через QList можно обеспечить их последовательный перебор, а через QHash - поиск по ключу.

Ага, уже так и сделал:
в QList - сам объект
в QHash - <идентификатор объекта, порядковый индекс объекта в QList>

т.е. чтобы найти нужный объект по его Id, быстренько получаем из QHash его индекс, а затем - моментальненько - из QList сам объект по индексу.
всё летает

[RXL]

в QHash - <идентификатор объекта, порядковый индекс объекта в QList>

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

[Алексей++]

Я вот тут вариант предложил http://www.forum.crossplatform.ru/index.php?showtopic=10873&st=0&gopid=70699&#entry70699

[demon051]

в QHash - <идентификатор объекта, порядковый индекс объекта в QList>

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

когда-то давно,  когда всего этого (list, map и т.д.) ещё не было и приходилось реализовывать все списки вручную, помнится мне, операция доступа по индексу [] реализовывалась как раз через указатели. Т.е. зная голову списка (указатель) и размер объекта, помещаемого в него, простым сложением или умножением - кому как нравится, можно адресоваться на объект с нужным индексом. Совсем не высшая математика и никаких логарифмов для вычисления скорости доступа
Всё элементарно, если делать правильно, т.е. просто
честно говоря, не знаю как работает доступ по индексу в списках Qt, и что они там могли навертеть от большого ума (почему там линейная сложность, откуда? если только размер объектов разный.... допускаю... ), но по крайней мере скорость в реализованном мной варианте осталась ровно такая (до миллисекунд не сравнивал), как была c одним только QHash

мне не надо лезть в середину. вся моя задача - поместить данные (а тормоза именно при помещении), а потом в размещенном порядке отобразить их для пользователя (тут в любом случае простой последовательный перебор по индексу или через итератор - без вариантов ).
Так что меня всё устраивает

а хранить указатели на одно и то же в паре разных мест = ну как-то мне это чем-то и почему-то не очень нравится. )
в общем, в моем конкретном случае мне это не нужно. и это очень хорошо!

[darkelf]

в QHash - <идентификатор объекта, порядковый индекс объекта в QList>

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

зная голову списка (указатель) и размер объекта, помещаемого в него, простым сложением или умножением - кому как нравится, можно адресоваться на объект с нужным индексом.

имхо, это немного не для списков. Так можно адресоваться в массивах, но не в списках. Для списков для поиска конкретного элемента необходимо пробежать все предыдущие элементы, посмотрев у каждого кто у них следующий. Если необходимо добавлять, например, в конец списка постоянно какие-то описатели, то каждое новое добавление будет линейно дольше предыдущего. Судя по документации в Qt списки реализованы как массивы, по крайней мере для указателей.

вся моя задача - поместить данные (а тормоза именно при помещении), а потом в размещенном порядке отобразить их для пользователя (тут в любом случае простой последовательный перебор по индексу или через итератор - без вариантов ).
Так что меня всё устраивает

Если Вы всё время помещаете в средину списка, то именно в Qt такое помещение будет дольше для списка, как это не странно, в таком случае лучше взять QLinkedList.

а хранить указатели на одно и то же в паре разных мест = ну как-то мне это чем-то и почему-то не очень нравится. )

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

[demon051]

в QHash - <идентификатор объекта, порядковый индекс объекта в QList>

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

зная голову списка (указатель) и размер объекта, помещаемого в него, простым сложением или умножением - кому как нравится, можно адресоваться на объект с нужным индексом.

имхо, это немного не для списков. Так можно адресоваться в массивах, но не в списках. Для списков для поиска конкретного элемента необходимо пробежать все предыдущие элементы, посмотрев у каждого кто у них следующий. Если необходимо добавлять, например, в конец списка постоянно какие-то описатели, то каждое новое добавление будет линейно дольше предыдущего. Судя по документации в Qt списки реализованы как массивы, по крайней мере для указателей.

вся моя задача - поместить данные (а тормоза именно при помещении), а потом в размещенном порядке отобразить их для пользователя (тут в любом случае простой последовательный перебор по индексу или через итератор - без вариантов ).
Так что меня всё устраивает

Если Вы всё время помещаете в средину списка, то именно в Qt такое помещение будет дольше для списка, как это не странно, в таком случае лучше взять QLinkedList.

а хранить указатели на одно и то же в паре разных мест = ну как-то мне это чем-то и почему-то не очень нравится. )

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

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!!

[Вад]

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!!

Для добавления исключительно в конец и произвольного доступа наверняка намного эффективнее будет std::deque (это если размер заранее неизвестен, иначе можно сразу массив/вектор нужного размера разместить).

[demon051]

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!!

Для добавления исключительно в конец и произвольного доступа наверняка намного эффективнее будет std::deque (это если размер заранее неизвестен, иначе можно сразу массив/вектор нужного размера разместить).

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

[RXL]

demon051, речь об организации структур, их плюсах и минусах. Писать можно в куда угодно и прочитать можно что угодно. Вопрос во времени и расходе памяти. В каждом конкретном случае можно найти оптимальный вариант, подобрать структуру или их комбинацию. Массивы и вектора не умеют расширяться на том же участке памяти, из-за этого огромный оверхед на больших объемах добавлений (к примеру, std::vector будет удваивать размер при каждой автоматической переалокации, но начинать он будет с очень малых размеров, в итоге, если нет возможности непрерывно расти в куче, оверхед процесса по памяти может достичь 2х). Связанный список не переалоцирует старую память, но имеет оверхед на поддержку связанности и медленный поиск. Упомянутый std::deque — симбиоз из вектора и связанного списка: сравнительно быстрый поиск, расширение алокацией дополнительных векторов.

Ручками когда-то писали не потому, что "не было", а потому что "не знали, что есть". Алгоритмы разработаны в 70-80-х, начало разработки конкретно STL —1992-й.

[Вад]

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!!

Для добавления исключительно в конец и произвольного доступа наверняка намного эффективнее будет std::deque (это если размер заранее неизвестен, иначе можно сразу массив/вектор нужного размера разместить).

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

Если не нужен, то зачем выше обсуждение того, как их по индексу извлекать? Это оно и есть - когда надо по индексу и быстро, без перебора всего списка.

[demon051]

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!!

Для добавления исключительно в конец и произвольного доступа наверняка намного эффективнее будет std::deque (это если размер заранее неизвестен, иначе можно сразу массив/вектор нужного размера разместить).

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

Если не нужен, то зачем выше обсуждение того, как их по индексу извлекать? Это оно и есть - когда надо по индексу и быстро, без перебора всего списка.

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

[Вад]

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!!

Для добавления исключительно в конец и произвольного доступа наверняка намного эффективнее будет std::deque (это если размер заранее неизвестен, иначе можно сразу массив/вектор нужного размера разместить).

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

Если не нужен, то зачем выше обсуждение того, как их по индексу извлекать? Это оно и есть - когда надо по индексу и быстро, без перебора всего списка.

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

Ну так надо же разобраться Как же, не разобравшись-то. Вот я в исходном постинге читаю, что хотелось выгрузить данные из базы в контейнер, сохраняя порядок, потом делать там поиск. Как делается поиск, не указывается, но раз принципиально сохранять порядок - можно рискнуть и телепатически предположить, что по тому же предикату. Или по другому?

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

Вроде, всё просто, но у вас в листе какой-то перебор с помещением ключа в объект. Если порядковый номер - то он не нужен, но всё равно эффективнее будут random-access-контейнеры vector и deque, чем список. Хотя задача "вывести в том же порядке" непонятна - если вывести все, то хватит итерирования по списку, не надо каждый объект там по очереди искать, и тогда оно будет не фатально хуже, чем в массиве. Что я упустил?

P.S. Если всё же хочется объединять результаты нескольких запросов (дублирования не будет?), то можно ведь в упорядоченный массив/дек слиянием сортировать. О каком количестве объектов речь?

[demon051]

Давайте уже прекратим Ну просто уже щас будем стебаться.
Я свою задачу решил. Работает. Всем спасибо за подсказки, особенно за те, которые помогли.
А объектов - непредсказуемое кол-во.