c# - マルチキーデータ構造

Question

複数のキーで検索できるデータ構造を探しています。例を使用して説明する方が簡単です。

var myDataStructure = new MultiKeyDataStructure<int, string, MyType>();
myDataStructure.Add(1, "some string 1", new MyType());
myDataStructure.Add(2, "some string 2", new MyType());

var myType = new MyType();
myDataStructure.Add(3, "some string 3", myType);

Tuple<string, MyType> t1 = myDataStructure[1];
Tuple<int, MyType> t2 = myDataStructure["some string 1"];
Tuple<int, string> t3 = myDataStructure[myType];

このようなことは可能ですか？もしそうなら、それを行うためにすでに存在するものはありますか？すべてをキーのように扱い、関連するすべてのキーを検索して返すものをどのように実装しますか？

理想的には、任意の数および/またはタイプのパラメーターを使用することも許可されます。

var myDataStructure = new MultiKeyDataStructure<int, string, Foo, Bar>();

Answer 1

したがって、これは正確に3つのキーで機能するものです。リストされたパターンに従って、4、5、6などのキー用に1つ作成できます。それは多くのコードになりますが、特に難しい作業ではありません（退屈なだけです）。

キーの各部分に辞書があるため、かなりのメモリを消費することに注意してください。これは、任意のキーからの非常に事実に基づくアクセスの柔軟性に対して支払う代償です。

public class MultiKeyDictionary<T1, T2, T3>
{
    private Dictionary<T1, Tuple<T1, T2, T3>> firstLookup = new Dictionary<T1, Tuple<T1, T2, T3>>();
    private Dictionary<T2, Tuple<T1, T2, T3>> secondLookup = new Dictionary<T2, Tuple<T1, T2, T3>>();
    private Dictionary<T3, Tuple<T1, T2, T3>> thirdLookup = new Dictionary<T3, Tuple<T1, T2, T3>>();

    public void Add(Tuple<T1, T2, T3> values)
    {
        if (!firstLookup.ContainsKey(values.Item1) &&
            !secondLookup.ContainsKey(values.Item2) &&
            !thirdLookup.ContainsKey(values.Item3))
        {
            firstLookup.Add(values.Item1, values);
            secondLookup.Add(values.Item2, values);
            thirdLookup.Add(values.Item3, values);
        }
        else
        {
            //throw an exeption or something.
        }
    }

    public Tuple<T1, T2, T3> GetFirst(T1 key)
    {
        return firstLookup[key];
    }

    public Tuple<T1, T2, T3> GetSecond(T2 key)
    {
        return secondLookup[key];
    }

    public Tuple<T1, T2, T3> GetThird(T3 key)
    {
        return thirdLookup[key];
    }

    public void RemoveFirst(T1 key)
    {
        var values = GetFirst(key);

        firstLookup.Remove(values.Item1);
        secondLookup.Remove(values.Item2);
        thirdLookup.Remove(values.Item3);
    }

    public void RemoveSecond(T2 key)
    {
        var values = GetSecond(key);

        firstLookup.Remove(values.Item1);
        secondLookup.Remove(values.Item2);
        thirdLookup.Remove(values.Item3);
    }

    public void RemoveThird(T3 key)
    {
        var values = GetThird(key);

        firstLookup.Remove(values.Item1);
        secondLookup.Remove(values.Item2);
        thirdLookup.Remove(values.Item3);
    }
}

以下は、まったく異なるアプローチです。各キーのルックアップを設定する代わりに、すべての値を1つのコレクションに格納し、線形検索を実行して特定のキーのアイテムを検索します。O（n）の検索/削除時間はありますが、O（1）の追加です。以前の実装では、O（1）の追加、削除、および検索が行われますが、それを行うにはより多くのメモリが必要になります。

public class MultiKeyDictionary2<T1, T2, T3>
{
    private HashSet<Tuple<T1, T2, T3>> lookup = new HashSet<Tuple<T1, T2, T3>>();
    private HashSet<T1> firstKeys = new HashSet<T1>();
    private HashSet<T2> secondKeys = new HashSet<T2>();
    private HashSet<T3> thirdKeys = new HashSet<T3>();

    public void Add(Tuple<T1, T2, T3> values)
    {
        if (lookup.Any(multiKey => object.Equals(multiKey.Item1, values.Item1) ||
            object.Equals(multiKey.Item2, values.Item2) ||
            object.Equals(multiKey.Item3, values.Item3)))
        {
            //throw an exception or something
        }
        else
        {
            lookup.Add(values);
        }
    }

    public Tuple<T1, T2, T3> GetFirst(T1 key)
    {
        return lookup.FirstOrDefault(values => object.Equals(values.Item1, key));
    }

    public Tuple<T1, T2, T3> GetSecond(T2 key)
    {
        return lookup.FirstOrDefault(values => object.Equals(values.Item2, key));
    }

    public Tuple<T1, T2, T3> GetThird(T3 key)
    {
        return lookup.FirstOrDefault(values => object.Equals(values.Item3, key));
    }

    public void RemoveFirst(T1 key)
    {
        var values = GetFirst(key);
        if (values != null)
            lookup.Remove(values);
    }

    public void RemoveSecond(T2 key)
    {
        var values = GetSecond(key);
        if (values != null)
            lookup.Remove(values);
    }

    public void RemoveThird(T3 key)
    {
        var values = GetThird(key);
        if (values != null)
            lookup.Remove(values);
    }
}

Answer 2

コンパイル時の型の安全性が必要だと言ったので、あきらめなければならないことがいくつかあります。

1. 任意の数のパラメーターを持つ機能（C＃には可変個引数のジェネリックはありません）
2. 同じタイプの複数のキーを持つ機能（コンパイラーはあいまいなオーバーロードについて文句を言います）

これらの2つの制限は、リフレクションベースのアプローチを使用することで解決できますが、コンパイル時の型の安全性が失われます。

したがって、これは制約に応じて使用するソリューションです（すべての汎用タイプが異なる場合にのみ機能します！）

class TripleKeyDictionnary<TKey1, TKey2, TKey3>
{
    public Tuple<TKey2, TKey3> this[TKey1 key]
    {
        get
        {
            return _key1Lookup[key];
        }
    }

    public Tuple<TKey1, TKey3> this[TKey2 key]
    {
        get
        {
            return _key2Lookup[key];
        }
    }

    public Tuple<TKey1, TKey2> this[TKey3 key]
    {
        get
        {
            return _key3Lookup[key];
        }
    }

    private Dictionary<TKey1, Tuple<TKey2, TKey3>> _key1Lookup = new Dictionary<TKey1, Tuple<TKey2, TKey3>>();
    private Dictionary<TKey2, Tuple<TKey1, TKey3>> _key2Lookup = new Dictionary<TKey2, Tuple<TKey1, TKey3>>();
    private Dictionary<TKey3, Tuple<TKey1, TKey2>> _key3Lookup = new Dictionary<TKey3, Tuple<TKey1, TKey2>>();

    public void Add(TKey1 key1, TKey2 key2, TKey3 key3)
    {
        _key1Lookup.Add(key1, Tuple.Create(key2, key3));
        _key2Lookup.Add(key2, Tuple.Create(key1, key3));
        _key3Lookup.Add(key3, Tuple.Create(key1, key2));
    }
}

Answer 3

まず、残念ながら何も組み込まれていないので、手作業で何かを実装する必要があります。

ここでの問題は、ジェネリック型定義の数が指定されていないクラスを作成できないことです。つまり、次のようなものは存在しません。

class MultiKeyDictionary<T1, ...>
{}

したがって、いくつかのケース（2キー、3キーなど、実装と同様のアプローチを使用Tuple<>）を実装することを決定するか、型安全性を放棄する必要があります。

最初のアプローチを決定した場合は、次のようなことを行う必要があります（3つのキーを使用した例）。

class ThreeKeysDict<T1,T2,T3>
{
   var dict1 = new Dictionary<T1,Tuple<T2,T3>>();
   var dict2 = new Dictionary<T2,Tuple<T1,T3>>();
   var dict3 = new Dictionary<T3,Tuple<T1,T2>>();
   public void Add(T1 key1,T2 key2, T3 key3)
   {
      dict1.Add(key1,Tuple.Create(key2,key3));
      dict2.Add(key2,Tuple.Create(key1,key3));
      dict3.Add(key3,Tuple.Create(key1,key2));
   }
   public Tuple<T2,T3> GetByKey1(T1 key1)
   {
      return dict1[key1];
   }
   public Tuple<T1,T3> GetByKey2(T2 key2)
   {
      return dict2[key2];
   }
   public Tuple<T1,T2> GetByKey3(T3 key3)
   {
      return dict3[key3];
   }
}

非汎用バージョンは次のようになります。

class MultiKeyDict
{
    Dictionary<object, object[]>[] indexesByKey;
    public MultiKeyDict(int nKeys)
    {
        indexesByKey = new Dictionary<object, object[]>[nKeys];
    }
    public void Add(params object[] values)
    {
        if (values.Length != indexesByKey.Length)
            throw new ArgumentException("Wrong number of arguments given");
        var objects = values.ToArray();
        for (int i = 0; i < indexesByKey.Length; i++)
            this.indexesByKey[i].Add(values[i], objects);
    }
    public object[] Get(int keyNum, object key)
    {
        return this.indexesByKey[keyNum][key];
    }
}

これらの2つのアプローチは、異なるキーの数が増えると（キーごとに1つの辞書を採用するため）、両方とも大量のメモリを使用します。

---

免責事項：

コードの断片はテストされておらず、null /範囲外チェックなどがありません。
これらは、全体的なアイデアを提供するためのものです。

Answer 4

このような状況に遭遇したときは、新しいデータ構造を考え出すのではなく、2つの辞書を使用するだけです。各ディクショナリには、値にマップされた可能なキーの1つがあります。

本当に抽象化したい場合は、必要なさまざまなタイプのキーの数に応じて、常に2つ以上の辞書を内部的に使用するクラスを作成できます。

Answer 5

どうですか

class MultiKeyLookup<A, B, C> : IEnumerable<Tuple<A, B, C>>
{
    private readonly ILookup<A, Tuple<B, C>> a;
    private readonly ILookup<B, Tuple<A, C>> b;
    private readonly ILookup<C, Tuple<A, B>> c;
    private readonly IEnumerable<Tuple<A, B, C>> order;

    public MultiKeyLookup(IEnumerable<Tuple<A, B, C>> source)
    {
        this.order = source.ToList();
        this.a = this.order.ToLookup(
            o => o.Item1, 
            o => new Tuple<B, C>(o.Item2, o.Item3));
        this.b = this.order.ToLookup(
            o => o.Item2, 
            o => new Tuple<A, C>(o.Item1, o.Item3));
        this.c = this.order.ToLookup(
            o => o.Item3, 
            o => new Tuple<A, B>(o.Item1, o.Item2));
    }

    public ILookup<A, Tuple<B, C>> Item1
    {
        get
        {
            return this.a
        }
    }

    public ILookup<B, Tuple<A, C>> Item2
    {
        get
        {
            return this.b
        }
    }

    public ILookup<C, Tuple<A, B>> Item3
    {
        get
        {
            return this.c
        }
    }

    public IEnumerator<Tuple<A, B, C>> GetEnumerator()
    {
        this.order.GetEnumerator();
    }

    public IEnumerator IEnumerable.GetEnumerator()
    {
        this.order.GetEnumerator();
    }
}

どちらを使用しますか、

var multiKeyLookup = new MultiKeyLookup(
    new[] {
        Tuple.Create(1, "some string 1", new MyType()),
        Tuple.Create(2, "some string 2", new MyType())}); 

var intMatches = multiKeyLookup.Item1[1];
var stringMatches = multiKeyLookup.Item2["some string 1"];
var typeMatches = multiKeyLookup.Item3[myType];

Answer 6

あなたが得ることができる最も近いものはおそらくHashSet<Tuple<int, string, MyType>>です。HashSetsは自動的に重複をチェックし、そのTuple値が同等かどうかをチェックします。

class MultiKey<T1, T2, T3> : HashSet<Tuple<T1, T2, T3>>
{
    public bool Add(T1 t1, T2 t2, T3 t3)
    {
        return this.Add(Tuple.Create(t1, t2, t3));
    }
    public T1 Get(T2 t2, T3 t3)
    {
        var match = this.SingleOrDefault(x => x.Item2.Equals(t2) && x.Item3.Equals(t3));
        if (match == null) return default(T1);
        else return match.Item1;
    }
    public T2 Get(T1 t1, T3 t3)
    {
        var match = this.SingleOrDefault(x => x.Item1.Equals(t1) && x.Item3.Equals(t3));
        if (match == null) return default(T2);
        else return match.Item2;
    }
    public T3 Get(T1 t1, T2 t2)
    {
        var match = this.SingleOrDefault(x => x.Item1.Equals(t1) && x.Item2.Equals(t2));
        if (match == null) return default(T3);
        else return match.Item3;
    }
}

使用法：

key.Add(1, "Foo", new MyType("foo"));
key.Add(2, "Bar", new MyType("bar"));
key.Add(2, "Bar", new MyType("bar")); // Does not add, because it already exists.
var key1 = key.Get("Bar", new Foo("bar")); // Returns 2
var defaultKey = key.Get("Bar", new Foo("foo")); // Returns 0, the default value for an int
var key2 = key.Get(1, new Foo("foo")); // returns "Foo"

MyTypesを多く使用する場合は、値が等しいかどうかを比較する必要がありますnew。それ以外の場合は、新しいものを作成すると、一意の値が保証されます。

Answer 7

そのようなデータ構造が存在するかどうかはわかりませんが、作成することはできます。

キー/サブキーが一意であると仮定します

以下はMultiKeyDictionary（2つの内部辞書を使用します。1つはkeys（as object）用で、もう1つはvalues用です）。

public class MultiKeyDictionary<TValue> 
{
    private Dictionary<Guid, TValue> values;
    private Dictionary<Object, Guid> keys;

    public MultiKeyDictionary()
    {
        keys = new Dictionary<Object,Guid>();
        values = new Dictionary<Guid,TValue>();
    }
    public IEnumerable<Object> Keys
    {
        get { return keys.Keys.AsEnumerable();} // May group according to values here
    }

    public IEnumerable<TValue> Values
    {
        get { return values.Values;}
    }

    public TValue this[object key]
    {
        get 
        {
            if (keys.ContainsKey(key)) 
            {
                var internalKey = keys[key];
                return values[internalKey];
            }
            throw new KeyNotFoundException();
        }
    }


    public void Add(TValue value,object key1, params object[] keys) // key1 to force minimum 1 key
    {
        Add(key1 , value);
        foreach( var key in keys)
        {
        Add (key, value);
        }
    }

    private void Add(Object key, TValue value)
    {
        var internalKey = Guid.NewGuid();
        keys.Add( key, internalKey);
        values.Add(internalKey, value);     
    }   
}

それはとして使用することができます

MultiKeyDictionary<string> dict = new MultiKeyDictionary<string>();
dict.Add("Hello" , 1,2,3,"StringKey"); // First item is value, remaining all are keys
Console.WriteLine(dict[1]); // Note 1 is key and not intex
Console.WriteLine(dict[2]); // Note 2 is key and not index
Console.WriteLine(dict["StringKey"]);

Answer 8

System.Tupleを念頭に置いて辞書キーとして使用して追加されました。使用法：

var dict = new Dictionary<Tuple<string, int>, DateTime>();
dict.Add(Tuple.Create("Louis", 14), new DateTime(1638, 9, 5));

タプル構文は面倒ですが、静的ファクトリメソッドは作成サイトで多くの手間をかけます。