3 ms·
> for the large number close to the 2^32 limit the result is still returned in around 10 seconds. This could be improved by arranging the if/else statements in
by Retr0id 3y ago
> for the large number close to the 2^32 limit the result is still returned in around 10 seconds.
This could be improved by arranging the if/else statements in a binary tree.
- elwell 3y agoThis is a great idea! Intuitively, I think it might make the program 3x size though?: first `if` for ==, then an `else if` for <, then `else` for >.
- vitiral 3y agoit would be extremely humorous if it actually *reduced* the speed since it required loading so much more code.
- hansjorg 3y agoCome to think of it, I'm sure there are other optimisations you could do as well.
- Scarblac 3y agoIt could also simply check the most common numbers first. We can spider the Internet and collect all usages of numbers, sort them, and find out what the optimal order is.
- Retr0id 3y agoTrue - given probability weights, the optimal decision order would be a Huffman tree https://en.wikipedia.org/wiki/Huffman_coding https://en.wikipedia.org/wiki/Huffman_coding
- Scarblac 3y agoI don't think it would help, you'd still need the 4 billion if statements to decide whether to take the left or the right branch from the root.
- sltkr 3y agoYes but you would only need to visit 32 of them, so it would run much faster (around a hundred million times faster).