嵌套循环最有效的数据结构？

Question

我逐行遍历第一个文件中的每一行（总共 3000 行）以在第二个文件中找到相应的标签（约 200 万行；47 MB）

目前，我有一个嵌套循环结构，外循环抓取一行（转换为列表），内循环遍历 200 万行（逐行）：

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)

-我意识到这是非常低效的，但我需要找到第一个范围与另一个文件的范围重叠的所有实例 - 逐行读取每个文件是最快的方法吗？如果不是，整个文件的最佳数据结构是什么
- 这些行应该在列表以外的不同数据结构中吗？

如果您有任何反馈，谢谢！

旁白：目的是如果在另一个文件的范围内找到数字，则标记一个数字范围（长话短说；可能不相关？）

Answer 1

您的目标似乎是找出一个范围 (row[3] to row[4]) 是否与另一个范围 (line[1]-50 to line[1]) 重叠。为此，只要 line[1]-50 或 row[3] 位于另一个范围内就足够了。这消除了第三个嵌套循环。

此外，将 200 万行的文件对其进行一次排序，然后在 3000 行循环中使用排序后的列表进行二分查找，从 O(nm) 算法切换到 O (nlogm) 一个。

（我的 Python 远非完美，但这应该会让你朝着正确的方向前进。）

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)

Answer 2

我认为有效的方法是...

先遍历目标文件，记录所有标签到字典哈希。 [LabelName] -> [Line number]
遍历源代码的每一行并从字典并打印（如果找不到则打印其他内容）

注意事项/提示

我认为以上是 O(n)
您也可以先遍历源文件并录制，然后再遍历目标文件。这将创建一个更小的字典（并使用更少的内存）但输出可能不是您想要的顺序。（较小的数据集通常具有更好的缓存命中率，所以这就是我提出这个问题的原因。）
另外，只是因为你提到了 most efficient，如果你想变得疯狂，我会尝试逐行跳过处理，就像处理一个大字符串一样处理输入。搜索新行 char + white-space + 标签名称。不过，使用这种技巧取决于输入数据的样子。如果“csv.reader”已经按行解析，那么这就不好了。此外，您可能需要一种具有更多控制权的低级语言来执行此方法。（注意：这个提示有 90% 的机会只会把你带到一个无处可去的兔子洞）

嵌套循环最有效的数据结构？

Most efficient data structure for a nested loop?

nested-loops

data-structures