MongoDB 中的高效中位数计算

Question

我们有一个名为 analytics 的 Mongo 集合，它通过 cookie ID 跟踪用户访问。当用户访问不同的页面时，我们想计算几个变量的中位数。

Mongo does not yet have an internal method for calculating the median. 我已经使用了下面的方法来确定它，但恐怕还有更有效的方法，因为我对 JS 还很陌生。如有任何意见，我们将不胜感激。

// Saves the JS function for calculating the Median. Makes it accessible to the Reducer.
db.system.js.save({_id: "myMedianValue",
    value: function (sortedArray) {
    var m = 0.0;
    if (sortedArray.length % 2 === 0) {
        //Even numbered array, average the middle two values
        idx2 = sortedArray.length / 2;
        idx1 = idx2 - 1;
        m = (sortedArray[idx1] + sortedArray[idx2]) / 2;
    } else {
        //Odd numbered array, take the middle value
        idx = Math.floor(sortedArray.length/2);
        m = sortedArray[idx];
    }
        return m
    }
});


var mapFunction = function () {
    key = this.cookieId;
    value = {
        // If there is only 1 view it will look like this
        // If there are multiple it gets passed to the reduceFunction
        medianVar1: this.Var1,
        medianVar2: this.Var2,
        viewCount: 1
    };

    emit(key, value);
    };

var reduceFunction = function(keyCookieId, valueDicts) {
    Var1Array = Array();
    Var2Array = Array();
    views = 0;

    for (var idx = 0; idx < valueDicts.length; idx++) {
        Var1Array.push(valueDicts[idx].medianVar1);
        Var2Array.push(valueDicts[idx].medianVar2);
        views += valueDicts[idx].viewCount;
    }


    reducedDict = {
        medianVar1: myMedianValue(Var1Array.sort(function(a, b){return a-b})),
        medianVar2: myMedianValue(Var2Array.sort(function(a, b){return a-b})),
        viewCount: views
    };

    return reducedDict
    };


db.analytics.mapReduce(mapFunction,
                       reduceFunction,
                       { out: "analytics_medians",
                         query: {Var1: {$exists:true},
                                 Var2: {$exists:true}
                                 }}
                                 )

Answer 1

获取中值的简单方法是在字段上建立索引，然后跳到结果中间的值。

> db.test.drop()
> db.test.insert([
    { "_id" : 0, "value" : 23 },
    { "_id" : 1, "value" : 45 },
    { "_id" : 2, "value" : 18 },
    { "_id" : 3, "value" : 94 },
    { "_id" : 4, "value" : 52 },
])
> db.test.ensureIndex({ "value" : 1 })
> var get_median = function() {
    var T = db.test.count()    // may want { "value" : { "$exists" : true } } if some fields may be missing the value field
    return db.test.find({}, { "_id" : 0, "value" : 1 }).sort({ "value" : 1 }).skip(Math.floor(T / 2)).limit(1).toArray()[0].value    // may want to adjust skip this a bit depending on how you compute median e.g. in case of even T
}
> get_median()
45

虽然跳过了也算不上惊艳，但至少查询会被索引覆盖。对于更新中位数，您可能会更喜欢。当有新文档进来或文档的 value 更新时，您将其 value 与中位数进行比较。如果新的 value 更高，您需要通过从当前中值文档中找到下一个最高的 value 来调整中值（或者取平均值，或者根据正确计算新中值的任何方法）遵守你的规则）

> db.test.find({ "value" : { "$gt" : median } }, { "_id" : 0, "value" : 1 }).sort({ "value" : 1 }).limit(1)

如果新 value 小于当前中位数，您将执行类似的操作。这会阻碍您在更新过程中的写作，并且需要考虑各种情况（您如何允许自己一次更新多个文档？更新具有中值的文档？更新 value 小于的文档value 大于中位数的中位数？），因此根据跳过过程偶尔更新可能更好。

Answer 2

我们最终更新了每个页面请求的中位数，而不是通过 cron 作业或其他东西批量更新。我们有一个节点 API，它使用 Mongo 的聚合框架来处理 match/sort 用户的结果。然后将结果数组传递给 Node.js 中的中值函数。然后将结果写回该用户的 Mongo。不是很满意，但它似乎没有锁定问题并且表现良好。

MongoDB 中的高效中位数计算

Efficient Median Calculation in MongoDB

mapreduce

median

mongodb