bearophileh...@lycos.com wrote: > Paul Rubin: >> I don't see how to delete a randomly chosen node if you use that trick, >> since the hash lookup doesn't give you two consecutive nodes in the linked >> list to xor together.< > > Thank you, I think you are right, I am sorry. > So on 32-bit CPUs you need to add 8 bytes to each value. > > On 64-bit CPUs you may use a double indexed list, instead of a double > linked list. And each index can be stored in 6 bytes instead of 8 > (281_474_976_710_656 buckets may be enough for most people), so you > need only 12 bytes for two indexes instead of 16 bytes, this helps the > L1 cache (and the small L2 cache too on Core i7) a bit. But this may > slow down too much the ordered iteration. > A sort of premature pessimization, then.
regards Steve -- Steve Holden +1 571 484 6266 +1 800 494 3119 Holden Web LLC http://www.holdenweb.com/ -- http://mail.python.org/mailman/listinfo/python-list
