Mercurial > repos > tabletprog
comparison modules/sets.tp @ 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 | a2d2d8e09291 |
comparison
equal
deleted
inserted
replaced
80:cbc92ee13f35 | 81:a905e13db753 |
---|---|
1 #{ | 1 #{ |
2 hash <- { | 2 hash <- { |
3 empty <- #{ | 3 empty <- #{ |
4 empty? <- { true } | 4 empty? <- { true } |
5 } | 5 } |
6 size <- 0 | |
7 hashdiffs <- #[0] | |
6 #{ | 8 #{ |
7 buckets <- #[empty empty empty empty] | 9 buckets <- #[empty empty empty empty] |
8 contains? <- :object { | 10 contains? <- :object { |
9 hv <- object hash | 11 hv <- object hash |
10 | 12 |
11 notdone <- true | 13 notdone <- true |
12 hashes <- #[hv (hv + 1) (hv - 1)] | 14 |
15 basehash <- hv | |
13 i <- 0 | 16 i <- 0 |
14 ret <- false | 17 ret <- false |
15 while: { if: notdone { i < 3 } } do: { | 18 while: { if: notdone { i < (hashdiffs length) } } do: { |
16 hv <- hashes get: i | 19 hv <- basehash + (hashdiffs get: i) |
17 trunc <- hv % (buckets length) | 20 trunc <- hv % (buckets length) |
18 if: trunc < 0 { trunc <- 0 - trunc } | 21 if: trunc < 0 { trunc <- 0 - trunc } |
19 bucketval <- (buckets get: trunc) | 22 bucketval <- (buckets get: trunc) |
20 if: (bucketval empty?) { | 23 if: (bucketval empty?) { |
21 notdone <- false | 24 notdone <- false |
39 v <- hv | 42 v <- hv |
40 eq <- :other { v = other } | 43 eq <- :other { v = other } |
41 } | 44 } |
42 } | 45 } |
43 notdone <- true | 46 notdone <- true |
44 hashes <- #[hv (hv + 1) (hv - 1)] | 47 basehash <- hv |
45 i <- 0 | 48 i <- 0 |
46 while: { if: notdone { i < 3 } } do: { | 49 while: { if: notdone { i < (hashdiffs length) } } do: { |
47 hv <- hashes get: i | 50 hv <- basehash + (hashdiffs get: i) |
48 trunc <- hv % (buckets length) | 51 trunc <- hv % (buckets length) |
49 if: trunc < 0 { trunc <- 0 - trunc } | 52 if: trunc < 0 { trunc <- 0 - trunc } |
50 bucketval <- (buckets get: trunc) | 53 bucketval <- (buckets get: trunc) |
51 if: (bucketval empty?) { | 54 if: (bucketval empty?) { |
55 size <- size + 1 | |
52 buckets set: trunc (makeBucket: hv) | 56 buckets set: trunc (makeBucket: hv) |
53 notdone <- false | 57 notdone <- false |
54 } else: { | 58 } else: { |
55 if: (bucketval eq: hv) { | 59 if: (bucketval eq: hv) { |
56 notdone <- false | 60 notdone <- false |
57 } | 61 } |
58 } | 62 } |
59 i <- i + 1 | 63 i <- i + 1 |
60 } | 64 } |
61 if: notdone { | 65 if: notdone { |
62 newsize <- (buckets length) * 3 | 66 newsize <- (buckets length) * 3 + 1 |
67 lastdiff <- hashdiffs get: ((hashdiffs length) - 1) | |
68 if: lastdiff <= 0 { | |
69 hashdiffs append: ((0 - lastdiff) + 1) | |
70 } else: { | |
71 hashdiffs append: (0 - lastdiff) | |
72 } | |
63 newbucks <- #[] | 73 newbucks <- #[] |
64 while: { (newbucks length) < newsize } do: { | 74 while: { (newbucks length) < newsize } do: { |
65 newbucks append: empty | 75 newbucks append: empty |
66 } | 76 } |
67 oldbucks <- buckets | 77 oldbucks <- buckets |