更好或更快：String.Contains 对比 List.Contains

Question

我知道这是一个愚蠢的问题，但我觉得有人可能想知道（或通知同事）这个。我没有附加特定的编程语言，因为我认为它可以适用于所有这些。如果我对此有误，请纠正我。

主要问题：在常量String或List<String>中查找条目更快and/or更好吗？

详细信息：假设我想查看给定扩展名是否在支持的扩展名列表中。以下哪项是最好的（关于编程风格）and/or 最快：

const String SUPPORTED = ".exe.bin.sh.png.bmp" /*etc*/;

public static bool IsSupported(String ext){
    ext = Normalize(ext);//put the extension in some expected state like lowercase
    //String.Contains
    return SUPPORTED.Contains(ext);
}

final static List<String> SUPPORTED = MakeAnImmutableList(".exe", ".bin", ".sh",
      ".png",".bmp" /*etc*/);
public static bool IsSupported(String ext){
    ext = Normalize(ext);//put the extension in some expected state like lowercase
    //List.Contains
    return SUPPORTED.Contains(ext);
}

Answer 1

好吧，它可能因实施而异，但如果想以一般化的方式看待这个问题，让我们看看。

如果你想在一个字符串中寻找一个特定的子字符串，比如说一个包含不同扩展名的不可变字符串中的文件扩展名，你只需要遍历一次带有扩展名的字符串。

另一方面，对于不可变字符串列表，仍然需要遍历该列表中的每个字符串加上遍历该列表的开销。

作为结论，以一般化的方式，您可以看到使用列表存储字符串需要更多处理。

但是，您可以通过其可读性、可维护性等来查看这两种解决方案。例如，如果您想要添加或删除新的扩展或应用更复杂的操作，使用字符串列表可能值得开销。

Answer 2

首先，请务必注意这些解决方案在功能上并不等同。对于 x 和 exe.bin 这样的字符串，子字符串搜索将 return true 而 List<String>.contains() 则不会。从这个意义上说，List<String> 版本可能更接近您想要的语义。任何可能的性能比较都应牢记这一点。

现在，开始表现。

理论上的

从渐近和算法复杂性的角度来看，随着字符串长度的增长，List<String>.contains() 方法将比其他方法更快。从概念上讲，String.contains 版本需要在 SUPPORTED 字符串中的每个位置寻找匹配项，而 List.contains() 版本只需要匹配开始在每个子字符串的开头 - 一旦发现当前候选字符串不匹配，它就会跳到下一个。这与上面提到的选项在功能上并不等同有关：String.contains 选项在理论上可以匹配更广泛的输入范围，因此在拒绝候选人之前它必须做更多的工作。

复杂性方面，这种差异可能类似于 List.contains() 的 O(N) 与 String.contains() 的 O(N^2) 如果您将 N 视为 候选人的数量 并假设每个候选人都有一个有限的长度，并在通常的暴力 "look for a match starting at each position" 算法中使用 String.contains() 方法。事实证明，Java String.contains() 实现并没有完全执行基本的 O(N^2) 搜索，但它也没有执行 Boyer-Moore。一般来说，您可以预期一旦子字符串足够长，List.String 方法会更快。

接近(r) 金属

从更接近金属的角度来看，这两种方法各有优势。 String.contains() 解决方案避免了遍历 List 元素的开销：整个调用将花费在内化的 String.contains 实现中，所有 char 构成整个SUPPORTED 字符串是连续的，所以这是内存友好的。 List.contains() 方法将花费大量时间进行从每个 List 元素到包含的 String 然后到包含的 char[] 数组所需的双重解引用，并且如果您比较的字符串非常短，这可能会占主导地位。

另一方面，List.contains 解决方案最终调用了 String.equals，这很可能是根据 Arrays.equal(char[], char[]) 实现的，它在 x86 平台上使用 SSE 和 AVX 内在函数进行了高度优化，并且很可能速度非常快，甚至与 String.contains() 的优化版本相比也是如此。因此，如果字符串变长，再次期待 List.contains() 领先。

综上所述，有一种简单、规范的方法可以快速完成此操作：HashSet<String> 包含所有候选字符串。这只是一个简单的 String.hash()（被缓存并且经常 "free"）和散列 table.
中的一次查找

更好或更快：String.Contains 对比 List.Contains

Better or Faster: String.Contains vs List.Contains

performance

conventions

理论上的

接近(r) 金属