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

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数，如果你计算一次，你可以在表格中简单地查找它。这称为记忆。您可以在Addy Osmani的Faster JavaScript Memoization中阅读更多相关信息。

您的代码

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

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

例

我递归地编写它，因为我认为代码更容易阅读。我传入没有空格的字符串(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))

"基准">

有记忆

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