3 ms·
Do you have any examples of the second class?
by momojo 2mo ago
Do you have any examples of the second class?
- zellyn 2mo agoThe 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 2mo agoWhat 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 2mo agoHundreds 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 2mo agoYeah, I found hundreds surprising (although not on reflection).
- __s 2mo agoDepends on comparison function. In clickhouse-c for type name lookup it's strcmp so I use generated hash table with no collisions & reusing cityhash function since we have it handy: https://github.com/ClickHouse/clickhouse-c/blob/4bdd89a02438d1e81ba7cf95dc111af8a23e313b/clickhouse.h#L1234 https://github.com/ClickHouse/clickhouse-c/blob/4bdd89a02438... Benchmarked an order of magnitude faster than linear scan or binary search. I agree with your general sentiment tho, which is why I measured
- swiftcoder 2mo agoMaybe more than that if you have a sub-optimal hash map implementations. There are a bunch of those floating around - for example, Java's build-in HashMap has traditionally been kneecapped by lack of value types, and if you are not careful you can incur 2x cache misses per lookup...
- __s 2mo agoSame with c++ stl unordered_map
- mrkeen 2mo agoNot 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 2mo agoHuffman 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.
- JohnKemeny 2mo agoYou can't do it faster than O(n log n) for the simple reason that you need to sort the frequencies. If the symbols come sorted, then you can do it in O(n) time, yes, using two queues.
- jvanderbot 2mo ago[dead]