it’s not about which function, it’s about which actions
would you rather step through the list adding 1 to each color, or would you step through it once to figure out what colors there are, then for each color step through the list and count that color?
figuring out which colors exist is nearly the same action as counting how many of each color there is
after having carried out roughly that action, you shouldn’t have to do anything else
you start out with a bunch of colors:
each one is worth 1
insert each pair, combining with (+) on conflict
If you do membership testing on a list on each insertion, then you end up doing
N*N amount of work where N is the number of colors
If you sort them, which takes
N * log N amount of work, then you can easily group and count, so this is better
But dict does insertion and lookup in constant time (1), and you have N insertions, so that would take
1 * N … which is
N, amount of work
if N is a million, then the first is a trillion work units, the second is about 20 million and the third is about 1 million. 20 and 1 is roughly the same thing so you can expect those two methods to take about the same amount of work while the one that is doing membership testing on a list … you’d probably go want to get a coffee, (unless you know it’s a small amount of unique colors which would keep the list small) past a million we might be talking about a vacation or retirement instead of a coffee.