D2009のためのより速いCompareTextの実装

Question

私はプログラムでハッシュマップデータ構造を広く使用しています。 Codegearフォーラムに投稿されたBarry Kellyのハッシュマップ実装を使用しています。その実装は内部的にRTLのCompareText関数を使用します。プロファイリングでは、SysUtils CompareText関数で多くの時間が費やされていることがわかりました。

私は

Fastcode site

を見ていたし、CompareTextのいくつかのより迅速な実装を発見しました。残念ながら、D2009とそのユニコード文字列では動作しないようです。

質問：D2009文字列をサポートする同様の高速バージョンがありますか？ CompareText関数は、ハッシュマップを使用しているとき（少なくとも私が現在使用している実装では）多く呼び出されているようですので、パフォーマンスの改善はほとんど差をつけることができません。あるいは、ここに提示されている実装もUnicode文字列のために機能するでしょうか？

Answer 1

多くのFastCode関数はおそらくコンパイルされ、Delphi 2009で正常に動作するように見えますが、すべての入力に対して正しいとは言えません。アセンブラで実装されているものは、文字がそれぞれ1バイトであると仮定されているので失敗します。 Delphiで実装されているものはもう少し良くなりますが、古いCompareTextの「大文字小文字を区別しない」という概念はASCIIに基づいているのに対し、新しいものはUnicodeに基づいているため、間違った結果を返すことがあります。文字が大文字と小文字を区別して保存されているとみなされるルールは、ASCII用のUnicodeとは異なるです。

Andreas氏は以下のコメントで、Unicode CompareTextはまだASCIIの大文字小文字の比較規則を使用しているので、いくつかのFastCode関数はうまく動作するはずです。文字サイズを前提にしていないことを確認するために、それらを使用する前に見てください。 FastCode関数が既にDelphi RTLに組み込まれていたことを思い出してください。 CompareTextがその1つであるかどうかはわかりません。

をハッシュテーブルに多く呼び出すと、ハッシュテーブルがうまくやっていないことがわかります。 CompareTextは、探しているもののハッシュがハッシュテーブル内の空でないバケットを指定したときにのみ呼び出されます。そこから、ハッシュテーブルはリニア検索を使用してバケット内の適切なアイテムを見つけることが多く、その検索中にすべてのアイテムに対してCompareTextが呼び出されます。それがあなたの作品をどのように使っているのかは分かりません。

これは、利用可能なバケットでより均等に結果を分配する別のハッシュ関数を使用して解決できます。バケットがすでに均等に埋まっている場合は、さらにバケットを必要とする可能性があります（ハッシュ関数が以上に均等に分散していることを確認してください）。も同様です。

使用しているハッシュマップクラスがTBucketListに基づいている場合は、バケットストレージに改善の余地があります。そのクラスは入力全体のハッシュを計算しません。使用するバケットは、入力のみを使用して決定します。クラスが文字列に対して計算された完全なハッシュを追跡している場合、線形検索中の比較はずっと高速になる可能性があります。単純にハッシュを比較し、ハッシュが完全に一致したときにのみ文字列を比較します。 （サポートされている最大サイズの256バケットバケットリストの場合、入力の1バイトだけがバケットを決定し、残りのバイトは無視されます）。I've written about TBucketList here before.