9

要求是确定呈现字符串的最有效方法，例如，"#1a2b3c"从"1a2b3c"集合中随机选择

"abcdef0123456789"

或者

["a", "b", "c", "d", "e", "f", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]

为了比较结果的一致性，字符串.length应该是精确7的，如上例所示。

确定过程结果时间的迭代次数应10000如以下代码中使用的那样。

我们可以从两个前瞻性的例子和基准开始调查。方法的基准应包含在答复的文本中。请注意，如果可以使用更准确的基准，或者可以改进问题的文本，请在评论中提出建议。相关：能熟练使用 Javascript 的人可以简单地向我解释一下这里发生了什么。

function randColor() {
  return '#' + (function co(lor) {
    return (lor += [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f'][Math.floor(Math.random() * 16)]) &&
      (lor.length == 6) ? lor : co(lor);
  })('');
}

console.time("random string recursion");

for (let i = 0; i < 10000; i++) {
  randColor()
}

console.timeEnd("random string recursion");

console.time("random string regexp");

for (let i = 0; i < 10000; i++) {
  "xxxxxx".replace(/x/g, function() {
    return "abcdef0123456789".charAt(Math.floor(Math.random() * 16))
  });
}

console.timeEnd("random string regexp");

什么是最有效的，其中效率被定义为“速度”和“存储”所需的最少资源量，以实现返回具有的.length字符串N？

速度和存储的效率是否会随着N增加而降低？

4

6 回答 6

6

另一种方法，假设字符介于[a-f0-9]. 它在速度和存储方面都很有效。

function randColor() {
  return '#' + (Math.floor(Math.random() * 16777216)).toString(16).padStart(6, '0');
}

console.time("random string hexa");

for (let i = 0; i < 10000; i++) {
  randColor()
}

console.timeEnd("random string hexa");

我使用 jsPerf 将其速度与问题中描述的方法进行了比较。这些是结果：https ://jsperf.com/generating-hex-string-of-n-length

铬 jsPerf 火狐浏览器 jsPerf

于 2017-10-04T03:49:10.343 回答
2

虽然处理的瓶颈通常在 ALU 中，但对于像乘法这样的原子操作，优化是由编译器在编译时完成的。乘法和递归方法之间唯一真正的区别是运行时要生成的随机数的数量。递归方法生成 6 个随机数，而乘法方法只生成一个随机数，因此这是本例中真正的瓶颈步骤。

function recc() {
  return '#' + (function co(lor) {
    return (lor += [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f'][Math.floor(Math.random() * 16)]) &&
      (lor.length == 6) ? lor : co(lor);
  })('');
}

console.time("random string recursion");

for (let i = 0; i < 100000; i++) {
  recc()
}

console.timeEnd("random string recursion");

function single_mult(len) {
  var max = 0;
  for (var i = 0; i < len; i++)
    max += 15 * Math.pow(16, i);

  return '#' + (Math.floor(Math.random() * max)).toString(16);
}

console.time("random string multiplication");

for (let i = 0; i < 100000; i++) {
  single_mult(6)
}

console.timeEnd("random string multiplication");

其他明显的延迟是对函数的调用次数。如果您能够n通过将循环放置在函数内部来避免调用函数次数，那么函数将执行得更快。

function loop_outside_function(){
  return Math.floor(Math.random() * 16777216).toString(16);
}

console.time('n function calls');
for (let i = 0; i < 100000; i++) {
  loop_outside_function();
}
console.timeEnd('n function calls');

console.time('loop inside function');
function loop_inside_function(){
  for (let i = 0; i < 100000; i++) {
    Math.floor(Math.random() * 16777216).toString(16);
  }
}
console.timeEnd('loop inside function');

原始答案

效率大致转化为计算机（在 ALU 中）花费的时钟周期数。所以这里是每个操作周期的感觉：

  • 乘法：5-6 cc
  • 添加量：2cc
  • 分区: 25 cc
  • 减法：2 cc
  • If..else：取决于 else 条件的数量。（每个 else 条件 1 cc，但通过分支预测优化）

最初提供的一个涉及六次乘法。一种更有效的方法是ncardeli 的回答，因为他将乘法减少到只有一个。您可以通过缓存长度属性使他的算法更高效。JonMark Perry 的答案与 ncardeli 的答案基本相同，但他对给定长度和基数乘以的值进行了硬编码。

function recc() {
  return '#' + (function co(lor) {
    return (lor += [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f'][Math.floor(Math.random() * 16)]) &&
      (lor.length == 6) ? lor : co(lor);
  })('');
}

console.time("random string recursion");

for (let i = 0; i < 100000; i++) {
  recc()
}

console.timeEnd("random string recursion");

function single_mult(len) {
  var max = 0;
  for (var i = 0; i < len; i++)
    max += 15 * Math.pow(16, i);

  return '#' + (Math.floor(Math.random() * max)).toString(16);
}

console.time("random string multiplication");

for (let i = 0; i < 100000; i++) {
  single_mult(6)
}

console.timeEnd("random string multiplication");

function get_length(len) {
  if (!get_length.cache) get_length.cache = {};
  if (get_length.cache[len] == null) {
    var max = 0;
    for (var i = 0; i < len; i++)
      max += 15 * Math.pow(16, i);
    get_length.cache[len] = max;
  }
  return get_length.cache[len];
}

function mult_with_cache(len) {
  let max = get_length(len)
  return '#' + (Math.floor(Math.random() * max)).toString(16);
}

console.time("random string Multiplication_cache");

for (let i = 0; i < 100000; i++) {
  mult_with_cache(6)
}

console.timeEnd("random string Multiplication_cache");

function iter() {
  for (let i = 0; i++ < 100000;) Math.floor(Math.random() * 16777216).toString(16);
}

function hard_coded(){
  return Math.floor(Math.random() * 16777216).toString(16);
}

console.time('hard coding values');
for (let i = 0; i < 100000; i++) {
  hard_coded();
}
console.timeEnd('hard coding values');

来自不同浏览器的基准：

                  Firefox     Chrome     Safari
Recursion          24.635     53.190     58.100
Mult                9.015     34.550     20.400
Mult_with_cache     8.950     32.105     19.500
HardCoded           6.340     29.610     16.500
于 2017-10-07T17:52:16.777 回答
2

我管理：

function iter() {
return '#'+('000000'+Math.floor(Math.random()*16777216).toString(16)).slice(-6);
}

console.time('go');
for (let i=0;i++<10000;) iter();
console.timeEnd('go');
console.log(clr=iter());
document.body.style.backgroundColor=clr;

我不确定这总体上如何比较，它似乎很快。我也不确定速记是否for-loop能取得任何成就。

于 2017-10-06T12:22:23.203 回答
2

我比较了 3 种不同的方法（并将原始问题中的方法添加为generate4）。该算法确实具有线性复杂度，这意味着执行时间将相对于字符数以线性方式增长。关于内存使用情况也可以这样说。

所以使用你的措辞，速度和记忆的效率确实随着N增加而降低，但是以线性方式，这是非常好的。

功能在这里：

function generate1(n) {
    var str = '#';
    for (var i = 0; i < n; i++) {
        // <<0 is faster than Math.floor
        str += (Math.random()*16<<0).toString(16);
    }
    return str;
}

function generate2(n) {
    var str = '#';
    var arr = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'];
    for (var i = 0; i < n; i++) {
        // <<0 is faster than Math.floor
        str += arr[Math.random()*16<<0];
    }
    return str;
}

function generate3(n) {
    var str = '';
    var temp = Math.ceil(n/6);
    for (var i = 0; i < temp; i++) {
        // <<0 is faster than Math.floor
        str += (Math.random()*0xFFFFFF<<0).toString(16); // 6 chars each
    }
    return '#' + str.substr(0, n);
}

function generate4(n) {
  return '#' + (function co(lor) {
    return (lor += [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f'][Math.floor(Math.random() * 16)]) &&
      (lor.length == n) ? lor : co(lor);
  })('');
}

这是创建的 JSPerf：https ://jsperf.com/generating-hex-strings

以下是结果： 铬合金

苹果浏览器

火狐

这些结果清楚地表明，选择一种方法而不是另一种方法可能会在不同的浏览器上产生不同的结果。尽管所有方法都给出了相同的算法复杂度，但我不会太担心。

于 2017-10-04T05:08:37.557 回答
1

对我来说，到目前为止，以下代码在所有三种浏览器上效果最好——

function getRandomColor(){
  return '#'+ (~~(Math.random()*(1<<24))).toString(16);
}

以下是结果快照-

在此处输入图像描述

在此处输入图像描述

在此处输入图像描述

在此处输入图像描述

请在此处找到 jsperf.com 上的测试

于 2017-10-11T00:01:36.987 回答
1

信任但验证胜利：

function color(){
 var buff = "#" + Math.random().toString(16).slice(-7,-1);
 return buff[6] ? buff : color();
}
于 2017-10-10T06:03:42.983 回答