3

いくつかの方法で解決できる興味深い問題があります。

  • 文字列を受け取る関数があります。
  • この関数がこの文字列を以前に見たことがない場合は、何らかの処理を実行する必要があります。
  • 関数が以前に文字列を見たことがある場合は、処理をスキップする必要があります。
  • 指定された時間が経過すると、関数は重複した文字列を受け入れる必要があります。
  • この関数は 1 秒間に何千回も呼び出される可能性があり、文字列データは非常に大きくなる可能性があります。

これは、実際のアプリケーションの高度に抽象化された説明であり、質問の目的のために核となる概念に取り掛かろうとしています。

関数は、重複を検出するために状態を保存する必要があります。また、重複を期限切れにするために、関連付けられたタイムスタンプを保存する必要があります。

文字列を保存する必要はありません。文字列の一意のハッシュは、衝突による誤検出がなく (完全なハッシュを使用しますか?)、ハッシュ関数のパフォーマンスが十分であれば問題ありません。

単純な実装は次のようになります (C# の場合):

 Dictionary<String,DateTime>

ただし、メモリ フットプリントを削減し、潜在的にパフォーマンスを向上させるために、基本的なハッシュ テーブルの代わりに、これを処理するカスタム データ構造を評価しています。

では、これらの制約が与えられた場合、何を使用しますか?

編集、提案された実装を変更する可能性のあるいくつかの追加情報:

  • 文字列の 99% は重複しません。
  • ほとんどすべての複製が連続して、またはほぼ順番に到着します。
  • 実際には、関数は複数のワーカー スレッドから呼び出されるため、状態管理を同期する必要があります。
4

4 に答える 4

5

最初に値の完全なセットを知らなくても「完全なハッシュ」を構築できるとは思いません（特に、値の数が限られているC＃intの場合）。したがって、どのような種類のハッシュでも、元の値を比較する機能が必要です。

辞書は、すぐに使用できるデータ構造で取得できる最高のものだと思います。カスタム比較が定義されたオブジェクトを保存できるため、文字列をメモリに保持することを簡単に回避し、文字列全体を取得できる場所を保存するだけで済みます。つまり、次の値を持つオブジェクト：

stringLocation.fileName="file13.txt";
stringLocation.fromOffset=100;
stringLocation.toOffset=345;
expiration= "2012-09-09T1100";
hashCode = 123456;

cutomom comparerは、保存されたhashCodeを返すか、必要に応じてファイルから文字列を取得して比較を実行します。

于 2012-04-14T05:03:23.043 に答える
2

衝突による誤検知がなければ、文字列の一意のハッシュで問題ありません。

ハッシュコードを文字列よりも短くしたい場合は、それは不可能です。

ハッシュコードを使用することは、誤検知があることを意味しますが、パフォーマンスの問題にならないほどまれであるということだけを意味します。

文字列の一部だけからハッシュコードを作成して、高速化することも検討します。それが誤検知が増えることを意味する場合でも、全体的なパフォーマンスが向上する可能性があります。

于 2012-04-14T05:04:28.830 に答える
2

メモリ フットプリントが許容範囲内であればHashset<string>、文字列用の と を格納するためのキューをお勧めしますTuple<DateTime, String>。何かのようなもの：

Hashset<string> Strings = new HashSet<string>();
Queue<Tuple<DateTime, String>> Expirations = new Queue<Tuple<DateTime, String>>();

さて、文字列が入ってくると：

if (Strings.Add(s))
{
    // string is new. process it.
    // and add it to the expiration queue
    Expirations.Enqueue(new Tuple<DateTime, String>(DateTime.Now + ExpireTime, s));
}

そして、どこかで有効期限を確認する必要があります。おそらく、新しい文字列を取得するたびに、次のようにします。

while (Expirations.Count > 0 && Expirations.Peek().Item1 < DateTime.Now)
{
    var e = Expirations.Dequeue();
    Strings.Remove(e.Item2);
}

ここのパフォーマンスを打ち負かすのは難しいでしょうHashset。確かに、文字列を保存していますが、これが誤検出を防ぐ唯一の方法です。

以外のタイム スタンプの使用を検討することもできDateTime.Nowます。私が通常行うことはStopwatch、プログラムの開始時に a を開始し、そのElapsedMilliseconds値を使用することです。これにより、夏時間の変更中、システムが (NTP を使用して) クロックを自動的に更新するとき、またはユーザーが日付/時刻を変更するときに発生する潜在的な問題を回避できます。

上記のソリューションが機能するかどうかは、文字列を格納する際のメモリ ヒットに耐えられるかどうかによって異なります。

「追加情報」掲載後に追記：

これが複数のスレッドからアクセスされる場合は、ではConcurrentDictionaryなくHashset、 とを使用することをお勧めします。または、非並行データ構造へのアクセスを同期するために使用できます。BlockingCollectionQueuelock

文字列の 99% が重複しないことが事実である場合、ディクショナリからものを削除できる有効期限キューがほぼ確実に必要になります。

于 2012-04-14T05:13:49.927 に答える
1

文字列全体を格納するためのメモリ フットプリントが許容できない場合は、次の 2 つの選択肢しかありません。

1) 文字列のハッシュのみを保存します。これは、ハッシュの衝突の可能性を意味します (ハッシュが文字列より短い場合)。優れたハッシュ関数 (MD5、SHA1 など) を使用すると、この衝突が発生することはほとんどありません。そのため、目的に対して十分に高速であるかどうかに依存します。

2) ある種の可逆圧縮を使用します。通常、文字列の圧縮率は良好 (約 10%) で、ZIP などの一部のアルゴリズムでは、高速 (かつ効率が低い) 圧縮と低速 (圧縮率が高い) 圧縮のどちらかを選択できます。文字列を圧縮するもう 1 つの方法は、文字列を UTF8 に変換することです。これは、高速で簡単に実行でき、非 Unicode 文字列の圧縮率が 50% 近くになります。

どの方法を選択しても、メモリ フットプリントとハッシュ/圧縮速度は常にトレードオフの関係にあります。最適なソリューションを選択するには、おそらくベンチマークを行う必要があります。

于 2012-04-14T05:44:37.713 に答える