Interesting coincidence, I'm currently working on a learned index on sorted keys that can advantageously replace binary search. It is very compact (additional space of 2% of the sorted key array, e.g. 40KB for 200MB of keys), and it is between 2x to 3x faster than binary search for the rank/indexOf methods. By design there are nearly no branches: the index of a key is approximated by using hierarchical linear segment computation. The PGM-Index paper is there: https://pgm.di.unipi.it/ And my implementation is here, just submitted in HPPC: https://github.com/carrotsearch/hppc/pull/39
Bruno Le ven. 28 juil. 2023 à 13:04, Dawid Weiss <dawid.we...@gmail.com> a écrit : > > Actually this is exactly the same for Java: >> > > Yup, I know (we all know by now, I guess). People (including me) evidently > crave this low, iron-level control, while at the same time mostly try to > dodge writing any software in languages that are designed to be close to > the hardware. There is a love-hate relationship there that I often find > amusing. > > D. > >>
