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;
}
}