Быстрый поиск комбинации строк в массиве

← →
Юрий Зотов © (2015-05-26 11:55) [80]

> Ega23 © (26.05.15 11:51) [78]

Не "на миллионе записей", а 10 тыс раз на миллионе записей.

← →
Ega23 © (2015-05-26 11:59) [81]

> Не "на миллионе записей", а 10 тыс раз на миллионе записей.

А. Т.е. у тебя массив входных данных на 10К строк + сама база на миллион. И надо найти всё это вот?
Тогда пёс его знает, тогда возможно действительно выгоднее данные на клиент тащить. Возможно частями.

← →
Sha © (2015-05-26 12:02) [82]

хеш или сортировка на эти 10К строк,
частями прочитать всю таблицу

← →
Kerk © (2015-05-26 12:06) [83]

> Юрий Зотов © (26.05.15 11:51) [77]
>
> > Как эти списки могут лежать в памяти, если оказалось, что сервер
> > приложений не может прокачать такой объем данных?
>
> Допустим, каким-то волшебным способом мы это сделали. Тогда
> задача сводится к быстрому поиску ФИО. Быстрее, чем это
> сделал бы сервер БД.

Если это не быстрее, чем 5 (или даже 50) минут, то я гладиолус:

> Kerk © (26.05.15 02:54) [62]
>
> Сгенерировал хэш-таблицу с миллионом записей (всякий мусор
> вместо фамилий/имен/отчеств). Сделал к ней 10000 обращений.
> Выполняется быстрее, чем за секунду. Без каких-то оптимизаций,
> просто в лоб решение.

И этот же ответ был дан еще в [2]. Чего тут вообще можно обсуждать, не представляю.

← →
Юрий Зотов © (2015-05-26 12:14) [84]

> Чего тут вообще можно обсуждать, не представляю.

Не представляешь - так и не обсуждай, никто не заставляет.

← →
Kerk © (2015-05-26 12:18) [85]

Ну так шел бы на сайт домохозяек тогда. Там бы приняли как родного :)

← →
Kerk © (2015-05-26 12:20) [86]

> Sha © (26.05.15 12:02) [82]
>
> хеш или сортировка на эти 10К строк,
> частями прочитать всю таблицу

Это слишком просто. Если так сделать, то проблемы не будет. А ведь так сильно хочется о ней поговорить :)

← →
sniknik © (2015-05-26 12:27) [87]

> Если так сделать, то проблемы не будет
почему не будет?
вот тебе нужны данные, значения, ты их обрабатываешь, памяти не хватает... ладно перевел в хеши, памяти хватает, значений нет, нечего обрабатывать... добавил значения "сбоку" хешей, памяти не хватает еще больше.
ну это не проблема..., зато хеши, самые быстрые и экономные. да.

← →
Sha © (2015-05-26 12:32) [88]

> sniknik © (26.05.15 12:27) [87]

там 10К хешей всего,
и то, если лень делать сортировку

← →
MsGuns © (2015-05-26 12:39) [89]

>Юрий Зотов © (26.05.15 08:35) [65]
>Любые изменения структуры БД (в том числе, создание таблиц, пусть даже и временных) - табу.

Ну это типичная "корпоративная" ситуация :)
ИМХО, не самый плохой выход - на клиенте или "местном" сервере поставить "свой" SQL-сервер (Postgress например - он бесплатный насколько помню) и там же написать серверное приложение на периодическое обновление с базы источника. Клиенты тащат нужное со "своего". Все будет летать.

← →
MsGuns © (2015-05-26 12:47) [90]

Преимущество "локального" сервера особенно проявляется на старых клиентских компах, коих пока еще в достатке сегодня в бюджетных конторах.

← →
TohaNik © (2015-05-26 12:57) [91]

Ну, это примерно
> ИМХО, не самый плохой выход - на клиенте или "местном" сервере
> поставить "свой" SQL-сервер (Postgress например - он бесплатный
> насколько помню)

Ну, это примерно как, "а мы дешевле можем", можно конечно порекомендовать пару штатных единиц или свои услуги...

← →
sniknik © (2015-05-26 13:25) [92]

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

в чем тогда смысл хешей? просто чтоб были? или слово нравится?

> поставить "свой" SQL-сервер (Postgress например - он бесплатный насколько помню)
тогда уж access, у него к бесплатности еще плюсы прям "под задачу"
1 можно связать с внешней базой, в принципе возможно, хотя не знаю как там получится... линк таблицу сделать (т.е. без данных в ней).
2 индексы у него регистронезависимые, то что нужно, но вот на линк (1 пункт) таблицу возможно не создадутся. но неважно, обновление таблицы, вместо корректировкой, в любом случае 1 запрос через ISAM (odbc + db2).

← →
sniknik © (2015-05-26 13:27) [93]

> вместо корректировкой,
вместе с корректировкой,
(там было про замену ё на е что то)

← →
Sha © (2015-05-26 13:42) [94]

> sniknik © (26.05.15 13:25) [92]

Вариант 1.
Предварительная сортировка массива 10К искомых данных.
Никаких хешей не вычисляем.
Считываем порции отсортированных данных.
В цикле сравниваем каждую прочитанную запись с подходящей записью из сортированного массива (как при сортировке слиянием).

Вариант 2.
Предварительное вычисление 10К хешей и их сортировка.
Считываем порции несортированных данных.
В цикле вычисляем хеш каждой прочитанной записи и ищем его в сортированном массиве. Для найденных хешей сравниваем сами данные.

← →
Eraser © (2015-05-26 14:00) [95]

> Юрий Зотов © (26.05.15 01:42) [53]

> Ок, прямо на глазах внедряю засос всей таблицы в код и запускаю.
> Получаю, естественно, Out of memory. Убедились. Но говорят
> - тогда грузи эту таблицу кусками. Объясняю - скорость упадет
> на порядок - то есть придем к тем же 50 минутам, что и сейчас
> (в лучшем случае).

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

ну а по мере утягивания данных их можно хэшировать и т.д.

← →
sniknik © (2015-05-26 14:38) [96]

Sha © (26.05.15 13:42) [94]
частичная обработка что в первом, что во втором случае это несколько из другой оперы... и как говорилось ТС не способствует ускорению. и хеши тут как то тоже... ну нафига? зачем промежуточное звено если нужны данные?

кстати с частичной обработкой разве нет проблем? ну к примеру как отбирать, по какому критерию, часть данных. если есть только 3 поля (ФИО) то как? по одой фамилии после по другой? т.е. в одном случае будет 5 записей, во втором миллион без пяти... ну, что-то типа.
или "лимитами" разбивать? так сервер их сформировать должен прежде чем вырезать "с и по", формировать будет по полным данным каждый раз. т.что скорее всего общее время обработки только вырастет, ну при остальных неизменных факторах, т.к. это будет дополнительная работа по формированию "кусков".

← →
sniknik © (2015-05-26 14:41) [97]

> ну а по мере утягивания данных их можно хэшировать и т.д.
ИМХО. обсуждение "сливается", "способ" уже подменяет "смысл" задачи. вот уже и хеширование само по себе заменяет обработку, превращается в самоцель.

← →
Sha © (2015-05-26 14:59) [98]

> sniknik © (26.05.15 14:38) [96]
> частичная обработка что в первом, что во втором случае это несколько из другой оперы...
> и как говорилось ТС не способствует ускорению.

Ну, если можно все обработать сразу, то это и есть одна часть.
А если нет, то и скорость без разницы: или медленно или никак.

> и хеши тут как то тоже... ну нафига?
> зачем промежуточное звено если нужны данные?

Затем, что поиск хешей в данной задаче может оказаться быстрее, чем сравнение данных.
Мы же скорость бьемся, или как?

> кстати с частичной обработкой разве нет проблем?
> ну к примеру как отбирать, по какому критерию, часть данных...

Ну, к примеру:
1 по диапазонам ID,
2 по любой накопленной статистике о количестве записей в диапазоне значений признака,
3 в цикле запрашивать Count и дробить диапазон фамилий.

← →
MsGuns © (2015-05-26 15:07) [99]

>тогда уж access, у него к бесплатности еще плюсы прям "под задачу"

Ну, он вовсе не бесплатный, конечно :) Впрочем, MSOffice в бюджетных шарашках обычно установлен лицензионный (по крайней мере в большинстве контор, где я околачивался, было так), так что проблем не должно быть.
Хотя я бы все же проголосовал за скл-сервер. Учитывая дерьмовость техники на местах, это однозначно даст хороший выигрыш в производительности.
Единственная трабла - придумать удовлетворительный алгоритм синхронизации данных с основной базой. Но тут возможностей немало - было бы желание :)

← →
Ega23 © (2015-05-26 15:15) [100]

> Ну, он вовсе не бесплатный, конечно

Оболочка - не бесплатная, движок - да.

> Хотя я бы все же проголосовал за скл-сервер.

Оракл. Дата грид.
Народ, харэ стебаться, не нужна тут СУБД.

← →
кгшзх © (2015-05-26 15:18) [101]

я-ву, я-ву взял я на халя-ву

← →
MsGuns © (2015-05-26 15:18) [102]

Путь оптимизации поиска чисто на клиенте (как вариант, активно здесь обсуждаемый,- через хеши, в том числе), ИМХО, имеет несколько весомых минусов, как-то
1) требует достаточно высокой производительности клиента
2) ориентирован на прямое извлечение данных с "базы", что может привести к необходимости изменения на клиенте при ЛЮБОМ изменении в самой "базе".
3) привязан к приложению. При необходимости добавления нового клиентского приложения с функцией поиска, придется "клеить" туда и все кешевые манипуляции.
4) любое изменение "кешевых" алгоритмов автоматически потребует передеплоя модифицированных приложений по всем клиентским ПК. Когда таких "киентов" - под сотню,- это гадкая штука, знаю не понаслышке.

← →
D.N. Polezhaev © (2015-05-26 15:18) [103]

> Допустим, каким-то волшебным способом мы это сделали. Тогда
> задача сводится к быстрому поиску ФИО. Быстрее, чем это
> сделал бы сервер БД.

1. Тогда надо таким же волшебным способом передать на клиента результат работы ДБ2.

2. Если же все таки опираться на то, что сырые данные на клиенте и с ними надо работать - то можно повториться в третий раз.

Задача - в чистом виде джойн / соединение двух таблиц (списков) по условию равенства некоторых свойств.

Есть ТРИ классических способа соединения из теории реляционных БД:

1) цикл в цикле - это полный перебор, понятно что он как раз медленно работает
2) соединение с помощью хеш-таблицы (о которой Kerk пятый раз говорит)
3) слияние с помощью отсортированных списков - это самый быстрый способ, если не учитывать время сортировки

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

Быстрее БД можно сделать только тогда, когда БД используется неправильным способом.

Итого: надо на клиенте вручную реализовать один из двух классических способов соединения списков. Или хеш, или слиянием сортированных списков.
Если уж нельзя подготовить данные так, чтобы сама БД могла сделать свою работу.

Даже непонятно, что тут еще можно обсудить. Это классика реляционных БД от начала их основания.

← →
MsGuns © (2015-05-26 15:19) [104]

>Народ, харэ стебаться, не нужна тут СУБД.

На 10 млн записей ? Ну-ну, Кулибин :)

← →
кгшзх © (2015-05-26 15:22) [105]

На 10 млн записей ? Ну-ну, Кулибин :)

он имел ввиду что нужна, но она там уже есть (дб2).
вторая он имел ввиду не нужна

я-ву, я-ву взял я на халя-ву

← →
MsGuns © (2015-05-26 15:22) [106]

>D.N. Polezhaev © (26.05.15 15:18) [103]

Дело говорит человек. Поддерживаю. По крайней мере я не знаю случаев, когда "ручная" выборка текстовых данных опережала СУБД

← →
sniknik © (2015-05-26 15:24) [107]

> Затем, что поиск хешей в данной задаче может оказаться быстрее, чем сравнение данных.
за счет чего? возьмем индексный поиск для примера. вариант с перебором и сравнением с тут же преобразованным в хеш только для сравнения, как то вообще критики не выдерживает.
индекс это (простейший случай) дерево, с разложением по буквам/узлам. поиск это сравнение по узлам с начальных букв, и чем шире дерево, короче путь от корня до последней буквы тем быстрее. хеш "компактнее" в смысле алфавита, т.е. дерево будет не "шире" но "выше".
за счет чего быстрее?

> Ну, к примеру:
> 1 по диапазонам ID,
> 2 по любой накопленной статистике о количестве записей в диапазоне значений признака,
> 3 в цикле запрашивать Count и дробить диапазон фамилий.
напомню
> если есть только 3 поля (ФИО) то как?
1, 2 "не в кассу". 3й это как? ты же (обсуждаем) обращение к базе (выборка порций оттуда), ни порядок, ни сортировка, ни позиция (фактически ничего) не гарантируется.
откуда Count? у вас будут отдельные, независимые друг от друга запросы, всегда начинающие с 0.
LIMIT-ы упоминали, но лимиты как говорил работают также с 0 формируя, и после выбирая из сформированного. никак иначе. никаких чудесных "сквозных между запросами каунтов" не бывает.

p.s. вы вообще с базами работали?

← →
sniknik © (2015-05-26 15:27) [108]

> Ну, он вовсе не бесплатный, конечно :)
не офис, движок имею ввиду. достаточно. бесплатный. и в винду включен по умолчанию (вырезать трудоемко, хотя пару раз за время работы встречал умельцев... правда там куча всего дополнительно по отваливалось)

> sniknik © (26.05.15 15:24) [107]
> p.s. вы вообще с базами работали?

Русский язык не родной?
Слово МОЖЕТ понимаем правильно?

>кгшзх © (26.05.15 15:22) [105]
>он имел ввиду что нужна, но она там уже есть (дб2).
>вторая он имел ввиду не нужна

Не знаю что он имел "в виду", но имеется факт - прямая выборка из "базы" имеющимися в наличии средствами не удовлетворяет по производительности. "Подкрутить" сервер невозможно априори. Более того, нет никакой гарантии, что владелец "базы" не нвертит там чего-нибуль такого, что в итоге получим еще бОльшие тормоза.

прямая выборка из "базы" имеющимися в наличии средствами не удовлетворяет по производительности.

Подкрутить" сервер невозможно априори.

Всегда есть другой способ.

>Всегда есть другой способ.

Ну дык ! Открой тайну. А то тут народ колья друг об друга обламывает.

если ничего не менять и всасывать все лимоны фамилий в массив, то можно рядом сделать "индексный массив" с границами индексы первичного массива по начальным буквам.

и при поиске перебор всего первичного массива не потребуется. но это в лоб и это первое что я бы попробовал.

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

Т.е. ты за хэш ?
Ну, по сути ?

> Это о чем, вообще?
> 3 в цикле запрашивать Count и дробить диапазон фамилий.
объясни "в запросах", и при поставленном выше условии (есть 3 поля - фио), как будет участвовать Count, в "дроблении". т.е. первый запрос на 5 первых тыс к примеру (можно 6 или 3), второй на 5 вторых с 5й по 10ю тысячу и тд.
???

Т.е. ты за хэш ?
Ну, по сути ?

Я не против него, но на само хеширование потеряется куча времени.

В то время как если обозначить с какого по какой индекс первичного массива идут ИИИ (Иванов Иван Иванович) - это уже стопроцентно поможет перебору.
И памяти дополнительно на этот псевдо-индекс отъесться не так много.

> кгшзх © (26.05.15 15:54) [117]
> Я не против него, но на само хеширование потеряется куча времени.

У меня хэширование миллиона строк занимает несколько секунд.

Тут та ситуация, когда почти любое адекватное решение будет быстрее нескольких минут.

> На 10 млн записей ? Ну-ну, Кулибин :)

На 10 миллионов записей СУБД уже есть. Я на всякий пожарный снова просмотрел начало, но не увидел, чтобы Зотыч про 10.000 запросов сразу написал.
И в такой постановке, скорее всего, данные действительно надо на клиент как-то тянуть. Возможно, тянуть частями, а после "дотягивать" изменения, на клиенте хэшировать, сортировать и хранить в бинарнике. Это к примеру.
Но СУБД ради этого дополнительную разворачивать - это из пушки по воробьям.

> Я не против него, но на само хеширование потеряется куча
> времени.

Да ну на. Это время будет на пару порядков (если не все три) меньше, чем передача данных по сети, раскладывание их по структурам, а также всякие дисковые операции при выборке.

> Быстрее, чем БД сделать это невозможно.

Это чрезвычайно смелое утверждение.

Быстрый поиск комбинации строк в массиве Найти похожие ветки