C# 中具有延迟输入的 AND 门

Question

我正在尝试实现一个具有多个输入的布尔与门。每个输入都有一个整数来标识它。输入信号随机到达，并存储在门中（因此它不是纯与门，而是具有延迟输入的门）。只有当所有输入信号都到达时，门才会触发。
注意：到达同一输入的 2 个信号不算作两个。

我想我应该创建一个字典来存储输入，当刺激到达时，更新该特定输入的 Id Key 的值，然后对所有值进行 AND 运算。如果结果为 1，则触发门并将字典的所有值重置为 0，然后再次等待。

我的方法听起来有些不对劲，我有一种感觉，一定有更优雅和更高性能的东西（.Net）。

Answer 1

我可能有点偏离基础，但这看起来像是 Rx 框架 非常适合。这样，您就可以转向纯粹的反应式编程，您可以声明在收到所有输入之前不会发送输出。对于外部消费者来说，您的门将充当 IObservable，这在某种程度上相当于 IEnumerable。任何观察者都只是看到输出的枚举，这些输出的发生延迟于输入的接收方式。

这里的主要好处是您可以链接可观察量。因此，如果您想将“与”门的输出链接到“或”门的输入，只需一行代码即可完成。对我来说，Rx 是对电路如何工作进行建模的完美框架，因为每个可观测值的结果都会在下一个可观测值的输入中发挥作用。

首先，我建议您观看 Channel9 上的系列视频。

Answer 2

如果输入 ID 是连续的，您可以使用 bool[] 而不是字典。

   bool[] inputs = new bool[10];

   void SetInput(int id, bool val)
   {
       inputs[id] = val;
   }

   bool trigger()
   {
        return inputs.All(b => b);
   }

   void reset()
   {
        Array.Clear(input, 0, inputs.Length);
   }

Answer 3

存储输入信息对我来说似乎没有必要。
每当信号到达时，只需检查它是否为零，确保结果为零。如果是之一，则无需执行任何具体操作。然后你只需要检查所有的输入信号是否已经到达。

Answer 4

编辑：

哦，我现在明白了，“多个”的意思是“两个以上”，并且值没有整数标识符，输入行。 可以。好吧，让我们重新开始吧。

您真的需要存储输入吗？如果任何输入为 false，则输出为 false，因此只要您至少有一个（或两个，如果您更喜欢）为 true 的输入，直到您获得 false 的输入。

哦，但是你说“到达同一输入的两个信号不算作两个”。为了强制执行此操作，您必须跟踪（但不一定存储）输入。这才是真正的原因。

所以真正的问题是：如何在 C# 中有效地存储（和检索）整数的稀疏数组？

每当您谈论稀疏数组时，字典（哈希表）无疑是显而易见的选择。但在这种情况下，每个条目只需要一个布尔值，而 Dictionary 确实有点浪费。

输入线路 ID 的最大范围是多少？是 [int.MinValue、int.MaxValue] 还是更易于管理的范围内的值？如果标识符的最大范围相对较小，您可能需要查看 System.Collections.BitArray 或 System.Collections.Specialized.BitVector32。

如果您使用这些位集合之一，则有两种选择：

1. 使用两个 BitArray/BitVector32：一个用于存储输入值，另一个用于存储信号是否已到达该线路。
2. 仅使用一个 BitArray/BitVector32。使用它来存储信号是否已到达给定线路，并保留一个单独的 bool 值，该值将与每个新输入进行与运算。此选项无法将一行上的 false 输入重置为同一行上的 true 输入。

假设输入行数为 32 或更少，上述选项 1 的高效 BitVector32 实现将如下所示：

class AndGate{
    BitVector32 activeLines;
    BitVector32 inputValues;

    public void Reset(){
        activeLines[-1] = inputValues[-1] = false; 
    }
    public void Input(int line, bool value){
        if(line < 0 || line > 31)
            throw new ArgumentOutOfRangeException("line");

        activeLines[1 << line] = true;
        inputValues[1 << line] = value;
    }
    public bool GetOutput(bool reset){
        bool rtn = activeLines.Data == inputValues.Data;
        if(reset)
            Reset();
        return rtn;
    }
}

如果您需要超过 32 行，则使用 BitArray 进行等效实现将类似，只是 GetOutput 会更复杂且效率更低。您最好使用 BitVector32（或普通的 int/uint）来滚动自己的 BitArray 等效项。

EDIT2：

鉴于OPs反对，我只能假设预期的行ID在[int.MinValue，int.MaxValue]中，并且行可以从 false 切换到 true。如果情况确实如此，那么像我上面概述的那样的密集实现是不切实际的。

所以我们回到了Dictionary<,>。然而，我们仍然可以对 Dictionary 进行一些优化。

1. 一种方法是使用 SortedList<,>。如果可以给出大量输入，SortedList<,> 将比 Dictionary<,> 使用显着更少的内存.

   例如，在 Dictionary 中，每个条目将使用至少 17 字节的内存。 SortedList 将仅使用 5。

   最大的缺点¹是向SortedList<,>添加新条目通常比向Dictionary<,>添加条目慢得多， >，因为其键值大于所添加条目的其他条目必须向下移动，以便为新条目腾出空间。我建议使用预期输入进行分析，以比较 SortedList<,> 和 Dictionary<,> 之间的内存使用情况和 CPU 消耗。

2. 另一个优化是将我上面提到的 BitVector32 方法与 Dictionary<,>/SortedList<,> 相结合。这可能²可以防止因存储 8 位布尔值以及存储大量键和（如果适用）哈希表开销而浪费大量空间。

允许这两个概念的示例实现如下：

class AndGate{

    struct AndEntry{
        BitVector32 activeLines;
        BitVector32 inputValues;

        public bool Output{get{return activeLines.Data == inputValues.Data;}}

        public void Input(int line, bool value){
            activeLines[1 << line] = true;
            inputValues[1 << line] = value;
        }
    }

    IDictionary<int, AndEntry> entries;

    public AndGate(bool useSortedList){
        if(useSortedList)
            entries = new SortedList<int, AndEntry>();
        else entries = new Dictionary<int, AndEntry>();
    }

    public void Reset(){entries.Clear();}

    public bool Input(int line, bool value){
        AndEntry entry;
        entries.TryGetValue(line / 32, out entry);
        /* no need to handle the not found case, since AndEntry is a struct */

        entry.Input(line & 31, value);
        entries[line / 32] = entry;
    }

    public bool GetOutput(bool reset){
        bool rtn = true;
        foreach(AndEntry value in entries.Values)
            if(!value.Output){
                rtn = false;
                break;
            }

        if(reset)
            Reset();
        return rtn;
    }
}

请记住，这些优化的唯一好处是使用更少的内存。仅当您期望许多输入时这才重要。 “许多”的确切含义很难确定，但对于简单的 Dictionary 实现，将其称为每个条目 20 个字节（以考虑开销）。因此，将您愿意使用的内存量除以 20。这就是“多”。但要注意 CPU 和内存之间的权衡。

<子>
¹ 之前有人天真地认为排序列表相对于哈希表（这就是 Dictionary<,> 的实现方式）的真正缺点是查找速度较慢。排序列表与哈希表，不要。他们会说，“但是在排序列表中查找的时间复杂度为 O(log N)，而在哈希表中查找的时间复杂度仅为 O(1)”。哎哟--de-freakin-do。其一，哈希表可能会降级为 O(N)，而排序列表始终为 O(log N)。对于两个人来说，即使您有 10 亿个项目，30 次整数比较（在本例中就是如此）也不会花费那么多。由于哈希表开销，许多人惊讶地发现排序列表在查找方面优于哈希表的频率。

_{² 同样，这取决于您的输入。如果 lineID & ~31 不会经常重叠（因此大多数 AndEntry 对象最终只存储一行），那么此解决方案将使用更多内存，而不是更少。相反，如果 lineID 中的其他 27 位集合倾向于重叠，则 Input() 中的不同掩码会更有效。}