Change elements to iterate over while iterating over list in Python

Question

This may not be a Python specific question, but here it goes:

I am trying to solve a numerical problem of the type in which I have to show which elements in a list a = [a_1,a_2,a_3,...] have some property X. However, when I prove it for some a_n, I will sometimes also prove it for other element(s) a_m in the list. So, to speed up the algorithm, I don't want to do the test those elements again.

Now, I can create a list has_property_X and, while iterating over a, test if each element is in the list (and populating that list after testing each element). However, I still have to go through each element in doing this.

Is there a smarter approach?

Is m guaranteed to be less than n? (or is m guaranteed to be greater than n?) — zachdj
– zachdj, Commented Nov 25, 2019 at 15:36
@zachdj if m is ever less than n, then the "bonus proof" is superfluous, because a_m was already proved before you reach a_n. So the efficiency gain is only in the case where m > n. There might, however, be some benefit of sorting the list somehow so that elements likely to produce many "bonus proofs" appear at the start of the list. — kaya3
– kaya3, Commented Nov 25, 2019 at 16:46
@kaya3 the sorting trick is what I had in mind. If m is less than n, then OP can improve efficiency by iterating over the list in reverse. — zachdj
– zachdj, Commented Nov 25, 2019 at 16:50

zachdj · Accepted Answer · 2019-11-25 15:54:13Z

One thing you could do is replace your list has_property_X with a lookup table (dictionary). The lookup table will keep track of each a_i. The key will be a_i and the value will be one of

None, if the element has not yet been processed
True, if the element has the property
False, if the element does not have the property.

This gives you complexity O(1) for checking if an element has already been processed. It would look something like this:

a = [1, 2, 3, 4, 5]  # your list `a`
lookup_table = {a_i: None for a_i in a}

for element in a:
    if lookup_table[element] is None:
        # determine if element has the property
        element_has_property = False

        # if, in the process, you determine that another element `a_m` also has the property,
        # then set lookup_table[a_m] = True
        lookup_table[element] = element_has_property

# assemble list of elements which have the target property
has_property_x = [a_i for a_i in lookup_table if lookup_table[a_i] ]

Andrex · Accepted Answer · 2019-11-25 15:57:35Z

0

I think your approach is correct, in the sense that the cost of time occurs in compute each a_i, and not in the lists loop . If you loop over the list a with a stop list has_x_property (or maybe a set if the repeated values don't matter)

for elem in a:
    if elem not in has_property_x:
        algoritm(elem)
        update(has_property_x)

answered Nov 25, 2019 at 15:57

Andrex

6821 gold badge8 silver badges26 bronze badges

Comments

Avatrin · Accepted Answer · 2019-11-26 14:28:57Z

0

While thinking a bit longer about it, I thought of the following approach:

a = [a_1,a_2,a_3...] #the list
has_property_X = []

while a!=[]:
    #algorithm that tests and removes a[0] and appends to has_property_X the elements that 
    #do and removes them from a as well

I don't know how good of an approach this is (lets say, compared to zachdj's). However, it does answer the question, and I don't see why it will do any worse...

answered Nov 26, 2019 at 14:28

Avatrin

1892 silver badges18 bronze badges

Collectives™ on Stack Overflow

Change elements to iterate over while iterating over list 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