В Python, как я должен эффективно сортировать один большой файл, чтобы соответствовать общим элементам из другого большого файла, когда оба файла не отсортированы?

Question

Я довольно новичок в Python и пишу скрипт, который должен взять два довольно больших текстовых файла (~ 10 МБ) и создать новый файл для каждого с некоторыми правилами, указанными ниже.

Файл A имеет разделенные табуляцией значения в каждой строке, файл B содержит идентификатор в одной строке и данные в следующей строке. Идентификаторы из файла B также присутствуют в файле A, но не все идентификаторы из файла A находятся в файле B и наоборот.

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

Вот как выглядит файл A:

Вот как выглядит файл B:

Как видите, элементы из файла A, столбец B, содержат идентификаторы, которые могут присутствовать или не присутствовать в файле A.

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

Сценарий работает нормально, но поскольку он содержит вложенный цикл, он, вероятно, равен O (n ^ 2) (на самом деле это O (m * n), поскольку m - это размер файла A, а n - размер файла B, но они обычно имеют одинаковый размер), что может стать проблемой, если я буду использовать их для реальных данных (сотни МБ или единицы ГБ).

def spectrosingle(inputline):
    if (len(inputline) > 0) and (not inputline[0] == "\t") :
        resline = re.findall(r'\d\t(.+?)\t\t\t\t|$', inputline)[0] # ID in spectro file is always followed by 3 empty columns, which is the only such occurence in the whole line
        return resline
    else:
        return None

try:
    fastafile = open('fastaseq.fasta', "r")
except:
    print("FASTA file corrupted or not found!\n")

try:
    spectrometry = open('spectro.txt', "r")
except:
    print("Spectro file corrupted or not found!\n")


missingarr = [] # array for IDs that are in spectro file but aren't present in fasta file 
misnum = 0 # counter for those IDs

with open('MAIN.fasta', mode='w') as output_handle:
    """Going through a nested cycle - for every sorted sequence in the spectrometry file,"
    "we are searching the unsorted FASTA until we find the corresponding file. If there's any sequence in the spectrometry file"
    "that is not anywhere in the fasta, it's marked so that it doesn't get copied into the final spectrometry file."""
    for line in spectrometry:
        fastaline1 = 'temp' # a temporary initialization for fastaline, so we can enter the While loop that checks if there are still lines left in the file
        missbool = True # a flag for IDs that are missing from fasta file
        speccheck = spectrosingle(line) # filters the ID from spectro file.
        if not speccheck:
            continue #spectrosingle function returns Nonetype if it gets a line without any sequence. This skips such lines.
        while fastaline1:
            fastaline1 = fastafile.readline()
            fastaline1 = fastaline1.partition(">")[2]
            fastaline1 = fastaline1.partition("\n")[0] #shave the header and newline symbols from the ID
            fastaline2 = fastafile.readline()
            if fastaline1 == speccheck:  #check if the sequence in FASTA file matches the one in the spectro file
                print("Sorted sequence ID %s." % (fastaline1))
                output_handle.write('>'+fastaline1+'\n') #write the header
                output_handle.write(fastaline2) #write the sequence
                missbool = False
                fastafile.seek(0) #return to the start of file for next cycle
                break
        if missbool: #this fires only when the whole fastafile has been searched and no matching sequence to the one from the spectro file has been found. 
            misnum = misnum + 1 # count the number of discarded sequence
            missingarr.append(speccheck) #append the discarded sequence to the array, so we later know which sequences not to include in the new spectro file
        fastafile.seek(0)

print("Sorting finished!\n")
fastafile.close()
spectrometry.close()

if misnum != 0: #check if there are any sequences marked for deletion
    num = 0
    blackbool = True
    blackword = missingarr[num]
else:
    blackbool = False # no marked sequences available

with open('spectro.txt', "r") as spectrometry, open(os.path.splitext(finpath)[0]+'\\' + prepid + 'FINAL_spectrometry.txt', mode='w') as final_output: #writing the final spectrometry file with deleted sequences which would cause a mismatch during the final merger of data
    fullspec = spectrometry.readlines() #might be memory-heavy, but still probably the most efficient way to do this
    if not blackbool: #no redundant characters, so the whole file is copied
        for line in fullspec:
            final_output.write(line)
    else:
        try:
            for line in fullspec:
                if ((re.search(blackword, line)) is None):#if the ID is marked, it is not transferred to the new file
                    final_output.write(line)
                else:
                    num = num + 1
                    blackword = missingarr[num]
        except:
            pass
print("There were %i redundant sequences in the spectro file, which have been filtered out.\n" % (num)
spectrometry.close()

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

Answer 1

Ваш код действительно не будет очень эффективным. Вместо этого я бы предложил использовать словарь для хранения данных из файла B для каждого идентификатора. Чтобы получить данные, вы можете просто вызвать next на том же итераторе, который читает файл (при условии, что имеется четное количество строк). Как то так (не проверено):

data = {}
with open("fileb") as fb:
    for line_id in fb:
        the_id = line_id.strip()[1:] # remove newline and ">"
        line_data = next(fb)  # get next line from file
        data[the_id] = line_data.strip()

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

Кроме того, но менее актуально, вместо того, чтобы использовать довольно сложное регулярное выражение для получения идентификатора из файла A, вы можете вместо этого либо просто split("\t") строка, либо использовать модуль csv. Примерно так (тоже не тестировалось):

with open("filea") as fa:
    for line in fa:
        num, the_id, more, stuff, dont, know, what = line.split("\t")
        if the_id in data:
            the_data = data.get(the_id)
            ... to stuff with data ...

Вместо перечисления всех столбцов вы также можете использовать *_ для захвата оставшихся полей:

        num, the_id, *other_stuff_we_do_not_care_about = line.split("\t")

Answer 2

Как сказал tobias_k:

Прочитать первый файл с помощью модуля csv;для второго файла используйте для idline в файле: dataline = next (file), сделайте что-нибудь с idline и dataline, затем поместите их в dict, сопоставляя ID с данными.