12

一部のC++コードをC＃に変換していますが、std :: map :: lower_bound（k）を呼び出して、キーがk以上のエントリをマップ内で検索します。ただし、.NETのSortedDictionaryで同じことを行う方法はありません。SortedListを使用して回避策を実装できると思いますが、残念ながら、SortedListは遅すぎます（キーの挿入と削除にはO（n））。私に何ができる？

注：特定のシナリオを利用する回避策を見つけました...具体的には、キーは0を少し超える整数の密集した集団であるため、辞書としてList <TValue>を使用し、リストインデックスは次のように機能します。キー、およびk以上のキーの検索は、数回のループ反復でのみ実行できます。しかし、元の質問が答えられるのを見るのはそれでもいいでしょう。

4

8 に答える 8

2

「次の上位キーの検索」操作と「次の下位キーの検索」操作をサポートするコレクション クラスをいくつか開発しました。

最初に、コンパクトなパトリシア トライコレクションのセットを作成しました。これらは、メモリ使用量を最小限に抑えるように設計されたセット/辞書です。これらは、URL の大規模なコレクションやその他の特定の種類のデータに対して特に効率的です。byte[]、string、およびすべてのプリミティブ整数型 (Int8..UInt64) など、特定の種類のキーのみがサポートされているため、これらは問題を部分的にしか解決しません。また、文字列の並べ替えでは大文字と小文字が区別されます。NuGet パッケージ: Loyc.Utilities

この回答を公開した後、この問題を一般的に解決する、よりソートされたデータ構造を作成しました: BList<T>、BDictionary<K,V>、BMultiMap<K,V>およびSparseAList<T>. 詳細については、2 番目の回答を参照してください。

于 2010-02-26T19:50:50.127 に答える
1

問題は、ディクショナリ/ハッシュ テーブルが入力値に基づいて一意のメモリ位置に到達するように設計されているため、格納する各値に関連する範囲に対応するように設計されたデータ構造が必要になることです。時間は各間隔を正しく更新します

スキップ リスト(またはバランスの取れたバイナリ ツリー) が役立つと思います。O(n) でルックアップを実行することはできませんが、対数的に行うことができ、ツリーよりも高速です。

.NET BCL に既にそのようなクラスが含まれているとは言えないため、これが適切な答えではないことはわかっています。残念ながら、自分で実装するか、それをサポートするサードパーティのアセンブリを見つける必要があります。ただし、 The CodeProject hereには良い例があるようです。

于 2009-11-06T23:55:05.407 に答える
1

任意のデータ型にこの機能を提供するいくつかのデータ構造を作成しました: BList<T>(並べ替えられたリスト)、BDictionary<K,V>(項目がキーで並べ替えられBMultiMap<K,V>た辞書)、および (キーに複数の値を関連付けることができる辞書)。詳細については、この記事を参照してください。これらの各データ構造は、 C++ のおよびのように機能するFindLowerBound()およびメソッドを提供します。内部的には、これらのコレクションはB+ ツリーに似ているため、パフォーマンスが高く、メモリ使用量が少なくなります。通常、64 ビットのキーと 64 ビットの値を想定すると、標準よりも約 44% 少ないメモリを使用します (平均して、標準よりもわずかに少ないメモリを使用します)。FindUpperBound()lower_boundupper_boundBDictionary<,>SortedDictionary<,>Dictionary<,>

また、「スパース」コレクション を作成しました。SparseAList<T>これは、コレクション内の任意の場所に「空のスペース」を挿入および削除できることを除いて似てBDictionary<int,T>います (空のスペースはメモリを消費しません)。詳細については、この記事を参照してください。

これらのコレクションはすべてLoyc.Collections NuGet パッケージに含まれています。

于 2014-05-21T22:26:57.833 に答える
0

SortedListの複雑さに関する質問には誤りがあると思います。

SortedListには、新しい項目を挿入するための O(log(n)) の償却された複雑さがあります。事前に容量がわかれば最悪O(Log(n))で済みます。

于 2009-11-07T15:47:14.583 に答える
0

ベース フレームワークには二分探索ツリー コレクションの実装がないため、ビルドするか、実装を見つける必要があります。ご指摘のとおり、SortedList は検索の点では最も近いですが、挿入/削除では (基になる配列の実装により) 遅くなります。

于 2009-11-07T02:06:42.630 に答える
0

K に最も近いものを見つける:

dict.Keys.Where(i => i >= K).OrderBy(i => i).First();

またははるかに高速：

public int? GetNearestKey(dict, K) 
{
    int? lowerK = null;
    foreach (int key in dict.Keys)
    {
        if (key == K) 
        {
            lowerK = K;
            break; 
        }
        else if (key >= K && (!lowerK.HasValue || key < lowerK))
        {
            lowerK = key;
        }
    }
    return lowerK;
}
于 2009-11-06T22:42:03.853 に答える
0

これはSortedSet<T>、次の拡張メソッドで実行できます。

public static class SortedSetExtensions
{
    public static bool FindLowerOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
    {
        if(set.Count == 0)
        {
            first = default(T);
            return false;
        }

        var minimum = set.Min;

        if(set.Comparer.Compare(minimum, value) > 0)
        {
            first = default(T);
            return false;
        }

        first = set.GetViewBetween(minimum, value).Max;
        return true;
    }

    public static bool FindGreaterOrEqualThan<T>(this SortedSet<T> set, T value, out T first)
    {
        if (set.Count == 0)
        {
            first = default(T);
            return false;
        }

        var maximum = set.Max;

        if (set.Comparer.Compare(maximum, value) < 0)
        {
            first = default(T);
            return false;
        }

        first = set.GetViewBetween(value, maximum).Min;
        return true;
    }
}
于 2016-03-03T08:57:47.217 に答える