Блог

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

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

     found = []
    for identifier in ids:
        with open("file.txt", 'r') as f:
            for line in f.readlines():
                if identifier in line:
                    found.append(line)
 

Однако это происходит очень медленно, поскольку я запускаю два вложенных цикла, а список идентификаторов и текстовый файл огромны. Есть ли в python более эффективный и эффективный способ решить эту проблему менее чем за O (n ^ 2)?

Дополнительная информация и ограничения:

• Любая строка может содержать только один идентификатор из моего списка или не содержать его
• Я не могу отсортировать файл на основе идентификаторов, поскольку они не обязательно имеют форму, которая может быть иерархически структурирована

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

 f = open("demofile.txt", "r")
mylines = f.readlines()
                       
found = []
for line in mylines:
   for identifier in ids:
      if identifier in line:
          found.append(line)
 

Неясно, как line составляется, но если его можно четко обозначить, вы можете создать identifier коллекцию a set , а затем проверить, есть ли идентификатор строки в наборе.

set это hashset , поэтому его поиск равен O (1), поэтому все должно выполняться в O (n) .

Использование readlines также кажется ненужным, лениво перебирайте файл.

 ids = set(ids)
with open('demofile.txt', 'r', encoding='utf-8') as f:
    found = [
        line
        for line in f
        if get_id(line) in ids
    ]
 

вам просто нужно предоставить get_id , который просто вырезает «уникальный идентификатор» «в некоторой позиции».

Я бы рекомендовал использовать https://pypi.org/project/triegex / чтобы создать регулярное выражение, которое соответствует любому из ваших идентификаторов и выполняет минимальное обратное отслеживание.

И теперь у вас есть только один цикл.

Ваш код будет повторять некоторые строки, если строка содержит более одного идентификатора.

Итак, здесь мы попробуем другую технику — я не уверен, что она будет быстрее или нет, — но в ней не будет повторяющихся линий, и эта техника основана на прочном фундаменте. Давайте попробуем использовать panads:

 import pandas as pd 
ids=['id1', 'id2', 'id3'] # list of string ids
df=pd.read_csv('file.txt', sep = "`", names = ['txt'])
found =list(df.txt.loc[df.txt.apply(lambda x: sum((id in x) for id in ids )>0)])
 

Некоторые пояснения

df=pd.read_csv('file.txt', sep = "`", names = ['txt']) Загрузите файл в DataFrame. Я использовал ` в качестве аргумента для рассмотрения всей строки как одного столбца, поскольку ` она редко используется в обычных текстовых строках.

(id in x) for id in ids генерирует список True и False на основе количества таких идентификаторов в каждой строке (строке), а внешний sum получит суммирование True

если у нас есть file.txt

 fwpep poweripoi id1 ewlfdfkd f p[woer[pwe dlkdfwero0iopwiperew
we;rioepo ,r rtoipweorit ,rt rtopipowerit
werert.rtrtid1eyri  id1  id2 pid2oerit poier tpoerit eropitpo
 

таким образом, найденный контент будет:

 Out[1]:found 
['fwpep poweripoi id1 ewlfdfkd f p[woer[pwe dlkdfwero0iopwiperew',
 'werert.rtrtid1eyri  id1  id2 pid2oerit poier tpoerit eropitpo']
 

между тем, ваше исходное содержимое кода будет

 Out[1]:found 
['fwpep poweripoi id1 ewlfdfkd f p[woer[pwe dlkdfwero0iopwiperew',
 'werert.rtrtid1eyri  id1  id2 pid2oerit poier tpoerit eropitpo',
 'werert.rtrtid1eyri  id1  id2 pid2oerit poier tpoerit eropitpo']