Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
courses:mapreduce-tutorial:step-27 [2012/01/28 18:58] straka |
courses:mapreduce-tutorial:step-27 [2012/01/31 13:13] straka |
||
---|---|---|---|
Line 24: | Line 24: | ||
public void write(DataOutput out) throws IOException { | public void write(DataOutput out) throws IOException { | ||
- | int highest_pos | + | int mask_shift |
- | while (highest_pos | + | while (mask_shift |
- | while (highest_pos | + | while (mask_shift |
- | out.writeByte(0x80 | ((value >> | + | out.writeByte(0x80 | ((value >> |
- | | + | |
} | } | ||
out.writeByte(value & 0x7F); | out.writeByte(value & 0x7F); | ||
Line 40: | Line 40: | ||
} | } | ||
</ | </ | ||
- | Remark: If the '' | + | Remark: If the '' |
Such implementation can be used as a type of //values//. If we wanted to use it as a type of //keys//, we need to implement [[http:// | Such implementation can be used as a type of //values//. If we wanted to use it as a type of //keys//, we need to implement [[http:// | ||
Line 76: | Line 76: | ||
public void setFirst(A first) { this.first = first; } | public void setFirst(A first) { this.first = first; } | ||
public void setSecond(B first) { this.second = second; } | public void setSecond(B first) { this.second = second; } | ||
+ | public String toString() { return String.format(" | ||
public PairWritable(A first, B second) { this.first = first; this.second = second; } | public PairWritable(A first, B second) { this.first = first; this.second = second; } | ||
} | } | ||
</ | </ | ||
+ | Remark: Remark: If the '' | ||
+ | We did not define '' | ||
+ | <code java> | ||
+ | public static class PairWritableComparable< | ||
+ | private A first; | ||
+ | private B second; | ||
+ | |||
+ | public void readFields(DataInput in) throws IOException { | ||
+ | first.readFields(in); | ||
+ | second.readFields(in); | ||
+ | } | ||
+ | |||
+ | public void write(DataOutput out) throws IOException { | ||
+ | first.write(out); | ||
+ | second.write(out); | ||
+ | } | ||
+ | |||
+ | public int compareTo(Object other) { | ||
+ | PairWritableComparable< | ||
+ | int cmpFirst = first.compareTo(otherPair.getFirst()); | ||
+ | if (cmpFirst < 0) return -1; | ||
+ | if (cmpFirst > 0) return 1; | ||
+ | return second.compareTo(otherPair.getSecond()); | ||
+ | } | ||
+ | |||
+ | public A getFirst() { return first; } | ||
+ | public B getSecond() { return second; } | ||
+ | public void setFirst(A first) { this.first = first; } | ||
+ | public void setSecond(B first) { this.second = second; } | ||
+ | public String toString() { return String.format(" | ||
+ | public PairWritableComparable(A first, B second) { this.first = first; this.second = second; } | ||
+ | } | ||
+ | </ | ||
+ | Remark: If the '' | ||
+ | |||
+ | ===== Exercise ===== | ||
+ | |||
+ | Imagine you want to create an inverted index. In the index, for each word and document containing the word, all positions of the word in the document have to be stored. | ||
+ | |||
+ | Create a type '' | ||
+ | * stores a document of type '' | ||
+ | * stores a list of positions of occurrence. The sequence of length //N// should be stored on disk as number //N// followed by //N// numbers -- positions of occurrence. Type '' | ||
+ | * is comparable, comparing using the '' | ||
+ | * has methods '' | ||
+ | |||
+ | Using this type, create an inverted index -- implement a Hadoop job, that for each word creates a //sorted// list of '' | ||
+ | |||
+ | |||
+ | |||
+ | ---- | ||
+ | |||
+ | < | ||
+ | <table style=" | ||
+ | <tr> | ||
+ | <td style=" | ||
+ | <td style=" | ||
+ | <td style=" | ||
+ | </tr> | ||
+ | </ | ||
+ | </ |