在Python中如何用更快的选项替换for循环

Question

我有两个数据帧，大约有10000行。它们与下面的a和b相似，但行数更多。你知道吗

 a
 Out[9]: 
     end  start
 0   4.0      3
 1   5.5      5
 2   7.5      7
 3   9.5      9
 4  11.5     11
 5  15.0     14
 6  18.0     17
 7  21.0     20
 8  26.0     25
 9  31.0     30

 b
 Out[10]: 
        status
 moment       
 8.0         o
 10.0        o
 14.5        o
 16.0        o
 19.0        o
 27.0        o
 28.0        o
 30.5        o
 35.0        o
 40.0        o
 50.0        o

我必须找到数据帧b中的所有时刻，它们属于数据帧a的结束和开始之间的时刻

我为此开发了for循环，它可以很好地处理小数据帧。你知道吗

 for r in a.index:    
     for k in b.index:
         if a.ix[r,'start'] <k and k <a.ix[r,'end']:
             b.ix[k,'status']='m' # replaces m to o if moment is in between start and end

下面您可以看到，在开始和结束之间的时刻，for循环是如何取代o->；m的。你知道吗

 n [12]: b
 Out[12]: 
        status
 moment       
 8.0         o
 10.0        o
 14.5        m
 16.0        o
 19.0        o
 27.0        o
 28.0        o
 30.5        m
 35.0        o
 40.0        o
 50.0        o

当我尝试将它用于巨大的数据帧（数据帧中超过10000行）时，它无法在合理的时间内获得更多的结果。你知道吗

你有什么想法，如何详细说明我的for循环更快，适合更长的数据帧？你知道吗

Answer 1

这里有一个没有for循环的选项，它不避免矢量扫描，而是矢量化的：

b[b.index.map(lambda m: ((m > a.start) & (m < a.end)).any())] = "m"

b

#   status
# moment    
# 8.0   o
# 10.0  o
# 14.5  m
# 16.0  o
# 19.0  o
# 27.0  o
# 28.0  o
# 30.5  m
# 35.0  o
# 40.0  o
# 50.0  o

Answer 2

您的解决方案是运行时的O(n^2)。就我所见，所有的数据帧都是排序的，如果整个DF都是这种情况，您可以使用分而治之的方法使之成为O(nlogn)。但是编码并不容易，您必须查找它，理解D&C方法并将其作为递归函数编写。我认为您可以为这个问题创建一个所谓的BinarySearch算法，每个元素都是O（logn），所以O（nlogn）。你知道吗

如果我错了，而且DF没有排序，但是您必须多次执行这种搜索，我建议您首先对它进行排序。排序也可以在D&C中完成，它通常被称为MergeSort和O（nlogn）。你知道吗