javascript - 仅第一个值发生更改时如何使用 Javascript 数组

Question

我有一个小应用程序，当用户通过在州之间移动县来假设改变人口时，它会重新计算每个州国会席位的分配。功能上有无限的组合，所以我需要动态计算它。

方法是fairly straightforward :您为每个州分配 1 个席位，然后根据人口/((seats * (seats + 1))) 对其进行加权，迭代分配剩余的 385 个席位，并将席位分配给最高优先级的州。 p>

我已经用显而易见的方式让这个工作正常了:

function apportion(states) {
    var totalReps = 435;

    // assign one seat to each state
    states.forEach(function(state) {
        state.totalReps = 1;
        totalReps -= 1;
        state.priority = state.data.population / Math.sqrt(2); //Calculate default quota
    });

    // sort function
    var topPriority = function(a, b) {
        return b.priority - a.priority;
    };

    // assign the remaining 385
    for (totalReps; totalReps > 0; totalReps -= 1) {
        states.sort(topPriority);    
        states[0].totalReps += 1;
        // recalculate the priority for this state
        states[0].priority = states[0].data.population / Math.sqrt(states[0].totalReps * (states[0].totalReps + 1));
    }    
    return states;
}

但是，当每秒调用几次时，它会有点拖沓。我想知道除了使用整个数组之外，是否有更好的方法将接收座位的状态放入排序数组中。我对 Javascript sort() 函数不太了解，也不知道它是否已经以最大效率执行此操作，而没有被告知数组中除第一个元素之外的所有元素都已排序。有没有更有效的方法可以手动实现？

jsFiddle在这里:http://jsfiddle.net/raphaeljs/zoyLb9g6/1/

Answer 1

使用避免排序的策略，以下代码保留与 states 对象对齐的优先级数组，并使用 Math.max 查找最高优先级值，然后 indexOf 查找其在数组中的位置，然后更新 states 对象和 priorities 数组。

与所有性能优化一样，它在不同的浏览器中具有非常不同的结果(请参阅 http://jsperf.com/calc-reps )，但至少不慢 (Chrome)，最多快 4 倍 (Firefox)。

function apportion1(states) {
    var totalReps = 435;
    var sqrt2 = Math.sqrt(2);
    var priorities = [];
    var max, idx, state, n;

    // assign one seat to each state
    states.forEach(function(state) {
        state.totalReps = 1;
        state.priority = state.data.population / sqrt2; //Calculate default quota
        priorities.push(state.priority);
    });

    totalReps -= states.length;

    while (totalReps--) {
      max = Math.max.apply(Math, priorities);
      idx = priorities.indexOf(max);
      state = states[idx];
      n = ++state.totalReps;
      state.priority = state.data.population / Math.sqrt(n * ++n);
      priorities[idx] = state.priority;
    }
    return states;
}

为了进行测试，我使用了一个假设的 states 对象，其中只有 5 个州，但有真实的人口数据。希望在全部 50 个州中， yield 会更大。

另一种策略是对人口进行排序，因为这就是优先级的分配方式，为每个州分配至少一个代表并计算优先级，然后从 0 开始添加代表并重新计算优先级。将会有一个阈值，低于该阈值的州不应获得更多代表。

交给你了。 ;-)

编辑

这是一个非常简单的根据人口分配的方法。如果可能分配过多或过少。在第一种情况下，找到优先级最低且至少有 2 个代表的状态(如果需要，可以重新计算优先级)并拿走一个代表。在第二个中，找到具有最高优先级的状态并添加一个代表(如果需要，还可以重新计算优先级)。

function simple(states) {
  var totalPop = 0;
  var totalReps = 435
  states.forEach(function(state){totalPop += state.data.population});
  var popperrep = totalPop/totalReps;
  states.forEach(function(state){
    state.totalReps = Math.round(state.data.population / popperrep);
    state.priority = state.data.population / Math.sqrt(state.totalReps * (state.totalReps + 1));
  });
  return states;
}

未经测试，但我敢打赌它比其他的快得多。 ;-)

我更新了 simple 函数的测试示例，以调整分布是否导致代表总数不正确。经过各种场景的测试，它给出了与原始代码相同的结果，尽管它使用了非常不同的算法。它比原始版本快数百倍，具有完整的 50 个状态。

这是简单函数的最终版本:

function simple(states) {
  var count = 0;
  var state, diff;
  var totalPop = states.reduce(function(prev, curr){return prev + curr.data.population},0);
  var totalReps = 435
  var popperrep = totalPop/totalReps;

  states.forEach(function(state){
    state.totalReps = Math.round(state.data.population / popperrep) || 1;
    state.priority = state.data.population / Math.sqrt(state.totalReps * (state.totalReps + 1));
    count += state.totalReps;
  });

  // If too many reps distributed, trim from lowest priority with 2 or more
  // If not enough reps distributed, add to highest priority
  while ((diff = count - totalReps)) {
    state = states[getPriority(diff < 0)];
    state.totalReps += diff > 0? -1 : 1;
    count += diff > 0? -1 : 1;
    state.priority = state.data.population / Math.sqrt(state.totalReps * (state.totalReps + 1));
    // console.log('Adjusted ' + state.data.name + ' ' + diff);
  }

  return states;

  // Get lowest priority state with 2 or more reps,
  // or highest priority state if high is true
  function getPriority(high) {
    var idx, p = high? 0 : +Infinity;
    states.forEach(function(state, i){

      if (( high && state.priority > p) || (!high && state.totalReps > 1 && state.priority < p)) {
        p = state.priority;
        idx = i;
      }
    });
    return idx;
  }
}