字符串比较与哈希
String Comparison vs. Hashing
我最近了解了 rolling hash 数据结构,基本上它的主要用途之一是搜索字符串中的子字符串。以下是我注意到的一些优点:
- 比较两个字符串的开销可能很大,因此应尽可能避免这种情况
- 散列字符串并比较散列通常比比较字符串快得多,但是每次重新散列新子字符串传统上需要线性时间
- 滚动散列能够在恒定时间内重新散列新的子字符串,使其更快、更高效地完成此任务
我继续在 JavaScript 中实现了滚动哈希,并开始分析滚动哈希、传统重新哈希和仅将子字符串相互比较之间的速度。
在我的发现中,子字符串越大,传统的重新散列方法 运行(如预期)花费的时间越长,其中滚动散列 运行 非常快(如预期)。但是,将子字符串一起比较 运行 比滚动散列快得多。怎么会这样?
为了直观起见,假设函数在约 240 万个字符串中搜索 100 个字符的子字符串的 运行ning 次如下:
- 滚动哈希 - 0.809 秒
- 传统重新散列 - 71.009 秒
- 只是比较字符串(没有散列) 0.089 秒
字符串比较怎么会比滚动哈希快这么多?它会不会特别与 JavaScript 有关?字符串是 JavaScript 中的原始类型;这会导致字符串在恒定时间内与 运行 进行比较吗?
我的主要困惑是 how/why 字符串比较在 JavaScript 中如此之快,而我的印象是它们应该相对较慢。
注:
通过 字符串比较 我指的是 stringA === stringB
注:
我在 Computer Science Community 上问过这个问题,并被告知我也应该在这里问这个问题,因为这很可能是 JavaScript 具体的。
经过一些测试和分析,我得出的结论是,有几个原因导致我的滚动哈希方法 运行ning 比简单地比较两个字符串稍微慢一些。
如果滚动哈希在恒定时间内声称运行,它怎么会比比较字符串慢?
函数相对较慢 - 调用函数比简单地executing code inline稍慢。在我的特殊情况下,一个
每次滚动哈希时都必须在我的对象上调用函数
重新哈希其内部 window,因此需要稍长的时间才能 运行
与字符串比较相比,因为该代码只是内联的。特别是因为我的基准测试有超过 200 万次迭代的滚动哈希 "shift",这个函数变慢可以更清楚地看到。
但是为什么字符串比较这么快?
字符串是原始的 - 基本上,因为 strings are a primitive type in JavaScript,尝试比较两个字符串将最
可能会调用一些直接在
口译员。这种低水平的评估可以像
体系结构可能可以(类似于比较数字)。
总结
在这种情况下,比较 JavaScript 中的字符串最终会比滚动哈希更快,因为字符串是 原始的 ,因此允许解释器使用这些元素非常快,因为简单地 调用函数会产生轻微的开销 并在很小的范围内减慢进程。
我最近了解了 rolling hash 数据结构,基本上它的主要用途之一是搜索字符串中的子字符串。以下是我注意到的一些优点:
- 比较两个字符串的开销可能很大,因此应尽可能避免这种情况
- 散列字符串并比较散列通常比比较字符串快得多,但是每次重新散列新子字符串传统上需要线性时间
- 滚动散列能够在恒定时间内重新散列新的子字符串,使其更快、更高效地完成此任务
我继续在 JavaScript 中实现了滚动哈希,并开始分析滚动哈希、传统重新哈希和仅将子字符串相互比较之间的速度。
在我的发现中,子字符串越大,传统的重新散列方法 运行(如预期)花费的时间越长,其中滚动散列 运行 非常快(如预期)。但是,将子字符串一起比较 运行 比滚动散列快得多。怎么会这样?
为了直观起见,假设函数在约 240 万个字符串中搜索 100 个字符的子字符串的 运行ning 次如下:
- 滚动哈希 - 0.809 秒
- 传统重新散列 - 71.009 秒
- 只是比较字符串(没有散列) 0.089 秒
字符串比较怎么会比滚动哈希快这么多?它会不会特别与 JavaScript 有关?字符串是 JavaScript 中的原始类型;这会导致字符串在恒定时间内与 运行 进行比较吗?
我的主要困惑是 how/why 字符串比较在 JavaScript 中如此之快,而我的印象是它们应该相对较慢。
注:
通过 字符串比较 我指的是 stringA === stringB
注: 我在 Computer Science Community 上问过这个问题,并被告知我也应该在这里问这个问题,因为这很可能是 JavaScript 具体的。
经过一些测试和分析,我得出的结论是,有几个原因导致我的滚动哈希方法 运行ning 比简单地比较两个字符串稍微慢一些。
如果滚动哈希在恒定时间内声称运行,它怎么会比比较字符串慢?
函数相对较慢 - 调用函数比简单地executing code inline稍慢。在我的特殊情况下,一个 每次滚动哈希时都必须在我的对象上调用函数 重新哈希其内部 window,因此需要稍长的时间才能 运行 与字符串比较相比,因为该代码只是内联的。特别是因为我的基准测试有超过 200 万次迭代的滚动哈希 "shift",这个函数变慢可以更清楚地看到。
但是为什么字符串比较这么快?
字符串是原始的 - 基本上,因为 strings are a primitive type in JavaScript,尝试比较两个字符串将最 可能会调用一些直接在 口译员。这种低水平的评估可以像 体系结构可能可以(类似于比较数字)。
总结
在这种情况下,比较 JavaScript 中的字符串最终会比滚动哈希更快,因为字符串是 原始的 ,因此允许解释器使用这些元素非常快,因为简单地 调用函数会产生轻微的开销 并在很小的范围内减慢进程。