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

← →
ухты © (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]

Главное, чтобы функция, отсекающая начало строки не "убивала" индекс

> SergP © (04.06.15 19:00) [261]

Убьет 100%. Уже обсуждалось. Если бы функции не убивали индексы, то решение было бы тривиальным. Но увы! - в нашей версии убивают.

> Убьет 100%. Уже обсуждалось. Если бы функции не убивали
> индексы, то решение было бы тривиальным. Но увы! - в нашей
> версии убивают.

Имелись ввиду функции, возвращающие подстроку начиная от начала строки.
Если таких нет, то можно попробовать
вместо условия substr(LastName,1,3)="Акс"
использовать:

(LastName between "Акс" and "Акт")

или (Lastname>"Акс" and LastName<"Акт")

Такая-то хрень по идее не должна убивать индексы.

> Имелись ввиду функции, возвращающие подстроку начиная от
> начала строки.

* при этом не убивающие индексы

Вот, смоделировал:
#!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"} за секунду с небольшим.

>Юрий Зотов © (03.06.15 16:38) [235]
> > SergP © (03.06.15 16:09) [232]
>
> Да, любая модификация запрещена. Можно считать, что от всего SQL остался только DML.

даже процедурку на sql сервере нельзя сделать?

> даже процедурку на sql сервере нельзя сделать?

Ну ЮЗ же писал что никаких модификаций, только ДМЛ.
Т.е. создание хранимых процедур запрещенно.
Хотя по идее этот запрет не должен препятствовать возможности выполнения блоков. Если это конечно что-то нам даст, в чем я сомневаюсь.

Ну так чем дело кончилось?

>Ну так чем дело кончилось?

В общем, все умерли :)

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