Great idea, although I seem to recall describing this exact mechanism several months ago.... great minds think alike I guess.
Ian. On Mon, Apr 02, 2001 at 08:32:32PM -0700, Mr.Bad wrote: > So, let's say that I'm doing something like the key indexer, that uses > incremented keys. EOF does this, too. > > Frequently, the incremented keys start at zero and go up. This is > probably the slowest way to do incremented keys, since you have to > test each value as you go along. > > Another way to find an "open" key would be to do a kind of binary > search. For example, start with value 1. If it's taken, double it to > value 2. If that's taken, double it to value 4. If -that- is taken, > double it to value 8. Again, if that's taken, double to value 16. > > If that -IS- taken, split the difference between this key and the last > taken key, and check that one. So, now we're at 12. Is that taken? If so, > split the difference between this one and the last checked open key, > so we're at 14. If that one isn't taken, split the difference down > again, to 13. If that's taken, then 14 is the next open key, and > that's where to insert to. > > In order, we checked 8 keys, instead of 14: > > number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 > > check order 1 2 3 4 6 8 7 5 > > This is kind of a trivial example, but if you think about having a key > index with thousands of incremented values, you've got a real time > savings here. > > Also note that after the number of inc values goes above a power of 2, > you don't have to check the keys between that power of two and the > next lower one again. So those will fall off the network, thankfully, > without the incrementer "losing its place." > > Anyways, I was just thinking that this is probably a smarter way to do > incrementing. > > ~Mr. Bad > > -- > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > Mr. Bad <mr.bad at pigdog.org> | Pigdog Journal | http://pigdog.org/ > freenet:MSK at SSK@u1AntQcZ81Y4c2tJKd1M87cZvPoQAge/pigdog+journal// > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > _______________________________________________ > Devl mailing list > Devl at freenetproject.org > http://lists.freenetproject.org/mailman/listinfo/devl -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 232 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20010403/b115f685/attachment.pgp>
