Den häufigsten Schlüssel in Reducer finden, Fehler: java.lang.ArrayIndexOutOfBoundsException: 1

Question

Ich muss den häufigsten Schlüssel finden, der von Mapper im Reducer ausgegeben wird. Mein Minderer arbeitet auf diese Weise fein:

public static class MyReducer extends Reducer<NullWritable, Text, NullWritable, Text> { 
    private Text result = new Text(); 
    private TreeMap<Double, Text> k_closest_points= new TreeMap<Double, Text>(); 
    public void reduce(NullWritable key, Iterable<Text> values, Context context) 
      throws IOException, InterruptedException { 

     Configuration conf = context.getConfiguration(); 
     int K = Integer.parseInt(conf.get("K")); 
     for (Text value : values) { 
      String v[] = value.toString().split("@"); //format of value from mapper: "Key@1.2345" 
      double distance = Double.parseDouble(v[1]); 
      k_closest_points.put(distance, new Text(value)); //finds the K smallest distances 
      if (k_closest_points.size() > K) 
       k_closest_points.remove(k_closest_points.lastKey()); 
     } 
     for (Text t : k_closest_points.values()) //it perfectly emits the K smallest distances and keys 
      context.write(NullWritable.get(), t); 
    } 
} 

Es ist die K-Instanzen mit den kleinsten Abständen findet und schreibt in die Ausgabedatei. Aber ich muss den häufigsten Schlüssel in meiner TreeMap finden. Also versuche ich es wie folgt:

public static class MyReducer extends Reducer<NullWritable, Text, NullWritable, Text> { 
    private Text result = new Text(); 
    private TreeMap<Double, Text> k_closest_points = new TreeMap<Double, Text>(); 

    public void reduce(NullWritable key, Iterable<Text> values, Context context) 
      throws IOException, InterruptedException { 

     Configuration conf = context.getConfiguration(); 
     int K = Integer.parseInt(conf.get("K")); 
     for (Text value : values) { 
      String v[] = value.toString().split("@"); 
      double distance = Double.parseDouble(v[1]); 
      k_closest_points.put(distance, new Text(value)); 
      if (k_closest_points.size() > K) 
       k_closest_points.remove(k_closest_points.lastKey()); 
     } 
     TreeMap<String, Integer> class_counts = new TreeMap<String, Integer>(); 
     for (Text value : k_closest_points.values()) { 
      String[] tmp = value.toString().split("@"); 
      if (class_counts.containsKey(tmp[0])) 
       class_counts.put(tmp[0], class_counts.get(tmp[0] + 1)); 
      else 
       class_counts.put(tmp[0], 1); 
     } 
     context.write(NullWritable.get(), new Text(class_counts.lastKey())); 
    } 
} 

Dann bekomme ich diesen Fehler:

Error: java.lang.ArrayIndexOutOfBoundsException: 1 
     at KNN$MyReducer.reduce(KNN.java:108) 
     at KNN$MyReducer.reduce(KNN.java:98) 
     at org.apache.hadoop.mapreduce.Reducer.run(Reducer.java:171) 

Können Sie mir bitte helfen dieses Problem beheben?

Answer 1

ein paar Dinge ... zuerst, Ihr Problem ist hier:

double distance = Double.parseDouble(v[1]); 

Sie auf "@" Aufspalten und es kann nicht in der Zeichenfolge sein. Wenn es nicht ist, wird es die OutOfBoundsException werfen. Ich würde eine Klausel wie hinzufügen:

if(v.length < 2) 
    continue; 

Zweite (und dies sollte nicht einmal kompilieren, es sei denn, ich bin verrückt), tmp ist ein String[], und doch hier sind Sie eigentlich nur verketten '1', um es in der put Betrieb (es ist eine Klammer Ausgabe):

class_counts.put(tmp[0], class_counts.get(tmp[0] + 1)); 

es sollte sein:

class_counts.put(tmp[0], class_counts.get(tmp[0]) + 1); 

es ist auch teuer aussehen der Schlüssel zweimal in einem potenziell großen Map. Hier ist, wie ich würde wieder schreiben Sie Ihre Minderer auf das, was Sie uns gegeben haben (das ist völlig ungetestet):

public static class MyReducer extends Reducer<NullWritable, Text, NullWritable, Text> { 
    private Text result = new Text(); 
    private TreeMap<Double, Text> k_closest_points = new TreeMap<Double, Text>(); 

    public void reduce(NullWritable key, Iterable<Text> values, Context context) 
      throws IOException, InterruptedException { 

     Configuration conf = context.getConfiguration(); 
     int K = Integer.parseInt(conf.get("K")); 

     for (Text value : values) { 
      String v[] = value.toString().split("@"); 
      if(v.length < 2) 
       continue; // consider adding an enum counter 

      double distance = Double.parseDouble(v[1]); 
      k_closest_points.put(distance, new Text(v[0])); // you've already split once, why do it again later? 

      if (k_closest_points.size() > K) 
       k_closest_points.remove(k_closest_points.lastKey()); 
     } 


     // exit early if nothing found 
     if(k_closest_points.isEmpty()) 
      return; 


     TreeMap<String, Integer> class_counts = new TreeMap<String, Integer>(); 
     for (Text value : k_closest_points.values()) { 
      String tmp = value.toString(); 
      Integer current_count = class_counts.get(tmp); 

      if (null != current_count) // avoid second lookup 
       class_counts.put(tmp, current_count + 1); 
      else 
       class_counts.put(tmp, 1); 
     } 

     context.write(NullWritable.get(), new Text(class_counts.lastKey())); 
    } 
} 

Als nächstes und semantisch, sind Sie ein KNN-Operation mit einem TreeMap als Datenstruktur der Wahl. Während dies insofern sinnvoll ist, als es intern Schlüssel in vergleichbarer Reihenfolge speichert, macht es keinen Sinn, eine Map für eine Operation zu verwenden, die mit hoher Wahrscheinlichkeit erforderlich ist, um Bindungen zu brechen. Hier ist warum:

int k = 2; 
TreeMap<Double, Text> map = new TreeMap<>(); 
map.put(1.0, new Text("close")); 
map.put(1.0, new Text("equally close")); 
map.put(1500.0, new Text("super far")); 
// ... your popping logic... 

Welche sind die beiden nächsten Punkte, die Sie beibehalten haben? "equally close" und "super far". Dies liegt daran, dass Sie nicht zwei Instanzen desselben Schlüssels haben können. Daher ist Ihr Algorithmus nicht in der Lage, Bindungen zu knacken. Es gibt ein paar Dinge, die Sie zu beheben tun könnte:

Erste, wenn Sie sich auf die Durchführung dieser Operation in der Reducer gesetzt sind und Sie wissen Ihre eingehenden Daten werden keine OutOfMemoryError verursachen, sollten Sie eine andere Verwendung verwenden

static class KNNEntry implements Comparable<KNNEntry> { 
    final Text text; 
    final Double dist; 

    KNNEntry(Text text, Double dist) { 
     this.text = text; 
     this.dist = dist; 
    } 

    @Override 
    public int compareTo(KNNEntry other) { 
     int comp = this.dist.compareTo(other.dist); 
     if(0 == comp) 
      return this.text.compareTo(other.text); 
     return comp; 
    } 
} 

und dann statt Ihrer TreeMap, eine TreeSet<KNNEntry>, die intern Art wird sich auf dem Comparator l zugrunde: eine benutzerdefinierte Comparable Objekt sortiert Struktur, wie ein TreeSet und bauen, dass es wird sortieren ogic haben wir gerade oben gebaut.Dann, nachdem Sie alle Schlüssel durchlaufen haben, durchlaufen Sie einfach die ersten k und behalten sie in der Reihenfolge bei. Dies hat jedoch einen Nachteil: Wenn Ihre Daten wirklich groß sind, können Sie den Heapspace überlaufen lassen, indem Sie alle Werte vom Reducer in den Speicher laden.

Zweite Option: machen die KNNEntry wir oben WritableComparable implementieren gebaut und emittieren, dass von Ihrem Mapper, dann secondary sorting verwenden die Sortierung Ihrer Eingaben zu behandeln. Dies wird ein wenig mehr haarig, da Sie viele Mapper und dann nur einen Reduzierer verwenden müssen, um die erste k zu erfassen. Wenn Ihre Daten klein genug sind, versuchen Sie die erste Option, um das Brechen zuzulassen.

Aber zurück zu Ihrer ursprünglichen Frage, erhalten Sie eine OutOfBoundsException, weil der Index, auf den Sie zugreifen möchten, nicht existiert, d.h. es gibt kein "@" in der Eingabe String.