我最近了解了滚动哈希数据结构,基本上是它在字符串中搜索子字符串的主要用途之一。我注意到了一些优点:
我继续并在JavaScript中实现了滚动哈希,并开始分析滚动哈希,传统重新哈希以及仅比较子字符串之间的速度。
在我的发现中,子字符串越大,运行传统的重新哈希处理方法(如预期的那样)所花费的时间就越长,在这种情况下,滚动哈希的运行速度非常快(如预期的那样)。但是,将子字符串进行比较比滚动哈希要快得多。怎么会这样
为了便于理解,我们假设以下功能的运行时间如下:在〜240万个字符串中搜索100个字符的子字符串:
字符串比较如何比滚动哈希更快?它可能与JavaScript特别有关吗?字符串是JavaScript中的原始类型;这会导致字符串比较在恒定时间内运行吗?
我的主要困惑是关于如何/为什么在JavaScript中字符串比较如此之快,当时我被认为应该比较慢。
注意:通过字符串比较,我指的是类似stringA === stringB
注意:我在计算机科学社区问了这个问题,并被告知我也应该在这里提出问题,因为这很可能是JavaScript特有的。
经过一些测试和分析,我得出的结论是,为什么我的滚动哈希方法比简单地比较两个字符串要慢一些原因。
如果滚动散列声称是在恒定时间内运行的,那么它比比较字符串还慢吗?
函数相对较慢-调用函数比简单地内联执行代码要慢一些。在我的特殊情况下,每次滚动哈希重新刷新其内部窗口时,都必须在我的对象上调用一个函数,因此与字符串比较相比,运行时间稍长一些,因为该代码只是内联的。尤其是由于我的基准测试具有超过200万次迭代的滚动哈希值“移位”,因此可以更清楚地看到此功能的降低。
但是为什么字符串比较这么快?
字符串是原始的-基本上,因为字符串是JavaScript中的原始类型,所以尝试比较两个字符串很可能会调用某些直接在解释器中编码的例程。可以尽可能快地完成体系结构的此低级评估(类似于比较数字)。
综上所述
在这种情况下,在JavaScript中比较字符串将比滚动哈希更快,因为字符串是原始字符串,因此允许解释器非常快速地使用这些元素,并且因为简单地调用函数会产生少量开销并减慢处理速度。规模很小。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句