7

私の目標は、メモリを犠牲にして要素の検索時間IList<T>を達成するインターフェイスを実装するデータ構造を作成することです。O(1)

背景 ご存じのとおり、すべての配列ベースのIList<T>実装にList<T>は、O(n)要素のルックアップ時間があります。これは、一致するものが見つかるまで、操作が下にある配列に対して likeint IndexOf(T element)またはbool Contains(T element)iterate することを意味します。

リストとハッシュテーブルの組み合わせを基になるデータ構造として使用するという、よく知られたアイデアの実現。値はリストに保持されます。ハッシュテーブルは、インデックスを値として保持し、リストの値をキーとして保持します。したがって、ハッシュテーブルを使用してルックアップを実行できます。

これがまさにKeyedCollection<TKey, TItem> MSDNの実装方法です。

これまでに試したこと

internal class MyList<T> : KeyedCollection<T, T>
{
    protected override T GetKeyForItem(T item)
    {
        return item;
    }
}

これは、1つの問題を除いてこれまでのところうまくいきました。このデータ構造は、背後で期待される動作を正確に模倣するものではありませんList<T>。ポイントは、List<T>重複を許可し、許可MyListしないということです。

質問

IList<T>すぐに使用できるデータ構造はありますか、または次のように実装するエレガントな方法をお勧めできますか?

  1. ルックアップ操作にはO(1)時間がかかります。
  2. 他のすべての操作はO()、List<T>
  3. メモリーは、ハッシュテーブルのオーバーヘッド (constantA + constantB * nバイト) によって損なわれる可能性があります。
  4. 重複を許可する必要があります
  5. null の許可はオプションです (null オブジェクトにボックス化できます)。
4

4 に答える 4

4

これを確認できる唯一の方法は、リストの辞書を使用することです。キーを押すと、その特定のキーを作成するすべての重複のリストが表示されます。常に最初のものを取ります。

于 2012-11-29T18:22:41.973 に答える
2

提案されたことに基づいてRyan Bennett、あなたが思いつく最善の方法は（順序が重要であると述べているため）、IListを実装し、内部的に次のようなものを持つクラスを作成することだと思います：

class MyList<T> : IList<T>
{
    Dictionary<T, List<int>> _indexMap;
    List<T> _items;


    public int IndexOf(T item)
    {
        List<int> indices;
        if(_indexMap.TryGetValue(item, out indices))
        {
            return indices[0];
        }
        return -1;
    }

    public void Add(T item)
    {
        List<int> indices;
        if(!_indexMap.TryGetValue(item, out indices))
        {
            indices = new List<int>();
            _indexMap[item] = indices;
        }

        indices.Add(_items.Count);
        _items.Add(item);
    }

    // Attempt at a Remove implementation, this could probably be improved
    // but here is my first crack at it
    public bool Remove(T item)
    {
        List<int> indices;
        if(!_indexMap.TryGetValue(item, out indices))
        {
            // Not found so can just return false
            return false;
        }

        int index = indices[0];
        indices.RemoveAt(0);
        if (indices.Count == 0)
        {
            _indexMap.Remove(item);
        }

        for(int i=index+1; i < _items.Count; ++i)
        {
            List<int> otherIndexList = _indexMap[_items[i]];
            for(int j=0; j < otherIndexList.Count; ++j)
            {
                int temp = otherIndexList[j];
                if (temp > index)
                {
                    otherIndexList[j] = --temp;
                }
            }
        }

        return _items.RemoveAt(index);
    }

    // ... Other similar type functions here
}

編集：

を実行すると、ここで物事が本当に粘着性になることに気付きましたRemove。インデックスのコレクションを調べて、値 > 削除するアイテムのインデックスでインデックスを更新する必要があります。これで、「削除」時間が増加しました。あなたはまた、正しくするのを難しくしました。このようなものを実装しようとする場合、このコレクションに大量の単体テストを投げます。

私はあなたが順序が重要であると述べていることを知っているので、重複を許可して O(log n) の操作時間を与えるソートリストアプローチを使用しないのはそのためだと思います。

編集 2: もう 1 つの簿記型アプローチ
私は頭の中でこれをバウンスしているだけなので、大まかな擬似コードのみを提供しますが、アイテムの辞書をインデックスのリストにマップし、インデックスを項目にマップする 2 番目のディクショナリ。T がクラスであるという制限を追加すると、参照の 2 つのストレージのオーバーヘッドのみが発生します。次に、新しいアイテムをコレクションに簡単に追加できるように、現在の「最後」を維持する必要があります。これにより、削除操作が少しきれいになります。インデックス>削除されたアイテムで何かを更新する必要があるため、それはまだO(n)です。最初の想像では、これは達成したいものに近づける潜在的な解決策のように思えます (私が目標を正しく理解している場合)。

于 2012-11-29T18:38:19.487 に答える
1

ハッシュ テーブルは、各キーのインデックスのリストを保持する必要があります。そして、これで十分だと思いますよね？

于 2012-11-29T18:25:15.153 に答える
0

O(1) の検索時間で構造を開発できれば、非常に金持ちになるでしょう :p

基本的にこのタイプの構造は存在しません。これに最も近いのはハッシュ テーブルです。

C# にはハッシュ テーブル タイプが組み込まれています - C~ Hash Table

于 2012-11-29T18:23:43.443 に答える