JavaScript switch 语句是线性的还是常数时间的？

Question

我的网站上有以下 JavaScript，因此当执行某些特定搜索时，答案会硬编码到特定页面：

function redirect() {
    var input = document.getElementById('searchBox').value.toLowerCase();

    switch (input) {
      case 'rectangular':
        window.location.replace('http://www.Example.com/Rectangular/');
        break;
      case 'elephant':
        window.location.replace('http://www.Example.com/Elephants/');
        break;
      case 'coils':
        window.location.replace('http://www.Example.com/Parts/');
        break;
      default: // No keyword detected: submit the normal search form.
        return true;
        break;
    }
    return false; // Don't let the form submit
}

我想知道 JavaScript 中的搜索语句是否与 case 语句的数量或常数时间成线性关系？如果是线性的，有没有更好的方法来编写这段代码，无论我编写的特殊情况有多少，它都是恒定时间？

Answer 1

规范不对 switch 语句做出任何时间复杂度保证。然而，它的语义需要对 case 表达式进行顺序评估，因此在一般情况下它的行为是线性的。

如果所有情况都是常量字符串或数字（并且相当简单），引擎可以自由优化评估，因此您可以期望恒定的时间复杂度。

如果你想强制执行优于线性的行为，你需要使用 Map 作为查找 table:

var redirects = new Map([
    ['rectangular', 'http://www.Example.com/Rectangular/'],
    ['elephant', 'http://www.Example.com/Elephants/'],
    ['coils', 'http://www.Example.com/Parts/']
]);
function redirect() {
    var input = document.getElementById('searchBox').value.toLowerCase();
    if (redirects.has(input)) {
        window.location.replace(redirects.get(input));
        return false; // Don't let the form submit
    } else {
        return true;
    }
}

在 ES6 之前的环境中，您也可以将对象用于相同的目的。所有引擎都实现了 O(1) 属性查找，尽管它们不是正式要求的。

Answer 2

这是 Bergi 在 ES5 中的等效答案。与您现在使用的相比，它会更快并且更容易修改。

var _redirectlist = {
  'rectangular': 'http://www.Example.com/Rectangular/',
  'elephant': 'http://www.Example.com/Elephants/',
  'coils': 'http://www.Example.com/Parts/'
};

function redirect() {
  var input = document.getElementById('searchBox').value.toLowerCase();

  // Redirect if we have the input in our list
  if (_redirectlist.hasOwnProperty(input)) {
    window.location.replace(_redirectlist[input]);
    return false;
  }

  return true;
}

JavaScript switch 语句是线性的还是常数时间的？

Is JavaScript switch statement linear or constant time?

javascript

switch-statement

time-complexity

constant-time