如何计算String数据集的fibonacci序列？

Question

我想为字符串数据集计算Fibonacci序列。我正在编写一个普通的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

Memoization

如果计算一次，你可以在表格中简单地查找斐波那契的n数量，而不是每次计算。这称为Memoization。您可以在Addy Osmani的Faster JavaScript Memoization中阅读更多相关信息。

Your Code

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

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

Example

我递归地写了它，因为我认为代码更容易阅读。我传入没有空格的字符串（createSecretString(messageWithoutWhitespace, memory, secret)并在每个递归中保存secret中的一个字母。在最后一次递归中，我返回连接到字符串的数组，大写所有字母一次。（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))

"Benchmark"

with memoization

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.");

without memoization

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.");