Commits

Benoit Boissinot committed 7e649bf

add double exponential exploration, with bounded sample size

Comments (0)

Files changed (1)

src/discovery_tonfa.py

     return i
 
 def clever_sample(dag, nodes, stop):
+    if len(nodes) < 200:
+        return set(nodes)
     heads = dag.headsof(nodes)
     sample = set()
 
     visit = list(heads)
     seen = set(stop)
 
+    roots = set()
+
     while visit:
         curr = visit.pop(0)
         if curr in seen:
         d = dist.setdefault(curr, 1)
         order.append(curr)
         seen.add(curr)
+
+        if not len(list(p for p in dag.parents(curr) if p not in stop)):
+            roots.add(curr)
+
         for p in dag.parents(curr):
             dist.setdefault(p, d+1)
             visit.append(p)
         if dist[n] == factor:
             sample.add(n)
 
+    children = {}
+    for n in dag.walk():
+        ps = dag.parents(n)
+        for p in ps:
+            children.setdefault(p, []).append(n)
+
+    visit = list(roots)
+    order = []
+    dist = {}
+    seen = set()
+    while visit:
+        curr = visit.pop(0)
+        if curr in seen:
+            continue
+        d = dist.setdefault(curr, 1)
+        order.append(curr)
+        seen.add(curr)
+        for c in children.get(curr, []):
+            if c not in nodes:
+                continue
+            dist.setdefault(c, d+1)
+            visit.append(c)
+
+    factor = 1
+    for n in order:
+        if dist[n] > factor:
+            factor *= 2
+        if dist[n] == factor:
+            sample.add(n)
+
     assert sample
+    if len(sample) > 200:
+        sample = random.sample(sample, 200)
     return sample
 
 class Client(Participant):
         while self._unknown:
             sample = clever_sample(self.dag, self._unknown, self._common)
             common = server.discover(sample)
-            self.writer.show("number of unkown left: %i, sample size: %s"
+            self.writer.show("number of unknown left: %i, sample size: %s"
                              % (len(self._unknown), len(sample)))
             i += 1
 
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.