I'm fond of this brain-expander, in spirit of TFA: "Did you know travelling salesperson is O(N) on a large class of graphs?"

Another insight: I regularly find that clever O(logn) solutions are just obliterated by a few mostly-branch-free O(N) pre-passes followed by a problem that computers enjoy, like contiguous memory access and vector operations.

▲

hahahaa 4 hours ago | parent | next [-]

Yeah why is "the algorithm" the thing we do in our head to mimick a 1970s computer and not what really happens on hardware.

	▲	xtajv 2 hours ago \| parent [-]
		At risk of disclosing certain personal details about myself on the internet, I pinky-promise that the two aren't as different as folks without certain cognitive limitations might think. Use the royal "we" with caution, please. P.S. in case it wasn't obvious, this isn't one of those "nyeh nyeh well you must be dumb because you don't cogitate in ways reminiscent of modern computing hardware" comments so much as a "you would not believe how simple-as-in-basic-as-in-limited some of us really cogitate while leveraging external systems to suggest otherwise ".

▲

momojo 4 hours ago | parent | prev [-]

Do you have any examples of the second class?

▲

zellyn 4 hours ago | parent | next [-]

The one that comes to mind is how big your hash maps have to get before all the clever algorithms beat linear scan, and it's surprisingly large on modern computers: linear memory access is _very_ predictable.

The Roc and Zig folks probably have actual numbers.

▲

tshaddox 3 hours ago | parent [-]

What are these surprisingly large numbers you've seen? I thought that linear scan optimizations are typically reserved for pretty small maps, like dozens or maybe hundreds of elements.

▲

inigyou an hour ago | parent [-]

Hundreds sounds about right, maybe up to a thousand.

But nobody expects that. Hashmap is supposed to be faster once you have, like, ten elements. That's what was promised to us.

	▲	zellyn an hour ago \| parent [-]
		Yeah, I found hundreds surprising (although not on reflection).

▲

mrkeen 4 hours ago | parent | prev | next [-]

Not sure if this counts, but I learned Huffman coding the intuitive tree-based way. From memory it was O(nlogn), but you can just O(n) it in-place in an array.

	▲	inigyou an hour ago \| parent [-]
		Huffman decoding you mean. All the fast decoders build tables processing N (8, 16, ...) bits at a time. If the next byte is 253 in state 6 that means output 15,28,28 and go to state 42... There are probably even faster ways I don't know of.

▲

jvanderbot 3 hours ago | parent | prev [-]

[dead]