Would be interesting to see how much better the set performs if you do seen_add = seen.add before the loop and use that to avoid the costly attribute lookups.

@Graipher Ok I'll add that and update. Any others?

sorry, only just saw that each value is already a min of a whole run.

@Graipher Added seen_add solution and also an improvement for Sriv's. Removed baseline, was left over from an earlier version. Yes, each time is a min-of-50, and I go round-robin, i.e., first column of times, then second, then third. That's to be more confident that if my PC somehow slows down for a while, it's not just unnoticeably affecting one solution three times. That's also why I won't sort the three times, since a slow-down for a while might then be spread across columns and be less obvious. If it all looks stable like it does here, I'm happy :-)

Nice. Not as much improvement as I was hoping for, though, but I guess that's why we measure. I'm always surprised by the overhead of set over a simple array.

@Graipher Well, at least you made me look for other improvements and Sriv_improved is quite a bit faster (and rather neat, I think :-).

@Graipher If you cared that much, you'd also want to alias seen.__contains__.

@Reinderien Why? It's ugly and slower.

As a side note: this is why neither SLOC nor "beauty" should be the guiding design principles. Speed matters :-) (yes, I know that maintainability, documentation, error-handling, etc. are critical. That's not in play in this simple example)

@superbrain I don't understand why it's slower - it's doing the exact same thing, attribute pre-binding. Is there something special about the is operator that doesn't benefit from direct calls to the underlying function?

@Reinderien Well if you look at dis.dis('x in a'), you'll see CONTAINS_OP. And that gets handled in C code without going through a Python function object. In cases of special syntax I'd assume that it's fastest to use that syntax.

Good to know :)

running your benchmarking code on tio shows similar timings for @Reinderien's solution and the original one. dict lookup would definitely be slower than set or list lookup.

i.stack.imgur.com/LqoPx.png results. the tio.run link is too long

@hjpotter92 tinyurl to the rescue :-) tinyurl.com/codereview-a-250645 Hmm, yeah... I used "Python 3.8 (pre-release)" there and 3.9.0 on my PC. Both are 64-bit, but maybe there was a significant change in the version, or their system differs significantly from mine? AJNeufeld's answer shows times very similar to mine (just a bit faster).

For comparison, on Tio, aneufeld_array comes in at 9.55ms and aneufeld_bytearray comes in at 6.86ms. I'm at a total loss to explain why Reinderien_improved comes in at near equal performance to the original on Tio, but double it with superb rain's and my benchmarking. Very odd.

@hjpotter92 Just tried with Python 3.7.8 64-bit (still had that installed) and got 6.67 ms for the original and 11.9 for Reinderien's (10.4 for the improved version). On TIO with "Python 3" (which is Python 3.7.4 64-bit), it's 7.55 vs 9.85 (7.95 for improved). So I guess it's not the Python version but somehow the system.

i tried on docker containers on my machine. the alpine one has skewed results, others (debian, ubuntu) had similar results to that of aneufeld's. alpine generated same times for original and reinderien's, others being 2-3 ms slower

Thanks for taking the time to write this up, the benchmarking is very interesting. I come from C so I'm always trying to think (within my limited knowledge of coding) about speed/memory optimizations. I also had no idea about False being faster than checking for 0 or 1.

@superbrain, is the False flag faster because it's just checking a single bit so it doesn't have to flip all the bits at all the memory locations that make up the list to 0000000....000, and instead just flip a single bit per memory location of the list?

@jeremyradcliff Not sure what you mean with "flip all the bits at all the memory locations". It's faster then checking truth of 0 or 1 because it's checked very early in the linked to PyObject_IsTrue and it's a simple pointer comparison. And both are faster than with the extra evaluation of == 1 because, well, that's an extra evaluation :-)

@superbrain, that makes sense thanks. By flipping the bits I meant that when I initialize a list with only zeros, whatever garbage values are at those memory locations have to be turned to zeros, so using 8 bits as an ex, if the value was 10110110, it has to be turned to 00000000, whereas maybe True/False is just a single bit flag or something like that. It was just a theory, I understand very little about this at this point

@jeremyradcliff Yeah, no, it's nothing like that. This is not like in C, where an array fully contain the int value or bool value. A Python list doesn't contain the values directly, as the values are objects. The list contains references (pointers in C) to those objects. A reference/pointer is a 32-bit value or 64-bit value depending on your Python version, regardless of the object type (bool, int, YourFancyClass). So it's not like 32 bits vs 1 bit but always 32 bits or always 64 bits.

@superbrain, thanks for explaining, I didn't realize lists in Python were arrays of pointers.

@jeremyradcliff NumPy for example has arrays with non-object values in them, that's one reason that makes it fast.