Lausnum skal skilað til viðkomandi dæmakennara (sjá lista yfir dæmatíma).
Reynið að skrifa stutt, skýr og hnitmiðuð forrit. Notið réttan inndrátt og gætið þess að forritin ykkar séu læsileg.
Skiladagur: þriðjudaginn 17. apríl fyrir kl 16:00
Gefum okkur að við séum með endalausan straum af gildum. Við getum byrjað að lesa strauminn á tilteknum tímapunkti en hann hættir aldrei. Slíkur straumur gæti til dæmis innihaldið fyrirspurnir á Google leitarvélina, Twitter skilaboð, o.s.frv.
Okkur langar til að vita K algengustu gildin (top K) í straumnum á hverjum tímapunkti í lestrinum.
Til að flækja málin þá skulum við gera ráð fyrir því að það séu svo mörg mismunandi gildi í straumnum að einföld talning með hakkatöflu er útilokuð því við höfum ekki pláss fyrir öll gildin. En á móti skulum við gera ráð fyrir að talningin þurfi ekki að vera alveg nákvæm -- við erum tilbúin að sætta okkur við skekkjur (en ætlum ekki að fara neitt nákvæmlega út í hversu mikla skekkju.)
Til að leysa verkefnið þá skuluð þið útfæra einfalda útgáfu af s.k. Count Min Sketch (CM) (gagnamót fyrir líkindafræðilega samantekt á gildum). Þið getið notað CM gagnamótið til að halda utan um tíðni gilda (innan vissra skekkjumarka).
Til að halda utan um top K gildin á hverjum tíma þá skuluð þið nota hrúgu með K gildum. Þegar nýtt gildi kemur inn þá er því bætt inn í CM gagnamótið, tíðni þess gildi er athuguð og ef hún er hærri en lægsta top K gildisins í hrúgunni og gildið er ekki þegar í hrúgunni þá skiptið þið minnsta gildinu út (og þurfið að koma hrúgunni á rétt form aftur), en ef gildið er þegar í hrúgunni þá uppfærið þið tíðni þess og lagfærið hrúguna.
Útfærslan á CM sketch byggir á sambærilegri hugmynd og svokallaðir Bloom filters. Bæði gagnamótin hafa það sameiginlegt að þurfa safn af H tætiföllum og útfærsla þeirra er það flóknasta í útfærslunni á bloom filters og CM.
Við skulum nota mobydick.txt til að prófa forritið. Það eru 22158 orð í henni. Við ætlum að finna topp 10 orðin í mobydick.txt.
Tíu algengustu orðin í mobydick.txt eru:
hhg@hhg:~/t2/V13a$ grep -o -E '\w+' mobydick.txt | sort | uniq -c | sort -n -k 1 | tail -n 10 2098 I 2183 it 2438 his 2945 that 3842 in 4474 to 4487 a 5951 and 6432 of 13555 the hhg@hhg:~/t2/V13a$
TopK forritið skilar okkur eftirfarandi nálgun:
hhg@hhg:~/t2/V13a$ java TopK < mobydick.txt | sort -n -k 1 1979 as 2029 I 2692 his 2968 that 4129 in 4631 to 4747 a 6061 and 6692 of 13839 the hhg@hhg:~/t2/V13a$
import java.util.Scanner; public class TopK { private CountMin cm; private TopHeap heap; private int k; public TopK(int k) { this.cm = new CountMin(0.01, 0.01); this.heap = new TopHeap(k); this.k = k; } public void add(String s) { cm.add(s); if (heap.contains(s)) { heap.increaseWeight(s, 1); return; } if (heap.count() < k) { heap.put(s, 1); return; } int n = cm.getEstimate(s); int worst = heap.peek(); if (n < worst) return; heap.replaceSmallest(s, n); } public int count(String key) { return cm.getEstimate(key); } public Iterable<String> keys() { return heap.keys(); } public static void main(String[] args) { Scanner scan = new Scanner(System.in); TopK top = new TopK(10); while (scan.hasNext()) { String word = scan.next(); top.add(word); } for (String s : top.keys()) { System.out.printf("%8d %s\n", top.count(s), s); } } }
import java.util.HashMap; import java.util.LinkedList; class TopHeap { // Gildin eru í f[0..n-1] í hrúgu með minnstu // þyngd efst (samkvæmt weight) // // Með öðrum orðum, þá gildir eftirfarandi // röð um hrúguna: // f[i].weight < f[2*i+1].weight // f[i].weight < f[2*i+2].weight // // Gildin eru einnig öll í map. private Element[] f; private HashMap<String, Element> map; private int n; public static class Element { String value; int weight; int position; } public TopHeap(int max) { this.n = 0; this.f = new Element[max]; this.map = new HashMap<String, Element>(); } public void increaseWeight(String key, int w) { Element e = map.get(key); e.weight += w; fixHeap(e.position); } public boolean contains(String key) { return map.containsKey(key); } public int peek() { return f[0].weight; } public void put(String s, int w) { Element e = new Element(); e.value = s; e.weight = w; e.position = n; f[n++] = e; map.put(s, e); fixHeapUp(n-1); } public void replaceSmallest(String key, int w) { Element smallest = f[0]; map.remove(smallest.value); smallest.value = key; smallest.weight = w; map.put(key, smallest); fixHeapDown(0); } public int count() { return n; } public Iterable<String> keys() { LinkedList<String> q = new LinkedList<String>(); for (int i = 0; i < n; i++) q.add(f[i].value); return q; } private static void swap(Element[] f, int a, int b) { Element tmp = f[a]; f[a] = f[b]; f[b] = tmp; f[a].position = a; f[b].position = b; } private void fixHeap(int i) { if (i != 0 && f[i].weight < f[(i-1)/2].weight) fixHeapUp(i); else fixHeapDown(i); } private void fixHeapUp(int i) { while (i > 0) { // f[0..n-1] er í hrúgu nema e.t.v. // er f[i] of neðarlega. int parent = (i-1)/2; if (f[parent].weight <= f[i].weight) break; // f[i] < f[parent], þ.e. barn er minna // en foreldri og þurfum því að víxla þeim swap(f, i, parent); i = parent; } } private void fixHeapDown(int i) { while (true) { // f[0..n-1] er hrúga nema e.t.v. // er f[i] of ofarlega. // 0 <= i <= n int b = 2*i+1; if (b >= n) return; // f[i] er barnlaust (lauf) if (b+1 < n && f[b+1].weight < f[b].weight) // Veljum hægra barnið ef það er minna en vinstra b++; if (f[i].weight <= f[b].weight) // f[i] er á réttum stað return; // f[b] < f[i], þ.e. foreldri er stærra // en barn og þurfum því að víxla þeim. swap(f, i, b); i = b; } } }
import java.security.MessageDigest; public class CountMin { private static MessageDigest md; private int width; private int depth; private int[][] count; static { try { md = MessageDigest.getInstance("SHA-1"); } catch (Exception e) { md = null; } } public CountMin(double eps, double delta) { this.width = (int) Math.ceil(Math.E / eps); this.depth = (int) Math.ceil(Math.log(1.0/delta)); count = new int[depth][width]; } public void add(String s) { int[] h = hash(s, depth); for (int i = 0; i < depth; i++) { int p = (h[i] & 0x7fffffff) % width; count[i][p]++; } } public int getEstimate(String s) { int[] h = hash(s, depth); int p = (h[0] & 0x7fffffff) % width; int min = count[0][p]; for (int i = 1; i < depth; i++) { p = (h[i] & 0x7fffffff) % width; if (count[i][p] < min) min = count[i][p]; } return min; } private static int[] hash(String s, int h) { int[] result = new int[h]; byte[] data = s.getBytes(); int k = 0; byte salt = 0; while (k < h) { byte[] digest; md.update(salt); salt++; digest = md.digest(data); int i = 0; while (i < digest.length && k < h) { result[k] = ((int)digest[i+3] & 0xff) | ((digest[i+2] & 0xff) << 8) | ((digest[i+1] & 0xff) << 16) | ((digest[i] & 0xff) << 24); k++; i += 4; } } return result; } }