Форум: "Прочее";
Текущий архив: 2016.03.13;
Скачать: [xml.tar.bz2];
Вниз
Быстрый поиск комбинации строк в массиве Найти похожие ветки
← →
Юрий Зотов © (2015-05-23 19:49) [0]Java.
В памяти лежит массив записей (неотсортированный, но если надо, то можно и отсортировать). Записей в массиве порядка миллиона. Каждая запись содержит 3 раздельные строки (ФИО).
Еще в памяти есть входные ФИО (тоже 3 раздельные строки). Задача - найти в массиве все записи, у которых ФИО совпадают со входными ФИО.
Перебор записей массива "в лоб" - слишком долго. Гугль не помог (может, плохо искал, но уж как сумел). Поэтому обращаюсь к сообществу за любыми полезными идеями.
Дополнительная информация:
1. Все строки уже в верхнем регистре.
2. Отчество может быть пустым, фамилия и имя всегда заполнены.
3. Букву Ё считаем буквой Е.
Спасибо заранее. Я знаю, что All может все.
← →
Юрий Зотов © (2015-05-23 20:02) [1]То есть, нужно некое подобие такого запроса:
select ... from ... where
translate(upper(LastName), "Ё", "Е") = :param1 -- фамилия
and -- то же самое для имени и отчества
Собственно, исходная информация из таблицы БД и берется, но медленно ( в таблице есть индекс по ФИО, но translate и upper его убивают). База - DB2.
← →
Kerk © (2015-05-23 20:14) [2]Чем тут не подходит обычная хэш-таблица?
← →
Jeer © (2015-05-23 20:19) [3]Юр, что-то непонятна постановка.
1. Запись, это есть и строка.
Сущности Ф.И.О в строке (записи) могут быть разнесены по полям (колонкам) записи.
Ты об этом?
2. При чем тут какая-то "память" и DB2?
Данные лежат в БД? Тогда все остальное - особенности.
← →
Rouse_ © (2015-05-23 20:21) [4]FTS на данные (а-ля индекс) и всех делоф
← →
Rouse_ © (2015-05-23 20:23) [5]Юр уйди от баз - у тебя же РО как я понял, там вме в разы проще со скоростью
← →
Rouse_ © (2015-05-23 20:26) [6]Просто попиариться - выборка данных по введенному слову менее полутора секунд, общий обьем базы за 40 гектаров
← →
Jeer © (2015-05-23 21:19) [7]Ну да, и поиск/выборка 2 килозаписей приведет к 1.5*2000 = 3000 сек, почти час.
← →
Юрий Зотов © (2015-05-23 21:44) [8]> Rouse_ © (23.05.15 20:26) [6]
У меня поисковых слов не одно, а комбинация из трех. И таких входных комбинаций 10 тысяч - то есть, поиск среди миллиона записей должен быть повторен 10 тысяч раз. Сейчас я это делаю за 50 минут, а хочется за 10.
← →
Kerk © (2015-05-23 21:51) [9]
> Юрий Зотов © (23.05.15 21:44) [8]
10 тыс обращений к хеш-таблице - это точно быстрее 50 минут.
← →
junglecat © (2015-05-23 21:56) [10]а если сделать индексируемую вьюху уже с translate & upper?
← →
кгшзх © (2015-05-23 22:10) [11]Удалено модератором
← →
Pavia © (2015-05-23 22:24) [12]Тут типичная поисковая задача.
По алгоритмам.
1) Линейный поиск O(N)
2) Бинарный поиск O(Log(N))
3) индексный поиск O(1)
По структурам
1) Массив O(N)
2) Хэш таблица O(1)
3) Дерево O(k*Log(N))
Для ускорения применяют индексирование. Т.е. Создание дополнительной структуры данных для ускорения поиска.
1) Индекс по ключу.
2) Суффиксное дерево
3) Обратный индекс.
Всё остальное является комбинацией всего выше перечисленного. В зависимости от требуемой скорости и доступного объема памяти.
Индекс можно сжимать. Обычно используют только дельта кодирование.
А для ключей суффиксное дерево.
В сжатом виде индекс обычно не превосходит 30%.
Для борьбы с Е,Ё во время построения индекса идёт обработка данных - лематизация. Который упрощает слова, до их основы.
Для 1 миллиона вообще сложная артиллерия не нужна. У меня на Delphi линейный поиск отлично отрабатывает за 150-60 мс. И да скорее всего у Вас проблема со скоростью вывода, а не поиска. Так что вам надо проверить. Нет ли лишних накладных расходов. Для Java думаю вам надо будет просто ускорить в 10 раз.
Достаточно проиндексировать по первой букве. Или использовать хэширование по фамилии что тоже будет быстрым. А далее линейным поиском.
← →
D.N. Polezhaev © (2015-05-23 22:50) [13]Что-то какой то простой вопрос от дяди Юры, потрепаться что ли ))
Давайте выступлю капитаном.
Данная задача в базах данных в чистом виде называется джойном или соединением по русски.
https://ru.m.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F_(%D0%A1%D0%A3%D0%91%D0%94)
Есть три классических алгоритма соединения.
дядя Юра говорит о том что соединение вложенными циклами работает долго - не удивительно, оно такое.
Остается попробовать соединение хешем или слиянием отсортированных списков. Если сортировать как пишет дядя Юра проблем нету - то последний способ конечно даст самый фантастишь по скорости - параллельно бегаем синхронно по двум отсортированным спискам.
Впрочем при соотношении тысяча к миллиону должен хорошо себя показать и хеш по данным где тысяча, солидарен с Керком.
Можно все это мутить самостоятельно в памяти, но я не понимаю зачем. Уверен, что дб2 в курсе про эти методы соединения и так.
Остается вопрос насчет тормозов функции преобразовния данных. Ну дык и постройте индекс по этой функции, если дб2 умеет строить индексы по функциям. Тогда условие джойна соединения будет
Translate(записьИзБольшойТаблицы) = Translate(записьИзМаленькойТаблицы)
И чтобы Translate был под индексом и там, и там.
Если же по функциям индекс строить не умеет, то денормализация данных и завести колонку с данными для сравнения, где все уже приведено.
Впрочем если бд отрабатывает медленно сейчас то она значит даже хеш не заюзала - надо разобраться почему. Возможно как то дать понять бд, что функция Translate детерменированная для конкретной записи.
← →
Pavia © (2015-05-23 22:56) [14]
> У меня поисковых слов не одно, а комбинация из трех. И таких
> входных комбинаций 10 тысяч - то есть, поиск среди миллиона
> записей должен быть повторен 10 тысяч раз. Сейчас я это
> делаю за 50 минут, а хочется за 10.
Берёте БД. Создаёте массив индексов, сортируете его по фамилии с учётом нормировки.
По массиву индексов создадим новый массив фамилий. Делаете нормализацию фамилии. Т.е. приводите к маленьким буквам(к маленьким быстрее так как их больше) заменяете "ё" на "е".
Затем группируете фамилии, указывая порядковый номер начала и конца где фамилии в массиве индексов совпадет.
Это будет массив ключей.
При поиске будете вначале ищете фамилию в массиве ключей. Затем линейный поиск по БД через индексы.
← →
Rouse_ © (2015-05-23 23:02) [15]При поиисковом запросе в 50 символов на 40 гигах время выборки около 17 секунд (Несколько фраз)
FTS тебе нужен
← →
Pavia © (2015-05-23 23:11) [16]
> При поиисковом запросе в 50 символов на 40 гигах время выборки
> около 17 секунд (Несколько фраз) FTS тебе нужен
Кстати да забыл упомянуть. Прикрутить с СУБД/БД полнотекстовый поиск(FTS). Всяк быстрее чем своё изобретать, делать. Разве что если есть проблемы с памятью и нужно сжать индекс тогда свой вариант лучше.
← →
кгшзх © (2015-05-23 23:11) [17]добавить индексный массив.
в котором для каждой буквы хранить границы индексов первичного массива.
для всех трех полей.
исходный массив заполнять с сортированного набора данных
я-ву я-ву взял я на ха-ля-вуууу
← →
Inovet © (2015-05-24 04:18) [18]Ну и я ляпну в довесок. МемориТэйбл какой-нить готовый - с индексами и шахматами, с поэтессами тоже, конечно.
← →
D.N. Polezhaev © (2015-05-24 11:13) [19]Причем тут вообще полнотекстовый поиск какой то бред пишите. Условия задачи вообще не в этом.
← →
Rouse_ © (2015-05-24 11:17) [20]Спасибо, мы оценили, особливо за условия задачи. Перечитай чтоли сам вопрос и погугли что есть FTS
← →
Rouse_ © (2015-05-24 11:32) [21]Юр попробую немного раскрыть тему.
С таким обьемом данных мы делали следующим образом.
При добавлении нового документа в базу каждое слово (токен) из документа добавлялось в некий аналог словаря (хэш таблицу) и с ним ассоциировалось ID документа, в котором данный токен встречается.
Сам документ сохранялся как есть + к нему писался довесок из массива уникальных токенов в том порядке как они идут в документе.
К примеру
ID токена - значение
0 - мама
1 - мыла
2 - раму
документ "мама мыла раму мама мыла раму" содержит блоб токенов вида "012012"
Потом прикрутили движок который ассоциирует пользовательский ввод с токенами и выдает наружу ID документов (буквально 200 миллисекунд на данный тип поиска, ибо уникальных токенов не так много, просадка на выделение памяти под хранение списка ID).
Если требовалось искать точное совпадение - начинал работать второй движок, который работает с массивом токенов, идущих в том порядке, в каком они встречаются в самом документе (тут основная задержка, но на пике выходим на 17 секунд)
← →
Kerk © (2015-05-24 12:05) [22]
> D.N. Polezhaev
Если у человека в руках молоток, то все кажется гвоздем :)
← →
Kerk © (2015-05-24 15:07) [23]
> Rouse_ © (24.05.15 11:32) [21]
Остановись на секунду. У человека три поля, в каждом из них по одному слову максимум. Всего данных - несколько десятков мегабайт максимум. Какие нафиг токены, какой нафиг полнотекстовый поиск, какие нафиг документы? Ты ему туда еще Сфинкса предложи прикрутить, ага.
Тут только два адекватных решения, одно из них в [2], другое в [10]. В [13] - вариации. Эта задача настолько проста, что ее даже обсуждать скучно.
← →
Rouse_ © (2015-05-24 15:30) [24]Нет у него полей - данные в памяти :)
← →
Inovet © (2015-05-24 15:49) [25]Ещё раз подумал, с учётом
> в таблице есть индекс по ФИО, но translate и upper его убивают
А надо ли что-то городить в памяти, нет ли в ДБ2 возможности пострить подходящий индекс? Collate там какой-нибудь с учётом регистра и буквы "Ё". Пост 10 тоже о том.
Это всё то же продолжение любви с Пенсионным Фондом? А я сразу говорил, что проблем много, с первого взгляда неочевидных и мелких. Та же "Ё" в паспорте и "Е" в ПФ, и наоборот. "Дальновидные" разработчики её сначала запретили, потом разрешили.
← →
Pavia © (2015-05-24 18:19) [26]
> Остановись на секунду. У человека три поля, в каждом из
> них по одному слову максимум. Всего данных - несколько десятков
> мегабайт максимум. Какие нафиг токены, какой нафиг полнотекстовый
> поиск, какие нафиг документы? Ты ему туда еще Сфинкса предложи
> прикрутить, ага.Тут только два адекватных решения, одно
> из них в [2], другое в [10]. В [13] - вариации. Эта задача
> настолько проста, что ее даже обсуждать скучно.
Классическая заблуждение. На самом делеё всё наоборот. Хэш-таблицы не ускоряют поиск. Они ускоряют сравнения. А токены это и есть хэши. А ускоряет поиск индексирование. Вот когда токенов много там да хэши ускоряют поиск, но также в качестве токена можно использовать порядковые номера слов в словаре. При этом поиск в словаре вести линейно.
Хотя на java я бы просто создал ассоциативный массив благо реализация встроена. Да и построен этот массив на основе хэширования.
А что-бы доказать что вы ошибаетесь. Предлагаю вам самому составить полный алгоритм действия.
← →
Pavia © (2015-05-24 18:28) [27]
> А что-бы доказать что вы ошибаетесь. Предлагаю вам самому
> составить полный алгоритм действия.
Хотя тут всего 3 слова. Так что число комбинаций мало и можно хэш-таблицы использовать.
← →
MsGuns © (2015-05-24 18:54) [28]Не удержусь, тоже "ляпну" :)
DB2 достаточно быстрая СУБД. Тормоз наверняка в запросе, нельзя ли его увидеть полностью. Ну и эти ё и е, нельзя ли обойтись без них - в результсете не должно быть слишком много записей - можно и на клиенте отбросить лишнее.
← →
Юрий Зотов © (2015-05-24 20:10) [29]Докладываю сообществу результаты.
Вначале то, о чем не упоминал ранее.
1. Обработка происходит в условиях дефицита памяти в клиенте. Поэтому лучше, конечно, проводить сравнение непосредственно на сервере, а не грузить всю кучу данных на клиент. Собственно, так изначально и делалось, но слишком медленно - почему проблема и возникла. Вариант сравнения на клиенте (почему я и написал, что все уже в памяти) рассматривался, как альтернативный, но крайне нежелательный.
2. БД чужая, я в ней не хозяин. Поэтому любое изменение в ее структуре требует согласования (которого не всегда удается достичь). И это была вторая причина для того, чтобы попытаться ускорить работу, засосав все данные одним запросом (а не 10-ю тысячами) и дальше сравнивать на клиенте. Хотя, повторюсь, этот вариант очень нежелателен.
Что в итоге было сделано.
1. Конечно, был нужен индекс. К счастью, его удалось согласовать с владельцем базы. Построил индекс, основанный на функциях replace (вместо translate) и upper. Облом - не понимает DB2 function-based индексов, ругается. Скорее всего, из-за старой версии сервера - но уж какая есть, никуда от нее не денешься.
2. В таблицу было добавлено генерируемое поле с автозаполнением. В нем - конкатенация ФИО и все те же replace и upper. По этому полю и был построен искомый индекс.
==============
Результат - 5 минут. Что даже лучше, чем хотелось.
Всем спасибо.
← →
D.N. Polezhaev © (2015-05-24 20:54) [30]Какой блин полнотекст.
Полнотекст - это поиск слов в неструктурированном тексте, желательно релевантно.
А тут прямое сравнение заранее типизированных структур (пусть и текстовых).
Можно, конечно, движку полнотекста задать условием полное совпадение без морфологии, расстояние между словами ноль и никаких других слов в тексте. Только зачем такой бред, решение естественно проиграет обычному условию соединения (тем более используется равенство), которые есть основа основ всех реляционных бд.
← →
D.N. Polezhaev © (2015-05-24 20:58) [31]То есть, это как вместо
CompareText(s1, s2)
Взять и заюзать регулярку зачем то.
← →
jack128 © (2015-05-25 01:44) [32]
> Результат - 5 минут
Описка?? 5 минут или 5 секунд???
← →
Германн © (2015-05-25 02:08) [33]
> jack128 © (25.05.15 01:44) [32]
>
>
> > Результат - 5 минут
>
> Описка?? 5 минут или 5 секунд???
>
Юра мечтал о 10 минутах вместо 50 минут.:)
← →
Дмитрий С © (2015-05-25 07:29) [34]Поиск по хеш таблице.
Я уверен, что если бы я задал такой вопрос, тот час был бы "отправлен" учиться :)
← →
Павел Калугин © (2015-05-25 07:51) [35]Простите не понял. Какие хеш таблицы? Поднять на клиента несколько миллионов записей, потом построить хеш и потом осуществлять поиск - за такое решение по голове погладят разве что кирпичом.
Решение добавить индексированное поле, содержащее поисковый ключ отчасти верное. Но имеет подводные камни.
Я бы рекомендовал добавить три поля в которых держать отдельно фамилию имя и отчество в верхнем регистре и очищенных от "мусора". Мусором кроме Е признал бы И Й пробелы, дефисы запятые и т. д.
Это позволило бы эффективнее искать, к примеру, по имени и фамилии без отчества
← →
Юрий Зотов © (2015-05-25 09:08) [36]> Дмитрий С © (25.05.15 07:29) [34]
> если бы я задал такой вопрос, тот час был бы "отправлен" учиться :)
Открою маленький секрет. Я задаю вопросы даже не с целью получить решение (обычно оно известно заранее), а с целью как бы "спровоцировать" обсуждение задачи и получить варианты решений. Пусть даже самые, на первый взгляд, бредовые. Своего рода "мозговой штурм" получается. А если обсуждающие начинают спорить о том, какое решение лучше - так вообще прекрасно, часть моей работы по выбору решения они делают за меня. Окончательный же выбор все равно происходит после чтения документации, потому что все детали задачи знаю лишь я один.
Возможность такого "штурма" и есть то самое преимущество, которое имеет живой активный форум перед документацией. Это преимущество я просто использую. И при этом совершенно не боюсь, что меня отправят учиться. Есть много вещей которые я знаю, но есть еще больше вещей, которых я не знаю. Как и каждый человек. Поэтому, если говорят "читай то-то", то не обижаться, а благодарить надо, а если еще и ссылку дадут - так вообще прекрасно.
Кроме того, вызвав обсуждение, я получаю возможность "проговорить" задачу. От этого она становится более четкой.
← →
Юрий Зотов © (2015-05-25 09:27) [37]> Павел Калугин © (25.05.15 07:51) [35]
> Решение добавить индексированное поле, содержащее поисковый
> ключ отчасти верное. Но имеет подводные камни.
Паша, а какие ты видишь камни? Поделись, плз. Это может быть важно.
← →
Дмитрий С © (2015-05-25 11:10) [38]
> Простите не понял. Какие хеш таблицы? Поднять на клиента
> несколько миллионов записей, потом построить хеш и потом
> осуществлять поиск
Например, завести поле с хешем фамилии и имени в таблице и индексировать его. Можно без заведения, некоторые субд такое позволяют.
> Открою маленький секрет. Я задаю вопросы даже не с целью
> получить решение (обычно оно известно заранее), а с целью
> как бы "спровоцировать" обсуждение задачи и получить варианты
> решений. Пусть даже самые, на первый взгляд, бредовые. Своего
> рода "мозговой штурм" получается. А если обсуждающие начинают
> спорить о том, какое решение лучше - так вообще прекрасно,
> часть моей работы по выбору решения они делают за меня.
> Окончательный же выбор все равно происходит после чтения
> документации, потому что все детали задачи знаю лишь я один.
>
Это хорошо. И хорошо, что получается. Тем не менее, меня бы все-равно отправили бы учиться :)
← →
Ega23 © (2015-05-25 11:30) [39]
> Например, завести поле с хешем фамилии и имени в таблице
> и индексировать его.
Результат хэш-функции может быть одинаков для разных входных параметров.
← →
MsGuns © (2015-05-25 12:49) [40]>Павел Калугин © (25.05.15 07:51) [35]
>Я бы рекомендовал добавить три поля в которых держать отдельно фамилию имя и отчество в верхнем регистре и очищенных от "мусора". Мусором кроме Е признал бы И Й пробелы, дефисы запятые и т. д.
Это позволило бы эффективнее искать, к примеру, по имени и фамилии без отчества
Невнимательно читаешь. Юра в самом начале сказал, что база - чужая.
Кроме того, тебе, как опытному разработчику, нельзя не знать, что недостаточно просто "исправить" ошибки в базе РАЗОВО, надо еще менять бизнес-правила и, соответственно, политику пользовательских приложений, через которые в базу добавляется информация. А это уже совсем иная "опера".
← →
MsGuns © (2015-05-25 12:53) [41]Немного из личного опыта. Когда-то пришлось делать системку, где была база населения. На момент, когда я приступил к работе, в имеющейся БД было порядка 2 млн. записей. База была на фоксе. Я ее перетаскивал в Paradox.
Жутчайшие тормоза при работе прекратились лишь тогда, когда я ввел доп.поле-ключ - инициалы.
← →
Ega23 © (2015-05-25 13:06) [42]
> База была на фоксе. Я ее перетаскивал в Paradox.
Вот на этом месте завис. Даже не знаю, что сказать.
← →
кгшзх © (2015-05-25 13:07) [43]так это поди было еще при андропове
← →
Ega23 © (2015-05-25 13:13) [44]Я не большой спец по обоим, но перетаск данных из фокса в парадокс мне кажется удивительным при любой власти.
← →
junglecat © (2015-05-25 13:26) [45]были времена, когда и фокс и парадокс считались прогрессивными субд. Ну типа как сейчас DB2
← →
Юрий Зотов © (2015-05-25 13:36) [46]> Дмитрий С © (25.05.15 11:10) [38]
> завести поле с хешем фамилии и имени в таблице и индексировать его.
Дык... а я что сделал?
← →
Ega23 © (2015-05-25 14:03) [47]
> фокс и парадокс считались прогрессивными субд
ИМХО, фокс всегда был "прогрессивнее" парадокса.
← →
Павел Калугин © (2015-05-25 15:51) [48]Юрий Cергеич, один вариант привел - нет отчетсва.
Второй - когда имя и фамилию перепутали полями или при вводе данных или при поиске. По отдельным полям такое можно выловить "комбинацией"
from t_Pers as t
where ((t.fio = @fio) or (t.name = @fio) )and ((t.name = @name)or (t.fio = @name))
Если поле одно то придется уже по подстроке сравнивать, что опять же будет очень долго.
Ну и правильно напомнили, обвесить придется табличку триггером, который это поле/поля заполняет. Иначе вся прелесть пропадет.
← →
MsGuns © (2015-05-25 17:25) [49]>ИМХО, фокс всегда был "прогрессивнее" парадокса.
Посмеялсо :)
← →
Юрий Зотов © (2015-05-26 00:40) [50]Блин. Рано радовался. Отменили доп. поле и индекс по нему. Аргумент один - не нравится. И все аргументы "за" перед ним бессильны.
Бред какой-то.
← →
Ega23 © (2015-05-26 01:11) [51]
> Отменили доп. поле и индекс по нему. Аргумент один - не
> нравится.
Сделай доп.таблицу "один к одному", уже в ней - это самое поле. Может так "понравится".
← →
Jeer © (2015-05-26 01:26) [52]>Юрий Зотов
"Да пни ты их по яйцам" (С)
← →
Юрий Зотов © (2015-05-26 01:42) [53]> Ega23 © (26.05.15 01:11) [51]
Настаивают вот на чем - засосать всю таблицу (где миллион записей) в память и делать поиск на клиенте. То есть, как раз то, что я обозначил в сабже. Объясняю - не хватит памяти. Не верят. Ок, прямо на глазах внедряю засос всей таблицы в код и запускаю. Получаю, естественно, Out of memory. Убедились. Но говорят - тогда грузи эту таблицу кусками. Объясняю - скорость упадет на порядок - то есть придем к тем же 50 минутам, что и сейчас (в лучшем случае). Снова не верят. Я офигеваю, дорогая редакция. Вместо того, чтобы использовать простое, документированное, гарантированно работающее решение и уже отлаженный код, предлагают изобрести велосипед с квадратными колесами, а код поломать и отлаживать его по новой.
Блин, и че я переживаю? Забить болт и делать, как просят. Я предупредил, что из этого получится? Предупредил. Ну и получайте, что хотели. Только претензии потом сами себе предъявляйте.
← →
Сергей Суровцев © (2015-05-26 01:44) [54]>Юрий Зотов © (26.05.15 00:40) [50]
>Блин. Рано радовался. Отменили доп. поле и индекс по нему. Аргумент один - не нравится. И все аргументы "за" перед ним бессильны.
Жестко 2 варианта:
1) есть поле и 5 минут
2) нет поля и 50 минут.
"7 целых шапок из овцы не выкроишь никак" (с)
← →
Jeer © (2015-05-26 01:49) [55]>Настаивают вот на чем
Я давно выбрал вариант, что настаиваю я - профи в том, в чем и сомнений нет.
← →
Юрий Зотов © (2015-05-26 01:52) [56]> Сергей Суровцев © (26.05.15 01:44) [54]
Один спец считает, что 7 шапок из овцы - запросто. И даже решил показать, как это делается, написал код. Получил, естественно, все то же out of memory. После чего сказал, что это мой код глючит.
← →
Сергей Суровцев © (2015-05-26 01:57) [57]А если разделить задачу? Сначала выборка по фамилии, а уже из этого набора поиск по имени и отчеству?
← →
Сергей Суровцев © (2015-05-26 02:00) [58]>Юрий Зотов © (26.05.15 01:52) [56]
>Один спец считает, что 7 шапок из овцы - запросто. И даже решил показать, как это делается, написал код.
Наблюдал таких. Сначала громко орут и матерят Билли, Win, язык прог. А потом тихо бормочут под нос "как же это я это пропустил..."
← →
Юрий Зотов © (2015-05-26 02:09) [59]> Сергей Суровцев © (26.05.15 01:57) [57]
Так суть проблемы не в этом. Главный вопрос - где искать, на сервере или на клиенте. Если на сервере (как сейчас и как нормальные люди делают) - то да, либо поле есть (и тогда 5 минут), либо поля нет (и тогда 50 минут). А если на клиенте, то идет нехватка памяти и чтобы ее избежать нужен какой извращенный алгоритм. Чесать левое ухо правой рукой через голову (а точнее - через другое место). Причем совсем не факт, что этот алгоритм даст выигрыш в скорости. Скорее всего, не даст и все потуги окажутся напрасными.
← →
Сергей Суровцев © (2015-05-26 02:16) [60]>Юрий Зотов ©
>Записей в массиве порядка миллиона.
Если я правильно понял, то миллион это ВСЕ фамилии. Если вытащить на клиента 1 фамилию, то выборка будет порядка на 2-3 меньше. А уже ее копать до совпадения массивом. Тогда лишнее поле в базе не понадобится. Основной отсев на сервере, добить на клиенте.
← →
Германн © (2015-05-26 02:48) [61]Удалено модератором
← →
Kerk © (2015-05-26 02:54) [62]Сгенерировал хэш-таблицу с миллионом записей (всякий мусор вместо фамилий/имен/отчеств). Сделал к ней 10000 обращений. Выполняется быстрее, чем за секунду. Без каких-то оптимизаций, просто в лоб решение.
Так что если действительно проблемы с памятью (правда, трудно такое представить), нужно сокращать выборку насколько можно.
Сделать select по фамилии, например, как предыдущий оратор советует, а потом уже хэш-таблицу. Или даже по первой букве фамилии. Если база данных захвачена павианами, то это скорее всего единственный вариант.
← →
Kerk © (2015-05-26 02:59) [63]Проблемы с памятью могут еще быть вызваны ее фрагментацией. Можно в эту сторону покопать. Потому что чисто по объему миллион коротких строчек - это вообще ни о чем.
← →
Павел Калугин © (2015-05-26 07:22) [64]Всю таблицу на клиента тащить смысла нет достаточно Id и фио. Но я подозреваю что там не миллион записей, а восемьдесят миллионов ;) потому 3*255*80000000 на какого клиента не хватит если не писать это порциями в файл ну и так долее. По сути реализовать локальную СУБД ради одного запроса.
Канал связи клиент-сервер безразмерный и моментальный изобрели уже?
Юрий Сергеич а проверь ка сколько на сервере будет идти инсерт во временную индексированную таблицу этих полей Id и очищенное фио.
Попутно глянь насколько производительность сервера просядет.
Любые телодвижения с клиентом априори будут медленнее.
Выдернуть 80 кусков на 80 клиентов во каждом осуществить поиск и потом результат обработать к выдаче врятли получиться. И не быстрее так уж точно.
← →
Юрий Зотов © (2015-05-26 08:35) [65]Любые изменения структуры БД (в том числе, создание таблиц, пусть даже и временных) - табу.
← →
Павел Калугин © (2015-05-26 09:19) [66]Юрий Сергеевич, а хранимых процедур в DB2 разве нетути?
Временная таблица "живет" только на время сессии, как переменная. (ну или переменная табличного типа, если такая есть)
Так что "табу" на это не распространяется ну никак...
← →
Юрий Зотов © (2015-05-26 09:40) [67]> Павел Калугин © (26.05.15 09:19) [66]
Я в курсе. Но все равно низзя. Считай, что доступен только DML.
← →
D.N. Polezhaev © (2015-05-26 09:41) [68]А какие проблемы с памятью? Миллион фамилий по 12 букв в unicode это 22МБ данных. Ну с именами отчествами меньше , но всяко меньше 100МБ.
Не понимаю как у профи хватает нервов с идиотами работать )
← →
Юрий Зотов © (2015-05-26 09:46) [69]> хранимых процедур в DB2 разве нетути?
В DB2 - есть. А в базе- нет. Почему - не знаю. Нет - и все. Запрещены.
← →
junglecat © (2015-05-26 09:47) [70]Удалено модератором
← →
Юрий Зотов © (2015-05-26 09:54) [71]> D.N. Polezhaev © (26.05.15 09:41) [68]
> А какие проблемы с памятью?
Да пустяк - при выполнении SELECT где-то в недрах сервера приложений возникает исключение Out of memory.
:o)
← →
sniknik © (2015-05-26 10:20) [72]> Юрий Зотов © (26.05.15 00:40) [50]
> Блин. Рано радовался. Отменили доп. поле и индекс по нему. Аргумент один - не нравится. И все аргументы "за" перед ним бессильны.
>
> Бред какой-то.
"родной" конторой повеяло... с таким "убойным" аргументом. ничего не докажешь (у меня не получалось).
> Блин, и че я переживаю? Забить болт и делать, как просят. Я предупредил, что из этого получится? Предупредил. Ну и получайте, что хотели. Только претензии потом сами себе предъявляйте.
а вот тут нет, претензии будут только к тебе, как к исполнителю... я как то пробовал, доходило, прямой письменный приказ выбить с а ля "делать ТАК", ничем не помог, в итоге "мы имели ввиду так, но чтобы правильно работало" (т.е. с неправильной логикой/действиями по ней, но с правильным результатом) и "если не знаешь как правильно спроси у кого нибудь".
лучше вообще не делать. ИМХО. типа "либо делаю по своему, либо кто нибудь другой, ну вот хотя бы тот кто за это решение".
← →
Kerk © (2015-05-26 11:31) [73]
> Да пустяк - при выполнении SELECT где-то в недрах сервера
> приложений возникает исключение Out of memory
Почему бы причину не выяснить?
← →
D.N. Polezhaev © (2015-05-26 11:45) [74]Тогда я вообще не понимаю.
По условиям задачи в памяти лежат два списка, их нужно соединить по условию равенства.
Как эти списки могут лежать в памяти, если оказалось, что сервер приложений не может прокачать такой объем данных?
Значит на клиенте задачу решить нельзя из-за не возможности получить сырые данные.
На бд задачу тоже нельзя решить поскольку не дают оптимизировать бд.
Ну и что теперь - всем спасибо все свободны, ветка какая то ни о чем...
← →
Юрий Зотов © (2015-05-26 11:47) [75]> Kerk © (26.05.15 11:31) [73]
Потому что код сервера приложений недоступен, а в нашем коде все, что можно было оптимизировать по памяти, уже сделано.
← →
Kerk © (2015-05-26 11:48) [76]
> D.N. Polezhaev © (26.05.15 11:45) [74]
Дык первый раз что ли :)
← →
Юрий Зотов © (2015-05-26 11:51) [77]> Как эти списки могут лежать в памяти, если оказалось, что сервер
> приложений не может прокачать такой объем данных?
Допустим, каким-то волшебным способом мы это сделали. Тогда задача сводится к быстрому поиску ФИО. Быстрее, чем это сделал бы сервер БД.
Сабж об этом.
← →
Ega23 © (2015-05-26 11:51) [78]я тут вот что хочу сказать. Я не верю в 50 минут тупо в лоб без индексирования фулл-сканом на миллионе записей. Даже с upper и replace.
Такие дела.
← →
sniknik © (2015-05-26 11:53) [79]> Тогда я вообще не понимаю.
но чтоб к утру было сделано!
стандартная ситуация. :)
← →
Юрий Зотов © (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]> Ну, он вовсе не бесплатный, конечно :)
не офис, движок имею ввиду. достаточно. бесплатный. и в винду включен по умолчанию (вырезать трудоемко, хотя пару раз за время работы встречал умельцев... правда там куча всего дополнительно по отваливалось)
← →
Sha © (2015-05-26 15:30) [109]> sniknik © (26.05.15 15:24) [107]
> p.s. вы вообще с базами работали?
Русский язык не родной?
Слово МОЖЕТ понимаем правильно?
← →
MsGuns © (2015-05-26 15:33) [110]>кгшзх © (26.05.15 15:22) [105]
>он имел ввиду что нужна, но она там уже есть (дб2).
>вторая он имел ввиду не нужна
Не знаю что он имел "в виду", но имеется факт - прямая выборка из "базы" имеющимися в наличии средствами не удовлетворяет по производительности. "Подкрутить" сервер невозможно априори. Более того, нет никакой гарантии, что владелец "базы" не нвертит там чего-нибуль такого, что в итоге получим еще бОльшие тормоза.
← →
кгшзх © (2015-05-26 15:34) [111]прямая выборка из "базы" имеющимися в наличии средствами не удовлетворяет по производительности.
Подкрутить" сервер невозможно априори.
Всегда есть другой способ.
← →
MsGuns © (2015-05-26 15:36) [112]>Всегда есть другой способ.
Ну дык ! Открой тайну. А то тут народ колья друг об друга обламывает.
← →
кгшзх © (2015-05-26 15:41) [113]если ничего не менять и всасывать все лимоны фамилий в массив, то можно рядом сделать "индексный массив" с границами индексы первичного массива по начальным буквам.
и при поиске перебор всего первичного массива не потребуется. но это в лоб и это первое что я бы попробовал.
если бы не помогло, я запустил бы точно такой же но распределенный на нужное количество экземпляров sql запрос, распараллеленный по тем же начальным буквам.
и ждал бы асинхронно прихода.
← →
MsGuns © (2015-05-26 15:43) [114]Т.е. ты за хэш ?
Ну, по сути ?
← →
Sha © (2015-05-26 15:43) [115]> sniknik © (26.05.15 15:24) [107]
> никаких чудесных "сквозных между запросами каунтов" не бывает.
Это о чем, вообще?
← →
sniknik © (2015-05-26 15:50) [116]> Это о чем, вообще?
> 3 в цикле запрашивать Count и дробить диапазон фамилий.
объясни "в запросах", и при поставленном выше условии (есть 3 поля - фио), как будет участвовать Count, в "дроблении". т.е. первый запрос на 5 первых тыс к примеру (можно 6 или 3), второй на 5 вторых с 5й по 10ю тысячу и тд.
???
← →
кгшзх © (2015-05-26 15:54) [117]Т.е. ты за хэш ?
Ну, по сути ?
Я не против него, но на само хеширование потеряется куча времени.
В то время как если обозначить с какого по какой индекс первичного массива идут ИИИ (Иванов Иван Иванович) - это уже стопроцентно поможет перебору.
И памяти дополнительно на этот псевдо-индекс отъесться не так много.
← →
Kerk © (2015-05-26 15:58) [118]
> кгшзх © (26.05.15 15:54) [117]
> Я не против него, но на само хеширование потеряется куча времени.
У меня хэширование миллиона строк занимает несколько секунд.
Тут та ситуация, когда почти любое адекватное решение будет быстрее нескольких минут.
← →
Ega23 © (2015-05-26 16:04) [119]
> На 10 млн записей ? Ну-ну, Кулибин :)
На 10 миллионов записей СУБД уже есть. Я на всякий пожарный снова просмотрел начало, но не увидел, чтобы Зотыч про 10.000 запросов сразу написал.
И в такой постановке, скорее всего, данные действительно надо на клиент как-то тянуть. Возможно, тянуть частями, а после "дотягивать" изменения, на клиенте хэшировать, сортировать и хранить в бинарнике. Это к примеру.
Но СУБД ради этого дополнительную разворачивать - это из пушки по воробьям.
> Я не против него, но на само хеширование потеряется куча
> времени.
Да ну на. Это время будет на пару порядков (если не все три) меньше, чем передача данных по сети, раскладывание их по структурам, а также всякие дисковые операции при выборке.
← →
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]>Ega23 © (26.05.15 18:29) [135]
>Ага, вот только как быть с синхронизацией данных? Данные-то нужны актуальные.
А то они на клиенте актуальнее будут? Там и каналы связи похилее, и железо несравнимо. И тянуть надо не один раз, а на КАЖДОГО клиента.
← →
Сергей Суровцев © (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, не важно с пропуском или без.
дополнение
пропуски важны, вернее их отсутствие, приводились мной для "логики"(под впечатлением) - "берем общее количество, делим пополам, и т.д. до оставшегося огрызка". так то, при изменении алгоритма это само собой не важно.
← →
Sha © (2015-05-27 15:40) [149]>Сергей Суровцев © (27.05.15 14:39) [146]
>> запрос дайте "Ивановых Иванов Иванычей". Ну не может их быть 10^5 штук.
>Теоретически может. Это раз.
Тогда пусть падает. Это два )
> Конец диапазона может попасть в середину полных однофамильцев
> и тогда следующим шагом пойдут дубли.
Ситуация большого количества полностью идентичных фио обрабатывается, все попадут в один диапазон. Уже дописываю.
> Единственный случай, когда можно брать таким методом это сквозные ID,
> не важно с пропуском или без. Там можно подобрать границы
Дык мне давно уже тут запретили юзать ID )
← →
Kerk © (2015-05-27 15:41) [150]Раз пошла такая пьянка. А читать напрямую из БД в обход глючного сервера приложений уже кто-нибудь предлагал?
← →
Сергей Суровцев © (2015-05-27 15:48) [151]>Sha © (27.05.15 15:40) [149]
>Дык мне давно уже тут запретили юзать ID )
А зря. ))
Какой-то идентификатор в этой базе должен быть. Пусть не ID сурагатный, а какой-нибудь ИНН, номер карты, еще что... Как-то же эту базу используют? Четко человека выделяют? Иначе она годится только для подбора статистики по однофамильцам. ))
← →
Jeer © (2015-05-27 15:49) [152]В довесок:
А настроить сервер приложений никто не пробовал?
← →
кгшзх © (2015-05-27 15:59) [153]прямой поиск это конечно самое прямое.
но.
там же на апп-сервере скорее всего все по взрослому, ява, хибернейт и все дела.
то есть если апп-сервер стартовал в понедельник, и в базу ФИО насовали тыщщу новых персоналий,
то в самом sql сервере сегодня их может еще не быть.
← →
sniknik © (2015-05-27 16:06) [154]> Дык мне давно уже тут запретили юзать ID )
его нет в исходных задачи. + с ним какое никакое костыльное(тормозное) решение с "кусочной технологией" возможно. и ты бы легко "отмазался" от необходимости понять проблему ТС.
> Как-то же эту базу используют?
а может не используют, не базу конечно а таблицу, только хотят? может это таблица логов с действиями по именам, куда только добавляли, и тут "внезапно" - а нафига нам такие логи если их не читать? ставят задачу по обработке/предоставлению статистики.
не сталкивались = не бывает?
← →
Сергей Суровцев © (2015-05-27 16:07) [155]Я вообще не понимаю и представить пока не могу сам смысл первоначальной задачи. Из миллиона нужно выбрать по произвольным фамилиям 10тыс. При этом в итоговую выборку попадут, естественно и все полные однофамильцы. И кому это поможет? То есть в итоговом будет точно больше 10тыс. и потом в них опять копаться еще что-то выгрызать?
Хорошо бы иметь изначальное понимание того что есть и того что надо. А то решаем узкую промежуточную задачу без понимания нужного результата, так еще и спорим, как лучше. )))
← →
Сергей Суровцев © (2015-05-27 16:21) [156]>sniknik © (27.05.15 16:06) [154]
>не сталкивались = не бывает?
Я чаще сталкивался с тем, что заказчик не совсем представляет что и как ему нужно. Например описывает проблему ориентируясь только на то, что он сам предполагает ее решение. А то что решение может быть альтернативным, причем с тем же или лучшим даже не задумывается. Так к примеру бывает со всякими группировочными таблицами, которые были "всегда", но понять что они нужны только как промежуточный вариант когда у тебя исходные данные на бумаге, а если в базе, то любой результат можно получить минуя их, это понять бывает непросто.
← →
Jeer © (2015-05-27 16:23) [157]Да так сечас Ю.З. и рассказал :)
С большой вероятностью ему вооще никто и ничего не запрещает, иначе он там не работал бы, я - тоже.
← →
Юрий Зотов © (2015-05-27 16:40) [158]В таблице, где миллион записей, ID есть (причем почему-то строковый).
Во входных данных (где 10 тыс. ФИО) никакой уникальности нет.
← →
Сергей Суровцев © (2015-05-27 16:52) [159]То что в результирующую таблицу попадет первый попавшийся полный однофамилец из исходного миллиона устраивает? Других критериев отбора кроме ФИО нет? Или в результирующую надо собрать и всех однофамильцев тоже?
← →
sniknik © (2015-05-27 17:03) [160]> Я чаще сталкивался с тем, что заказчик не совсем представляет что и как ему нужно.
тут заказчик "местный бос", который по ходу развития ветки "зарубил" вполне годное, рабочее решение со словами "не нравится"... ну, я так думаю это показатель что и как он себе представляет ему нужно (у нас в конторе также кстати).
> никакой уникальности нет.
даже в ID? (строковый намекает...). если да, то считай его нет.
← →
sniknik © (2015-05-27 17:09) [161]кстати миллион это не много... серьезно, выборка миллиона это секунд 5, записать в локальную (акксесс) базу еще сек 20 - 30. 10 тыщь для обработки (джойнов/реплейсов) вообще не серьезно... а база/движок реально сделает все быстрее "велосипеда" как бы мы тут не изгалялись...
ИМХО, в дроблении/обработке кусками нет смысла. переложить (пусть каждый раз все) в локальную базу, + обработать в ней это 2-3мин. не должно быть проблемой.
← →
Eraser © (2015-05-27 17:17) [162]
> sniknik © (27.05.15 17:09) [161]
вы про локальную базу тут уже всю плешь проели. см. внимательно
> Юрий Зотов © (26.05.15 09:54) [71]
> > D.N. Polezhaev © (26.05.15 09:41) [68]
>
> > А какие проблемы с памятью?
>
> Да пустяк - при выполнении SELECT где-то в недрах сервера
> приложений возникает исключение Out of memory.
> :o)
← →
Юрий Зотов © (2015-05-27 17:37) [163]> Сергей Суровцев © (27.05.15 16:52) [159]
> То что в результирующую таблицу
1. Создание таблиц и представлений в БД запрещено, даже временных. На клиенте БД (которым является апп-сервер) можно создать таблицу в памяти, если хватит самой этой памяти.
> попадет первый попавшийся полный однофамилец
> из исходного миллиона устраивает?
2. Нет. Должны попасть все, у кого совпали ФИО (с учетом Ё-Е). То есть, если на входе есть Иванов Семен Петрович, а в БД таких 20 человек, то в результат должны попасть все 20 (причем, и СемЕны, и СемЁны).
> Других критериев отбора кроме ФИО нет?
3. Можно считать, что нет. Первичный отбор идет именно по ФИО. Получившийся в его результате первичный набор записей потом как-то обрабатывается и при обработке действительно учитываются другие критерии - но для сабжа это уже неважно. Важно получить этот самый первичный набор.
> Или в результирующую надо собрать и всех однофамильцев тоже?
См.п.п. 1 и 2.
← →
sniknik © (2015-05-27 17:49) [164]> см. внимательно
я это видел. и не верю... на миллионе записей всего, что-то не так делали, ИМХО, а вот access через свой исам возможно сделает либо так... либо по другому. там 1 запрос всего то будет, ошибиться трудно.
← →
sniknik © (2015-05-27 17:52) [165]а вот это
> На клиенте БД (которым является апп-сервер) можно создать таблицу в памяти
уже явный запрет на создание файлов/баз клиентом.
← →
Sha © (2015-05-27 18:23) [166]Допилил. Вроде работает.
На миллионе - мгновенно, на 10 миллионах - примерно 1 сек.
Время почти не зависит от того, как читаем: по частям или нет.
unit ZotovFIOForm;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Memo3: TMemo;
Memo1: TMemo;
Memo2: TMemo;
procedure Button1Click(Sender: TObject);
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
const
Kilo= 1000;
BaseLimit= 1000 * Kilo;
ListLimit= 10 * Kilo;
ReadLimit= 100 * Kilo;
function GenerateFio(i: integer): string;
begin;
Result:=Format("%.10d", [i]);
end;
//имитация наполнения базы
procedure GenerateBase(var Base: TStringList);
var
i, k: integer;
begin;
Base.Clear;
i:=0;
repeat;
inc(i);
if i mod 7<4 then begin;
if i mod 19=0 then k:=Random(50) else k:=0;
repeat;
Base.Add(GenerateFio(i));
dec(k);
until k<0;
end;
until Base.Count>=BaseLimit;
end;
//имитация создания списка искомых записей
procedure GenerateList(var List: TStringList);
var
i: integer;
begin;
List.Clear;
i:=0;
repeat;
inc(i,1+Random(200));
until List.Add(GenerateFio(i))>=ListLimit;
end;
//гарантируем отсутствие дубликатов в списке искомых записей
procedure DelDuples(var List: TStringList);
var
i: integer;
begin;
for i:=List.Count-1 downto 1 do if List[i]=List[i-1] then List.Delete(i);
end;
//поиск записей List в базе одним куском
procedure FindFio1(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; BaseLeft, BaseRight: integer;
var Res: TStringList);
begin;
if BaseLeft<BaseRight then while true do begin;
if List[ListLeft]<Base[BaseLeft] then begin;
inc(ListLeft); if ListLeft>=ListRight then exit;
end
else begin;
if List[ListLeft]>Base[BaseLeft] then inc(BaseLeft)
else repeat;
Res.Add(Base[BaseLeft]); inc(BaseLeft);
until (BaseLeft>=BaseRight) or (Base[BaseLeft]<>List[ListLeft]);
if BaseLeft>=BaseRight then exit;
end;
end;
end;
//имитация SQL COUNT и SQL SELECT
procedure CountAndGet(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; var BaseLeft, BaseRight, BaseCount: integer);
var
ValueFrom, ValueTo: string;
IncludeValueTo: boolean;
begin;
ValueFrom:=List[ListLeft];
IncludeValueTo:=false;
if ListRight=ListLeft then IncludeValueTo:=true
else if ListRight=List.Count then begin;
dec(ListRight); IncludeValueTo:=true;
end;
ValueTo:=List[ListRight];
if not Base.Find(ValueFrom, BaseLeft) then inc(BaseLeft)
else while (BaseLeft>0) and (Base[BaseLeft-1]=ValueFrom) do dec(BaseLeft);
if Base.Find(ValueTo, BaseRight) then begin;
inc(BaseRight);
if IncludeValueTo then while (BaseRight<Base.Count) and (Base[BaseRight]=ValueTo) do inc(BaseRight);
end;
BaseCount:=BaseRight-BaseLeft;
end;
//поиск записей List в базе по частям размером не более ReadLimit или максимума однофамильцев
procedure FindFio2(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList;
var Res: TStringList);
var
BaseLeft, BaseRight, BaseCount, IgnoreLeft, IgnoreRight, IgnoreCount, Current, Left, Right: integer;
Stack: array[0..31] of integer;
begin;
if ListLeft<ListRight then begin;
Current:=0; Stack[Current]:=ListRight;
Left:=ListLeft;
while Current>=0 do begin;
Right:=Stack[Current]; dec(Current);
while Left+1<Right do begin;
CountAndGet(List, Left, Right, Base, IgnoreLeft, IgnoreRight, BaseCount); //SQL COUNT HERE
if BaseCount<=ReadLimit then break;
inc(Current); Stack[Current]:=Right;
Right:=Left+(Right-Left) div 2;
end;
if BaseCount>0 then begin;
CountAndGet(List, Left, Right, Base, BaseLeft, BaseRight, IgnoreCount); //SQL SELECT HERE
FindFio1(List, Left, Right, Base, BaseLeft, BaseRight, Res);
end;
Left:=Right;
end;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
Base, List, Fio1, Fio2: TStringList;
begin;
Base:=TStringList.Create;
List:=TStringList.Create;
Fio1:=TStringList.Create;
Fio2:=TStringList.Create;
try
Memo3.Lines.Add("generate...");
//RandSeed:=0;
Randomize;
GenerateBase(Base); Base.Sort;
GenerateList(List); List.Sort; DelDuples(List);
Memo3.Lines.Add("start...");
FindFio1(List, 0, List.Count, Base, 0, Base.Count, Fio1);
Memo3.Lines.Add("done FindFio1: "+IntToStr(Fio1.Count));
if Kilo<=10 then Memo1.Text:=Fio1.Text;
FindFio2(List, 0, List.Count, Base, Fio2);
Memo3.Lines.Add("done FindFio2: "+IntToStr(Fio2.Count));
if Kilo<=10 then Memo2.Text:=Fio2.Text;
finally
Base.Free;
List.Free;
Fio1.Free;
Fio2.Free;
end;
end;
end.
← →
Sha © (2015-05-27 21:33) [167]исправлен баг в процедуре CountAndGet:
//имитация SQL COUNT и SQL SELECT
procedure CountAndGet(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; var BaseLeft, BaseRight, BaseCount: integer);
var
ValueFrom, ValueTo: string;
IncludeValueTo: boolean;
begin;
ValueFrom:=List[ListLeft];
IncludeValueTo:=false;
if ListRight=ListLeft then IncludeValueTo:=true
else if ListRight=List.Count then begin;
dec(ListRight); IncludeValueTo:=true;
end;
ValueTo:=List[ListRight];
if Base.Find(ValueFrom, BaseLeft)
then while (BaseLeft>0) and (Base[BaseLeft-1]=ValueFrom) do dec(BaseLeft);
if Base.Find(ValueTo, BaseRight)
then if IncludeValueTo
then begin;
inc(BaseRight);
while (BaseRight<Base.Count) and (Base[BaseRight]=ValueTo) do inc(BaseRight);
end
else while (BaseRight>0) and (Base[BaseRight-1]=ValueTo) do dec(BaseRight);
BaseCount:=BaseRight-BaseLeft;
end;
← →
Sha © (2015-05-28 09:22) [168]В процедуре поиска по частям FindFio2 количество вызовов процедуры CountAndGet с целью подсчета размера части уменьшено примерно в 2 раза.
Попутно исправлена небольшая неточность.
//поиск записей List в базе по частям размером не более ReadLimit или максимума однофамильцев
procedure FindFio2(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList;
var Res: TStringList);
type
TStack= record
Right, Size: integer;
end;
var
BaseLeft, BaseRight, BaseCount, IgnoreLeft, IgnoreRight, IgnoreCount, Current, Left, Right, Size: integer;
Stack: array[0..31] of TStack;
begin;
if ListLeft<ListRight then begin;
CountAndGet(List, ListLeft, ListRight, Base, IgnoreLeft, IgnoreRight, BaseCount); //SQL COUNT HERE
Current:=0; Stack[Current].Right:=ListRight; Stack[Current].Size:=BaseCount;
Left:=ListLeft;
while Current>=0 do begin;
Right:=Stack[Current].Right; Size:=Stack[Current].Size; dec(Current);
while (Size>ReadLimit) and (Left+1<Right) do begin;
inc(Current); Stack[Current].Right:=Right;
Right:=Left+(Right-Left) div 2;
CountAndGet(List, Left, Right, Base, IgnoreLeft, IgnoreRight, BaseCount); //SQL COUNT HERE
Stack[Current].Size:=Size-BaseCount;
Size:=BaseCount;
end;
if Size>0 then begin;
CountAndGet(List, Left, Right, Base, BaseLeft, BaseRight, IgnoreCount); //SQL SELECT HERE
FindFio1(List, Left, Right, Base, BaseLeft, BaseRight, Res);
end;
Left:=Right;
end;
end;
end;
← →
Игорь Шевченко © (2015-05-28 10:22) [169]Sha © (28.05.15 09:22) [168]
Как ты это читаешь - не понимаю
← →
Sha © (2015-05-28 11:55) [170]а я не читаю )
← →
Игорь Шевченко © (2015-05-28 11:58) [171]Sha © (28.05.15 11:55) [170]
Великолепно! Я верю, что твой код работает быстро, и даже очень быстро.
← →
Sha © (2015-05-28 12:23) [172]Игорь Шевченко © (28.05.15 11:58) [171]
На сам деле там есть "лишние" переменные, можно обойтись их меньшим числом, и есть что упростить. Например, имеет смысл разделить селект и каунт. Это всего лишь код, написанный за пару часов в перерывах между работой и совещаниями. Излишества и некрасивости - только для того, чтобы "оно почти работало". Даже не альфа-версия. Просто не падает при отладке. Нисколько не претендую на вылизанный код. Просто демонстрация идеи. А то тут не все слова иногда бывают понятны. Решил добавить кода. Дабы усугубить.
← →
MsGuns © (2015-05-28 12:29) [173]>На миллионе - мгновенно, на 10 миллионах - примерно 1 сек.
Огласите характеристики выч.системы (ПК), пжслт
← →
Sha © (2015-05-28 12:43) [174]> MsGuns © (28.05.15 12:29) [173]
>> На миллионе - мгновенно, на 10 миллионах - примерно 1 сек.
> Огласите характеристики выч.системы (ПК), пжслт
i5-3470 @ 3.2GHz, 4Gb
Приведено время работы процедур FindFio1 и FindFio2 при эмуляции COUNT/SELECT запросов к базе операциями в ОП. Чтобы получить реальное время работы на миллионе записей при максимальном размере части 10^5 записей, к этому времени надо добавить время выполнения примерно 10 COUNT и 10 SELECT. Кроме того, если SELECT возвращает несортированные записи, то надо добавить время сортировки записей в ОП.
← →
sniknik © (2015-05-28 13:04) [175]> Огласите характеристики выч.системы (ПК), пжслт
а смысл? "эмуляция" с позиционной(/локальной) логикой доступа, а ля "ValueTo:=List[ListRight];", вместо "клиент серверной" по данным, чем он показателен? да ничем.
или сомнения какие, что позиционное быстрее выбора по данным/условию (значение > чего-то, или меньше, пусть даже по индексу)? с указателями еще быстрее, а уж если оптимизатор выкинет расчеты как ни на что не влияющие, то будет вообще мгновенно на любом количестве...
> if Kilo<=10 then Memo1.Text:=Fio1.Text;
вот это вот условие оно же никогда не сработает вроде? значит вывода нет (проверить работу оптимизатора...).
← →
Sha © (2015-05-28 13:16) [176]> sniknik © (28.05.15 13:04) [175]
> "эмуляция" с позиционной(/локальной) логикой доступа, а ля "ValueTo:=List[ListRight];",
>вместо "клиент серверной" по данным, чем он показателен? да ничем.
Кому ничем, а кому говорит о том, что время работы алгоритма целиком определяется временем последовательного выполнения сервером БД 20-40 запросов. Т.е. алгоритм, в принципе, годен.
> или сомнения какие, что позиционное быстрее выбора по данным/условию...
че за бред
>> if Kilo<=10 then Memo1.Text:=Fio1.Text;
> вот это вот условие оно же никогда не сработает вроде?
> значит вывода нет (проверить работу оптимизатора...).
даже не думал, что тут возможны непонятки...
(подсказка: есть такое слово - отладка)
← →
MsGuns © (2015-05-28 13:28) [177]Для чистоты экперимента неплохо б прогнать тест на каком-нибудь целенончике с 500M ОЗУ.
← →
sniknik © (2015-05-28 14:11) [178]> че за бред
нормальный такой "бред"...
в общем то весь спор в том, что вам говорят - нельзя при работе сервером базы указывать позицию, говорить "дай мне с сотой по тысячную записи". нет там позиций. а вы пытаетесь это опровергнуть рассказывая, и теперь показывая как это можно сделать... почему то опять пользуясь "локальным алгоритмом"/списком, где это все есть, и это никем не опровергалось.
← →
MsGuns © (2015-05-28 14:26) [179]Коля, я вообще не врубился как они хотят заменить выборку из базы с ФИО на какие-то "индексы" (ID).
← →
Sha © (2015-05-28 14:28) [180]> sniknik © (28.05.15 14:11) [178]
>> че за бред
> нормальный такой "бред"...
> в общем то весь спор в том, что вам говорят - нельзя при работе сервером базы указывать позицию,
> говорить "дай мне с сотой по тысячную записи". нет там позиций.
> а вы пытаетесь это опровергнуть рассказывая,
> и теперь показывая как это можно сделать... почему то опять пользуясь "локальным алгоритмом"/списком, где это все есть,
> и это никем не опровергалось.
Не надоело?
Который по счету раз приписывать другому какую-то выдуманную хрень?
Нежелание понять чужую мысль просто зашкаливает.
Ты бы пример привел уже наконец, где обнаружил обращение к данным не по значению.
← →
Illusion © (2015-05-28 14:42) [181]Удалено модератором
← →
Eraser © (2015-05-28 14:52) [182]
> sniknik © (28.05.15 14:11) [178]
> нормальный такой "бред"...
> в общем то весь спор в том, что вам говорят - нельзя при
> работе сервером базы указывать позицию, говорить "дай мне
> с сотой по тысячную записи". нет там позиций. а вы пытаетесь
> это опровергнуть рассказывая, и теперь показывая как это
> можно сделать... почему то опять пользуясь "локальным алгоритмом"/списком,
> где это все есть, и это никем не опровергалось.
где первоисточник этого условия? или я что-то пропустил?
← →
ухты © (2015-05-28 15:01) [183]Задача же "одноразовая", так чего тут думать? еще можно понять если эти запросы высоко-нагрузочные, а так ...
← →
kaif © (2015-05-28 17:58) [184]А нельзя на клиенте какую-нибудь человеческую базу данных поставить?
Маленькую...
Туда закачать в нормальном виде, сделав три колонки, индекс, и там искать...
← →
Sha © (2015-05-28 21:42) [185]попытался немного повысить читаемость: букв стало больше, результат остался тем же )
unit ZotovFIOForm;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Memo1: TMemo;
Memo2: TMemo;
Memo3: TMemo;
Button1: TButton;
Button2: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
const
Kilo= 1000; //1..10000;
BaseLimit= 1000 * Kilo;
ListLimit= 10 * Kilo;
ReadLimit= 100 * Kilo;
function GenerateFio(i: integer): string;
begin;
Result:=Format("%.10d", [i]);
end;
//создание списка записей, среди которых будем искать (имитация БД)
procedure GenerateBase(var Base: TStringList);
var
i, k: integer;
begin;
Base.Clear;
i:=0;
repeat;
inc(i);
if i mod 7<4 then begin;
if i mod 19=0 then k:=Random(50) else k:=0;
repeat;
Base.Add(GenerateFio(i));
dec(k);
until k<0;
end;
until Base.Count>=BaseLimit;
end;
//создание списка искомых записей
procedure GenerateList(var List: TStringList);
var
i: integer;
begin;
List.Clear;
i:=0;
repeat;
inc(i,1+Random(200));
until List.Add(GenerateFio(i))>=ListLimit;
end;
//гарантируем отсутствие дубликатов в списке искомых записей
procedure DelDuples(var List: TStringList);
var
i: integer;
begin;
for i:=List.Count-1 downto 1 do if List[i]=List[i-1] then List.Delete(i);
end;
//определение границ интервала для SQL SELECT и SQL COUNT
procedure ListIndexesToValues(List: TStringList; ListLeft, ListRight: integer;
var ValueFrom, ValueTo: string; var IncludeValueTo: boolean);
begin;
ValueFrom:=List[ListLeft];
IncludeValueTo:=false;
if ListRight=ListLeft then IncludeValueTo:=true
else if ListRight=List.Count then begin;
dec(ListRight); IncludeValueTo:=true;
end;
ValueTo:=List[ListRight];
end;
//имитация SQL SELECT и SQL COUNT
procedure FakeSelectCount(const ValueFrom, ValueTo: string; IncludeValueTo: boolean;
Base: TStringList; var BaseLeft, BaseRight, BaseCount: integer);
begin;
if Base.Find(ValueFrom, BaseLeft)
then while (BaseLeft>0) and (Base[BaseLeft-1]=ValueFrom) do dec(BaseLeft);
if Base.Find(ValueTo, BaseRight)
then if IncludeValueTo
then begin;
inc(BaseRight);
while (BaseRight<Base.Count) and (Base[BaseRight]=ValueTo) do inc(BaseRight);
end
else while (BaseRight>0) and (Base[BaseRight-1]=ValueTo) do dec(BaseRight);
BaseCount:=BaseRight-BaseLeft;
end;
//определение количества записей в БД в заданном интервале значений
procedure SqlCount(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; var BaseCount: integer);
var
BaseLeft, BaseRight: integer;
ValueFrom, ValueTo: string;
IncludeValueTo: boolean;
begin;
ListIndexesToValues(List, ListLeft, ListRight, ValueFrom, ValueTo, IncludeValueTo);
FakeSelectCount(ValueFrom, ValueTo, IncludeValueTo, Base, BaseLeft, BaseRight, BaseCount); //SQL COUNT HERE
end;
//выборка записей из БД в заданном интервале значений
procedure SqlSelect(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; var BaseLeft, BaseRight: integer);
var
BaseCount: integer;
ValueFrom, ValueTo: string;
IncludeValueTo: boolean;
begin;
ListIndexesToValues(List, ListLeft, ListRight, ValueFrom, ValueTo, IncludeValueTo);
FakeSelectCount(ValueFrom, ValueTo, IncludeValueTo, Base, BaseLeft, BaseRight, BaseCount); //SQL SELECT HERE
end;
//поиск записей из интервала List в интервале Base, найденные помещаются в Res
procedure FindFio(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; BaseLeft, BaseRight: integer;
var Res: TStringList);
begin;
if BaseLeft<BaseRight then while true do begin;
if List[ListLeft]<Base[BaseLeft] then begin;
inc(ListLeft); if ListLeft>=ListRight then exit;
end
else begin;
if List[ListLeft]>Base[BaseLeft] then inc(BaseLeft)
else repeat;
Res.Add(Base[BaseLeft]); inc(BaseLeft);
until (BaseLeft>=BaseRight) or (Base[BaseLeft]<>List[ListLeft]);
if BaseLeft>=BaseRight then exit;
end;
end;
end;
//поиск записей List в базе одним запросом
procedure FindFio1(List, Base: TStringList; var Res: TStringList);
var
ListLeft, ListRight, BaseLeft, BaseRight: integer;
begin;
ListLeft:=0;
ListRight:=List.Count;
if ListLeft<ListRight then begin;
SqlSelect(List, ListLeft, ListRight, Base, BaseLeft, BaseRight);
FindFio(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, Res);
end;
end;
//поиск записей List в базе по частям размером не более ReadLimit или максимума однофамильцев
procedure FindFio2(List, Base: TStringList; var Res: TStringList);
type
TStack= record
Right, Count: integer;
end;
var
ListLeft, ListRight, PartCount, BaseLeft, BaseRight, BaseCount, Current: integer;
Stack: array[0..31] of TStack;
begin;
ListLeft:=0;
ListRight:=List.Count;
if ListLeft<ListRight then begin;
SqlCount(List, ListLeft, ListRight, Base, BaseCount);
Current:=0;
Stack[Current].Right:=ListRight;
Stack[Current].Count:=BaseCount;
while Current>=0 do begin;
ListRight:=Stack[Current].Right;
PartCount:=Stack[Current].Count;
dec(Current);
while (PartCount>ReadLimit) and (ListLeft+1<ListRight) do begin;
inc(Current);
Stack[Current].Right:=ListRight;
ListRight:=ListLeft+(ListRight-ListLeft) div 2;
SqlCount(List, ListLeft, ListRight, Base, BaseCount);
Stack[Current].Count:=PartCount-BaseCount;
PartCount:=BaseCount;
end;
if PartCount>0 then begin;
SqlSelect(List, ListLeft, ListRight, Base, BaseLeft, BaseRight);
FindFio(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, Res);
end;
ListLeft:=ListRight;
end;
end;
end;
← →
Sha © (2015-05-28 21:42) [186]
procedure TForm1.Button1Click(Sender: TObject);
var
Base, List, Fio1, Fio2: TStringList;
Seed: integer;
begin;
Base:=TStringList.Create;
List:=TStringList.Create;
Fio1:=TStringList.Create;
Fio2:=TStringList.Create;
try
if Sender<>nil then Memo3.Lines.Add("generate...");
Randomize;
//RandSeed:=-2046000228;
Seed:=RandSeed;
GenerateBase(Base); Base.Sort;
GenerateList(List); List.Sort; DelDuples(List);
if Sender<>nil then Memo3.Lines.Add("start...");
FindFio1(List, Base, Fio1);
if Sender<>nil then Memo3.Lines.Add("done FindFio1: "+IntToStr(Fio1.Count));
FindFio2(List, Base, Fio2);
if Sender<>nil then Memo3.Lines.Add("done FindFio2: "+IntToStr(Fio2.Count));
if (Sender<>nil) or (Fio1.Count<>Fio2.Count) then begin;
if Fio1.Count<>Fio2.Count then Memo3.Lines.Add(Format("error: %d %d %d",[Seed, Fio1.Count, Fio2.Count]));
if Kilo<=10 then begin;
Memo1.Text:=Fio1.Text;
Memo2.Text:=Fio2.Text;
end;
end;
finally
Base.Free;
List.Free;
Fio1.Free;
Fio2.Free;
end;
end;
//testing
procedure TForm1.Button2Click(Sender: TObject);
var
i: integer;
begin;
//RandSeed:=-2046000228;
if Kilo<>1 then begin;
Memo3.Lines.Add("wrong kilo");
exit;
end;
for i:=1 to 10000 do begin;
Button1Click(nil);
if i mod 1000=0 then Memo3.Lines.Add(IntToStr(i)+" loops done");
end;
Memo3.Lines.Add("All loops done");
end;
end.
← →
Игорь Шевченко © (2015-05-28 23:11) [187]Sha © (28.05.15 21:42) [185]
> procedure DelDuples(var List: TStringList);
> var
> i: integer;
> begin;
> for i:=List.Count-1 downto 1 do if List[i]=List[i-1] then
> List.Delete(i);
> end;
При всем уважении - зачем у параметра модификатор var ?
← →
ogs © (2015-05-28 23:45) [188]Удалено модератором
← →
Sha © (2015-05-29 02:12) [189]> Игорь Шевченко © (28.05.15 23:11) [187]
> ogs © (28.05.15 23:45) [188]
Как уже писал где-то выше, у этого кода одна цель - подкрепить идею, которую с переменным успехом пытался описать. Когда я (не особенно долго) думал над тем, какой выбрать тип для хранения данных, первая мысль была - это массив записей, содержащих строки и другую необходимую информацию (о буквах ё). Она базировалась на том, что, в принципе, весь код можно построить так, что в любой момент будет заранее известна результирующая длина такого массива, и можно будет работать с ним, в частности, удалять записи довольно быстро. Однако в этом случае код будет содержать ненужные для понимая основной идеи (о которой здесь и зашел спор) подробности этой самой организации, которые будут отвлекать внимание. Поэтому еще после некоторых размышлений победила идея простоты. Если вместо трех строк оставить одну, выкинуть ё-флаги, то можно будет использовать TStringList, у которого есть полезные и удобные в нашем случае вещи (Find, Grow, Delete), которые могут упростить код и сделать его прозрачнее, т.к., по-моему мнению, станет возможно обеспечить соответствие почти один-в-один между строкой текста и строкой кода. А если потом потребуется обсудить выкинутые детали - потом и обсудим, как изменить код под реальную задачу. Как раз для этого у параметров и оставлены маячки-модификаторы. Сейчас замедления это никакого не дает, зато потом может пригодиться. Это если говорить кратко. Относительно использования в примере TStringList были и другие соображения, менее заслуживающие упоминания.
← →
kaif © (2015-05-29 05:14) [190]Не хочу быть назойливым. Но наверняка в Java есть уже написанные движки маленьких баз данных, которые можно было бы использовать для решения подобных задач. Первое же, что попалось в гугле:
http://hsqldb.org/
HSQLDB (HyperSQL DataBase) is the leading SQL relational database software written in Java. It offers a small, fast multithreaded and transactional database engine with in-memory and disk-based tables and supports embedded and server modes.
Судя по тому, как автор сабжа хочет побольше разных идей, может стоит посвятить пару часов и копнуть в направлении подобных маленьких баз. Чтобы не изобретать велосипед на ровном месте. И не писать заново код всякий раз, когда заказчик попросит внести туда еще что-нибудь. Например, к каждому челу еще и дату его рождения.
← →
кгшзх © (2015-05-29 08:26) [191]вся ява вот и есть такая. точнее явосообщество.
"три биллионс девайсес ран ява"
"нас миллиарды, наверняка кто-то уже написал готовый класс за нас, надо его только найти"
и находят.
а потом мучительно сопрягают найденных ужей и ежей.
я-ву, я-ву взял я на ха-лявууууу.
← →
Sha © (2015-05-29 09:30) [192]Sha © (29.05.15 02:12) [189]
Тем не менее, помимо борьбы за чистоту параметров есть одна нереализованная оптимизация, которую давно держу в голове.
В реальной жизни на большом массиве искомых значений нам всегда удастся подобрать несколько элементов этого массива так, чтобы разбить все значения в БД на 10 примерно одинаковых по размеру частей. Но что делать, когда жизнь нереальная или массив маленький, или наоборот?
Подбирая размер части, мы каждый раз сдвигаем ее границы, пока в худшем случае не получим ListLeft+1=ListRight. Т.к. при этом мы считаем, что правая граница не входит в диапазон, то по-существу весь диапазон схлопнулся до однофамильцев из List[ListLeft]. И это можно учесть в запросе SELECT. Но было бы неверно учесть этот факт в запросе COUNT, т.к. это испортит статистику для следующей части. В таком случае встает вопрос, как быть, если мы хотим знать количество считанных записей заранее, скажем, чтобы выделить память? Т.к. эта ситуация, по идее, чрезвычайно редкая, и уж точно не возникнет более 10 раз за время работы алгоритма, то ничто не мешает нам пересчитать количество записей в диапазоне в этом редком случае, повторно выполнив COUNT, учитывающий текущее состояние вычислений.
← →
Игорь Шевченко © (2015-05-29 11:32) [193]
> Как раз для этого у параметров и оставлены маячки-модификаторы.
> Сейчас замедления это никакого не дает, зато потом может
> пригодиться.
var подразумевает, что значение переменной меняется в теле функции. Я изменения не увидел (другой List не подставился), поэтому и спросил.
← →
Sha © (2015-05-29 12:03) [194]Игорь Шевченко © (29.05.15 11:32) [193]
Разумеется. Так и должно быть.
Но var там окажется нужен, если мы вдруг захотим поменять тип параметра. Например, на массив записей.
← →
Sha © (2015-05-29 13:06) [195]Измененные с учетом [192] процедуры:
//выборка записей из БД в заданном интервале значений
procedure SqlSelect(List: TStringList; ListLeft, ListRight: integer;
Base: TStringList; var BaseLeft, BaseRight, BaseCount: integer);
var
IgnoreLeft, IgnoreRight, IgnoreCount: integer;
ValueFrom, ValueTo: string;
IncludeValueTo: boolean;
begin;
//учтем особый случай, когда диапазон схлопнулся до однофамильцев и однофамильцы находятся не в самом конце List
if (ListLeft+1=ListRight) and (ListRight<List.Count) then ListRight:=ListLeft;
ListIndexesToValues(List, ListLeft, ListRight, ValueFrom, ValueTo, IncludeValueTo);
//пересчитаем COUNT в особом случае, если нам требуется предварительно уточнить количество записей в диапазоне
if ListLeft=ListRight
then FakeSelectCount(ValueFrom, ValueTo, IncludeValueTo, Base, IgnoreLeft, IgnoreRight, BaseCount); //SQL COUNT HERE
FakeSelectCount(ValueFrom, ValueTo, IncludeValueTo, Base, BaseLeft, BaseRight, IgnoreCount); //SQL SELECT HERE
end;
//поиск записей List в базе одним запросом
procedure FindFio1(List, Base: TStringList; var Res: TStringList);
var
ListLeft, ListRight, BaseLeft, BaseRight, IgnoreCount: integer;
begin;
ListLeft:=0;
ListRight:=List.Count;
if ListLeft<ListRight then begin;
SqlSelect(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, IgnoreCount);
FindFio(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, Res);
end;
end;
//поиск записей List в базе по частям размером не более ReadLimit или максимума однофамильцев
procedure FindFio2(List, Base: TStringList; var Res: TStringList);
type
TStack= record
Right, Count: integer;
end;
var
ListLeft, ListRight, PartCount, BaseLeft, BaseRight, BaseCount, Current: integer;
Stack: array[0..31] of TStack;
begin;
ListLeft:=0;
ListRight:=List.Count;
if ListLeft<ListRight then begin;
SqlCount(List, ListLeft, ListRight, Base, BaseCount);
Current:=0;
Stack[Current].Right:=ListRight;
Stack[Current].Count:=BaseCount;
while Current>=0 do begin;
ListRight:=Stack[Current].Right;
PartCount:=Stack[Current].Count;
dec(Current);
while (PartCount>ReadLimit) and (ListLeft+1<ListRight) do begin;
inc(Current);
Stack[Current].Right:=ListRight;
ListRight:=ListLeft+(ListRight-ListLeft) div 2;
SqlCount(List, ListLeft, ListRight, Base, BaseCount);
Stack[Current].Count:=PartCount-BaseCount;
PartCount:=BaseCount;
end;
if PartCount>0 then begin;
SqlSelect(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, PartCount);
if PartCount>0 then FindFio(List, ListLeft, ListRight, Base, BaseLeft, BaseRight, Res);
end;
ListLeft:=ListRight;
end;
end;
end;
← →
Jeer © (2015-05-30 18:17) [196]Шо интересно - Зотову это помогло или так, было за потрепаться?
← →
картман © (2015-05-30 21:56) [197]Индексы для хакеров))
← →
Inovet © (2015-05-30 22:33) [198]Я там где-то ещё в самом начале про мемори готовую тейбл говорил. Уж про целую СУБД не решился упомянуть, ибо как-то оно совсем неправильно. Но всяко может быть, как видим.
← →
Romkin © (2015-06-02 10:44) [199]Вот смотрю и думаю: из БД же можно взять отсортированные уже строки, пусть по частям и медленно. Отсортировать массив фио и за один проход слить с имеющимся в БД, выявляя равенство.
Не будет ли это достаточно быстро?
← →
Юрий Зотов © (2015-06-02 11:08) [200]> Romkin © (02.06.15 10:44) [199]
Вот такой запрос работает быстро:select ... from ... where
фамилия = :param1 and имя = :param2 and отчество = :param3
Но вся проблема в функциях. Как только в запрос включаем функции, начинаются тормоза:select ... from ... where
replace(upper(фамилия), "Ё", "Е") = :param1
and
replace(upper(имя), "Ё", "Е") = :param2
and
replace(upper(отчество), "Ё", "Е") = :param3
где параметры - это входные ФИО, соответственно подготовленные.
← →
sniknik © (2015-06-02 11:11) [201]> Как только в запрос включаем функции, начинаются тормоза:
по вычислению индекс не используется, считай нет его там. всегда фул скан.
← →
Sha © (2015-06-02 11:13) [202]> Romkin © (02.06.15 10:44) [199]
> Вот смотрю и думаю...
Именно это и делает предложенный код
← →
Sha © (2015-06-02 11:19) [203]> Юрий Зотов © (02.06.15 11:08) [200]
> Но вся проблема в функциях.
> Как только в запрос включаем функции, начинаются тормоза
Понимаю, что текущая структура базы - священная корова,
но все же рискну предложить хранение фио без буквы ё,
а замены всех е-ё в фио задавать флагами в отдельном целочисленном поле.
← →
Romkin © (2015-06-02 12:06) [204]
> Но вся проблема в функциях. Как только в запрос включаем
> функции, начинаются тормоза:
Нее, where не надо. select replace(upper(фамилия || " " || имя), "Ё", "Е")... from ... order by 1 rows from 1 to 10000; и т.д., пусть БД трудится.
> Именно это и делает предложенный код
Тогда он должен быть короче, слишком много эмуляции :) Зачем делить на равные интервалы, когда можно просто читать по n строк?
← →
Romkin © (2015-06-02 12:08) [205]Вообще загрузился. Даже пакетами читать не надо, просто итератор (ну или если нельзя - то итератор с пакетным чтением внутри).
← →
sniknik © (2015-06-02 12:15) [206]> Понимаю, что текущая структура базы - священная корова,
предложение было на первой странице, по моему - не трогать существующее, но добавить поле поиска, индексированное, с нужными преобразованиями "replace(upper...", одно для трех (слить с разделителем). заполнялось бы при добавлении/изменении основных. т.е. вполне нормальное, ничего не ломающее, ни на что кардинально не влияющее, с возможностью "отката без потерь"...
единственное размер таблицы в 2 раза больше станет (на 1 миллионе, ИМХО, не существенно, ну было 300мб станет 600мг стоит париться?), ну и если кто работал с таблицей через "звездочку" (не буду говорить что это нельзя, плохо... все знают, и все равно многие делают. по разным причинам) те получат дополнительный тормоз на запросах.
отказались с "аргументом" боса "не нравится".
← →
Юрий Зотов © (2015-06-02 14:32) [207]В общем, пока что сделано так:
select ... from ... where
replace(upper(
фамилия || " " || имя || " " || coalesce(отчество, " ")), "Ё", "Е") = :param1
При таком запросе, если в таблице есть соответствующий индекс, то DB2 его использует автоматом. В тестовой базе он есть, в боевой - нет. Но боевой сервер гораздо мощнее тестового, поэтому решили, что бороться за память/скорость будем, если возникнут проблемы на боевом.
← →
sniknik © (2015-06-02 14:54) [208]> При таком запросе, если в таблице есть соответствующий индекс, то DB2 его использует автоматом.
DB2 умеет по выражению как фокспро?
есть сделанный (такая фигня проходит?) -
CREATE INDEX ComplexIndex ON (replace(upper(фамилия || " " || имя || " " || coalesce(отчество, " ")), "Ё", "Е"))
?
← →
Юрий Зотов © (2015-06-02 15:14) [209]> sniknik © (02.06.15 14:54) [208]
Если верить документации IBM, то умеет, начиная с 10.5 (function-based indexes). А у нас, к сожалению, более ранняя. Но можно построить автовычисляемое поле (в котором будет это самое выражение), а индекс вешать уже на это поле. Правда, могут возникнуть небольшие тормоза (за счет переиндексации), но они не должны быть ощутимыми.
← →
SergP © (2015-06-02 15:15) [210]
> select ... from ... where
> replace(upper(
> фамилия || " " || имя || " " || coalesce(отчество, "
> ")), "Ё", "Е") = :param1
А не лучше ли один раз в таблице исправить все Ё на Е, чем потом постоянно ощущать тормоза, связанные с поиском?
← →
Юрий Зотов © (2015-06-02 15:27) [211]> SergP © (02.06.15 15:15) [210]
Низзя. Базой командуем не мы. Но даже если было бы можно, то все равно низзя. Потому что ФИО в базе должно быть точно таким же, как в паспорте.
Ну и возможны коллизии. Мы же не знаем, какой еще софт, кроме нашего, с это базой работает. Поменяешь Ё на Е - а где-то что-то отвалиться может.
← →
SergP © (2015-06-02 16:12) [212]1. Почему в первом посте (как собственно и в теме) речь шла о массиве, а не о базе?
2. Базой командуем не мы, но возможность ее модификации имеется?
Например если создать еще одно поле в виде ФИО где буквы Ё уже будут заменены на Е, а для того, чтобы оно заполнялось/изменялось вместе с заполнением/изменением оригинальных полей, использовать триггеры. Или так нехорошо?
← →
Юрий Зотов © (2015-06-02 16:38) [213]> SergP © (02.06.15 16:12) [212]
> 1. Почему в первом посте (как собственно и в теме) речь шла о массиве,
> а не о базе?
Потому что, если бы удалось закачать все таблицу в массив и найти алгоритм быстрого поиска по этому массиву, то к записям в этом массиве уже можно применять любые функции. Вариант обходной и не самый лучший, но тоже вариант.
> 2. Базой командуем не мы, но возможность ее модификации имеется?
По согласованию с хозяевами. Которое не всегда удается. И об этом говорилось.
> Например если создать еще одно поле в виде ФИО где буквы
> Ё уже будут заменены на Е, а для того, чтобы оно
> заполнялось/изменялось вместе с заполнением/изменением
> оригинальных полей
Об этом тоже уже говорилось, несколько раз. Последний - [209].
← →
SergP © (2015-06-02 16:49) [214]
> Потому что, если бы удалось закачать все таблицу в массив
> и найти алгоритм быстрого поиска по этому массиву, то к
> записям в этом массиве уже можно применять любые функции.
> Вариант обходной и не самый лучший, но тоже вариант.
Ну с алгоритмом быстрого поиска по массиву проблем-то не должно быть.
Единственная проблема, как я понимаю, заключается во времени закачки таблицы в массив?
← →
Юрий Зотов © (2015-06-02 16:52) [215]> SergP © (02.06.15 16:49) [214]
> Единственная проблема, как я понимаю, заключается во времени
> закачки таблицы в массив?
В нехватке памяти. Почему и возникла мысль грузить таблицу кусками. А Саша даже пример написал (за что ему спасибо, этот пример может очень пригодиться).
← →
sniknik © (2015-06-02 16:57) [216]> закачать все таблицу в массив
не лучший вариант перекидывать все в массив, двойной расход памяти как минимум... почему не работать в с полученным рекордсетом (ADO например, он и индекс локальный может, и поиск по нему)? рекордсет удается получить, вот такой к примеру -
select replace(upper(фамилия || " " || имя || " " || coalesce(отчество, " ")), "Ё", "Е") AS param1 from table1
?
без условия where, без джойнов с риском неправильно составить условие и получить гетерогенное объединение, а простую "плоскую таблицу". так и не понял из ранних обсуждений.
← →
Romkin © (2015-06-02 17:51) [217]
> не лучший вариант перекидывать все в массив, двойной расход
> памяти как минимум... почему не работать в с полученным
> рекордсетом (ADO например, он и индекс локальный может,
> и поиск по нему)?
Проблема в нехватке памяти. Ява там, панимаш?
У меня Питон за секунду файл в 10000 с миллионом записей сверяет, тихо расходуя свои 30 Мб оперативы, но это несолидно.
← →
Юрий Зотов © (2015-06-02 18:06) [218]> Romkin © (02.06.15 17:51) [217]
Out of Memory возникает в апп-сервере (почему - вопрос не ко мне). С этим приходится считаться.
← →
SergP © (2015-06-02 19:15) [219]
> не лучший вариант перекидывать все в массив, двойной расход
> памяти как минимум...
Если в таблице информация обновляется очень редко, а поисков по ФИО нужно производить очень много, типа так что загрузил утром таблицу в массив и целый день постоянно там что-то ищется, то почему бы и нет?
Тем более что в массиве информацию можно держать в несколько ином виде чем в таблице, более удобном для поиска, и чтобы минимизировать кол-во используемой памяти...
← →
Сергей Суровцев © (2015-06-02 19:29) [220]>sniknik © (02.06.15 16:57) [216]
>без условия where, без джойнов с риском неправильно составить условие и
>получить гетерогенное объединение, а простую "плоскую таблицу". так и не
>понял из ранних обсуждений.
А почему без джойнов? Обе таблицы на сервере. И та что на 10тыс, и та что на 1 миллион. Сервак говорят мощный. Это как раз самое его дело, такие запросы обрабатывать.
>Юрий Зотов © (02.06.15 16:52) [215]
>В нехватке памяти. Почему и возникла мысль грузить таблицу кусками. А
>Саша даже пример написал (за что ему спасибо, этот пример может очень
>пригодиться).
Пример полезный, только после появления информации о наличии ID в основной таблице, пусть и строковой привязка к ФИО для задачи перекачки теряет актуальность.
← →
Сергей Суровцев © (2015-06-02 19:32) [221]>SergP © (02.06.15 19:15) [219]
>Если в таблице информация обновляется очень редко, а поисков по ФИО
>нужно производить очень много, типа так что загрузил утром таблицу в
>массив и целый день постоянно там что-то ищется, то почему бы и нет?
То есть актуальной сегодняшней информации в обработке не будет никогда? ))
← →
SergP © (2015-06-02 19:57) [222]
> То есть актуальной сегодняшней информации в обработке не
> будет никогда? ))
Не. Ну я же не знаю что хранит эта таблица и для чего нужен поиск по ней, и насколько важно иметь ли для поиска "актуальную сегодняшнюю информацию".
Все зависит от ситуации.
← →
Юрий Зотов © (2015-06-02 20:12) [223]> Сергей Суровцев © (02.06.15 19:29) [220]
> Обе таблицы на сервере.
Таблица одна (которая на миллион записей). Входящие ФИО (которых 10 тыс.) берутся из файла.
← →
sniknik © (2015-06-02 22:21) [224]> А почему без джойнов?
для проверки, убедится что нет типа такого
... from table1, table2 where 1=:param2
или другой похожей глупости. достаточно допустить логическую ошибку в условии и никакой памяти не напасешься
(неявный джойн всего со всем, 1 миллион * 10 тыс = 27 гиг чисто данных, без структуры, при выборке всего 3х полей по 1 байту...)
← →
sniknik © (2015-06-02 22:25) [225]> Сервак говорят мощный. Это как раз самое его дело, такие запросы обрабатывать.
:) ... вот бы тебя свести с нашими "бд-админами". у нас тоже сервак мощный, а проблемы похожие.
← →
Сергей Суровцев © (2015-06-02 23:38) [226]>sniknik © (02.06.15 22:21) [224]
>для проверки, убедится что нет типа такого
Страховки от глупостей еще не придумали. Только неусыпный контроль спасет отца русской демократии.
>:) ... вот бы тебя свести с нашими "бд-админами". у нас тоже сервак мощный, а проблемы похожие.
А есть ли в природе админы, довольные своим железом?
← →
Игорь Шевченко © (2015-06-03 10:24) [227]sniknik © (02.06.15 22:25) [225]
> вот бы тебя свести с нашими "бд-админами". у нас тоже сервак
> мощный, а проблемы похожие.
Какой-то ты нелояльный ни разу, все у вас плохо, и с XML проблемы, и с базами данных, и код корявый пишут :)
← →
Romkin © (2015-06-03 11:42) [228]
> Out of Memory возникает в апп-сервере (почему - вопрос не
> ко мне). С этим приходится считаться.
При слиянии нужна одна запись в каждый момент времени. Думаю, что фетчить по одной или пакетами понемногу возможно, просто набор должен быть уже отсортирован на сервере БД, о чем я говорю.
← →
sniknik © (2015-06-03 12:14) [229]> Какой-то ты нелояльный ни разу, все у вас плохо, и с XML проблемы, и с базами данных, и код корявый пишут :)
ну, что есть то есть, и чем дольше работаю с тем большим количеством проблем приходится сталкиваться... а у вас не так? врете небось.
← →
Юрий Зотов © (2015-06-03 13:24) [230]> Romkin © (03.06.15 11:42) [228]
Рома, о каком слиянии идет речь?
Есть таблица БД с миллионом ФИО. Есть 10 тыс. входных ФИО, загруженных из дискового файла (а в БД их нет - какое слияние?). Каждая входная запись может совпасть с одной или несколькими записями из БД (а может и не совпасть ни с одной).
Задача: для каждой входной записи получить все ее совпадения с БД. С минимальным расходом памяти, с приемлемой скоростью, без изменения структуры БД и считая букву Ё буквой Е.
Варианты решения "в лоб" очевидны, но ни один из них не прокатывает. Потому что либо требует модификации БД, либо слишком медленный, либо слетает по памяти апп-сервер.
← →
Romkin © (2015-06-03 15:59) [231]
> Рома, о каком слиянии идет речь?
>
> Есть таблица БД с миллионом ФИО. Есть 10 тыс. входных ФИО,
> загруженных из дискового файла (а в БД их нет - какое слияние?
> ). Каждая входная запись может совпасть с одной или несколькими
> записями из БД (а может и не совпасть ни с одной).
>
> Задача: для каждой входной записи получить все ее совпадения
> с БД. С минимальным расходом памяти, с приемлемой скоростью,
> без изменения структуры БД и считая букву Ё буквой Е.
>
> Варианты решения "в лоб" очевидны, но ни один из них не
> прокатывает. Потому что либо требует модификации БД, либо
> слишком медленный, либо слетает по памяти апп-сервер.
Я вообще ничего уже не понимаю. Просто один раз маленькими пакетами прочитать миллион записей из БД можно? Не запоминая их?
Если да, - то читать сразу с сортировкой из БД и мерджить, выявляя дубликаты. И что-то мне подсказывает, что так будет быстрее всего :)
← →
SergP © (2015-06-03 16:09) [232]
> Потому что либо требует модификации БД
Любая модификация запрещена? Или запрещено только менять структуру и данные в имеющихся объектах?
например в БД можно создавать какие-нить временные таблицы или материализованные представления?
← →
картман © (2015-06-03 16:11) [233]
> Юрий Зотов © (03.06.15 13:24) [230]
локальный индекс, не?
← →
Юрий Зотов © (2015-06-03 16:35) [234]> Romkin © (03.06.15 15:59) [231]
Давай не примере.
Миллионная таблица в базе (первое поле - строковый ID):
a Иванов Иван Иванович
b Петров Петр Петрович
c Семенов СемЁн Семенович
d Семенов СемЕн Семенович
e Петров Петр Петрович
и т.д.
В 10-тысячном входном файле (нумерация строк условная)
1 Иванов Иван Иванович
2 Петров Петр Петрович
3 Семенов СемЕн Семенович
4 Нектов Некто Нектович
и т.д.
В цикле j := 1 to 4 идем по строкам входного файла. На каждом витке цикла должны получить следующее:
при j = 1 (на входе - Иванов Иван Иванович)
a Иванов Иван Иванович
при j = 2 (на входе - Петров Петр Петрович)
b Петров Петр Петрович
e Петров Петр Петрович
при j = 3 (на входе - Семенов СемЕн Семенович)
c Семенов СемЁн Семенович
d Семенов СемЕн Семенович
при j = 4 (на входе - Нектов Некто Нектович)
пусто
и т.д.
Все полученные таким образом записи накапливаются в общем списке и затем как-то обрабатываются. Отказаться от этого общего списка (ради экономии памяти) по ряду причин нельзя.
← →
Юрий Зотов © (2015-06-03 16:38) [235]> SergP © (03.06.15 16:09) [232]
Да, любая модификация запрещена. Можно считать, что от всего SQL остался только DML.
← →
Romkin © (2015-06-03 16:40) [236]
> например в БД можно создавать какие-нить временные таблицы
> или материализованные представления?
Нельзя ему.
Но сделать запрос видаselect translate(upper(LastName), "Ё", "Е") as name ... from ... order by nameили подобный, думаю, ничто не мешает.
def find_equal(seq1, seq2):
it1, it2 = iter(seq1), iter(seq2) # iterators
name1, name2 = next(it1), next(it2)
try:
d = [] #list
while True:
if name1 == name2:
d.append(name1)
name1 = next(it1)
name2 = next(it2)
elif name1 > name2:
name2 = next(it2)
elif name2 > name1:
name1 = next(it1)
except StopIteration: # NoSuchElementException
return d
← →
Romkin © (2015-06-03 16:44) [237]
> Давай не примере.
1. Указанный запрос с order by выдаст записи в отсортированном виде. Если итерировать по нему неможно - указывать rows или limit, кусками читать.
2. Список в памяти отсортировать
3. Проитерировать оба отсортированных списка, выявляя дубликаты.
← →
ухты © (2015-06-03 16:51) [238]
> В цикле j := 1 to 4 идем по строкам входного файла.
неужели там нет других способов, xml к примеру или table types или еще чего?
только работать как с допотопной базой можно?
← →
Юрий Зотов © (2015-06-03 16:57) [239]> ухты © (03.06.15 16:51) [238]
> xml
В реальности, там или текстовый файл, или файл xml. По сути, это без разницы. Только парсеры разные, а в итоге все равно получаем входной список ФИО.
← →
ухты © (2015-06-03 16:58) [240]да я не про файл а про запросы
← →
Юрий Зотов © (2015-06-03 16:59) [241]> *текстовый файл
Точнее, файл CSV.
← →
картман © (2015-06-03 17:27) [242]
> Юрий Зотов © (03.06.15 16:38) [235]
>
> > SergP © (03.06.15 16:09) [232]
>
> Да, любая модификация запрещена
в смысле, на клиенте строить индекс, свой собственный
← →
SergP © (2015-06-03 19:42) [243]
> в смысле, на клиенте строить индекс, свой собственный
Это как? Таблица в базе на сервере а индекс на клиенте?
Тогда как его строить-то? Ведь для его построения понадобится вся информация из таблицы. А если "выкачивать" всю инфу из таблицы на клиент, то почему бы ее сразу и не запихнуть в массив и работать уже с массивом? тогда и индекс строить не нужно, ибо достаточно преобразовать буквы Ё->Е в массиве, затем отсортировать массив и искать по нему обычным бинарным поиском.
Или я чего-то не понимаю?
1 миллион записей, из которых в массиве нам нужны только поля с фамилией, именем, и отчеством, ну еще плюс первичный ключ - это получится массив размером навскидку 50-70 мб, если эту инфу тянуть с базы в естественном виде, если поизвращаться - то можно уменьшить до 16 мб и даже меньше.
← →
картман © (2015-06-03 19:56) [244]
> SergP © (03.06.15 19:42) [243]
или так
← →
Юрий Зотов © (2015-06-03 20:02) [245]> SergP © (03.06.15 19:42) [243]
> 1 миллион записей, из которых в массиве нам нужны только поля с
> фамилией, именем, и отчеством, ну еще плюс первичный ключ
Нет, конечно. Я не упомянул другие поля, поскольку к проблеме они не относятся. Просто написал, что при такой попытке идет вылет по памяти.
На самом же деле тащатся 22 поля. Они используются при обработке.
← →
SergP © (2015-06-03 20:15) [246]
> Юрий Зотов © (03.06.15 20:02) [245]
>
> > SergP © (03.06.15 19:42) [243]
>
> > 1 миллион записей, из которых в массиве нам нужны только
> поля с
> > фамилией, именем, и отчеством, ну еще плюс первичный ключ
>
> Нет, конечно. Я не упомянул другие поля, поскольку к проблеме
> они не относятся. Просто написал, что при такой попытке
> идет вылет по памяти.
>
> На самом же деле тащатся 22 поля. Они используются при обработке.
>
Ну так для поиска нужны только ФИО и первичный ключ, а остальные поля уже можно с базы быстро достать по первичному ключу.
А если при попытке тянуть только ПК и ФИО идет вылет по памяти, можно попробовать тянуть по частям. Не совсем понял какая проблема возникает если тянуть таблицу по частям нарезанную поперек (т.е. по по записям), но а если попробовать нарезать вдоль?
например одним запросом тянем ПК и фамилию, другим ПК и имя, третим ПК и отчество?
Ну или вообще не тянуть например фамилию в том виде в котором она там имеется, а стянуть двумя запросами: первым запросом "справочник уникальных фамилий", вторым ПК и код фамилии по "справочнику"?
← →
SergP © (2015-06-03 20:55) [247]
> Просто написал, что при такой попытке идет вылет по памяти.
При какой попытке?
при попытке стянуть 3-4 поля или 22 поля?
← →
sniknik © (2015-06-03 23:20) [248]> Это как? Таблица в базе на сервере а индекс на клиенте?
ADODataSet может строить индекс в памяти, по вытянутым данным естественно, или данные можно сохранить в локальную таблицу/базу и индексировать/обрабатывать независимо от сервера.
есть варианты короче. и их уже предлагали.
> то почему бы ее сразу и не запихнуть в массив и работать уже с массивом?
"сразу" это работать с рекордсетом, не тратя времени на перекладывание, и возможностей у него больше, и не нужно занимаемую память удваивать на полученный рекердсет с данными + еще и массив на момент запихивания.
← →
d2pak © (2015-06-03 23:25) [249]>Юрий Зотов
А на какой машине вы пытаетесь выполнять инструкции?
Я к тому, что миллион записей не так уж и много...
← →
SergP © (2015-06-04 11:56) [250]
> но translate и upper его убивают
В каком виде хранятся ФИО в БД?
Т.е.:
ПУПКИН ВАСИЛИЙ ИВАНОВИЧ
Пупкин Василий Иванович
пупкин василий иванович
или там нет никакого порядка?
т.е. обязательно ли использовать UPPER применительно к полям таблицы?
← →
Romkin © (2015-06-04 11:56) [251]
> Я к тому, что миллион записей не так уж и много...
Не так уж мало, особенно с доп. полями и на сервере приложений, там обвязка может быть большой. И он сам может быть наивно построен.
Но вопрос-то в другом: для поиска все записи не нужны, при слиянии единовременно нужна одна запись из запроса каждый раз, для сравнения. И если сервер БД не падает при сортировке миллиона записей, то все должно пройти, и быстро.
← →
Ega23 © (2015-06-04 12:02) [252]- Я тебе рубль дал?
- Дал.
- За кефиром послал?
- Послал.
- Кефира не было?
- Не было.
- Где деньги?
- Какие деньги?
(с)
← →
Ega23 © (2015-06-04 12:02) [253]Опс, веткой ошибся
← →
Inovet © (2015-06-04 15:44) [254]> [250] SergP © (04.06.15 11:56)
> т.е. обязательно ли использовать UPPER применительно к полям таблицы?
Так сказано же, что надо. Видимо в XML сразу в Upper передаётся, а вбазе, по идее, должно правильно быть, как в паспорте, в смысле - регистр символов.
← →
Inovet © (2015-06-04 15:49) [255]> [254] Inovet © (04.06.15 15:44)
> как в паспорте
А в паспорте как раз тоже в Upper. Ну тогда по другим причинам надо, зря что ли бы Юра мудрил.
← →
Юрий Зотов © (2015-06-04 17:04) [256]Нужна не сама Upper, нужна независимость от регистра. Например, Оглы и оглы - это должно быть одно и то же.
Кроме того, если не поднимать в upper, то replace придется использовать дважды (для Ё и для ё). А это функция совсем не быстрая.
← →
Romkin © (2015-06-04 17:15) [257]БД предназначена для массивной обработки данных, логично предварительно на ней обработку и делать, оно быстро.
Сейчас попробовал, запрос типаselect REPLACE(UPPER(NAME), "A", "B") || " " ||
REPLACE(UPPER(PATRONYMIC), "A", "B") || " " ||
REPLACE(UPPER(SURNAME), "A", "B") as FULL_NAME
from "NAMES"
order by FULL_NAME
у меня за 8 секунд выполняется на миллионе записей, их прочитать надо еще. Это на слабеньком компе. Вот, собственно, и отсортированный массив для поиска дубликатов.
Ну а дальше просто один проход по этому массиву, если почему-то падает - ну rows по сотне тысяч за раз брать.
← →
SergP © (2015-06-04 17:36) [258]
> Юрий Зотов © (04.06.15 17:04) [256]
>
> Нужна не сама Upper, нужна независимость от регистра. Например,
> Оглы и оглы - это должно быть одно и то же.
>
> Кроме того, если не поднимать в upper, то replace придется
> использовать дважды (для Ё и для ё). А это функция совсем
> не быстрая.
Ну это понятно. Но я спрашивал для другого...
Не уверен что сработает, но смысл использовать имеющиеся индексы по ФИО для участка фамилии до первой буквы Е
Например если мы делаем не такой запрос:
select ... from ... where
translate(upper(LastName), "Ё", "Е") = :param1 -- фамилия
and -- то же самое для имени и отчества
а предварительно в фамилии ищем первое вхождение буквы Е, е, и приводим кусок фамилии (до буквы Е) в тот вид, в котором оно в базе хранится...
Затем:
к примеру имея фамилию АКСЕНОВ, а в базе оно хранится в виде Аксёнов
select ... from ... where
substr(LastName,1,3)="Акс" and
translate(upper(LastName), "Ё", "Е") = "АКСЕНОВ"
and -- то же самое для имени и отчества
Если для условия substr(LastName,1,3)="Акс" будет использоваться индекс, то и весь запрос должен выполняться намного быстрее.
Для отдельных фамилий, конечно ничего не поменяется в скорости, но среднестатистическая скорость обработки запроса должна значительно возрасти...
То же самое делаем для имени и отчества..
Я конечно не уверен что индекс будет использоваться в случае условия substr(LastName,1,3)="Акс", пусть знатоки БД скажут.
Ну и нужно чтобы в БД ФИО имело какой-то определенный вид, а не так, типа
ПуПКин вАсИЛий ИвАнОвиЧ.
← →
Сергей Суровцев © (2015-06-04 18:46) [259]>SergP © (04.06.15 17:36) [258]
>Не уверен что сработает, но смысл использовать имеющиеся индексы по ФИО
>для участка фамилии до первой буквы Е
>предварительно в фамилии ищем первое вхождение буквы Е, е, и приводим
>кусок фамилии (до буквы Е) в тот вид, в котором оно в базе хранится...
>к примеру имея фамилию АКСЕНОВ, а в базе оно хранится в виде Аксёнов
А что будешь делать с фамилией Весёлкин?
← →
SergP © (2015-06-04 18:57) [260]
> А что будешь делать с фамилией Весёлкин?
Аналогично. Фамилии начинающиеся на "В" отберутся по индексу, а далее обычным методом.
select ... from ... where
substr(LastName,1,1)="В" and
translate(upper(LastName), "Ё", "Е") = "ВЕСЕЛКИН"
and -- то же самое для имени и отчества
Вот только ФИО типа Ежова Евлампия Ерофеевна будут искаться долго, но если хотя бы 1 первая буква в фамилии, имени или отчестве будет не Е/Ё то уже скорость должна значительно возрастать... А если буква не одна, а несколько - то еще значительнее.
Т.е. будет значительно ускорятся поиск пусть и не всех ФИО, но тем не менее их подавляющего кол-ва.
← →
SergP © (2015-06-04 19:00) [261]Главное, чтобы функция, отсекающая начало строки не "убивала" индекс
← →
Юрий Зотов © (2015-06-04 19:53) [262]> SergP © (04.06.15 19:00) [261]
Убьет 100%. Уже обсуждалось. Если бы функции не убивали индексы, то решение было бы тривиальным. Но увы! - в нашей версии убивают.
← →
SergP © (2015-06-04 20:37) [263]
> Убьет 100%. Уже обсуждалось. Если бы функции не убивали
> индексы, то решение было бы тривиальным. Но увы! - в нашей
> версии убивают.
Имелись ввиду функции, возвращающие подстроку начиная от начала строки.
Если таких нет, то можно попробовать
вместо условия substr(LastName,1,3)="Акс"
использовать:
(LastName between "Акс" and "Акт")
или (Lastname>"Акс" and LastName<"Акт")
Такая-то хрень по идее не должна убивать индексы.
← →
SergP © (2015-06-04 20:38) [264]
> Имелись ввиду функции, возвращающие подстроку начиная от
> начала строки.
* при этом не убивающие индексы
← →
Romkin © (2015-06-04 22:39) [265]Вот, смоделировал:
#!usr/bin/env python3
def rec_from_str(fullname):
""" Замена Ё на Е, приведение к верхнему регистру и создание кортежа """
return tuple(fullname.upper().replace("Ё", "Е").split())
def load_names(filename):
""" Загрузка и сортировка списка.
Возвращает список кортежей с заменой букв и компонентами в верхнем
регистре.
Аналог
select REPLACE(UPPER(surname), "Ё", "Е"),
REPLACE(UPPER(name), "Ё", "Е"),
REPLACE(UPPER(patronymic), "Ё", "Е")
from name_table
order by 1,2,3
"""
with open(filename, "r") as f:
return sorted(rec_from_str(line.strip()) for line in f)
def select_rows(filename, start, stop):
""" Аналог
select REPLACE(UPPER(surname), "Ё", "Е"),
REPLACE(UPPER(name), "Ё", "Е"),
REPLACE(UPPER(patronymic), "Ё", "Е")
from name_table
order by 1,2,3
rows :start to :stop
И да, постоянно открывает-сортирует-отбирает
"""
name_list = load_names(filename)
return name_list[start:stop]
def iter_dataset(filename, packet_size=100000):
""" Итерация по запросу, c выборкой packet_size записей за раз """
start = 0
while True:
packet = select_rows(filename, start, start + packet_size)
if not packet:
break
yield from iter(packet)
start += packet_size
def find_equal(iter1, iter2):
""" merge join """
name1, name2 = next(iter1), next(iter2)
try:
found = [] #list
while True:
if name1 == name2:
found.append(name1)
name1 = next(iter1)
name2 = next(iter2)
elif name1 > name2:
name2 = next(iter2)
elif name2 > name1:
name1 = next(iter1)
except StopIteration: # NoSuchElementException
return found
def main():
from os import path
from datetime import datetime
names = load_names(path.join(path.expanduser("~"), "name_list"))
print("Список загружен:", len(names))
tablename = path.join(path.expanduser("~"), "long_list")
starttime = datetime.now()
print(starttime)
found = find_equal(iter(names), iter_dataset(tablename))
finishtime = datetime.now()
print(finishtime)
print("Совпадения")
for rec in found:
print(rec)
print("Время:", finishtime - starttime)
if __name__ == "__main__":
main()
Вывод:Список загружен: 10000
2015-06-04 22:21:34.315667
2015-06-04 22:22:43.560686
Совпадения
("ЕСЗСИЬФЙ", "ДТЯЮШЕЯ", "ДЕЪЖЕЩОПФЮМСЖБЯЗ")
("ФЕЧ", "ЦЮДМЩА", "ЖЕЫИЩД")
("ФХБЮСЮУИТХТЩЙГЫЛТЛЕ", "ЪХЮКШЭДЦМАУГУАЫЗЬПДЪЯДЫХ", "ЭМЧСШЖЕОЫЬИЭА")
Время: 0:01:09.245019
В long_list миллион строк в utf8. То есть Питон слил за минуту с небольшим два файла в 10000 строк и в миллион, с заменой букв и т.д. При этом большой файл специально читался пакетами по сотне тысяч записей, с переоткрыванием и сортировкой.
Собственно, реализовано простое пересечение двух множеств, прямое выражениеwith open("/home/roman/name_list", "r") as f1, open("/home/roman/long_list") as f2:
print(set(f1) & set(f2))
выдает {"Есзсиьфй Дтяюшея Дёъжещопфюмсжбяз\n", "Фёч Цюдмща Жёыищд\n", "Фхбюсюуитхтщйгылтле Ъхюкшэдцмаугуаызьпдъядых Эмчсшжёоыьиэа\n"} за секунду с небольшим.
← →
virex(home) © (2015-06-08 06:15) [266]>Юрий Зотов © (03.06.15 16:38) [235]
> > SergP © (03.06.15 16:09) [232]
>
> Да, любая модификация запрещена. Можно считать, что от всего SQL остался только DML.
даже процедурку на sql сервере нельзя сделать?
← →
SergP © (2015-06-08 11:48) [267]
> даже процедурку на sql сервере нельзя сделать?
Ну ЮЗ же писал что никаких модификаций, только ДМЛ.
Т.е. создание хранимых процедур запрещенно.
Хотя по идее этот запрет не должен препятствовать возможности выполнения блоков. Если это конечно что-то нам даст, в чем я сомневаюсь.
← →
Сергей Суровцев © (2015-07-02 17:36) [268]Ну так чем дело кончилось?
← →
MsGuns © (2015-07-02 17:54) [269]>Ну так чем дело кончилось?
В общем, все умерли :)
← →
Юрий Зотов © (2015-07-02 22:16) [270]> Сергей Суровцев © (02.07.15 17:36) [268]
См. [207]. Будут жалобы - будем бороться. Пока их нет.
Страницы: 1 2 3 4 5 6 7 вся ветка
Форум: "Прочее";
Текущий архив: 2016.03.13;
Скачать: [xml.tar.bz2];
Память: 1.4 MB
Время: 0.015 c
