Блог

Я перебираю каждую строку в первом файле (всего 3000 строк), чтобы найти соответствующую метку во втором файле, строка за строкой (что составляет ~2 миллиона строк; 47 МБ).

В настоящее время у меня есть вложенная структура цикла, в которой внешний цикл захватывает строку (преобразуется в список), а внутренний цикл повторяется через 2 миллиона строк (строка за строкой):

 for row in read_FIMO: #read_FIMO is first file; 3000 lines long
     with open("chr8labels.txt") as label: #2 million lines long  
         for line in csv.reader(label, delimiter="t"): #list
            for i in range(int(row[3]),int(row[4])):  
                if i in  range((int(line[1])-50),int(line[1])):#compare the ranges in each list
                    line1=str(line)  
                    row1=str(row)  
                    outF.append(row1 "t" line1)
 

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

СПАСИБО, если у вас есть какие-либо отзывы!

в стороне: цель состоит в том, чтобы пометить диапазон чисел, если числа находятся в диапазонах другого файла(длинная история; может быть, не имеет значения?)

Ваша цель, по-видимому, состоит в том, чтобы определить, перекрывается ли один диапазон ( row[3] to row[4] ) с другим ( line[1]-50 to line[1] ). Для этого достаточно того, что либо line[1]-50 или row[3] лежит внутри другого диапазона. Это устраняет третий вложенный цикл.

Кроме того, возьмите файл с 2 миллионами строк и отсортируйте его один раз, а затем используйте отсортированный список в цикле из 3000 строк для двоичного поиска, перейдя от алгоритма O(nm) к алгоритму O(nlogm).

(Мой питон далек от совершенства, но это должно помочь вам двигаться в правильном направлении.)

 with open("...") as label:
  reader = csv.reader(label, delimiter="t")
  lines = list(reader)
  lines.sort(key=lambda line: int(line[1]))

for row in read_FIMO:
  # Find the nearest, lesser value in lines smaller than row[3]
  line = binary_search(lines, int(row[3]))

  # If what you're after is multiple matches, then
  # instead of getting a single line, get the smallest and 
  # largest indexes whose ranges overlap (which you can do with a 
  # binary search for row[3] and row[4] 50)
  # e.g.,
  # smallestIndex = binary_search(lines, int(row[3]))
  # largestIndex = binary_search(lines, int(row[4]) 50)
  # for index in range(smallestIndex, largestIndex 1):

  lower1 = int(line[1] - 50)
  lower2 = int(row[3])
  upper1 = int(line[1])
  upper2 = int(row[4])
  if (lower1 > lower2 and lower1 < upper1) or (lower2 > lower1 and lower2 < upper2):
    line1=str(line)  
    row1=str(row)  
    outF.append(row1 "t" line1)

 

Я думаю, что эффективным способом было бы…

1. Сначала просмотрите файл назначения и запишите все метки в хэш словаря. [LabelName] -> [Line number]
2. Просмотрите каждую строку источника, найдите строку из словаря и распечатайте (или распечатайте что-нибудь еще, если не найдено).

Примечания / Советы

• Я думаю, что вышесказанное было бы O(n)
• Вы также можете сначала просмотреть исходный файл, а затем записать его в файл назначения. Это позволило бы создать словарь меньшего размера (и использовать меньше памяти), но выходные данные могут быть не в том порядке, в котором вы хотели бы. (меньшие наборы данных часто имеют лучшее соотношение попаданий в кэш, поэтому я поднимаю этот вопрос.)
• Кроме того, только потому , что вы упомянули most efficient , и если вы хотите сойти с ума, я бы попробовал пропустить построчную обработку и просто пройти через ввод, как будто это одна большая строка. Найдите символ новой строки пробел имя метки. Однако использование этого совета зависит от того, как выглядят входные данные. Если «csv.reader» уже выполняет синтаксический анализ по строкам, то это было бы нехорошо. Кроме того, для выполнения этого метода вам может потребоваться язык более низкого уровня с большим контролем. (Внимание: вероятность 90%, что этот совет просто приведет вас к кроличьей норе, которая никуда не ведет)