3 ms·
Elegant Six-Page Proof Reveals the Emergence of Random Structure
- rurban 4y agoNow that's something I can really use in one of my current problems. Calculating a minimal perfect hash by creating acyclic random graphs. This conjecture gives now tresholds when to stop trying creating random graphs and start afresh. This eg is needed for large perfect hashes in gperf or integer sets in compilers, such as eg. for C switch statements with Unicode. switch in C is only efficient for dense tables, but not sparse. sparse tables are linear, but could be constant. A switch in Pascal was constant, but so far GCC and llvm didn't care. see http://ilan.schnell-web.net/prog/perfect-hash/algo.html http://ilan.schnell-web.net/prog/perfect-hash/algo.html and http://programming.sirrida.de/hashing.html#c_case_of_string http://programming.sirrida.de/hashing.html#c_case_of_string