计算中位数 - 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

正确的结果应该是；

Median: 1663.5

Answer 1

将您的中位数方法更改为：

function median(values){
  if(values.length ===0) throw new Error("No inputs");

  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;
}

fiddle

Answer 2

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;
    });
  }
};

Answer 3

这是另一个解决方案：

function median(numbers) {
    const sorted = Array.from(numbers).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

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

有一种更快的中值算法，它根据一个主元将数组分成两部分，然后在更大的集合中寻找中值。这是一些 javascript 代码，但是 here is a more detailed explanation

// 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);
   }
}

细心的读者会注意到一些事情：

我只是将 Russel Cohen 的 Python 解决方案运行sliterated 到 JS 中，所以所有的荣誉都归功于他。
有几个小的优化值得做，但值得做的是并行化，代码也是如此更容易改变更快 single-threaded 或更快 multi-threaded，版本。
这是平均线性时间 算法，有更有效的确定性线性时间版本，参见Russel's post 了解详情，包括性能数据。

2019 年 9 月 19 日补充：

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

如果数组的元素数量为奇数（一个数字即可找到），排序比这个 "fast median" 命题慢 20%。
如果有偶数个元素，"fast"算法慢40%，因为它过滤了两次数据，找到第k和k+1个元素进行平均.可以编写一个不执行此操作的快速中位数版本。

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

Answer 5

为了在时间复杂度方面获得更好的性能，请使用 MaxHeap - MinHeap 来查找数组流的中值。

Answer 6

更简单更高效

const median = dataSet => {
  if (dataSet.length === 1) return dataSet[0]
  const sorted = ([ ...dataSet ]).sort()
  const ceil = Math.ceil(sorted.length / 2)
  const floor = Math.floor(sorted.length / 2)
  if (ceil === floor) return sorted[floor]
  return ((sorted[ceil] + sorted[floor]) / 2)
}

Answer 7

简短而甜美。

Array.prototype.median = function () {
  return this.slice().sort((a, b) => a - b)[Math.floor(this.length / 2)]; 
};

用法

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

也适用于字符串

["a","a","b","b","c","d","e"].median()

Answer 8

TypeScript 答案 2020：

// Calculate Median 
const calculateMedian = (array: Array<number>) => {
  // Check If Data Exists
  if (array.length >= 1) {
    // Sort Array
    array = array.sort((a: number, b: number) => {
      return a - b;
    });

    // Array Length: Even
    if (array.length % 2 === 0) {
      // Average Of Two Middle Numbers
      return (array[(array.length / 2) - 1] + array[array.length / 2]) / 2;
    }
    // Array Length: Odd
    else {
      // Middle Number
      return array[(array.length - 1) / 2];
    }
  }
  else {
    // Error
    console.error('Error: Empty Array (calculateMedian)');
  }
};

Answer 9

简单的解决方案：

function calcMedian(array) {
  const {
    length
  } = array;

  if (length < 1)
    return 0;

  //sort array asc
  array.sort((a, b) => a - b);

  if (length % 2) {
    //length of array is odd
    return array[(length + 1) / 2 - 1];
  } else {
    //length of array is even
    return 0.5 * [(array[length / 2 - 1] + array[length / 2])];
  }
}

console.log(2, calcMedian([1, 2, 2, 5, 6]));
console.log(3.5, calcMedian([1, 2, 2, 5, 6, 7]));
console.log(9, calcMedian([13, 9, 8, 15, 7]));
console.log(3.5, calcMedian([1, 4, 6, 3]));
console.log(5, calcMedian([5, 1, 11, 2, 8]));

Answer 10

更简单、更高效且易于阅读

克隆数据以避免更改原始数据。
对值列表进行排序。
得到中间点。
从列表中获取中位数。
return中位数。

function getMedian(data) {
    const values = [...data];
    const v   = values.sort( (a, b) => a - b);
    const mid = Math.floor( v.length / 2);
    const median = (v.length % 2 !== 0) ? v[mid] : (v[mid - 1] + v[mid]) / 2; 
    return median;
}

Answer 11

       const medianArr = (x) => {
        let sortedx = x.sort((a,b)=> a-b);
        let halfIndex = Math.floor(sortedx.length/2);
        
         return (sortedx.length%2) ? (sortedx[Math.floor(sortedx.length/2)]) :  ((sortedx[halfIndex-1]+sortedx[halfIndex])/2)
    }
    
    console.log(medianArr([1,2,3,4,5]));
    console.log(medianArr([1,2,3,4,5,6]));

Answer 12

2022 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 === 0 ? ((s[mid - 1] + s[mid]) / 2) : s[mid];
};

备注：

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

Answer 13

const median = (arr) => {
  return arr.slice().sort((a, b) => a - b)[Math.floor(arr.length / 2)];
};

计算中位数 - javascript

Calculating median - javascript

javascript

median

2022 TypeScript 方法