Đây không phải là câu trả lời chính xác cho câu hỏi của bạn, nhưng tôi có một lớp làm tăng hiệu suất của Chứa() trên một bộ sưu tập. Tôi đã phân lớp một Hàng đợi và thêm một Dictionary để ánh xạ hashcodes vào danh sách các đối tượng.Hàm Dictionary.Contains() là O (1) trong khi List.Contains(), Queue.Contains() và Stack.Contains() là O (n).
Loại giá trị của từ điển là hàng đợi chứa đối tượng có cùng mã băm. Người gọi có thể cung cấp một đối tượng lớp tùy chỉnh thực hiện IEqualityComparer. Bạn có thể sử dụng mẫu này cho Ngăn xếp hoặc Danh sách. Mã sẽ chỉ cần một vài thay đổi.
/// <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
}
}
Thử nghiệm đơn giản của tôi cho thấy rằng HashQueue.Contains() chạy nhanh hơn nhiều so với Queue.Contains(). Chạy mã thử nghiệm với số lượng được đặt là 10.000 sẽ mất 0,00045 giây đối với phiên bản HashQueue và 0,37 giây đối với phiên bản Hàng đợi. Với số lượng 100.000, phiên bản HashQueue mất 0,0031 giây trong khi Hàng đợi mất 36,38 giây!
Đây là mã thử nghiệm của tôi:
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();
}
Vấn đề gì với từ điển? Nó được thiết kế để sử dụng trong trường hợp như của bạn. – Kamarey
@Kamarey: HashSet có thể là một lựa chọn tốt hơn. –
HashSet là những gì tôi đang tìm kiếm. – DSent