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
