8

Имеется файл со строками, в котором нужно искать строку по введенному пользователем значению. Содержание файла такого вида:

45
123
0000
77788
77789
999900

То есть все строки различной длины. Пользователь вводит число, которое больше, чем число в БД. То есть к примеру если он введет 450, 45000123 или 45777, то должна найтись первая строка, если введет 77788013 или 7778888, то четвертая и так далее.

Пробовал использовать функцию find(), но она ищет только по точному значению. Difflib так же мне ничем не помогла.

Есть идея перебирать посимвольно каждую строку и пользовательский ввод, там где по максимуму совпадений я узнаю длину поля в БД, потом уже этой длиной ограничить пользовательский ввод и применить функцию find(), но как это реализовать - не знаю.

Больше примеров:

3766
376690
3767
3768
3769
971
9712
971200
9712234
97124
97125
97126
971287
971288

Человек вводит число 3766823013 - находится 3766.
Вводит 3766900124 - находится 376690. Вводит 9712473023 - находится строка 97124.
Вводит 97122348230 находится - 9712234.

Файл большой - 150 мб таких строк.

Правильным оказался ответ:

filestr.find(userstr)==0 or userstr.find(filestr)==0

Работает абсолютно, как надо - не отнять, ни прибавить.

Я не ввожу никого ни в какое заблуждение. Метод find() действительно ищет только точное совпадение (по крайней мере у меня он работает именно так), но стоило мне его заменить на filestr.find(userstr)==0 or userstr.find(filestr)==0 и как по волшебству стало все работать как надо.

13
  • Читать строку из файла и регэкспом сравнивать со введенной пользователем?
    – Ekkertan
    Commented 3 апр. 2012 в 9:46
  • А если пользователь введёт 77790 или 777905? И ещё, могут ли в бде быть строки 77789 777891 т.е. начало второй строки совпадает с первой?
    – alexlz
    Commented 3 апр. 2012 в 10:19
  • Регэксп, думаю, что подойдет. Если пользователь введет 77790, то четвертая, если 777905, то так же - четвертая. Да, строки могут быть 77789 и 777891 - должно искаться до последнего совпадающего символа. Если надо очень конкретно, то скажу, что это телефонная БД префиксов мобильных операторов. Пользователь вводит номер телефона (который по любому больше префикса) и находит строку этого префикса. Длины префикса и телефона абсолютно разные (префикс 2-6 символов, телефонный номер 7-14 символов)
    – Killer1999
    Commented 3 апр. 2012 в 11:27
  • 1
    Прошу прощения, правда Ваша. Да, именно так. Надо найти те строки, которые совпадают с началом проверяемой и выбрать из них наиболее длинную.
    – Killer1999
    Commented 3 апр. 2012 в 12:23
  • 1
    Так примерно (см ответ @Ilya)? res = '' for row in rows: if row == arg[:len(row)] and len(row) > len(res): res = row Если у вас БД -- какая-нибудь sql'я, то запрос написать весьма несложно.
    – alexlz
    Commented 3 апр. 2012 в 14:43

4 ответа 4

8

Перебирайте построчно файл и ищите одну строку в другой и наоборот.

(filestr in userstr) or (userstr in filestr)

Или через find, тогда по началу строки сравнивать можно так:

filestr.find(userstr)==0 or userstr.find(filestr)==0
5
  • 1
    @avp Ответ, куда добавляю комментарий, не тот, но туда уже не лезет. Какие 150мег, Вы что. Если посмотрите, @Killer1999 написал: префиксы номеров мобильной связи. Это получится на каждого человека свой префикс?
    – alexlz
    Commented 3 апр. 2012 в 17:25
  • @alexlz, ТС в конце вопроса добавил: > Файл большой - 150 мб таких строк. Если файл действительно на 150 мб, то таки да, нужно более оптимальный алгоритм реализовывать. Или бинарный поиск или хотя бы сегментировать файл, например, по первым двум цифрам. Commented 4 апр. 2012 в 8:01
  • Вот это я как-то просмотрел. Ещё и @avp писал, что файл таким быть не может. Но тогда непонятно желание возиться с txt файлом. Ну если не mysql/sqlite, то, возможно какой-нибудь berkley db... Но тут надо смотреть ТС, какой объём работы, желаемое время ответа и пр.
    – alexlz
    Commented 4 апр. 2012 в 8:25
  • @alexlz, на самом деле работа с файлами при правильной (для ограниченного круга задач) организации данных всегда эффективнее, чем с СУБД. Только программа д.б. хорошо написана. По поводу 150М, я думаю автор на самом деле погорячился (или у него не префиксы телефонов).
    – avp
    Commented 4 апр. 2012 в 8:35
  • @avp "правильной", "ограниченного круга", "хорошо написана". Чем-то мне эти рассуждения напоминают сказку о высокой эффективности писанных на асме программ. Даже если и достигнут чудо-результат, то жизнь меняется, и программы тоже. А при внесении корректировок в что-то тщательно вылизанное вручную риск потерять в эффективности (несмотря на высокую стоимость работ) неотличим от 100% (невооружённым глазом). Надо будет ему сделать более оперативные корректировки (большого-то файла), или на строки ещё атрибут навесить или ещё что -- и вся стройная конструкция будет вызывать только кучу мата.
    – alexlz
    Commented 4 апр. 2012 в 9:19
6

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

arg = '45000123'

with open('file.dat') as fp:
    for row in fp:
        row = row.rstrip()
        if row == arg[:len(row)]:
            print(row)
3
+100

Архитектура

Два решения через trie, одно через двоичный поиск.

Все решения используют один и тот же протокол:

  • make(seq) - строит поисковую таблицу читая последовательность префиксов seq;
  • prefix_len(table, s) - возвращает длину префикса из таблицы; если префикса нет, возвращает -1;
  • save(table, f) - сохраняет таблицу в файл;
  • load(f) - читает таблицу из файла.

save/load удобны для тестирования. Данных много, строить каждый раз таблицу с нуля накладно.

Тестовые данные

Алгоритмы оцениваются по времени построения таблицы, объёму получившейся таблицы на диске и в памяти, по времени одного запроса. Тестировались два разных набора префиксов: один из соседнего ответа, второй более случайный. Генератор для второго:

import itertools
import random
import sys

s = int(sys.argv[1])
n = int(sys.argv[2])
p = float(sys.argv[3])
b = int(sys.argv[4])

random.seed(s)
while b > 0:
    for c in itertools.product('0123456789', repeat=n):
        if b <= 0:
            break
        if random.random() < p:
            print(''.join(c))
            b -= len(c)
    n += 1

Этот код порождает префиксы с общим числом символов около 150 миллионов:

$ python gen-random-prefixes.py 42 2 0.25 150_000_000
01
03
07
09
10
12
13
16
19
23
...
65427578
65427584
65427589
65427590
65427591
65427592
65427595
65427598
65427599
65427601

Миллион запросов порождает этот код:

import itertools
import random
import sys

s = int(sys.argv[1])
n1 = int(sys.argv[2])
n2 = int(sys.argv[3])
k = int(sys.argv[4])

random.seed(s)
for _ in range(k):
    n = random.randrange(n1, n2)
    print(''.join(random.choices('0123456789', k=n)))
$ python gen-random-requests.py 4242 7 11 1000000
1632504174
1131266
90208566
3316448741
94987864
41454832
0375100555
749931845
5314923
151098151
...
69074190
97368304
8460381
8414310892
9293950
184240618
7116417498
162559013
787488982
297770516

Решения

Универсальное trie

Trie - дерево, каждый узел словарь словарей: {символ: словарь для поддерева}. Нам интересны не любые префиксы, а только те что попадают в строку полностью. Например: префикс 44 не соответствует строке 456. Они совпадают по первому символу, но это не подходит. Поэтому в словарях специально помечены символы, которые завершают префикс: в словаре для этих символов храниться ключ - пустая строка.

Trie строится за линейное время от общего числа символов в префиксах. Поиск префикса для строки делается за длину строки. Сложность обозначим O(N); O(r) где N - число символов во всех префиксах, r - длина строки в запросе.

def make(seq):
    trie = {}
    for s in seq:
        node = trie
        for c in s:
            # move to child
            node = node.setdefault(c, {})
        # mark last node as end of string
        node[''] = None
    return trie


def prefix_len(trie, s):
    node = trie
    j = -1
    for i, c in enumerate(s):
        # node is marked as end of string
        if '' in node:
            j = i

        # move to child if present
        node = node.get(c)
        if node is None:
            break
    else:
        # node is marked as end of string
        if '' in node:
            j = len(s)
    return j

Упакованное trie

Универсальное trie тратит много памяти. Хотя память линейная, константа велика. Известно что алфавит - цифры, можно заменить словари на массивы из десяти элементов. Эти массивы можно собрать в один большой массив. Там есть ещё тонкости, но я их опускаю. Сложность не меняется по сравнению с универсальным trie.

ARRAY_TYPE = 'Q'
ABSENT = 1 << (array.array(ARRAY_TYPE).itemsize * 8) - 1
EMPTY = (ABSENT, ) * 10

def make(seq):
    trie = array.array(ARRAY_TYPE, [0] * 2)

    for s in seq:
        # trie root node
        p = 0
        for i in map(int, s):
            # this is a leaf (no subtree)
            if trie[p] < 2:
                # allocate new node
                trie[p] |= len(trie)
                trie.extend(EMPTY)

            # move to ith child
            p = (trie[p] & ~1) + i

            # mark child present
            if trie[p] == ABSENT:
                trie[p] = 0

        # mark last node as end of string
        trie[p] |= 1

    return trie


def prefix_len(trie, s):
    p = 0
    j = -1
    for k, i in enumerate(map(int, s)):
        # node is marked as end of string
        if trie[p] & 1 != 0:
            j = k

        # this is a leaf (no subtree) 
        if trie[p] < 2:
            break

        # move to child
        p = (trie[p] & ~1) + i

        # if child is absent
        if trie[p] == ABSENT:
            break
    else:
        # node is marked as end of string
        if trie[p] & 1 != 0:
            j = len(s)
    return j

Двоичный поиск

Все префиксы распределяются в списки по длине. Каждый список сортируется. При поиске префикса в каждом списке делается двоичный поиск. Сложность хуже чем у trie: O(N·log N); O(r·log N). Зато константы лучше: обработка trie буквально посимвольная, со списками можно работать как c едиными объектами.

def make(seq):
    table = []
    for s in seq:
        n = len(s)
        if n >= len(table):
            table.extend([] for _ in range(n - len(table) + 1))
        table[n].append(s)
    for row in table:
        row.sort()
    return table


def prefix_len(table, s):
    for n in range(min(len(s) + 1, len(table)))[::-1]:
        row = table[n]
        s_n = s[:n]
        i = bisect.bisect_left(row, s_n)
        if i < len(row) and row[i] == s_n:
            return n
    return -1

Сравнение

Все три решения тестировались, все они возвращают одинаковые ответы.

  • Время построения таблицы включает построение таблицы в памяти и запись её на диск с помощью pickle.
  • Место на диске в комментариях не нуждается.
  • Для измерения места в памяти программа считывала таблицу с диска и останавливалась в ожидании ввода. Пока она висела я смотрел сколько памяти занимает процесс.
  • Время загрузки таблицы с диска включает загрузку, исполнение одного запроса, выход из программы. Один запрос ничего не занимает, очистка памяти для универсального trie1 заметна, я её проигнорировал.
  • Время одного запроса мерялось хитро: запускались прогоны с миллионом запросов и с двумя миллионами. Разница времён делилась на миллион, получалось время одного запроса. Вычитание удаляет время загрузки и обработки первого миллиона запросов. Оставшееся время приходится на второй миллион.

data_150.txt

В каком-то смысле это вырожденный тест: префиксы числа в дапазоне [1, 16839793].

Универсальное trie Упакованное trie Двоичный поиск
Время построения таблицы 28 с 56 с 11 c
Место на диске 136 MB 135 MB 174 MB
Место в памяти 4800 MB 139 MB 1200 MB
Время загрузки таблицы с диска 9.2 с 0.2 с 1.6 с
Время одного запроса 3.2·10-6 с 5.0·10-6 с 5.1·10-6 с

Случайные префиксы

Универсальное trie Упакованное trie Двоичный поиск
Время построения таблицы 46 с 70 с 13 c
Место на диске 187 MB 582 MB 207 MB
Место в памяти 6100 MB 586 MB 1400 MB
Время загрузки таблицы с диска 19.0 с 0.6 с 1.9 с
Время одного запроса 3.8·10-6 с 5.5·10-6 с 9.3·10-6 с

Выводы

Все варианты выполняют запрос быстрее десяти микросекунд. То есть, сто тысяч запросов в секунду или быстрее. Учтите что в это время входит ввод данных и вывод результата. Это очень быстро.

Время построения таблиц от десяти секунд до минуты. Эта операция делается один раз для списка префиксов, надо потерпеть. Зато потом запросы будут обрабатываться очень быстро.

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

Время загрузки с диска приемлемо для упакованного trie и двоичного поиска. Две секунды и сервис готов к работе.

Исходные коды можно найти в репозитории trie2.

6
  • Это впечатляет! Спасибо что откликнулись на конкурс! Commented 28 июл. в 19:12
  • Интересная и неожиданно эффективная идея с поиском в списках по возрастанию длины. Про упакованные trie - ещё есть patricia trie и др. разновидности.
    – MBo
    Commented 29 июл. в 1:23
  • @MBo конкурс ещё продолжается! Вы могли бы не только упомянуть patricia trie и др. разновидности упакованных trie, но и оформить решение с их использованием... :) Commented 29 июл. в 5:54
  • Я приняла вызов! Дополнительно подготовила данные разбив на множества по длине строк, поиск начинается с множеств содержащих элементы максимальной длинны, ещё включила регулярки и это позволило более чем в 1000 раз ускорить обработку! Чуть позже добавлю запись подготовленных данных на диск с помощью pickle и тесты на случайном наборе. Commented 29 июл. в 10:26
  • Предлагаю заменить словарь на массив из 10 элементов.
    – Qwertiy
    Commented 29 июл. в 22:17
3

Не знаю работало бы это 12 лет назад...

На текущий момент я бы решила так:

import re

data = """
45
123
0000
77788
77789
999900
3766
376690
3767
3768
3769
971
9712
971200
9712234
97124
97125
97126
971287
971288
"""

prep_data = sorted((l.strip() for l in data.splitlines()), key=len, reverse=True)
paterns = re.compile(f"(^{')|(^'.join(prep_data)})")

try:
    print(max((s for t in re.findall(paterns, input()) for s in t if s), key=len))
except ValueError:
    print("Совпадений не найдено.")

Для файла размером 150 мб regex отработает намного быстрее for.

^^^^^^
Скрытое утверждение ошибочно по следующим причинам:

  1. При запуске интерпретатора происходит автоматическое интернирование коротких строк и они помещаются в хэш таблицу. Это значительно ускоряет последующую обработку. Однако, этого не происходит при чтении строк из файла или облачного (сетевого) хранилища, а в вопросе указано что чтение происходит из файла. Конечно, можно использовать функцию intern() для обработки таких строк, но по прежнему сохраняется асимптотическая сложность O(n) в цикле for.
  2. Очень длинные регулярные выражения работают очень медленно (можете сами в этом убедиться, на GitHub выложено всё для тестирования).
    Конечно, можно создать кортеж с паттернами для каждой строки из файла, но:
    • я не проверяла даёт ли преимущество использование регулярок при поиске в хешированных строках,
    • т.к. это не позволяет избавиться от сложности O(n) в цикле for.

Следуя утверждению в 13 строке PEP-20,
идеальное решение выглядит так:

import re
from datetime import datetime


start = datetime.now()
with open("data_150мб.txt", "r") as f:
    _data = f.read()
end = datetime.now()
print(f"Время чтения файла: {end - start}")

start = datetime.now()
data = tuple((l.strip() for l in _data.splitlines()))
end = datetime.now()
print(f"Время подготовки данных: {end - start}")

start = datetime.now()
max_len, min_len = max(data, key=len), min(data, key=len)
map_set = {"*" * x: set() for x in range(len(min_len), len(max_len)+1)}
for s in (l.strip() for l in _data.splitlines()):
    map_set["*" * len(s)].add(s)
end = datetime.now()
print(f"Время дополнительной подготовки данных: {end - start}")


users_input = input("\nВведённое значение: ")
userstr = users_input


# Обработка данных принятым решением (Yura Ivanov)
print("\nОбработка данных принятым решением (Yura Ivanov):")
buffer = ""
start = datetime.now()
for filestr in data:
    if filestr.find(userstr)==0 or userstr.find(filestr)==0:
        if len(filestr) > len(buffer):
            buffer = filestr
else:
    end = datetime.now()
    if buffer:
        print(f"Найдено совпадение: {buffer}")
        print(f"Время обработки решением (Yura Ivanov): {end - start}")
    else:
        print("Совпадений не найдено.")
        print(f"Время обработки решением (Yura Ivanov): {end - start}")


# Обработка данных решением (Ilya Pirogov)
print("\nОбработка данных решением (Ilya Pirogov):")
buffer = ""
start = datetime.now()
for filestr in data:
    if filestr == userstr[:len(filestr)]:
        if len(filestr) > len(buffer):
            buffer = filestr
else:
    end = datetime.now()
    if buffer:
        print(f"Найдено совпадение: {buffer}")
        print(f"Время обработки решением (Ilya Pirogov): {end - start}")
    else:
        print("Совпадений не найдено.")
        print(f"Время обработки решением (Ilya Pirogov): {end - start}")


# Идеальное решение.
print("\nОбработка данных идеальным решением:")
start = datetime.now()
for i, char in enumerate(users_input):

    if i == 0 and users_input[:i+1] not in data:
        end = datetime.now()
        print("Совпадений не найдено.")
        print(f"Время обработки идеальным решением: {end - start}")
        break

    elif users_input[:i+1] in data:
        continue

    else:
        end = datetime.now()
        print(f"Найдено совпадение: {users_input[:i]}")
        print(f"Время обработки идеальным решением: {end - start}")
        break


# Оптимизированное идеальное решение.
print("\nОбработка данных оптимизированным идеальным решением:")
start = datetime.now()
for l in range(len(max_len), len(min_len)-1, -1):

    if ((_match := re.search(fr"^\d{'{'}{l}{'}'}", _input))
            and (result := _match.group()) in map_set["*"*l]):
        end = datetime.now()
        print(f"Найдено совпадение: {result}")
        print(f"Время обработки идеальным решением: {end - start}")
        break

    elif l == len(min_len):
        end = datetime.now()
        print(f"Совпадений не найдено.")
        print(f"Время обработки идеальным решением: {end - start}")
        break

    else:
        continue

Вывод в консоль:

(.venv) PS C:\KWORK> & c:/KWORK/.venv/Scripts/python.exe c:/KWORK/my_test.py
Время чтения файла: 0:00:01.417997
Время первичной подготовки данных: 0:00:27.071317
Время дополнительной подготовки данных: 0:00:23.429867

Введённое значение: 16839793_ftugyuih

Обработка данных принятым решением (Yura Ivanov):
Найдено совпадение: 16839793
Время обработки решением (Yura Ivanov): 0:00:12.538662

Обработка данных решением (Ilya Pirogov):
Найдено совпадение: 16839793
Время обработки решением (Ilya Pirogov): 0:00:08.350430

Обработка данных идеальным решением:
Найдено совпадение: 16839793
Время обработки идеальным решением: 0:00:01.055001

Обработка данных оптимизированным идеальным решением:
Найдено совпадение: 16839793
Время обработки идеальным решением: 0:00:00.001001
(.venv) PS C:\KWORK>

Резюме:

Для поиска идеального решения надо оценить все аспекты задачи.
В данной задаче итерация от обратного (по введённой строке) в десятки раз сокращает время обработки!

P.S.
Выражаю благодарность:

@insolor за экскурс в историю Python,
@CrazyElf за ёмкий комментарий: "... Как-то это как-то )) ...",
@MBo за указание направления Похоже, это задача для trie ...,
@StanislavVolodarskiy за его замечания и вопрос:
Это точно будет работать? - хороший критик ценнее 1000 фанатов!

19
  • 3
    f-строки только в Python 3.6 появились в 2016 году, до этого format или % нужно было использовать. Но сейчас уже все равно, это же не письмо в прошлое)
    – insolor
    Commented 19 июл. в 12:04
  • 1
    Вот, с некоторыми адаптациями на Python2.7 работает: i.sstatic.net/mLsJVHHD.png
    – insolor
    Commented 19 июл. в 12:32
  • 1
    Похоже, это задача для trie (как и в вашем решении, требуется один раз предобработать файл)
    – MBo
    Commented 19 июл. в 12:55
  • 1
    Ну, в Python3 уже тогда был input обычный. В Python2 input - это eval(input()), в Python3 его выпилили, а raw_input переименовали в input. 12 лет назад актуальный Python3 был скорее всего 3.2 или 3.3, там не было например f-строк и всяких аннотаций, но в целом на такой сложности задачах код более-менее похожий будет на современный.
    – insolor
    Commented 19 июл. в 13:20
  • 2
    @insolor Ясно. (ещё один голос и я получу значок Возрождение) - в настоящее письмо получится. Commented 19 июл. в 13:25

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.