计算中位数 - javascript

Question

我一直试图计算中位数,但我仍然有一些数学问题,因为我无法得到正确的中值,无法找出原因.这是代码;

class StatsCollector {

    constructor() {
        this.inputNumber = 0;
        this.average = 0;

        this.timeout = 19000;

        this.frequencies = new Map();
        for (let i of Array(this.timeout).keys()) {
            this.frequencies.set(i, 0);
        }
    }

    pushValue(responseTimeMs) {
        let req = responseTimeMs;
        if (req > this.timeout) {
            req = this.timeout;
        }

        this.average = (this.average * this.inputNumber + req) / (this.inputNumber + 1);

        console.log(responseTimeMs / 1000)
        let groupIndex = Math.floor(responseTimeMs / 1000);
        this.frequencies.set(groupIndex, this.frequencies.get(groupIndex) + 1);

        this.inputNumber += 1;
    }

    getMedian() {
        let medianElement = 0;
        if (this.inputNumber <= 0) {
            return 0;
        }
        if (this.inputNumber == 1) {
            return this.average
        }
        if (this.inputNumber == 2) {
            return this.average
        }
        if (this.inputNumber > 2) {
            medianElement = this.inputNumber / 2;
        }

        let minCumulativeFreq = 0;
        let maxCumulativeFreq = 0;
        let cumulativeFreq = 0;
        let freqGroup = 0;
        for (let i of Array(20).keys()) {
            if (medianElement <= cumulativeFreq + this.frequencies.get(i)) {
                minCumulativeFreq = cumulativeFreq;
                maxCumulativeFreq = cumulativeFreq + this.frequencies.get(i);
                freqGroup = i;
                break;
            }
            cumulativeFreq += this.frequencies.get(i);
        }

        return (((medianElement - minCumulativeFreq) / (maxCumulativeFreq - minCumulativeFreq)) + (freqGroup)) * 1000;
    }

    getAverage() {
        return this.average;
    }

}

这是我输入值时结果的快照

342,654,987,1093,2234,6243,7087,20123

应该是正确的结果;

中位数:1663.5

Answer 1

将中位数方法更改为:

function median(values){
  if(values.length ===0) return 0;

  values.sort(function(a,b){
    return a-b;
  });

  var half = Math.floor(values.length / 2);

  if (values.length % 2)
    return values[half];

  return (values[half - 1] + values[half]) / 2.0;
}

小提琴

Answer 2

2024 年 TypeScript 方法

const median = (arr: number[]): number | undefined => {
  if (!arr.length) return undefined;
  const s = [...arr].sort((a, b) => a - b);
  const mid = Math.floor(s.length / 2);
  return s.length % 2 ? s[mid] : ((s[mid - 1] + s[mid]) / 2);
};

笔记：

• 函数签名 ( ) 中的类型number[]确保只能将数字数组传递给函数。但它可能是空的。
• if (!arr.length) return undefined;检查可能的空数组，该数组没有中位数。
• [...arr]创建传入数组的副本以确保我们不会覆盖原始数组。
• .sort((a, b) => a - b)按升序对数字数组进行排序。
• Math.floor(s.length / 2)如果数组长度为奇数，则查找中间元素的索引；如果数组长度为偶数，则查找中间右侧的元素。
• s.length % 2判断数组的长度是否为偶数。
• (s[mid - 1] + s[mid]) / 2如果数组的长度是偶数，则对数组中间的两项进行平均。
• s[mid]是奇数长度数组的中间项。

Answer 3

这是另一个解决方案：

function median(numbers) {
    const sorted = numbers.slice().sort((a, b) => a - b);
    const middle = Math.floor(sorted.length / 2);

    if (sorted.length % 2 === 0) {
        return (sorted[middle - 1] + sorted[middle]) / 2;
    }

    return sorted[middle];
}

console.log(median([4, 5, 7, 1, 33]));

Answer 4

上面的解决方案 - 排序然后找到中间 - 很好，但在大型数据集上很慢。首先对数据进行排序的复杂度为 nx log(n)。

有一种更快的中值算法，它包括根据枢轴将数组分成两部分，然后在更大的集合中寻找中值。这是一些javascript代码，但这里有更详细的解释

// Trying some array
alert(quickselect_median([7,3,5])); // 2300,5,4,0,123,2,76,768,28]));

function quickselect_median(arr) {
   const L = arr.length, halfL = L/2;
   if (L % 2 == 1)
      return quickselect(arr, halfL);
   else
      return 0.5 * (quickselect(arr, halfL - 1) + quickselect(arr, halfL));
}

function quickselect(arr, k) {
   // Select the kth element in arr
   // arr: List of numerics
   // k: Index
   // return: The kth element (in numerical order) of arr
   if (arr.length == 1)
      return arr[0];
   else {
      const pivot = arr[0];
      const lows = arr.filter((e)=>(e<pivot));
      const highs = arr.filter((e)=>(e>pivot));
      const pivots = arr.filter((e)=>(e==pivot));
      if (k < lows.length) // the pivot is too high
         return quickselect(lows, k);
      else if (k < lows.length + pivots.length)// We got lucky and guessed the median
         return pivot;
      else // the pivot is too low
         return quickselect(highs, k - lows.length - pivots.length);
   }
}

细心的读者会注意到以下几点：

1. 我只是简单地将 Russel Cohen 的 Python 解决方案音译为 JS，因此对他的所有荣誉都是如此。
2. 有几个小的优化值得做，但也有值得做的并行化，而且代码在更快的单线程或更快的多线程版本中更容易更改。
3. 这是平均线性时间 算法，有更高效的确定性线性时间版本，请参阅Russel 的帖子了解详细信息，包括性能数据。

2019 年 9 月 19 日补充：

一个评论询问这是否值得在 javascript 中做。我在JSPerf 中运行了代码，它给出了有趣的结果。

• 如果数组有奇数个元素（要查找一个数字），则排序比这个“快速中位数”命题慢 20%。

• 如果有偶数个元素，“快速”算法会慢 40%，因为它过滤数据两次，以找到第 k 个元素和 k+1 个元素以求平均值。可以编写一个不这样做的快速中位数版本。

该测试使用了相当小的数组（jsperf 测试中的 29 个元素）。随着数组变大，效果似乎更加明显。一个更普遍的观点是：它表明这些类型的优化在 Javascript 中是值得做的。大量的计算是在 JS 中完成的，包括大量数据（想想仪表板、电子表格、数据可视化）和资源有限的系统（想想移动和嵌入式计算）。

Answer 5

`

var arr = {  
  max: function(array) {
    return Math.max.apply(null, array);
  },

  min: function(array) {
    return Math.min.apply(null, array);
  },

  range: function(array) {
    return arr.max(array) - arr.min(array);
  },

  midrange: function(array) {
    return arr.range(array) / 2;
  },

  sum: function(array) {
    var num = 0;
    for (var i = 0, l = array.length; i < l; i++) num += array[i];
    return num;
  },

  mean: function(array) {
    return arr.sum(array) / array.length;
  },

  median: function(array) {
    array.sort(function(a, b) {
      return a - b;
    });
    var mid = array.length / 2;
    return mid % 1 ? array[mid - 0.5] : (array[mid - 1] + array[mid]) / 2;
  },

  modes: function(array) {
    if (!array.length) return [];
    var modeMap = {},
      maxCount = 1,
      modes = [array[0]];

    array.forEach(function(val) {
      if (!modeMap[val]) modeMap[val] = 1;
      else modeMap[val]++;

      if (modeMap[val] > maxCount) {
        modes = [val];
        maxCount = modeMap[val];
      }
      else if (modeMap[val] === maxCount) {
        modes.push(val);
        maxCount = modeMap[val];
      }
    });
    return modes;
  },

  variance: function(array) {
    var mean = arr.mean(array);
    return arr.mean(array.map(function(num) {
      return Math.pow(num - mean, 2);
    }));
  },

  standardDeviation: function(array) {
    return Math.sqrt(arr.variance(array));
  },

  meanAbsoluteDeviation: function(array) {
    var mean = arr.mean(array);
    return arr.mean(array.map(function(num) {
      return Math.abs(num - mean);
    }));
  },

  zScores: function(array) {
    var mean = arr.mean(array);
    var standardDeviation = arr.standardDeviation(array);
    return array.map(function(num) {
      return (num - mean) / standardDeviation;
    });
  }
};

`