Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: QHash vs QList. Один уродует порядок, другой тормозит...  (Прочитано 847 раз)
0 Пользователей и 1 Гость смотрят эту тему.
demon051
Постоялец

ru
Offline Offline

« : 14-06-2018 07:41 » 

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

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

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

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

Help me!!! Please!!! Улыбаюсь
Записан
darkelf
Молодой специалист

ua
Offline Offline

« Ответ #1 : 14-06-2018 09:55 » 

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

ru
Offline Offline

« Ответ #2 : 14-06-2018 10:23 » 

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

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

т.е. чтобы найти нужный объект по его Id, быстренько получаем из QHash его индекс, а затем - моментальненько - из QList сам объект по индексу.
всё летает Улыбаюсь
« Последнее редактирование: 14-06-2018 10:29 от demon051 » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #3 : 14-06-2018 15:19 » 

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

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #4 : 15-06-2018 04:25 » 

Я вот тут вариант предложил http://www.forum.crossplatform.ru/index.php?showtopic=10873&st=0&gopid=70699&#entry70699
« Последнее редактирование: 15-06-2018 04:29 от Алексей++ » Записан

demon051
Постоялец

ru
Offline Offline

« Ответ #5 : 15-06-2018 05:25 » 

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

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

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

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

а хранить указатели на одно и то же в паре разных мест = ну как-то мне это чем-то и почему-то не очень нравится. )
в общем, в моем конкретном случае мне это не нужно. и это очень хорошо!
« Последнее редактирование: 15-06-2018 05:41 от demon051 » Записан
darkelf
Молодой специалист

ua
Offline Offline

« Ответ #6 : 15-06-2018 08:17 » 

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

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

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

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

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

ru
Offline Offline

« Ответ #7 : 15-06-2018 08:31 » 

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

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

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

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

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

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

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 15-06-2018 10:09 » 

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!! УлыбаюсьУлыбаюсьУлыбаюсь
Для добавления исключительно в конец и произвольного доступа наверняка намного эффективнее будет std::deque (это если размер заранее неизвестен, иначе можно сразу массив/вектор нужного размера разместить).
« Последнее редактирование: 15-06-2018 10:11 от Вад » Записан
demon051
Постоялец

ru
Offline Offline

« Ответ #9 : 15-06-2018 11:25 » 

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!! УлыбаюсьУлыбаюсьУлыбаюсь
Для добавления исключительно в конец и произвольного доступа наверняка намного эффективнее будет std::deque (это если размер заранее неизвестен, иначе можно сразу массив/вектор нужного размера разместить).
произвольный доступ не нужен!!!!! уже написано и не раз по теме Улыбаюсь нужна только  вставка в конец и последовательный перебор от начала и до конца.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #10 : 15-06-2018 18:04 » 

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

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #11 : 16-06-2018 00:06 » 

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!! УлыбаюсьУлыбаюсьУлыбаюсь
Для добавления исключительно в конец и произвольного доступа наверняка намного эффективнее будет std::deque (это если размер заранее неизвестен, иначе можно сразу массив/вектор нужного размера разместить).
произвольный доступ не нужен!!!!! уже написано и не раз по теме Улыбаюсь нужна только  вставка в конец и последовательный перебор от начала и до конца.
Если не нужен, то зачем выше обсуждение того, как их по индексу извлекать? Это оно и есть - когда надо по индексу и быстро, без перебора всего списка.
Записан
demon051
Постоялец

ru
Offline Offline

« Ответ #12 : 18-06-2018 05:12 » 

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!! УлыбаюсьУлыбаюсьУлыбаюсь
Для добавления исключительно в конец и произвольного доступа наверняка намного эффективнее будет std::deque (это если размер заранее неизвестен, иначе можно сразу массив/вектор нужного размера разместить).
произвольный доступ не нужен!!!!! уже написано и не раз по теме Улыбаюсь нужна только  вставка в конец и последовательный перебор от начала и до конца.
Если не нужен, то зачем выше обсуждение того, как их по индексу извлекать? Это оно и есть - когда надо по индексу и быстро, без перебора всего списка.

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

ru
Offline Offline
Пол: Мужской

« Ответ #13 : 20-06-2018 17:32 » 

я же написал, что я всё время добавляю в конец списка и больше НИКУДА!!! УлыбаюсьУлыбаюсьУлыбаюсь
Для добавления исключительно в конец и произвольного доступа наверняка намного эффективнее будет std::deque (это если размер заранее неизвестен, иначе можно сразу массив/вектор нужного размера разместить).
произвольный доступ не нужен!!!!! уже написано и не раз по теме Улыбаюсь нужна только  вставка в конец и последовательный перебор от начала и до конца.
Если не нужен, то зачем выше обсуждение того, как их по индексу извлекать? Это оно и есть - когда надо по индексу и быстро, без перебора всего списка.

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

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

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

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

P.S. Если всё же хочется объединять результаты нескольких запросов (дублирования не будет?), то можно ведь в упорядоченный массив/дек слиянием сортировать. О каком количестве объектов речь?
« Последнее редактирование: 20-06-2018 17:41 от Вад » Записан
demon051
Постоялец

ru
Offline Offline

« Ответ #14 : 21-06-2018 05:04 » new

Давайте уже прекратим Улыбаюсь Ну просто уже щас будем стебаться. Улыбаюсь
Я свою задачу решил. Работает. Всем спасибо за подсказки, особенно за те, которые помогли.
А объектов - непредсказуемое кол-во.
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines