Dies ist nicht gerade eine Antwort auf Ihre Frage, aber ich habe eine Klasse, die die Leistung von Contains() auf eine Sammlung erhöht. Ich habe eine Queue unterklassifiziert und ein Dictionary hinzugefügt, das Hashcodes auf Listen von Objekten abbildet. Die Dictionary.Contains() Funktion ist O(1), während List.Contains() , Queue.Contains() y Stack.Contains() sind O(n).
Der Wertetyp des Wörterbuchs ist eine Warteschlange, die Objekte mit demselben Hashcode enthält. Der Aufrufer kann ein benutzerdefiniertes Klassenobjekt liefern, das IEqualityComparer implementiert. Sie könnten dieses Muster für Stacks oder Lists verwenden. Der Code müsste nur geringfügig geändert werden.
/// <summary>
/// This is a class that mimics a queue, except the Contains() operation is O(1) rather than O(n) thanks to an internal dictionary.
/// The dictionary remembers the hashcodes of the items that have been enqueued and dequeued.
/// Hashcode collisions are stored in a queue to maintain FIFO order.
/// </summary>
/// <typeparam name="T"></typeparam>
private class HashQueue<T> : Queue<T>
{
private readonly IEqualityComparer<T> _comp;
public readonly Dictionary<int, Queue<T>> _hashes; //_hashes.Count doesn't always equal base.Count (due to collisions)
public HashQueue(IEqualityComparer<T> comp = null) : base()
{
this._comp = comp;
this._hashes = new Dictionary<int, Queue<T>>();
}
public HashQueue(int capacity, IEqualityComparer<T> comp = null) : base(capacity)
{
this._comp = comp;
this._hashes = new Dictionary<int, Queue<T>>(capacity);
}
public HashQueue(IEnumerable<T> collection, IEqualityComparer<T> comp = null) : base(collection)
{
this._comp = comp;
this._hashes = new Dictionary<int, Queue<T>>(base.Count);
foreach (var item in collection)
{
this.EnqueueDictionary(item);
}
}
public new void Enqueue(T item)
{
base.Enqueue(item); //add to queue
this.EnqueueDictionary(item);
}
private void EnqueueDictionary(T item)
{
int hash = this._comp == null ? item.GetHashCode() : this._comp.GetHashCode(item);
Queue<T> temp;
if (!this._hashes.TryGetValue(hash, out temp))
{
temp = new Queue<T>();
this._hashes.Add(hash, temp);
}
temp.Enqueue(item);
}
public new T Dequeue()
{
T result = base.Dequeue(); //remove from queue
int hash = this._comp == null ? result.GetHashCode() : this._comp.GetHashCode(result);
Queue<T> temp;
if (this._hashes.TryGetValue(hash, out temp))
{
temp.Dequeue();
if (temp.Count == 0)
this._hashes.Remove(hash);
}
return result;
}
public new bool Contains(T item)
{ //This is O(1), whereas Queue.Contains is (n)
int hash = this._comp == null ? item.GetHashCode() : this._comp.GetHashCode(item);
return this._hashes.ContainsKey(hash);
}
public new void Clear()
{
foreach (var item in this._hashes.Values)
item.Clear(); //clear collision lists
this._hashes.Clear(); //clear dictionary
base.Clear(); //clear queue
}
}
Meine einfachen Tests zeigen, dass meine HashQueue.Contains() läuft viel schneller als Queue.Contains() . Die Ausführung des Testcodes mit einer Zählung von 10.000 dauert 0,00045 Sekunden für die HashQueue-Version und 0,37 Sekunden für die Queue-Version. Bei einer Anzahl von 100.000 benötigt die HashQueue-Version 0,0031 Sekunden, während die Queue-Version 36,38 Sekunden benötigt!
Hier ist mein Testcode:
static void Main(string[] args)
{
int count = 10000;
{ //HashQueue
var q = new HashQueue<int>(count);
for (int i = 0; i < count; i++) //load queue (not timed)
q.Enqueue(i);
System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < count; i++)
{
bool contains = q.Contains(i);
}
sw.Stop();
Console.WriteLine(string.Format("HashQueue, {0}", sw.Elapsed));
}
{ //Queue
var q = new Queue<int>(count);
for (int i = 0; i < count; i++) //load queue (not timed)
q.Enqueue(i);
System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < count; i++)
{
bool contains = q.Contains(i);
}
sw.Stop();
Console.WriteLine(string.Format("Queue, {0}", sw.Elapsed));
}
Console.ReadLine();
}
