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

← →
Ega23 © (2015-05-26 16:07) [120]

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

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

← →
кгшзх © (2015-05-26 16:09) [121]

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

Нахрена хешировать-мушировать, если куда полезнее иметь границы индексов ппервичного массива?

← →
Ega23 © (2015-05-26 16:09) [122]

> куда полезнее иметь границы индексов ппервичного массива?

И что это даст?

← →
MsGuns © (2015-05-26 16:11) [123]

>Но СУБД ради этого дополнительную разворачивать - это из пушки по воробьям

Если оракл, то да. Но я об нем по-моему и не заикался. А "развернуть" какой-нибудь постгресс или мускул ОДИН раз на сервере, ИМХО, гораздо проще, чем изобретать всякие хэши и лепить их на КАЖДЫЙ клиент, пусть даже методом простого копирования.

← →
Sha © (2015-05-26 16:11) [124]

> sniknik © (26.05.15 15:50) [116]

Если не считать программиста идиотом, то можно предположить,
что он будет действовать примерно следующим образом:

1. Когда видит, что фамилий в диапазоне слишком много,
он разбивает диапазон фамилий на части до тех пор,
пока самая левая часть не станет скажем 100000 записей или меньше.

2. После этого данные левой части считываются и обрабатываются.

3. Повторяем процесс для несчитанной правой диапазона.

4. Границы разбиения можно сохранить в ini, чтобы не повторять разбиение каждый раз, а только проверять валидность количества.

← →
кгшзх © (2015-05-26 16:12) [125]

перебор будет не всего массива а начиная с и по

Ищем например петрова василия михайловича.

смотрим в индексный массив по "пвм" и видим, что такие имена идут в исходном массиве с 10000 по 20000 строку.

← →
Ega23 © (2015-05-26 16:18) [126]

> смотрим в индексный массив по "пвм" и видим, что такие имена
> идут в исходном массиве с 10000 по 20000 строку.

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

← →
MsGuns © (2015-05-26 16:27) [127]

Изобретаем новый поисковик ?

← →
кгшзх © (2015-05-26 16:28) [128]

всем можно мне нельзя?

← →
D.N. Polezhaev © (2015-05-26 16:35) [129]

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

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

И в таком аспекте можно обогнать БД на джойне, особенно если мощность клиента сравнима с сервером :)) Но выигрыш, если и будет - то не большой.

Я хотел сказать, что алгоритмы принципиально будут одинаковые, да и задача есть классика для реляционных БД, это их первейшая задача - уметь строить соединения, в отличие там, допустим, от "NoSql" БД.

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

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

← →
sniknik © (2015-05-26 17:40) [130]

> Если не считать программиста идиотом, то можно предположить,
> что он будет действовать примерно следующим образом:
пусть он гений, у него НЕТ таких, и вообще многих возможностей. работа локально с массивом/таблицей/... ОЧЕНЬ отличается от ситуации когда те же данные лежат на sql ом сервере.

последний раз, больше не буду.
> 1. Когда видит, что фамилий в диапазоне слишком много,
> он разбивает диапазон фамилий на части до тех пор,
> пока самая левая часть не станет скажем 100000 записей или меньше.
КАК, он это сделает? массив не прямо тут, под рукой, он ТАМ. здесь нет количества, нет диапазона, есть запрос в котором ты должен задать условие... и задать его так чтобы получить нужное количество, диапазон, раз уж свели к нему. а следующим запросом следующий, не пересекающийся диапазон...
что НЕВОЗМОЖНО если нет определяющего значения для использования его в условии запроса.

> 3. Повторяем процесс для несчитанной правой диапазона.
как определить несчитанный диапазон?

у тебя логика "файл-серверная", а все субд уже на "клиент-сервер" перешли, давно.

← →
Sha © (2015-05-26 17:52) [131]

> sniknik © (26.05.15 17:40) [130]
> у тебя логика "файл-серверная", а все субд уже на "клиент-сервер" перешли, давно.

Читаю диапазон из ini:
"".."Козлов"
150000

Смотрю 150000>100000

Спрашиваю, скока в интервале "".."Дятлов"

Получаю 80000

Сравниваю 80000<100000

Читаю из базы интервал "".."Дятлов"

Читаю из базы интервал "Дятлов".."Козлов"

← →
Sha © (2015-05-26 17:55) [132]

Сорри, торопился, улетело в процессе редактирования, но суть должна быть понятно.

А если опять непонятно, то не моя логика тут виновата. Я так думаю )

← →
sniknik © (2015-05-26 18:11) [133]

> Смотрю 150000>100000
раньше просил
> объясни "в запросах",
именно поэтому... нет, такого в sql, невозможно задать такое условие (с лимитами не рассматриваю, только усложнять, т.к. там оно не по порядку в базе выбирает).

> Спрашиваю, скока в интервале "".."Дятлов"
> Получаю 80000
частность, ты принял определителем диапазона сами данные, фамилию. это не гарантированно, так же как и порядок выборки

а допустим они там ВСЕ с фамилией "Дятлов", и тебе пришло количеств = 10 миллионов. а диапазон для переноса на клиент/обработку положили в 10-тыс.

> А если опять непонятно, то не моя логика тут виновата. Я так думаю )
понятно. больше чем ты думаешь. понятно, что это кривая логика.

← →
Сергей Суровцев © (2015-05-26 18:20) [134]

Решение MsGuns самое красивое, по сути это обход админа основной БД. На дубле можно уже и индексы строить и еще много чего. Только вряд ли прокатит. Именно по этой же причине. Начнут трещать про безопасность данных, неподконтрольность и т.д. А втихую дак делать себе дороже. Опять же сервак нужен неслабый, а это уже административное решение, а не программирование.

Но на клиента тащить всю таблицу тоже не вариант. Сейчас строк миллион. А завтра будет 2, 10, тогда как? Да и моща клиента с серваком несравнима. По сути, конечно, должна быть классика - основная выборка на БД.

← →
Ega23 © (2015-05-26 18:29) [135]

> Решение MsGuns самое красивое, по сути это обход админа
> основной БД

Ага, вот только как быть с синхронизацией данных? Данные-то нужны актуальные.

← →
Сергей Суровцев © (2015-05-26 18:39) [136]

>Ega23 © (26.05.15 18:29) [135]
>Ага, вот только как быть с синхронизацией данных? Данные-то нужны актуальные.

А то они на клиенте актуальнее будут? Там и каналы связи похилее, и железо несравнимо. И тянуть надо не один раз, а на КАЖДОГО клиента.

← →
Сергей Суровцев © (2015-05-26 18:39) [137]

← →
Сергей Суровцев © (2015-05-26 19:03) [138]

>Sha © (26.05.15 17:52) [131]
>Читаю из базы интервал "Дятлов".."Козлов"

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

← →
Sha © (2015-05-26 19:52) [139]

> sniknik © (26.05.15 18:11) [133]
> а допустим они там ВСЕ с фамилией "Дятлов",

А также с тем же именем и отчеством, и нет идентификаторов, и нет индексов ни по какому полю.
"вы вообще с базами работали?" )))

> понятно, что это кривая логика.
Если бы было понятно, то "нет, такого в sql" ты не писал бы.

> Сергей Суровцев © (26.05.15 19:03) [138]
> ..Алгоритм будет весьма сложный, причем нужно гарантировать, что никого не упустит.

Вот более простая модификация. Может, чуть более медленная.

Сортируем искомые 10К записей. Это начальный диапазон.
Узнаем сколько в базе от первой записи до последней.
Если больше их там 100К, уменьшаем диапазон вдвое (до 5К).
Повторяем пока получим, в границах диапазона в базе лежит меньше 100К
или границы диапазона сойдутся так, что между ними нет искомых записей.
В первом случае запрашиваем все записи диапазона,
во втором - каждую из границ отдельно.
Как-то одним из ранее описанных способов обрабатываем полученные данные.
Откусываем обработанный диапазон от начального диапазона.
Повторяем для оставшегося огрызка.

← →
sniknik © (2015-05-26 22:58) [140]

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

про нет идентификаторов, условие задачи такое было, ну вот нету идентификаторов. если "переусловить" то это "игра в поддавки", давай уж сразу - "есть id - автоинкремент, без дырок, суть порядковый номер записи"... и все ПРОБЛЕМ НЕТ. но тока в реальности такого не бывает. а в идеальном мире Юрий бы уже все решил, как было сказано, изменением структуры таблицы "костылизируя" текущие недостатки архитектуры.

> Если бы было понятно, то "нет, такого в sql" ты не писал бы.
ну да, счаз проникнусь, раскаюсь, пойму... и блин все одно нет такого в sql.

> Вот более простая модификация. Может, чуть более медленная.
> Сортируем искомые 10К записей. Это начальный диапазон.
> ...
чтобы отсортировать нужно их получить на клиента, все. так и не доходит? ты опять оперируешь файл-серверной логикой.
И границы ты не определишь, т.к. выборка будет вся, по условию. т.е. на запрос "дайте ивановых" ты их всех и получишь, будь их все 10к или он всего один. и в том и другом случае проблема, усложнение, и никакого диапазона.
ну, для полноты можно команды типа "лимит" обговорить, они делают вид что дают диапазон, но дают его по готовому отсортированному результату. без "order by" даже не начнет, а с ним, при множестве повторений значений в поле будет та же неопределенность в порядке записей (по сортируемому полю значения одинаковы и серверу пофигу будет что там "страницы" поменялись и записи не в том порядке, что были... по сортируемому порядок есть? есть! будьте довольны...)

← →
Kerk © (2015-05-26 23:05) [141]

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

http://ic.pics.livejournal.com/zeit_raffer/72797520/5107/5107_original.jpg

← →
Sha © (2015-05-26 23:38) [142]

> sniknik © (26.05.15 22:58) [140]
> чтобы отсортировать нужно их получить на клиента, все.
> так и не доходит?

До кого-то точно не доходит.
Получаю диапазон FIO, по нему индекс есть по условию.
Сортирую полученную часть.

> ты опять оперируешь файл-серверной логикой.

ну да, ведь select же

> И границы ты не определишь, т.к. выборка будет вся, по условию.
> т.е. на запрос "дайте ивановых" ты их всех и получишь,

запрос дайте "Ивановых Иванов Иванычей". Ну не может их быть 10^5 штук. И потом, насколько я понимаю, в данном случае нет смысла хранить в базе 10^5 АБСОЛЮТНО одинаковых записей. Хоть какое-то различие должно быть. Значение этого различающегося поля можно использовать в качестве доп условия. Но, разумеется, скорее всего это не потребуется.

PS завтра пример напишу, если время будет

← →
Sha © (2015-05-27 09:21) [143]

> Сергей Суровцев © (26.05.15 18:20) [134]
> Решение MsGuns самое красивое, по сути это обход админа основной БД.
> На дубле можно уже и индексы строить и еще много чего.

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

← →
TohaNik © (2015-05-27 12:45) [144]

> Sha © (27.05.15 09:21) [143]

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

← →
Romkin © (2015-05-27 13:04) [145]

Добавлю и свои пять копеек: поставить memcached, кусками закачать данные - и найти.

← →
Сергей Суровцев © (2015-05-27 14:39) [146]

>Sha © (26.05.15 23:38) [142]
>запрос дайте "Ивановых Иванов Иванычей". Ну не может их быть 10^5 штук.

Теоретически может. Это раз. Конец диапазона может попасть в середину полных однофамильцев и тогда следующим шагом пойдут дубли. Это два. Наличие доп. поля ничего не даст, поскольку не участвует в теоретическом определении порядка, как ФИО. Да, некоторые записи отличаются этим полем, а некоторые нет. Можем точно сказать что с таким значением уже взяли, а с таким еще надо? Нет. Единственный случай, когда можно брать таким методом это сквозные ID, не важно с пропуском или без. Там можно подобрать границы, иначе гарантировать ничего нельзя, а это неприемлемо.

← →
Ega23 © (2015-05-27 14:56) [147]

Надо сортировать по ID т его в выборку включать. Тогда, может быть, удастся всё это дело частями затянуть (если перед затягиванием snapshot-транзакцию открыть и в её рамках всё это дело тащить).

← →
sniknik © (2015-05-27 14:58) [148]

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

>Сергей Суровцев © (27.05.15 14:39) [146]
>> запрос дайте "Ивановых Иванов Иванычей". Ну не может их быть 10^5 штук.
>Теоретически может. Это раз.

Тогда пусть падает. Это два )

> Конец диапазона может попасть в середину полных однофамильцев
> и тогда следующим шагом пойдут дубли.

Ситуация большого количества полностью идентичных фио обрабатывается, все попадут в один диапазон. Уже дописываю.

> Единственный случай, когда можно брать таким методом это сквозные ID,
> не важно с пропуском или без. Там можно подобрать границы

Дык мне давно уже тут запретили юзать ID )

Раз пошла такая пьянка. А читать напрямую из БД в обход глючного сервера приложений уже кто-нибудь предлагал?

>Sha © (27.05.15 15:40) [149]
>Дык мне давно уже тут запретили юзать ID )

А зря. ))
Какой-то идентификатор в этой базе должен быть. Пусть не ID сурагатный, а какой-нибудь ИНН, номер карты, еще что... Как-то же эту базу используют? Четко человека выделяют? Иначе она годится только для подбора статистики по однофамильцам. ))

В довесок:
А настроить сервер приложений никто не пробовал?

прямой поиск это конечно самое прямое.
но.

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

то есть если апп-сервер стартовал в понедельник, и в базу ФИО насовали тыщщу новых персоналий,
то в самом sql сервере сегодня их может еще не быть.

> Дык мне давно уже тут запретили юзать ID )
его нет в исходных задачи. + с ним какое никакое костыльное(тормозное) решение с "кусочной технологией" возможно. и ты бы легко "отмазался" от необходимости понять проблему ТС.

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

Я вообще не понимаю и представить пока не могу сам смысл первоначальной задачи. Из миллиона нужно выбрать по произвольным фамилиям 10тыс. При этом в итоговую выборку попадут, естественно и все полные однофамильцы. И кому это поможет? То есть в итоговом будет точно больше 10тыс. и потом в них опять копаться еще что-то выгрызать?
Хорошо бы иметь изначальное понимание того что есть и того что надо. А то решаем узкую промежуточную задачу без понимания нужного результата, так еще и спорим, как лучше. )))

>sniknik © (27.05.15 16:06) [154]
>не сталкивались = не бывает?

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

Да так сечас Ю.З. и рассказал :)
С большой вероятностью ему вооще никто и ничего не запрещает, иначе он там не работал бы, я - тоже.

В таблице, где миллион записей, ID есть (причем почему-то строковый).

Во входных данных (где 10 тыс. ФИО) никакой уникальности нет.

То что в результирующую таблицу попадет первый попавшийся полный однофамилец из исходного миллиона устраивает? Других критериев отбора кроме ФИО нет? Или в результирующую надо собрать и всех однофамильцев тоже?

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

> никакой уникальности нет.
даже в ID? (строковый намекает...). если да, то считай его нет.

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