如何计算字符串数据集的斐波那契数列？

Question

我想计算字符串数据集的斐波那契数列。我正在编写一个普通的 JavaScript 函数，但我想使用最新的 ECMAScript 功能编写代码。

var message = "The Da Vinci Code is a 2003 mystery-detective novel by Dan Brown";

function FibonacciSecret(message) {
  var s = '';
  for (var i = 0; i < 10; i++) {
    s += message.replace(/\s+/g, '').substr(getNthValue(i), 1).toUpperCase();
    if (i != 9) {
      s += "-";
    }
  }

  function getNthValue(n) {
    if (n <= 1) {
      return n;
    }
    if (n > 1) {
      return getNthValue(n - 1) + getNthValue(n - 2);
    }
  }
  return s;
}

console.log(FibonacciSecret(message)); // "T-H-H-E-D-V-C-E-M-T"

Answer 1

记忆

不必每次都计算 斐波那契 的 n 个数，如果您计算过一次，您可以在 table 中简单地查找它。这称为 Memoization。您可以在 Addy Osmani 的 Faster JavaScript Memoization 中阅读更多相关信息。

你的代码

每次调用 FibonacciSecret 时都会定义函数 getNthValue。如果你在外面定义它可能会有更好的性能，但我没有测试它。但是测试你的代码肯定会更好。

此外，在每次迭代中，您删除空格 message.replace(/\s+/g, '') 并调用 toUpperCase，但调用一次就足够了。

例子

我递归写的，因为我觉得代码更容易阅读。我传入不带空格的字符串 (createSecretString(messageWithoutWhitespace, memory, secret)，并在每次递归时在 secret 中保存一个字母。在最后一次递归中，我 return 将数组连接到一个字符串，并将所有字母大写一次。（ secret.join('-').toUpperCase())

const message = "The Da Vinci Code is a 2003 mystery-detective novel by Dan Brown";
const fibonacciMemory = {}

function fibonacci(x, memory = {}) {
  if (memory[x]) {
    return memory[x]
  }
  if (x < 1) {
    return 0
  }
  if (x <= 2) {
    return 1
  }
  return memory[x] = fibonacci(x - 1, memory) + fibonacci(x - 2, memory);
}

function createSecretString(message, memory, secret) {
  const length = secret.length - 1
  return length < 10 
    ? createSecretString(message, memory, secret.concat(message.substr(fibonacci(length, memory), 1))) 
    : secret.join('-').toUpperCase()
}

function fibonacciSecret(message, memory, secret = []) {
  const messageWithoutWhitespace = message.replace(/\s+/g, '')
  return createSecretString(messageWithoutWhitespace, memory, secret)
}

console.log(fibonacciSecret(message, fibonacciMemory))

“基准”

带记忆

const message = "The Da Vinci Code is a 2003 mystery-detective novel by Dan Brown";
const fibonacciMemory = {}

function fibonacci(x, memory = {}) {
  if (memory[x]) {
    return memory[x]
  }
  if (x < 1) {
    return 0
  }
  if (x <= 2) {
    return 1
  }
  return memory[x] = fibonacci(x - 1, memory) + fibonacci(x - 2, memory);
}

function createSecretString(message, memory, secret) {
  const length = secret.length - 1
  return length < 10 
    ? createSecretString(message, memory, secret.concat(message.substr(fibonacci(length, memory), 1))) 
    : secret.join('-').toUpperCase()
}

function fibonacciSecret(message, memory, secret = []) {
  const messageWithoutWhitespace = message.replace(/\s+/g, '')
  return createSecretString(messageWithoutWhitespace, memory, secret)
}

const t0 = performance.now();
fibonacciSecret(message, fibonacciMemory);
const t1 = performance.now();
console.log("First call took " + (t1 - t0) + " milliseconds.");

var t2 = performance.now();
fibonacciSecret(message, fibonacciMemory);
var t3 = performance.now();
console.log("Second call took " + (t3 - t2) + " milliseconds.");

没有记忆

var message = "The Da Vinci Code is a 2003 mystery-detective novel by Dan Brown";

function FibonacciSecret(message){
  var s = '';
   for(var i = 0; i < 10; i++) {
   s += message.replace(/\s+/g,'').substr(getNthValue(i), 1).toUpperCase();
   if(i != 9) {
       s += "-";
      }
   }

   function getNthValue(n) {
   if(n <= 1) {
       return n;
      }
   if(n > 1) {
       return getNthValue(n-1) + getNthValue(n-2);
      }
   }
   return s;
}

var t0 = performance.now();
FibonacciSecret(message);
var t1 = performance.now();
console.log("Call took " + (t1 - t0) + " milliseconds.");

如何计算字符串数据集的斐波那契数列？

How to calculate fibonacci-sequence for String data set?

javascript

algorithm

memoization

fibonacci

ecmascript-6

记忆

你的代码

例子

“基准”