在Reducer中查找最常见的键，错误:java.lang.ArrayIndexOutOfBounds异常:1

Question

我需要在Reducer中找到Mapper发出的最常见的键。我的减速器以这种方式工作正常：

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

它查找距离最小的 K 个实例并写入输出文件。但我需要在树状图中找到最常用的键。所以我像下面这样尝试：

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

然后我得到这个错误：

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)

你能帮我解决这个问题吗？

Answer 1

有几件事...首先，你的问题就在这里：

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

您正在拆分"@"它可能不在字符串中。如果不是，它将抛出OutOfBoundsException.我会添加一个这样的条款：

if(v.length < 2)
    continue;

其次(除非我疯了，否则这甚至不应该编译(，tmp是一个String[]，但在这里你实际上只是在put操作中连接'1'它(这是一个括号问题(：

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

它应该是：

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

在一个潜在的大Map中查找两次密钥也很昂贵。以下是我如何根据您提供给我们的内容重写您的化简器(这是完全未经测试的(：

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

接下来，更语义上，您将使用 TreeMap 作为您选择的数据结构来执行 KNN 操作。虽然这是有道理的，因为它在内部按比较顺序存储密钥，但对几乎无疑需要断开关系的操作使用 Map 是没有意义的。原因如下：

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...

您保留了哪两个最接近的点？ "equally close"和"super far" .这是因为您不能拥有同一密钥的两个实例。因此，您的算法无法断开连接。您可以采取一些措施来解决此问题：

首先，如果您设置为在Reducer中执行此操作，并且您知道传入的数据不会导致OutOfMemoryError，请考虑使用不同的排序结构(如TreeSet(并构建它将排序的自定义Comparable对象：

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

然后代替你的TreeMap，使用TreeSet<KNNEntry>，它将根据我们上面刚刚构建的Comparator逻辑在内部对自身进行排序。然后在您完成所有键之后，只需循环访问第一个键k，按顺序保留它们。但是，这有一个缺点：如果数据确实很大，则可以通过将化简器中的所有值加载到内存中来溢出堆空间。

第二种选择：让我们上面构建的KNNEntry实现WritableComparable，并从您的Mapper发出它，然后使用二次排序来处理条目的排序。这变得更加毛茸茸的，因为您必须使用大量映射器，然后只有一个化简器来捕获第一个k。如果数据足够小，请尝试第一个选项以允许平局中断。

但是，回到您最初的问题，您得到了一个OutOfBoundsException，因为您尝试访问的索引不存在，即输入String中没有"@"。