C#布尔窗口最常见

Question

我想创建一个移动窗口，存储布尔值并输出最常见的布尔值。

我希望能够在飞行中添加新的值，例如：

bool[] window = { false, false, true, true, true };

新增"false"值，数组移位：

bool[] window = { false, true, true, true, false };

预期输出应为"true"。

对此，最好/最有效的方法是什么？我应该使用LINQ吗？任何例子都将不胜感激。非常感谢。

Answer 1

这是一个具有O(1(插入和读取功能的版本，而Joel的版本具有O(N(读取功能。

public class BoolWindowedMode
{
private readonly bool[] history;
private int used;
private int count;
private int rotation;
public BoolWindow(int width)
{ history = new bool[width]; }
public void Insert(bool newValue)
{
// remove old entry from count
if (history[rotation]) --count;
// count new entry
if (newValue) ++count;
// replace old entry in history, shifting
history[rotation] = newValue;
if (++rotation >= history.Length) rotation = 0;
if (used < history.Length) ++used;
}
public int CountOfTrue => count;
public int CountOfFalse => used - count;
public bool Mode => count > used - count;
}

如果你只需要"；正确的"；结果一旦插入了足够的值来填充窗口，就可以消除used变量。

Answer 2

public class BoolWindow : IEnumerable<bool>
{
private static int MaxSize = 5;
private Queue<bool> data = new Queue<bool>(MaxSize);
public void Add(bool newValue)
{
if (data.Count >= MaxSize) data.Dequeue();
data.Enqueue(newValue);
}
public bool MostFrequentValue()
{
//What do you want if the size is even and both true and false are the same?
return data.Select(b => b?1:-1).Sum() > 0;
// Also: we could optimize this by looping manually until one value
// is > Count/2, but that's probably more trouble than it's worth
}    
public IEnumerator<bool> GetEnumerator()
{
return data.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}

Answer 3

您确实可以像前面建议的那样使用Queue<bool>。但在某些情况下，它可能会导致性能问题。在5次第一次插入之后，每次插入将花费Dequeue和Enqueue。

效率取决于的实施。NET，我不是这方面的专家，但它可能是次优的。假设队列已达到其容量，则Dequeue只能增加头索引，但随后Enqueue将需要重新分配。如果Dequeue不仅仅是递增索引，那么它可能需要复制整个队列。

由于Queue不限于预定义的窗口大小，因此其实现可能不如特定的循环队列实现。

因此，如果效率至关重要，您可以尝试使用固定大小的数组，并在其顶部管理循环队列

BTW-如果元素的数量是偶数(例如，在我们得到5个条目之前(，并且我们有相同数量的true和false，那么不清楚最常见的值应该是什么。我任意选择了false。

实施：

public class CyclicQueueBool 
{
public CyclicQueueBool(int maxSize)
{
int internalSize = maxSize + 1;
m_Queue_ = new bool[internalSize];
m_Head_ = 0;
m_Tail_ = 0;
}
// Get the actual number of elements in the queue (smaller than MaxSize() in case it is not full)
public int NumberOfActualElements()
{
if (m_Head_ >= m_Tail_)
return (int)m_Head_ - (int)m_Tail_;
int maxSize = m_Queue_.Length - 1;
return (int)(maxSize - m_Tail_ + m_Head_ + 1);
}
// Check if the queue is empty or full:
public bool IsEmpty() { return (m_Head_ == m_Tail_); }
public bool IsFull() { return (_Next(m_Head_) == m_Tail_); }
// Push a new element to the queue. If the queue is full the oldest element is discarded to keep the size.
public void Push(bool elem)
{
if (IsFull())
{
m_Tail_ = _Next(m_Tail_);
}
m_Queue_[(int)(m_Head_)] = elem;
m_Head_ = _Next(m_Head_);
}
// Access element by index:
// NOTE:    Q[0]                is Tail() (i.e. the oldest)
//          Q[NumElements-1]    is Head() (i.e. the newest)
public bool this[int index]
{
get { return m_Queue_[(int)((index + m_Tail_) % m_Queue_.Length)]; }
set { m_Queue_[(int)((index + m_Tail_) % m_Queue_.Length)] = value; }
}
// Get common value:
public bool GetCommonValue()
{
int numTrue = 0;
int numFalse = 0;
int numElems = this.NumberOfActualElements();
for (int i = 0; i < numElems; ++i)
{
if (this[i])
{
numTrue++;
}
else
{
numFalse++;
}
}
return (numTrue > numFalse);
}

protected int _Next(int i) { return (i + 1) % m_Queue_.Length; }
protected int _Prev(int i) { return (i + m_Queue_.Length - 1) % m_Queue_.Length; }
protected bool[] m_Queue_;
protected int m_Head_;
protected int m_Tail_;
}

class Program
{
static void Main(string[] args)
{
CyclicQueueBool q = new CyclicQueueBool(5);
q.Push(false);
q.Push(true);
q.Push(false);
q.Push(false);
q.Push(true);
Console.WriteLine("GetCommonValue: " + q.GetCommonValue());
}
}

更新：基于@Ben Voigt的评论，我将实现中的List<bool>替换为bool[]。