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 ;)
On Sun, May 20, 2018 at 9:48 PM, Ian Mallett <i...@geometrian.com> wrote: > On Sun, May 20, 2018 at 8:35 PM, Daniel Foerster <pydsig...@gmail.com> > wrote: > >> The third, and probably most convenient based on where you seem to be at >> in the curriculum, is to do something like Ian suggested. I think there's a >> simpler way to do it with similar performance though I've not benched to >> find out; I don't think autoresizing should be too much of a concern, >> especially early in a class like this. >> >> index = 0 >> # Could also use a for loop to avoid repeatedly len()ing: >> ## for _discarded in range(len(my_list)): >> >> while index < len(my_list): >> if need_to_delete(my_list[index]): >> del my_list[index] >> # We don't need to update the index after deleting because now >> the next >> # item is sitting in the current slot >> else: >> index += 1 >> >> > The `list` type is an array, so the `del` operation is implicitly copying > the remaining elements of the list forward. This will be O(n^2) operations > over the whole algorithm. My example copies each element at most once, so > there are only O(n) operations total. This version may be more clear, > though. > > Ian >
