On 10/28/21, 3:15 PM, "Andres Freund" <and...@anarazel.de> wrote:
> Which leads to to wonder whether the better fix would be to switch to deleting
> the last element, but still use the while (!empty) style. That should convert
> the O(n^2) due to 1cff1b9 back to O(n). It might or might not be faster/slower
> than using foreach(), but it should be within the same ballpark.

Yeah, deleting from the end of the list yields a similar improvement.
foreach() appears to be slightly faster, but the difference is
basically negligible.  For a list of a million integers, foreach()
consistently takes ~12ms, deleting from the end of the list takes
~15ms, and deleting from the beginning of the list takes ~4 minutes.

Nathan

Reply via email to