代码之家 › 专栏 › 技术社区 › Abdul Rafay

JavaScript——数组中最大数组和的最佳方法

arrays javascript

Abdul Rafay · 技术社区 · 8 年前

我有以下数组:

   arr = [
     [ 1, 1, 1, 1, 1, 1, 1 ],
     [ 1, 1, 0, 0, 1, 1, 0 ],
     [ 1, 0, 0, 0, 1, 0, 0 ],
     [ 0, 0, 0, 0, 0, 0, 0 ],
     [ 0, 1, 0, 1, 0, 0, 2 ],
     [ 1, 0, 0, 1, 0, 2, 4 ],
     [ 0, 0, 0, 0, 2, 4, 4 ],
     [ 0, 0, 0, 0, 4, 4, 0 ],
     [ 1, 1, 1, 0, 0, 0, 0 ],
     [ 1, 1, 0, 2, 0, 0, 2 ],
     [ 1, 0, 0, 4, 0, 2, 0 ],
     [ 0, 0, 0, 4, 2, 0, 0 ],
     [ 0, 0, 2, 0, 0, 0, 1 ],
     [ 0, 2, 4, 0, 0, 1, 2 ],
     [ 2, 4, 4, 2, 1, 2, 4 ],
     [ 4, 4, 0, 0, 2, 4, 0 ]
  ]

目前,我正在获取最大数组和 arr 也就是19岁

   function getMaxSum(arr) {
      return arr.map(e => e.reduce((a, b) => a + b, 0)).sort((a,b) => a - b)[arr.length - 1];
   }

我需要知道有没有更好的方法来实现这个目标?
我使用原始数组的数组长度来获取结果数组的最后一个元素,因为在本例中,原始数组和结果数组的长度是相同的。如果情况不同,则如何在此处使用结果数组的长度:

返回arr.map(e=>e.reduce((a,b)=>a+b,0)).sort((a,b)=>a-b)[ 酒店雇员和饭馆雇员 -1];

2 回复 | 直到 8 年前

Emil S. Jørgensen 8 年前

最佳策略应该是我们需要最少与阵列交互的策略。

在我的方法中,我单独测试数组产品,并将其与循环中的变量进行比较。这样我就不需要运行一个新的隐含循环 Math.max 再次检查我的所有条目,获得速度提升。

这也节省了内存管理,因为我不需要映射和返回 数学.max .

在循环结束时,我只返回变量。

var data = [
    [1, 1, 1, 1, 1, 1, 1],
    [1, 1, 0, 0, 1, 1, 0],
    [1, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0, 0, 2],
    [1, 0, 0, 1, 0, 2, 4],
    [0, 0, 0, 0, 2, 4, 4],
    [0, 0, 0, 0, 4, 4, 0],
    [1, 1, 1, 0, 0, 0, 0],
    [1, 1, 0, 2, 0, 0, 2],
    [1, 0, 0, 4, 0, 2, 0],
    [0, 0, 0, 4, 2, 0, 0],
    [0, 0, 2, 0, 0, 0, 1],
    [0, 2, 4, 0, 0, 1, 2],
    [2, 4, 4, 2, 1, 2, 4],
    [4, 4, 0, 0, 2, 4, 0]
];
function getMaxSum1(arr) {
    //The original method
    return arr.map(function (e) { return e.reduce(function (a, b) { return a + b; }, 0); }).sort(function (a, b) { return a - b; })[arr.length - 1];
}
function getMaxSum2(arr) {
    //From https://stackoverflow.com/a/51704254/5242739
    return Math.max.apply(Math, arr.map(function (e) { return e.reduce(function (a, b) { return a + b; }, 0); }));
}
function sumArray(arr) {
    var val = 0;
    for (var index = 0; index < arr.length; index++) {
        val += val;
    }
    return val;
}
function getMaxSum3(arr) {
    //My method
    var max;
    for (var i = 0; i < arr.length; i++) {
        var val = sumArray(arr[i]);
        if (max === void 0 || val > max) {
            max = val;
        }
    }
    return max;
}
//TEST
//parameters
var runs = 10;
var tests = 100000;
//output area
var out = document.body.appendChild(document.createElement("pre"));
//test functions
function simulate1() {
    var t = tests;
    var dt = Date.now();
    while (t--) {
        getMaxSum1(data);
    }
    out.textContent += 'getMaxSum1 took: ' + (Date.now() - dt) + "ms\n";
    requestAnimationFrame(simulate2);
}
function simulate2() {
    var t = tests;
    var dt = Date.now();
    while (t--) {
        getMaxSum2(data);
    }
    out.textContent += 'getMaxSum2 took: ' + (Date.now() - dt) + "ms\n";
    requestAnimationFrame(simulate3);
}
function simulate3() {
    var t = tests;
    var dt = Date.now();
    while (t--) {
        getMaxSum3(data);
    }
    out.textContent += 'getMaxSum3 took: ' + (Date.now() - dt) + "ms\n\n";
    if (runs--) {
        requestAnimationFrame(simulate1);
    }
}
//start
simulate1();

pre {
  max-height: 200px;
  overflow-y: scroll;
  background-color: #eee;
}

我包括 OliverRadini's answer 比较相对速度提升。

OliverRadini 8 年前

虽然没有很大的改进,但是将这些价值观传播到 Math.max

const data = [
     [ 1, 1, 1, 1, 1, 1, 1 ],
     [ 1, 1, 0, 0, 1, 1, 0 ],
     [ 1, 0, 0, 0, 1, 0, 0 ],
     [ 0, 0, 0, 0, 0, 0, 0 ],
     [ 0, 1, 0, 1, 0, 0, 2 ],
     [ 1, 0, 0, 1, 0, 2, 4 ],
     [ 0, 0, 0, 0, 2, 4, 4 ],
     [ 0, 0, 0, 0, 4, 4, 0 ],
     [ 1, 1, 1, 0, 0, 0, 0 ],
     [ 1, 1, 0, 2, 0, 0, 2 ],
     [ 1, 0, 0, 4, 0, 2, 0 ],
     [ 0, 0, 0, 4, 2, 0, 0 ],
     [ 0, 0, 2, 0, 0, 0, 1 ],
     [ 0, 2, 4, 0, 0, 1, 2 ],
     [ 2, 4, 4, 2, 1, 2, 4 ],
     [ 4, 4, 0, 0, 2, 4, 0 ]
  ]

function getMaxSum(arr) {
  return Math.max(...arr.map(e => e.reduce((a, b) => a + b, 0)))
}

console.log(getMaxSum(data))

正如@Rajesh所指出的,Math.max比一种

const numbers = Array(10000).fill().map((x,i)=>i);

const max = numbersIn => Math.max(...numbersIn);
const getMaxViaSort = numbersIn => numbersIn
  .sort((a, b) => a > b ? -1 : 1)[0]

console.time('max');
max(numbers);
console.timeEnd('max');

console.time('max via sort');
getMaxViaSort(numbers);
console.timeEnd('max via sort');