Re: [pygame] Iterate over list and delete

[Ian Mallett <ian@xxxxxxxxxxxxxx>]

On Sun, May 20, 2018 at 9:25 PM, Daniel Foerster <pydsigner@xxxxxxxxx> wrote:

The relevance of N exponent versus the discarded coefficients depends on how big N may be. With the likely sizes of N in a Pygame class, the difference between the algorithms seems probably negligible. A quick test with 20% deletion shows that your algorithm becomes more efficient around N=7000, but either can handle well over N=20000 in 10ms. Of course, a list comprehension can handle almost 100,000 in the same 10ms so the point is all rather moot in real-world code ;)

​These results were surprising to me, so I coded up a test (see attached!).

I measure the breakeven point at a similar level, 5500 elements. MrGumm's version is functionally equivalent to mine, but seems to run much faster than either of ours (mine and Daniel's)—almost as fast as the list comprehension, which I confirm to be fastest. My guess is that my `while` loop (instead of `for` over the elements explicitly) is confusing the Python JIT into not optimizing somehow.

Also, this discussion on StackOverflow is relevant.

Ian​

import timeit


def listcomp_remove(my_list, delete_predicate):
    my_list[:] = [item for item in my_list if not delete_predicate(item)]
def daniel_remove(my_list, delete_predicate):
    index = 0
    while index < len(my_list):
        if delete_predicate(my_list[index]):
            del my_list[index]
        else:
            index += 1
def ian_remove(my_list, delete_predicate):
    i_read  = 0
    i_write = 0
    while i_read < len(my_list):
        item = my_list[i_read]
        i_read += 1
        if delete_predicate(item):
            pass
        else:
            my_list[i_write] = item
            i_write += 1
    while len(my_list) > i_write:
        my_list.pop()
def mrgumm_remove(my_list, delete_predicate):
    i_write = 0
    for item in my_list:
        if not delete_predicate(item):
            my_list[i_write] = item
            i_write += 1
    del my_list[i_write:len(my_list)]
def tyler_remove(my_list, delete_predicate):
    for val in reversed(my_list):
        if delete_predicate(val):
            my_list.remove(val)

def delete_third(item):
    return item%3 == 0
def delete_fifth(item):
    return item%5 == 0

def run_test_10(remove_alg, delete_predicate):
    my_list = list(range(0,10,1))
    print("Before: "+str(my_list))
    remove_alg(my_list,delete_predicate)
    print("After:  "+str(my_list))
run_test_10(listcomp_remove,delete_fifth)
run_test_10(daniel_remove,  delete_fifth)
run_test_10(ian_remove,     delete_fifth)
run_test_10(mrgumm_remove,  delete_fifth)
run_test_10(tyler_remove,   delete_fifth)

def run_test_n(remove_alg, delete_predicate, n):
    my_list = None
    def setup_list():
        nonlocal my_list
        my_list = list(range(0,n,1))
    def remove():
        nonlocal my_list
        remove_alg(my_list,delete_predicate)
    stats = timeit.repeat(stmt=remove,setup=setup_list, repeat=50,number=1)
    print(sum(stats)/len(stats))
run_test_n(listcomp_remove,delete_fifth, 5500)
run_test_n(daniel_remove,  delete_fifth, 5500)
run_test_n(ian_remove,     delete_fifth, 5500)
run_test_n(mrgumm_remove,  delete_fifth, 5500)
run_test_n(tyler_remove,   delete_fifth, 5500)