1D -> 2D 数组 W/Normal 曲线子数组长度

Question

我正在尝试将一个一维数组分解为一个二维数组，其中子数组的长度各不相同。此方差应遵循高斯曲线 [或丘形状]。因此，假设我们创建的二维数组变量名为 gaussianCurve。 gaussianCurve[0] & gaussianCurve[n] 中的数组长度为 1，而 gaussianCurve[n/2] 将是参数 "maxArrayLength" 提供的最大值。这迫使 gaussianCurve 索引的数量变为可变。

假设我有以下伪代码：

function (oneDimentionalArray, maxArrayLength) {
// oneDimentionalArray is ["A","B","C","D","E","F","G","H","I","J","K"]
// maxArrayLength is 5
// Currently working like this (i.e. "batches"):
// return [["A","B","C","D","E"],["F","G","H","I","J"],["K"]]
// would LIKE it to work like this
    gaussianCurve = []
    gaussianCurve.push(["A"])
    gaussianCurve.push(["B", "C"])
    gaussianCurve.push(["D", "E", "F", "G", "H"])
    gaussianCurve.push(["I", "J"])
    gaussianCurve.push(["K"])

    return  gaussianCurve
}

我为什么要这样的东西？进度条。

他们没有显示我正在立即取得进步
1. 这是因为必须先完成第一个作业才能移动条形图
他们在 95%+ 时减速，有时甚至停留在 100%
1. 真烦人

欢迎提出任何建议。我只是没有在脑海中看到答案。

编辑：我觉得它措辞不佳，所以我正在重新措辞。

...gaussianCurve[0].length & gaussianCurve[gaussianCurve.length - 1].length 将为 1，而 gaussianCurve[gaussianCurve.length/2].length 将达到 "maxArrayLength".

输入：

function gaussianRefactor(["A","B","C","D","E","F","G","H","I","J","K"], 1)
function gaussianRefactor(["A","B","C","D","E","F","G","H","I","J","K"], 2)
function gaussianRefactor(["A","B","C","D","E","F","G","H","I","J","K"], 4)
function gaussianRefactor(["A","B","C","D","E","F","G","H","I","J","K"], 8)
function gaussianRefactor(["A","B","C","D","E","F","G","H","I","J","K"], 16)

输出：

[["A"],["B"],["C"],["D"],["E"],["F"],["G"],["H"],["I"],["J"],["K"]]
[["A"],["B","C"],["D","E"],["F","G"],["H","I"],["J"],["K"]]
[["A"],["B","C","D"],["E","F","G","H"],["I","J","K"]]
[["A"],["B","C","D","E","F","G","H","I"],["J","K"]]
[["A","B","C","D","E","F","G","H","I","J","K"]]

内部数组的长度不得超过 maxArrayLength

Answer 1

我快速试了一下，似乎有效。一些潜在的改进：

函数的输入检查
它将所有可能的剩余值放入中间箱。对于偶数总箱，它会受益于一些平衡。之后，尝试根据输入数据中的原始索引对每个 bin 进行排序可能会很好，因为现在事情可能会乱序结束。但是，如果这只是为了让进度条具有非线性分布的作业，则顺序可能无关紧要。

function probability(s, m, x) {
 var eExp = -Math.pow(x - m, 2) /
  (2 * Math.pow(s, 2));
 return 1/(Math.sqrt(2*Math.PI) * s) *
  Math.pow(Math.E, eExp);
}

function gassianArray(input, nBins) {
 // first try to determine a reasonable value of s so that the outer bins have a value
 var s = 0.1;
 var sMax = 10;
 var m = (nBins - 1) / 2.0;
 var outerBinMinimum = 1 / input.length;
 var p = 0;
 while (true && s <= sMax) {
  p = probability(s, m, 0);
  if (p >= outerBinMinimum) {
   break;
  } else {
   s += 0.1;
  }
 }

 // holds arrays
 var output = [];
 // holds desired array sizes
 var outputLengths = [];
 // fill these based on probability density
 for (var b=0; b<nBins; b++) {
  var n = Math.floor(probability(s, m, b) * input.length);
  output.push([]);
  outputLengths.push(n);
 }

 // fill arrays from outside, leaving extra values for the middle
 var midIndex = Math.floor(m);
 // left side
 for (var i=0; i<midIndex; i++) {
  for (var j=0; j<outputLengths[i]; j++) {
   output[i].push(input.shift());
  }
 }
 // right side
 for (var i=nBins-1; i>=midIndex; i--) {
  for (var j=0; j<outputLengths[i]; j++) {
   output[i].push(input.pop());
  }
  output[i].reverse();
 }
 // whatever remains goes in the "middle"
 while (input.length !== 0) {
  output[midIndex].unshift(input.pop());
 }

 return output;
}

var input = ["A","B","C","D","E","F","G","H","I","J","K"];
var n = 5;
console.log(gassianArray(input, n));
/*
[ [ 'A' ],
  [ 'B', 'C' ],
  [ 'E', 'D', 'F', 'G', 'H' ],
  [ 'I', 'J' ],
  [ 'K' ] ]
*/


var input = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"];
var n = 6;
console.log(gassianArray(input, n));
/*
[ [ 'A' ],
  [ 'B', 'C', 'D', 'E' ],
  [ 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N' ],
  [ 'O', 'P', 'Q', 'R', 'S', 'T', 'U' ],
  [ 'V', 'W', 'X', 'Y' ],
  [ 'Z' ] ]
*/

Answer 2

非常有趣的挑战。 :)

我玩了一下，这是我想出的：

function chunk(arr, start, n) {
  if (arr.length < n) {
    return null;
  }

  return arr.splice(start, n);
}

function gaussianArray(arr, max) {
  const len = arr.length;

  if (max > len) {
    return [arr];
  }

  const curve = [];

  // Extract middle.
  const mid = Math.floor(len / 2);
  const startIndex = mid - (max / 2) + 1;
  const highest = arr.splice(startIndex, max);

  curve.push(highest);

  // Splits the rest in 2 arrays; left side and right side, middle already excluded.
  const leftArr = arr.slice(0, startIndex);
  const rightArr = arr.slice(startIndex, len);

  let leftMax = max;
  let rightMax = max;

  // Adds chunks from left side.
  while (leftArr.length) {
    const leftChunk = chunk(leftArr, leftArr.length - leftMax, leftMax);

    if (leftChunk) {
      curve.unshift(leftChunk);
    } else {
      leftMax--;
    }
  }

  // Adds chunks from right side.
  while (rightArr.length) {
    const rightChunk = chunk(rightArr, 0, rightMax);

    if (rightChunk) {
      curve.push(rightChunk);
    } else {
      rightMax--;
    }
  }

  return curve;
}

console.log(JSON.stringify(gaussianArray(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 1)));
console.log(JSON.stringify(gaussianArray(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 2)));
console.log(JSON.stringify(gaussianArray(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 4)));
console.log(JSON.stringify(gaussianArray(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 8)));
console.log(JSON.stringify(gaussianArray(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 16)));

这不是你想要的，但我认为它应该接近解决你的进度条问题......

Answer 3

这更符合我的想法。我非常不喜欢我寻找西格玛的方式。我知道我应该重新排序公式来计算它，但我还没有让它起作用。无论如何，这是“答案”，尽管它对于我在问题中作为示例提供的较小数组失败了，但它成功地完成了我需要做的事情。如果有人想添加改进，请告诉我。

var gaussianRefactor = function(srcOneDimentionalArray, srcMaxArrayLength) {
  var finalArray = [];
  if (srcOneDimentionalArray.length <= srcMaxArrayLength) {
    finalArray.push(srcOneDimentionalArray);
    return finalArray;
  }
  if (srcMaxArrayLength === 1) {
  for(var lengthOne = 0; lengthOne < srcOneDimentionalArray.length; lengthOne++)
    finalArray.push([srcOneDimentionalArray[lengthOne]]);
    return finalArray;
  }
  var maxArrayLength = srcMaxArrayLength;
  var oneDimentionalArray = srcOneDimentionalArray.slice(0);
  for (var x = srcMaxArrayLength; x > 1 && maxArrayLength / oneDimentionalArray.length > 0.3333; x--) {
    maxArrayLength--;
  }
  var standardChunkSize = srcOneDimentionalArray.length / maxArrayLength;
  var predictedSize = (3 * Math.floor(standardChunkSize)) % 2 === 0 ? 3 * Math.floor(standardChunkSize) + 1 : 3 * Math.floor(standardChunkSize);
  var predictedSizeCenter = Math.ceil(predictedSize / 2);
  var sigma = 0.2034185 * Math.pow(standardChunkSize, 1.963449);
  var multiplicand = 1 / (Math.sqrt(sigma) * Math.sqrt(2 * Math.PI));
  var centerGauss = maxArrayLength / multiplicand;
  var mu = 0;
  var delta;
  var fraction;
  var exponent;
  var full;
  var subArrayLength;
  var subArray;
  var notWideEnough = true;
  var maxElements;
  var maxAttempts = Math.max(Math.ceil(sigma), 100);
  var currentAttempts = 0;
  while (notWideEnough && currentAttempts < maxAttempts) {
    maxElements = 0;
    for (var j = 0; j < predictedSize; j++) {
      delta = (j - predictedSizeCenter) - mu;
      fraction = delta / Math.sqrt(sigma);
      exponent = -0.5 * Math.pow(fraction, 2);
      full = multiplicand * Math.exp(exponent);
      subArrayLength = Math.floor(full * centerGauss);
      maxElements += subArrayLength;
    }
    if (maxElements >= srcOneDimentionalArray.length) {
      notWideEnough = false;
    } else {
      sigma = sigma + sigma * 0.05;
    }
    currentAttempts++;
  }
  if (currentAttempts === maxAttempts) {
    return false;
  }

  for (var i = 0; i < predictedSize; i++) {
    delta = (i - predictedSizeCenter) - mu;
    fraction = delta / Math.sqrt(sigma);
    exponent = -0.5 * Math.pow(fraction, 2);
    full = multiplicand * Math.exp(exponent);
    subArrayLength = Math.floor(full * centerGauss);
    if (subArrayLength < 1 || oneDimentionalArray.length < 1) {
      continue;
    }
    subArray = oneDimentionalArray.slice(0, subArrayLength);
    oneDimentionalArray = oneDimentionalArray.slice(subArrayLength, oneDimentionalArray.length);
    finalArray.push(subArray);
  }
  return finalArray;
}

输入

gaussianRefactor(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 1)
gaussianRefactor(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 2)
gaussianRefactor(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 4)
gaussianRefactor(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 8)
gaussianRefactor(["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K"], 16)

输出

[["A"],["B"],["C"],["D"],["E"],["F"],["G"],["H"],["I"],["J"],["K"]]
[["A"],["B"],["C"],["D"],["E"],["F","G"],["H"],["I"],["J"],["K"]]
[["A"],["B"],["C","D"],["E","F","G"],["H","I"],["J"],["K"]]
[["A"],["B"],["C","D"],["E","F","G"],["H","I"],["J"],["K"]]
[["A","B","C","D","E","F","G","H","I","J","K"]]

-- 编辑 2021 -- https://jsfiddle.net/brightmatter_og/xzfwjeaq/ 我找到了我正在寻找的答案。如果有人感兴趣，我会放在这里。

function removeMeFromTheList(removeMe, theList) {
  for (let i = 0; i < theList.length; i++) {
    if (theList[i] === removeMe) {
      theList.splice(i, 1);
      return;
    }
  }
}

function makeListOfGaussianLists(chunkWeights, objects) {
  const listOfLists = [];
  const chunkWeightsSize = Object.keys(chunkWeights).length;
  if (chunkWeightsSize < 1 || objects.length < chunkWeightsSize) {
    console.info("chunkWeights.length:" + chunkWeightsSize + " - objects.length:" + objects.length);
    return null;
  }
  const elementCount = objects.length / chunkWeightsSize;
  let modifiedElementCount = null;
  for (let i = 0; i < chunkWeightsSize; i++) {
    modifiedElementCount = parseInt(chunkWeights[i] * elementCount);
    let innerList = [];
    for (let j = modifiedElementCount; j > 0; j--) {
      const obj = objects[0];
      if (obj == null) {
        break;
      }
      innerList.push(obj);
      removeMeFromTheList(obj, objects);
    }
    listOfLists.push(innerList);
  }
  if (objects.length > 0) {
    do {
      for (let i = 0; i < listOfLists.length; i++) {
        const obj = objects[0];
        if (obj == null) {
          break;
        }
        listOfLists[i].push(obj);
        removeMeFromTheList(obj, objects);
      }
    } while (objects.length > 0);
  }
  return listOfLists;
}

function subListWeightBuilder(partitionCount) {
  const gauss = [];
  const population = 250;
  const chunkWeights = {};
  if (partitionCount > population) {
    return chunkWeights;
  }
  for (let i = 0; i < population * 2; i++) {
    gauss.push(randomGaussian());
  }
  gauss.sort(function(a, b){return a - b});
  const partitionWidth = gauss.length / partitionCount;
  let currentCount = 0;
  let chunkWeightsIndex = 0;
  let pastTheFirst = false;
  for (let j = 0; j < gauss.length; j++) {
    if (currentCount < partitionWidth) {
      chunkWeights[chunkWeightsIndex] = 1 / (Math.abs(gauss[j]) + 0.66);
    } else {
      chunkWeightsIndex++;
      currentCount = 0;
    }
    currentCount++;
  }
  let offset = 0;
  for (let key in chunkWeights) {
    offset += chunkWeights[key];
  }
  offset /= partitionCount;
  offset = (1 - offset) + Number.MIN_VALUE;
  for (let key in chunkWeights) {
    let value = chunkWeights[key];
    chunkWeights[key] = value + offset;
  }
  return chunkWeights;
}

function randomGaussian() {
  let r = 0;
  const iteration = 6;
  for (let i = iteration; i > 0; i--) {
    r += Math.random();
  }
  return r / iteration - 0.5;
}

function pressButton() {
  let partitionCount = 23;
  console.info(makeListOfGaussianLists(subListWeightBuilder(partitionCount), makeRandomString(333).split("")));
  partitionCount = 41;
  console.info(makeListOfGaussianLists(subListWeightBuilder(partitionCount), makeRandomString(666).split("")));
  partitionCount = 67;
  console.info(makeListOfGaussianLists(subListWeightBuilder(partitionCount), makeRandomString(1000).split("")));
  partitionCount = 41;
  console.info(makeListOfGaussianLists(subListWeightBuilder(partitionCount), makeRandomString(1333).split("")));
  partitionCount = 23;
  console.info(makeListOfGaussianLists(subListWeightBuilder(partitionCount), makeRandomString(1666).split("")));
}

function makeRandomString(size) {
  const loops = parseInt(size / 11);
  let theResult = "";
  for(let i = loops; i > 0; i--) {
    theResult += Array(11 + 1).join((Math.random().toString(36) + '00000000000000000').slice(2, 18)).slice(0, 11);
  }
  return theResult += Array((size - 11 * loops) + 1).join((Math.random().toString(36) + '00000000000000000').slice(2, 18)).slice(0, (size - 11 * loops))
}

1D -> 2D 数组 W/Normal 曲线子数组长度

1D -> 2D Array W/Normal Curve Sub-Array Lengths

javascript

arrays

gaussian

splice

batching