Эффективный медианный расчет в MongoDB

Question

У нас есть коллекция Mongo с именем analytics, и она отслеживает посещения пользователей идентификатором файла cookie. Мы хотим рассчитать медианы для нескольких переменных, поскольку пользователи посещают разные страницы.

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

Мы закончили тем, что обновили медианный запрос каждой страницы, а не навалом с заданием cron или чем-то еще. У нас есть API-интерфейс Node, который использует структуру агрегации Mongo для выполнения сопоставления/сортировки результатов пользователя. Затем массив результатов переходит к медианной функции в узле. Затем результаты записываются обратно в Mongo для этого пользователя. Не очень доволен этим, но, похоже, он не имеет проблем с блокировкой и хорошо работает.

Answer 2

Простым способом получения медианного значения является индексирование по полю, а затем переход к значению в середине результатов.

> 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 больше, чем медиана?), поэтому было бы лучше просто обновлять время от времени на основе процедуры пропуска.