Show More
@@ -56,23 +56,23 b' from . import (' | |||||
56 | util, |
|
56 | util, | |
57 | ) |
|
57 | ) | |
58 |
|
58 | |||
59 |
def _updatesample(dag, |
|
59 | def _updatesample(dag, revs, sample, quicksamplesize=0): | |
60 | """update an existing sample to match the expected size |
|
60 | """update an existing sample to match the expected size | |
61 |
|
61 | |||
62 |
The sample is updated with |
|
62 | The sample is updated with revs exponentially distant from each head of the | |
63 |
< |
|
63 | <revs> set. (H~1, H~2, H~4, H~8, etc). | |
64 |
|
64 | |||
65 | If a target size is specified, the sampling will stop once this size is |
|
65 | If a target size is specified, the sampling will stop once this size is | |
66 |
reached. Otherwise sampling will happen until roots of the < |
|
66 | reached. Otherwise sampling will happen until roots of the <revs> set are | |
67 | reached. |
|
67 | reached. | |
68 |
|
68 | |||
69 | :dag: a dag object from dagutil |
|
69 | :dag: a dag object from dagutil | |
70 |
: |
|
70 | :revs: set of revs we want to discover (if None, assume the whole dag) | |
71 | :sample: a sample to update |
|
71 | :sample: a sample to update | |
72 | :quicksamplesize: optional target size of the sample""" |
|
72 | :quicksamplesize: optional target size of the sample""" | |
73 |
# if |
|
73 | # if revs is empty we scan the entire graph | |
74 |
if |
|
74 | if revs: | |
75 |
heads = dag.headsetofconnecteds( |
|
75 | heads = dag.headsetofconnecteds(revs) | |
76 | else: |
|
76 | else: | |
77 | heads = dag.heads() |
|
77 | heads = dag.heads() | |
78 | dist = {} |
|
78 | dist = {} | |
@@ -92,36 +92,36 b' def _updatesample(dag, nodes, sample, qu' | |||||
92 | return |
|
92 | return | |
93 | seen.add(curr) |
|
93 | seen.add(curr) | |
94 | for p in dag.parents(curr): |
|
94 | for p in dag.parents(curr): | |
95 |
if not |
|
95 | if not revs or p in revs: | |
96 | dist.setdefault(p, d + 1) |
|
96 | dist.setdefault(p, d + 1) | |
97 | visit.append(p) |
|
97 | visit.append(p) | |
98 |
|
98 | |||
99 |
def _takequicksample(dag, |
|
99 | def _takequicksample(dag, revs, size): | |
100 | """takes a quick sample of size <size> |
|
100 | """takes a quick sample of size <size> | |
101 |
|
101 | |||
102 | It is meant for initial sampling and focuses on querying heads and close |
|
102 | It is meant for initial sampling and focuses on querying heads and close | |
103 | ancestors of heads. |
|
103 | ancestors of heads. | |
104 |
|
104 | |||
105 | :dag: a dag object |
|
105 | :dag: a dag object | |
106 |
: |
|
106 | :revs: set of revs to discover | |
107 | :size: the maximum size of the sample""" |
|
107 | :size: the maximum size of the sample""" | |
108 |
sample = dag.headsetofconnecteds( |
|
108 | sample = dag.headsetofconnecteds(revs) | |
109 | if len(sample) >= size: |
|
109 | if len(sample) >= size: | |
110 | return _limitsample(sample, size) |
|
110 | return _limitsample(sample, size) | |
111 | _updatesample(dag, None, sample, quicksamplesize=size) |
|
111 | _updatesample(dag, None, sample, quicksamplesize=size) | |
112 | return sample |
|
112 | return sample | |
113 |
|
113 | |||
114 |
def _takefullsample(dag, |
|
114 | def _takefullsample(dag, revs, size): | |
115 |
sample = dag.headsetofconnecteds( |
|
115 | sample = dag.headsetofconnecteds(revs) | |
116 | # update from heads |
|
116 | # update from heads | |
117 |
_updatesample(dag, |
|
117 | _updatesample(dag, revs, sample) | |
118 | # update from roots |
|
118 | # update from roots | |
119 |
_updatesample(dag.inverse(), |
|
119 | _updatesample(dag.inverse(), revs, sample) | |
120 | assert sample |
|
120 | assert sample | |
121 | sample = _limitsample(sample, size) |
|
121 | sample = _limitsample(sample, size) | |
122 | if len(sample) < size: |
|
122 | if len(sample) < size: | |
123 | more = size - len(sample) |
|
123 | more = size - len(sample) | |
124 |
sample.update(random.sample(list( |
|
124 | sample.update(random.sample(list(revs - sample), more)) | |
125 | return sample |
|
125 | return sample | |
126 |
|
126 | |||
127 | def _limitsample(sample, desiredlen): |
|
127 | def _limitsample(sample, desiredlen): |
General Comments 0
You need to be logged in to leave comments.
Login now