3

我有一个有趣的 Javascript 任务（在 Node.js，FWIW 中执行）：我需要取数据集的“加权中位数”，我有值（在这种情况下为收入）和每个数据集的权重。例如：

income  #people
0   5
16000   3
20000   8
32000   4
40000   3
41000   1
50000   2
90000   1

换句话说，8 人赚 2 万美元，2 人赚 5 万美元，等等。我需要“加权中位数”——所有 27 人的中位数。

天真的方法是创建一个数组并用每个值作为种子，如下所示：

var incomes = [0, 0, 0, 0, 0, 16000, 16000, 16000, 20000, 20000, 20000, 20000, 20000, 20000, 20000, 20000, 32000, 32000, 32000, 32000, 40000, 40000, 40000, 41000, 50000, 50000, 90000];

然后可以轻松地获取该数组的中位数（即 20,000 美元）。实际上，我拥有每个样本 7,000 到 14,000 人的数据。虽然我确信 Node 可以处理这么大的数组，但感觉非常草率。

我目前的解决方案是计算假设的详细数组中中值的索引——在这种情况下为 13——并循环遍历收入和权重数组，将累积权重相加，直到达到或超过中点. 这是一个简化的例子。（显然，对于偶数列表，中位数需要稍微不同的规则。这只是一个 POC。）

var halfway = 13,
    progress = 0;

var vals = [[0,5], [16000,3], [20000,8], [32000,4], [40000,3], [41000,1], [50000,2], [90000,1]];

for (var v = 0; v < vals.length; v += 1) {
    progress += vals[v][1];

    if (progress >= halfway) {
        var median = vals[v][0];
        break;
    }
}

这工作正常，但是当你想开始计算四分位数时它会变得混乱等等。对我来说更容易的是能够在详细数组中的适当位置创建一个稀疏的值数组，而无需填写所有中间值，然后在该数组上执行查找任何索引直到最大值。但是，如果（很可能）我在备用数组中寻找的索引未填充，我需要一些有效的机制来查找稀疏数组中的先前已知索引。

这似乎是一个相当普遍的问题。

4

1 回答 1

1

在计算效率方面，我认为你所拥有的和你将得到的一样好，尽管我不确定你在四分位数方面面临什么困难（抱歉代表太低，无法要求澄清）。

让我们先看看你所拥有的东西的效率。您有一个长度为 n 的数组，您逐步将其添加到一个计数器并中途中断（我假设给出了中途信息，再次抱歉太低而无法询问）。所以看一个简单的 O(n) 还不错。

现在你提出的是某种形式的查找，给定一个索引知道最近的填充索引，O(1)。那会更好，所以让我们看看我们需要什么。那么我们需要通过循环将给定的数据移动到一些新的数据结构中......哦，哎呀，这意味着回到了O（n）。

故事的寓意是你所拥有的是好的，好的工作。

于 2014-09-24T21:16:52.750 回答