Вопрос оптимизации

[deis]

Есть некий алгоритм поиска заданного значения, а вопрос, собственно, следующий. Что будет быстрее - искать значение непосредственно в данных QSqlQuery через seek() и value(int) или предварительно выгрузить данные в QList<Type> и искать уже через него?

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

[Astrologer]

Что значит есть некоторый алгоритм поиска? Что за алгоритм? От него очень много зависит. И алгоритмов поиска куча. И выгружать тогда уже в QMap or QHash, в контейнеры оптимизированные для поиска, в которых время поиска амортизированное. ИМХО, если данных не очень много - не заморачивайся и ищи с seek().

http://doc.trolltech.com/4.4/containers.html#algorithmic-complexity

[deis]

Алгоритм здесь совершенно не при чем - он одинаков в обоих случаях. Я уже померил - обращение к данным через QList (функция at()) в пределе будет примерно в пять раз быстрее, чем через QSqlQuery (соответственно, функции seek() и value()). Поэтому если число обращений к содержащимся в выборке данным значительно превышает ее размер, то целесообразнее выгружать данные сначала в QList, а затем уже выбирать из него...

[Astrologer]

Вот и ответ на ваш вопрос. Не совсем понял - то есть алгоритм поиска не влияет на скорость поиска?

[deis]

Собственно алгоритм поиска никак не влияет на скорость извлечения из выборки отдельных ее элементов - конечно, если используется один и тот же метод доступа к данным, а вопрос был именно о сравнении скоростей различных методов доступа к элементам выборки - для одного и того же алгоритма

[crossly]

быстрее будет

Код:

select ... from <table> where value in (....)

[deis]

У меня поиск по многим значениям, а фактически по всем, встречающимся в выборке - и не по одному разу (этот факт учитывается), при этом число обращений к ней многократно превышает ее размер. В данном случае единственное оптимальное решение - загрузить всю выборку сразу за один запрос, а потом уже в ней ковыряться...

[Kolobok]

Поиск в базе будет быстрее.

[deis]

Это не имеет отношения собственно к теме вопроса, но в данном случае это не совсем так, поскольку алгоритм поиска оптимизирован под структуру данных. Грубо говоря, из 100 элементов выборки 90 имеют одно и тоже значение, остальные распределяются более-менее равномерно, поэтому повторный поиск осуществляется уже не среди исходных данных как таковых, а среди данных, описывающих их распределение, к тому же и база далеко не localhost. Естественно, данные отбираются из нее в отсортированном по необходимому признаку виде, поэтому и первоначальный поиск - это далеко не тупой перебор и даже не половинное деление. Как-то так...

[Astrologer]

=) новый алгоритм поиска? Поделитесь?

[deis]

Алгоритм прост до безобразия, самое главное - правильная организация хранения исходных данных в самой базе данных...