On Sun, May 20, 2018 at 9:25 PM, Daniel Foerster <pydsig...@gmail.com>
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
<https://stackoverflow.com/questions/5745881/fast-way-to-remove-a-few-items-from-a-list-queue>
.
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)
