如何在一段时间内从队列中删除重复的项目？

Question

我想以有效的方式从队列中删除重复的条目。 队列有一个带有 DateTime 和 FullPath 以及其他一些内容的自定义类。

private Queue<MyCustomClass> SharedQueue;

类中的 DateTime 是插入队列时的时间戳。我想使用的逻辑如下：如果完整路径在 4 秒窗口内相同（即，如果在重复完整路径的 4 秒内添加到队列），则从队列中删除重复项。我有一些想要观看的事件，但仍然会出现一些重复的事件，这没关系。

我正在使用 c# 2.0 和 FileSystemWatcher 类和工作队列。

有很多方法可以做到这一点： 每次添加项目时都会修剪队列，或者当我在队列上工作时跳过当前重复项目的处理。

或者我应该使用“全局私有”变量 Dictionary<字符串、日期时间> ？这样我就可以快速搜索到吗？或者队列的本地副本？也许最好将本地队列限制为 100 个项目，以防出现许多文件事件？虽然就我而言，它“应该”只有相对较少的文件要在文件夹中监视...但事情总是会发生变化...

感谢您的帮助。

：编辑：美国东部时间 2 月 10 日 8:54： 因此，据我所知，我决定实施一个很好的简单解决方案。 我不认为我持有 Dict 键太久...

：编辑：2 月 10 日 9:53 EST：更新，因为我的词典不能包含重复的值。

   public void QueueInput(HotSynchUnit.RcdFSWFile rcd)
// start the worker thread when program starts.
// call Terminate.Set() in the programs exit routine or close handler etc.
{
  // lock shared queue
  lock (SharedQueue)
  {
    if (!IsDuplicateQueueInput(rcd))  // only add unique values to queue
    {
      SharedQueue.Enqueue(rcd);
      SomethingToDo.Set();
    }
  }
} // public void QueueInput

private bool IsDuplicateQueueInput(HotSynchUnit.RcdFSWFile rcd)
/* Return true if the object is a duplicate object.
 * Pseudo Code:
 * 
 * isDuplicate = false
 * Lock Dictionary
 * -If lastTimeStamp > 4 seconds ago then       // Optimization: save lastTimeStamp
 *    if Dict.Count > 0 then clear Dictionary
 *    return isDuplicate
 * -If not Dict.TryGetValue(sPath, dtTimeStamp) then
 *    Dict.AddKey()
 * -Else
 *    Compare key timestamp to Currenttime
 *    if key timestamp is <= 4 seconds ago then
 *       IsDuplicate = True
 *
 *    Dict.RemoveKey()
 *    Dict.AddKey()
 * 
 * return isDuplicate
*/
{
  // put real code here
}

Answer 1

我只是考虑使用类似于通用哈希表的任何集合...类似这样的东西：

Dictionary<string, YourClass> dict = new Dictionary<string, YourClass>();

/// just let's assume you want to add/check for "c:\demo.txt"

if (!dict.ContainsKey(@"c:\demo.txt"))
{
   /// add items to dict by passing fullPath as key and your objects as value
   dict.add(@"c:\demo.txt", obj1);
} 
else if (dict[@"c:\demo.txt"].CheckForIntervall())
{
   /// replace current object in dictionary with new object - in case you want to..
   /// or just do what you want to 
}

编辑 - 您的自定义类可能具有这样的功能：

class YOURCUSTOMCLASS
{
    private DateTime creationTime;

    public DateTime CreationTime
    { get { return creationTime; } }

    public YOURCUSTOMCLASS(parametersGoesHere xyz)
    {
          creationTime = DateTime.Now;
    }

    /// in this case this method will return true
    /// if the timeSpan between this object and otherObject
    /// is greater than 4 seconds
    public bool CheckForInterval(YOURCUSTOMCLASS otherObject)
    {
         TimeSpan diff = otherObj.CreationTime.Subtract(creationTime);

         /// you may replace 4 through any other digit, or even better take
         /// a const/global var/static ...
         return diff.TotalSeconds > 4;
    }

    /// all the other stuff you need ...
}

当然您会< em>放松队列的功能 - 但如果您的队列包含许多元素，您将运行时间大幅增加。

哈

Answer 2

我会创建一个子类：

class MyDeduplicatedQueue : Queue<MyCustomObject> {
    /// etc
}

然后您可以将所有适当的过滤逻辑放入 Enqueue 方法中。

Answer 3

我将创建一个包装类，而不是从队列扩展，因为基本类型 Queue 的用户期望不同的行为。 （当您这样做时，.NET 4.0 中的数据协定甚至可能会抱怨。）

在内部，您可以有一个实际的队列来将所需的调用重定向到其中。
每次 Queue() 调用时，您都可以将尚未包含的新元素添加到字典中。在此之前，您可以从该字典中清空所有早于 x 秒的元素，并将它们按顺序添加到内部队列中。

出队时，您必须检查内部队列是否包含元素，否则从字典中选择最早的元素。

这当然只是一种可能的实现。当许多不同的元素可能快速排队时，字典将很快填满，并且可能需要添加额外的逻辑来解决这个问题。

Answer 4

如果插入有重复的路径，为什么不直接拒绝插入呢？您所要做的就是从队列尾部开始线性搜索，并在找到重复项（并拒绝插入）或时间戳超过时间限制（并插入记录）时停止？看起来比保留另一个数据结构和所有相关逻辑要简单得多。