запустить для цикла ограниченные итерации в Python

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, но можно ли запустить цикл for для ограниченных итераций, как в C?

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

Answer 1

Попробуйте это:

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 - количество объектов с требуемым атрибутом.

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, где вы уменьшаете mid, пока не найдете первый объект, а затем выполните цикл вперед, чтобы получить их все.Вы можете немного ускорить его, сохранив старый mid и сохранив элементы так, как вы находите их в «цикле назад», а затем снова прыгните вперед перед циклом вперед.