Есть ли какой-нибудь алгоритм, который можно применить к этой программе?

Question

Я делаю стажера, пишущего программу для сопоставления генов.

Например: Файл "A" содержит несколько строк генного типа. (исходные данные не отсортированы) rs17760268 rs10439884 rs4911642 rs157640 rs1958589 rs10886159 rs424232 ....

и файл "B" содержит 900 тысяч rs, как указано выше (также не отсортировано)

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

Есть ли какой-нибудь алгоритм, который можно применить к этой программе?

Кстати, я постараюсь, чтобы моя программа выполняла многократную обработку, и посмотрю, получится ли она лучше.

pseudocode:
read File "A" by string, append to A[]
A[] = rs numbers from File "A"

read File "B" by string
for gene_B in file_B_reader:
    for gene_A in A:
        if gene_A == gene_B:
            #append to result[]

Answer 1

Хотя ваши объяснения довольно неясны, я полагаю, что вы добавляете значения A в список.Вместо этого используйте словарь, и вы сможете искать его гораздо эффективнее.

Answer 2

Не думаю, что сначала нужно что-то сортировать.

• Обрабатывать большой список B в хэш-карту или хэш-набор, O (n) амортизироваться
• Перебирать список Aи удалить из A, если не в B, O (m)
• return A

Итого: O (n + m)

Answer 3

Из описания, по-видимому, вы хотите, чтобы result[] содержал rs строк, которые находятся в A и B (он же Пересечение ).

Ваш алгоритмO(n*m), но вы могли бы легко улучшить это, сначала отсортировав оба файла (O(n*logn) для сортировок на основе сравнения), а затем одновременно считав оба из них, увеличив позицию в файле с меньшим текущим номером rs и добавивсоответствует result[] одновременно.