Finding most common key in Reducer, Error: java.lang.ArrayIndexOutOfBoundsException: 1
Finding most common key in Reducer, Error: java.lang.ArrayIndexOutOfBoundsException: 1
我需要在 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个实例并写入输出文件。但我需要在我的 TreeMap 中找到最常用的键。所以我正在尝试如下：
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)
你能帮我解决这个问题吗？
一些事情...首先，您的问题在这里：
double distance = Double.parseDouble(v[1]);
您在 "@" 上拆分，它可能不在字符串中。如果不是，它将抛出 OutOfBoundsException。我会添加一个子句：
if(v.length < 2)
continue;
其次（除非我疯了，否则这甚至不应该编译），tmp 是一个 String[]，但在这里你实际上只是将 '1' 连接到它在 put 操作中（这是一个括号问题）：
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;
}
}
然后使用 TreeSet<KNNEntry> 而不是您的 TreeMap，它将根据我们刚刚在上面构建的 Comparator 逻辑在内部对自身进行排序。然后在你完成所有键之后，只需遍历第一个 k，按顺序保留它们。不过，这有一个缺点：如果您的数据确实很大，您可以通过将所有值从 reducer 加载到内存中来溢出堆空间。
第二个选项：让我们在上面构建的 KNNEntry 实现 WritableComparable，并从你的 Mapper 发出它，然后使用 secondary sorting 来处理条目的排序。这变得有点复杂，因为您必须使用大量映射器，然后只使用一个缩减器来捕获第一个 k。如果您的数据足够小，请尝试第一个选项以允许打破平局。
但是，回到你原来的问题，你得到一个 OutOfBoundsException 因为你试图访问的索引不存在，即输入中没有“@” String.
我需要在 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个实例并写入输出文件。但我需要在我的 TreeMap 中找到最常用的键。所以我正在尝试如下：
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)
你能帮我解决这个问题吗？
一些事情...首先，您的问题在这里：
double distance = Double.parseDouble(v[1]);
您在 "@" 上拆分，它可能不在字符串中。如果不是，它将抛出 OutOfBoundsException。我会添加一个子句：
if(v.length < 2)
continue;
其次（除非我疯了，否则这甚至不应该编译），tmp 是一个 String[]，但在这里你实际上只是将 '1' 连接到它在 put 操作中（这是一个括号问题）：
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;
}
}
然后使用 TreeSet<KNNEntry> 而不是您的 TreeMap，它将根据我们刚刚在上面构建的 Comparator 逻辑在内部对自身进行排序。然后在你完成所有键之后，只需遍历第一个 k，按顺序保留它们。不过，这有一个缺点：如果您的数据确实很大，您可以通过将所有值从 reducer 加载到内存中来溢出堆空间。
第二个选项：让我们在上面构建的 KNNEntry 实现 WritableComparable，并从你的 Mapper 发出它，然后使用 secondary sorting 来处理条目的排序。这变得有点复杂，因为您必须使用大量映射器，然后只使用一个缩减器来捕获第一个 k。如果您的数据足够小，请尝试第一个选项以允许打破平局。
但是，回到你原来的问题，你得到一个 OutOfBoundsException 因为你试图访问的索引不存在，即输入中没有“@” String.