Mercurial > repos > tabletprog
changeset 81:a905e13db753
Increase the number of buckets checked in a hash set as it grows to keep space overhead reasonable
author | Mike Pavone <pavone@retrodev.com> |
---|---|
date | Wed, 18 Jul 2012 08:59:08 -0700 |
parents | cbc92ee13f35 |
children | 48daa1d3e052 |
files | modules/sets.tp |
diffstat | 1 files changed, 17 insertions(+), 7 deletions(-) [+] |
line wrap: on
line diff
--- a/modules/sets.tp Mon Jul 16 01:22:48 2012 -0700 +++ b/modules/sets.tp Wed Jul 18 08:59:08 2012 -0700 @@ -3,17 +3,20 @@ empty <- #{ empty? <- { true } } + size <- 0 + hashdiffs <- #[0] #{ buckets <- #[empty empty empty empty] contains? <- :object { hv <- object hash notdone <- true - hashes <- #[hv (hv + 1) (hv - 1)] + + basehash <- hv i <- 0 ret <- false - while: { if: notdone { i < 3 } } do: { - hv <- hashes get: i + while: { if: notdone { i < (hashdiffs length) } } do: { + hv <- basehash + (hashdiffs get: i) trunc <- hv % (buckets length) if: trunc < 0 { trunc <- 0 - trunc } bucketval <- (buckets get: trunc) @@ -41,14 +44,15 @@ } } notdone <- true - hashes <- #[hv (hv + 1) (hv - 1)] + basehash <- hv i <- 0 - while: { if: notdone { i < 3 } } do: { - hv <- hashes get: i + while: { if: notdone { i < (hashdiffs length) } } do: { + hv <- basehash + (hashdiffs get: i) trunc <- hv % (buckets length) if: trunc < 0 { trunc <- 0 - trunc } bucketval <- (buckets get: trunc) if: (bucketval empty?) { + size <- size + 1 buckets set: trunc (makeBucket: hv) notdone <- false } else: { @@ -59,7 +63,13 @@ i <- i + 1 } if: notdone { - newsize <- (buckets length) * 3 + newsize <- (buckets length) * 3 + 1 + lastdiff <- hashdiffs get: ((hashdiffs length) - 1) + if: lastdiff <= 0 { + hashdiffs append: ((0 - lastdiff) + 1) + } else: { + hashdiffs append: (0 - lastdiff) + } newbucks <- #[] while: { (newbucks length) < newsize } do: { newbucks append: empty