run for loop limited iterations in python

Question

I have an extremely large list of objects and I need to find all that have the identical attribute (any_object.any_attribute) and then append them to a new list. So I have pre-sorted them and run a binary search algo. I have found the object with the matching attribute but the problem is that there are more than one such objects (they are neighbours) but I can't figure out a clean way of running a loop on these contiguous objects so that they all can be appended. My code is pasted below.

  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

So I need to write some new code in the last else block which would iterate over all the objects with the same attributes and append them. Sounds like a for loop would be needed but is it possible to run a for loop for limited iterations, like in C?

I do not want to iterate over the whole list as that would be slower and one of the requirements of this script is that it has to be fast and efficient. It will be run on really large sets of data and we are looking at execution times of 10-12 hrs. Thanks in advance!

Mark Byers · Accepted Answer · 2011-10-18 08:42:18Z

4

Try this:

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

This runs in O(m) time where m is the number of objects with the desired attribute.

answered Oct 18, 2011 at 8:42

Mark Byers

844k202 gold badges1.6k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

eumiro · Accepted Answer · 2011-10-18 08:52:22Z

2

If you are going to perform this search more often then create a list of this attribute:

attr_list = [o.attr for o in sortedObjects]

and then use the bisect module:

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]

answered Oct 18, 2011 at 8:52

eumiro

214k36 gold badges307 silver badges264 bronze badges

Comments

Emil Vikström · Accepted Answer · 2011-10-18 08:43:38Z

0

Run a second loop inside the else block, where you decrease mid until you find the first object, then loop forward to fetch them all. You can speed it up a little bit by saving the old mid and save the elements as you find them in the "backwards loop", and then jump forward again before the forward loop.

answered Oct 18, 2011 at 8:43

Emil Vikström

92.3k17 gold badges144 silver badges178 bronze badges

Collectives™ on Stack Overflow

run for loop limited iterations in python

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related