Tyler: That's clever, but still runs into the nasty nasty problems of using .remove(), which requires iteration over the entire list. In practice, it's 3x slower than either index-tracking algorithm at N=1000, while being slightly faster at N=100 and 50% faster at N=10— but almost 20x slower at N=10000.
On Sun, May 20, 2018 at 10:34 PM, Tyler Laing <trinio...@gmail.com> wrote: > What about reversing through the list? > > for val in reversed(myList): > if check(val): > myList.remove(val) > > The way it works is that reversed returns an iterator that doesn't copy > from your list, but handles changes in the list correctly for you. So its > both memory and time efficient (one pass, one instance). In addition, by > going backwards, even if there's another instance of the removed item, the > iterator that reversed returns doesn't barf or skip. > > On Sun, May 20, 2018 at 8: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 ;) >> >> >> 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 >>> >> >> >
