在Python中限制for循环的迭代次数

Question

我有一个非常大的对象列表，我需要找出所有具有相同属性（any_object.any_attribute）的对象，然后把它们添加到一个新列表中。为了做到这一点，我已经提前对它们进行了排序，并运行了一个二分查找算法。

我找到了具有匹配属性的对象，但问题是有多个这样的对象（它们是相邻的），我不知道怎么干净利落地循环遍历这些相邻的对象，以便把它们都添加进去。我的代码如下。

  low   = 0
  high  = len(sortedObjects)
  while low < high:
    mid = (low + high)/2
    if sortedObjects[mid].attr < desired_attr:
      low = mid + 1
    elif sortedSamples[mid].attr > desired_attr:
      high = mid
    else:
      newList.append(sortedObjects[mid])
      break

所以我需要在最后的else块中写一些新代码，来遍历所有具有相同属性的对象并将它们添加进去。听起来需要用到for循环，但像在C语言中那样，能否限制for循环的迭代次数呢？

我不想遍历整个列表，因为那样会比较慢，而这个脚本的一个要求就是必须快速高效。它将运行在非常大的数据集上，我们希望执行时间在10到12小时之间。提前谢谢你们！

Answer 1

在else部分再加一个循环，里面把mid的值逐渐减小，直到找到第一个对象为止。然后再向前循环，把所有的对象都找出来。为了加快速度，你可以先保存之前的mid值，然后在“向后循环”中找到对象时把它们存起来，接着在进入向前循环之前再跳回去。

Answer 2

如果你打算经常进行这样的搜索，那就先创建一个这个属性的列表：

attr_list = [o.attr for o in sortedObjects]

然后使用 bisect 模块：

import bisect
left_i = bisect.bisect_left(attr_list, desired_attr)
right_i = bisect.bisect_right(attr_list, desired_attr, left_i)
newList = sortedObjects[left_i:right_i]

Answer 3

试试这个：

else:
    # Find the first element that matches
    while mid > 0 and sortedSamples[mid - 1].attr == desired_attr:
        mid -= 1

    # Iterate until an element that doesn't match is found.
    while mid < len(sortedSamples) and sortedSamples[mid].attr == desired_attr:
        newList.append(sortedObjects[mid])
        mid += 1

这个方法的运行时间是O(m)，其中m是拥有你想要的属性的对象数量。