在地图中排序减少

Question

我正在尝试在矩阵的映射减少转置中实现一个简单的问题。输入：

   1 2 3 
   4 5 6 
   7 8 9 

期望的输出-

   1 4 7 
   2 5 8 
   7 8 9 

我的地图输出是

(0,1) (1,4), (2,7), (0,2) (1,5), (2,8)

等等。

我期望使用reducer方法方法作为0-{1,2,7} , 1-{4,5,8}，并直接使用write以序列化形式写入对象。但是随机和排序并没有给出所需的输出。在map方法之后，我得到的输出是0-{1,7,2} , 1-{5,4,8}。

如果我的密钥是通用的，SS 在这种情况下如何工作。以及这种情况的解决方案是什么。

Answer 1

键将在进入reduce阶段时进行排序，给定值集中的值将不会排序。
传递到化简器的值不能保证顺序，这不是Hadoop的工作方式。

你的问题（如你所说）是一个"简单问题"（在许多其他不同的框架和范式中）。对于 map reduce，这个问题不是一个容易（或适当）的问题。

---

针对您的情况的解决方案是使用更复杂的键，以确保输出按您最初想要的顺序排列，或者通过辅助排序映射减少作业传递输出，从键和单个值创建组合键。

Answer 2

不保证减少输入的值顺序。

您可以使用第二个MapReduce程序进行排序或您可以使用比较器。这是一个很好的博客来解决此案https://vangjee.wordpress.com/2012/03/20/secondary-sorting-aka-sorting-values-in-hadoops-mapreduce-programming-paradigm/

Answer 3

可以构造一个还包含列索引的值。

public class ColumnValue implements Writable{

    public double column;
    public double value;
    public PartialWritablePhase1(long column, double value){
        this.column = column;
        this.value = value;     
    }

    @Override
    public void readFields(DataInput in) throws IOException {
        this.column = in.readLong();
        this.value = in.readDouble();
    }
    @Override
    public void write(DataOutput out) throws IOException {
        out.writeLong(column);
        out.writeDouble(value);

    }
    @Override
    public String toString() {
            return column+" "+value;
}

}

然后，您可以在减速器中使用它

public void reduce(LongWritable key, Iterable<ColumnValue> values, Context context)
            throws IOException, InterruptedException {
        for (ColumnVal val : values) {
            //Store values of column in OrderedByColumn an ordered tree set by column
           // or any structure you want
        }

        Iterator<ColumnValue> keySetIterator = OrderedByColumn.iterator();
        while(keySetIterator.hasNext()){
          context.write(new LongWritable(key.get()), keySetIterator.next());
        }

    }

Answer 4

强制对

Reducer 中的值进行排序的唯一方法是创建自定义组合键并实现您自己的组比较器。这将实现您想要的。

public class CompositeKey implements WritableComparable<CompositeKey> {
    private int id;
    private int order;
    @Override
    public void readFields(DataInput in) throws IOException {
        id = in.readInt();
        order = in.readInt();
    }
    @Override
    public void write(DataOutput out) throws IOException {
        out.writeInt(id);
        out.writeInt(order);
    }
    @Override
    public int hashCode() {
        return id;
    }
    @Override
    public int compareTo(CompositeKey other) {
        if(this.id != other.id) {
            return this.id - other.id;
        }
        return this.order - other.order;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public int getOrder() {
        return order;
    }
    public void setOrder(int order) {
        this.order = order;
    }
}

id 字段对应于映射器输出的键。顺序字段对应于您希望值在化简器中为每个键显示的顺序。例如，您的映射器现在应该为第一个元素输出（键：{id=0，订单=0}，值：1），为第二个元素输出（键：{id=0，订单=1}，值：2）。这样，您将订购元素。

最后，为了仅按键 ID 对键值对进行分组，您需要编写自己的组比较器。

public class CompKeyGroupComparator extends WritableComparator {
    public CompKeyGroupComparator() {
        super(CompositeKey.class, true);
    }
    @Override
    public int compare(WritableComparable a, WritableComparable b) {
        CompositeKey lKey = (CompositeKey) a;
        CompositeKey rKey = (CompositeKey) b;
        return lKey.getId() - rKey.getId();
    }
}

要设置组比较器：

job.setGroupingComparatorClass(CompKeyGroupComparator.class);

现在，您的化简器将获得您在映射器中给出的顺序的值。0-{1,2,7} ， 1-{4,5,8} 等

Answer 5

在我看来，这可能是由于在缓冲区中排序时在地图端使用快速排序引起的。快速排序不稳定。

（但我发现当数字小于 13 时会使用 InsertSort。InsertSort是稳定的，所以我不确定QuickSort是否负责这里的9个键值对。