.NET中最有效的实现UniqueQueue和UniqueReplacementQueue集合 [英] The Most Efficient Implementation of UniqueQueue and UniqueReplacementQueue Collections in .NET
问题描述
考虑到Enqueue和Dequeue操作的速度同样重要的事实，在.NET中UniqueQueue和UniqueReplacementQueue集合的最高效（在速度方面）的实现是什么。
UniqueQueue是一个无法重复的队列。因此，如果我将一个元素推送到队列中，那么只有在队列中不存在该元素时才添加。
UniqueReplacementQueue是一个队列， 。不同的是，如果我推一个已经存在于队列中的元素，它将替换在同一位置的现有元素。
我当前的UniqueQueue和UniqueReplacementQueue实现：
sealed class UniqueQueue< T> ：IQueue< T>
{
readonly LinkedList< T>列表;
readonly IDictionary< T，int>字典;
public UniqueQueue（LinkedList< T> list，IDictionary< T，int> dictionary）
{
this.list =
this.dictionary = dictionary;
}
public int长度
{
get {return list.Count; }
}
public T Dequeue（）
{
if（list.Count == 0）
{
throw new InvalidOperationException 队列是空的）;
}
var element = list.First.Value;
dictionary.Remove（element）;
list.RemoveFirst（）;
return element;
}
public void enqueue（T element）
{
dictionary [element] = 0;
if（dictionary.Count> list.Count）
{
list.AddLast（element）;
}
}
}
sealed class UniqueReplacementQueue< T> ：IQueue< T>
{
readonly LinkedList< T>列表;
readonly IDictionary< T，T>字典;
public UniqueReplacementQueue（LinkedList< T> list，IDictionary< T，T> dictionary）
{
this.list = list;
this.dictionary = dictionary;
}
public int长度
{
get {return list.Count; }
}
public T Dequeue（）
{
if（list.Count == 0）
{
throw new InvalidOperationException 队列是空的）;
}
var element = dictionary [list.First.Value];
dictionary.Remove（element）;
list.RemoveFirst（）;
return element;
}
public void Enqueue（T element）
{
dictionary [element] = element;
if（dictionary.Count> list.Count）
{
list.AddLast（element）;
}
}
}
这很漂亮，但是有一个内部HashSet和Queue的类。 Enqueue第一的自定义方法尝试将其添加到哈希集。如果HashSet.Add调用返回false，我们不会将它排队。如果集合的大小足够容纳所有元素，则HashSet.Add（）是一个O（1）操作。
这是唯一的缺点是内存使用，如果这是一个关注你。这里是一个实现：
public class UniqueQueue< T& ：IEnumerable< T> {
private HashSet< T> hashSet;
私人队列< T>队列;
public UniqueQueue（）{
hashSet = new HashSet< T>（）;
queue = new Queue< T>（）;
}
public int Count {
get {
return hashSet.Count;
}
}
public void Clear（）{
hashSet.Clear（）;
queue.Clear（）;
}
public bool包含（T item）{
return hashSet.Contains（item）;
}
public void Enqueue（T item）{
if（hashSet.Add（item））{
queue.Enqueue（item）;
}
}
public T Dequeue（）{
T item = queue.Dequeue（）;
hashSet.Remove（item）;
return item;
}
public T Peek（）{
return queue.Peek（）;
}
public IEnumerator< T> GetEnumerator（）{
return queue.GetEnumerator（）;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator（）{
return queue.GetEnumerator（）;
}
}
HashSet可以随时使用，因为它通常更快。这可能更好，如果.NET的维护者将这些方法标记为虚拟，但在这里我们是。
BTW;我听说有一些BS法律问题使用代码从这里或什么？放心，使用这个，但你死了好。这是根据无他妈的许可证许可。
What is the most efficient (in terms of speed) implementation of UniqueQueue and UniqueReplacementQueue collections in .NET considering the fact that the speed of Enqueue and Dequeue operations is equally important.
UniqueQueue is a queue where duplicates are not possible. So if I push an element to the queue it is added in only case it doesn't already exist in the queue.
UniqueReplacementQueue is a queue where duplicates are not possible either. The difference is that if I push an element which already exists in the queue, it replaces the existing element at the same position. It makes sense for reference types.
My current implementation of UniqueQueue and UniqueReplacementQueue:
sealed class UniqueQueue<T> : IQueue<T>
{
readonly LinkedList<T> list;
readonly IDictionary<T, int> dictionary;
public UniqueQueue(LinkedList<T> list, IDictionary<T, int> dictionary)
{
this.list = list;
this.dictionary = dictionary;
}
public int Length
{
get { return list.Count; }
}
public T Dequeue()
{
if (list.Count == 0)
{
throw new InvalidOperationException("The queue is empty");
}
var element = list.First.Value;
dictionary.Remove(element);
list.RemoveFirst();
return element;
}
public void Enqueue(T element)
{
dictionary[element] = 0;
if (dictionary.Count > list.Count)
{
list.AddLast(element);
}
}
}
sealed class UniqueReplacementQueue<T> : IQueue<T>
{
readonly LinkedList<T> list;
readonly IDictionary<T, T> dictionary;
public UniqueReplacementQueue(LinkedList<T> list, IDictionary<T, T> dictionary)
{
this.list = list;
this.dictionary = dictionary;
}
public int Length
{
get { return list.Count; }
}
public T Dequeue()
{
if (list.Count == 0)
{
throw new InvalidOperationException("The queue is empty");
}
var element = dictionary[list.First.Value];
dictionary.Remove(element);
list.RemoveFirst();
return element;
}
public void Enqueue(T element)
{
dictionary[element] = element;
if (dictionary.Count > list.Count)
{
list.AddLast(element);
}
}
}
This is pretty old, but how about a class that has an internal HashSet, and Queue. A custom method for Enqueue firsts tries to add it to the hashset. if the HashSet.Add call returns false, we do not enqueue it. HashSet.Add() is an O(1) operation if the set is of a size large enough to hold all elements.
The only drawback to this is memory usage if this is a concern for you. Here is an implementation:
public class UniqueQueue<T> : IEnumerable<T> {
private HashSet<T> hashSet;
private Queue<T> queue;
public UniqueQueue() {
hashSet = new HashSet<T>();
queue = new Queue<T>();
}
public int Count {
get {
return hashSet.Count;
}
}
public void Clear() {
hashSet.Clear();
queue.Clear();
}
public bool Contains(T item) {
return hashSet.Contains(item);
}
public void Enqueue(T item) {
if (hashSet.Add(item)) {
queue.Enqueue(item);
}
}
public T Dequeue() {
T item = queue.Dequeue();
hashSet.Remove(item);
return item;
}
public T Peek() {
return queue.Peek();
}
public IEnumerator<T> GetEnumerator() {
return queue.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
return queue.GetEnumerator();
}
}
The HashSet is used whenever it can because it is typically faster. This could be nicer if the maintainers of .NET marked these methods as virtual, but alas here we are.
BTW; I hear that there is some BS legal issue with using code from here or something? Rest assured, use this however you damned well please. This is licensed under the no fucking license license.
这篇关于.NET中最有效的实现UniqueQueue和UniqueReplacementQueue集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
