文字列比較の時間の複雑さ

Question

どの比較に時間がかかりますか？

a=one, b=two
if a != b: doThis()

対

a = helloworldhelloworldhelloworld
b = https://www.somerandomurls.com/directory/anotherdirectory/helloworld.html
if a != b: doThis()

私は、多くの場合、数千行を持って私のデータベースに対してこれをチェックする必要があります。私は特定のプログラミング言語を探しているわけではありません。私はちょうどどの比較がより速くかかるか知りたい。ご覧のとおり、bの値は最初の例では長い文字列で、2番目の例では短い文字列です。だから、それが比較で何か変わるかもしれないのだろうか。

Answer 1

通常、文字列の比較は文字のリニアスキャンを行い、文字が一致しない最初のインデックスでfalseを返します。

時間の複雑さはO（N）であり、実際の所要時間は、統計的に差が出現するまでにスキャンする必要のある文字の数によって異なります。すべての文字列がhttp：//で始まる場合、最初の7文字をスキャンするための一定のオーバーヘッドが発生します（比較アルゴリズムを特殊なデータに合わせないでください）。

長い文字列がある場合は、多くの文字列の先頭が同じ開始文字となり、文字列のハッシュを比較して文字列の線形比較ハッシュが一致する場合（ハッシュの衝突の可能性を除外するために）想定されている長い文字列よりも短いハッシュを使用して初期比較を行う場合、クエリ戦略を慎重に設計することで、システムのIOとRAMの要件を減らすことができます。