c# - 协调 3 个列表的最佳算法

Question

我正在寻找一种方法来协调来自 3 个不同来源的元素。我已经将元素简化为只有一个键(字符串)和版本(长)。

列表是同时获得的(2 个来自单独的数据库查询，1 个来自另一个系统上的内存缓存)。

对于我的最终结果，我只关心所有 3 个源中版本不同的元素。所以我关心的结果将是一个 key 列表，每个系统中都有相应的版本。

Element1 | system1:v100    | system2:v100 | system3:v101 |
Element2 | system1:missing | system2:v200 | system3:v200 |

并且可以丢弃具有相同版本的元素。

我想到的两种实现方式是

1. 等待所有数据源完成检索，然后循环遍历每个列表以聚合主列表，其中包含键的并集 + 所有 3 个版本(丢弃所有相同的项目)。

2. 一旦完成第一个列表的检索，将其放入并发集合中，例如字典(在 .net 4.0 中提供)，并在它们完成后立即开始聚合剩余列表(放入并发集合中)可用的。

我的想法是第二种方法会更快一些，但可能不会快很多。在所有 3 个来源都存在之前，我真的不能做太多事情，所以从第二种方法中获得的东西并不多，并且引入了争用。

也许有完全不同的方法来解决这个问题？此外，由于版本是使用 long 存储的，并且会有成百上千(可能是数百万)个元素，内存分配可能是一个问题(可能不是一个大问题，因为这些对象是短暂的)

Answer 1

HashSet 是一个选项，因为它具有 Union 和 Intersect 方法

HashSet.UnionWith Method

要使用它，您必须覆盖 Equals 和 GetHashCode。
一个好的(唯一的)散列是性能的关键。

如果版本都是 v 那么 numeric 可以使用 numeric 来构建散列，缺失为 0。
有 Int32 可以玩，所以如果版本是 Int10 或更低可以创建一个完美的散列。

另一个选项是 ConcurrentDictionary(没有并发的 HashSet)并且将所有三个都输入其中。
仍然需要覆盖 Equals 和 GetHashCode。
我的直觉是三个 HashSet，然后 Union 会更快。

如果所有版本都是数字并且您可以使用 0 来表示缺失，那么可以打包成 UInt32 或 UInt64 并将其直接放入 HashSet 中。 Union 之后解压。使用位推 << 而不是数学来打包解包。

这只是两个 UInt16，但它在 2 秒内运行。
这将比散列类更快。

如果所有三个版本都很长，那么 HashSet <integral type>不会是一个选项。
长 1 ^ 长 2 ^ 长 3；可能是一个很好的散列，但这不是我的专长。
我知道元组上的 GetHashCode 不好。

class Program
{
    static void Main(string[] args)
    {
        HashSetComposite hsc1 = new HashSetComposite();
        HashSetComposite hsc2 = new HashSetComposite();
        for (UInt16 i = 0; i < 100; i++)
        {
            for (UInt16 j = 0; j < 40000; j++)
            {
                hsc1.Add(i, j);
            }
            for (UInt16 j = 20000; j < 60000; j++)
            {
                hsc2.Add(i, j);
            }
        }
        Console.WriteLine(hsc1.Intersect(hsc2).Count().ToString());
        Console.WriteLine(hsc1.Union(hsc2).Count().ToString());
    }
}

public class HashSetComposite : HashSet<UInt32>
{
    public void Add(UInt16 u1, UInt16 u2)
    {      
        UInt32 unsignedKey = (((UInt32)u1) << 16) | u2;
        Add(unsignedKey);           
    }
    //left over notes from long
    //ulong unsignedKey = (long) key;
    //uint lowBits = (uint) (unsignedKey & 0xffffffffUL);
    //uint highBits = (uint) (unsignedKey >> 32);
    //int i1 = (int) highBits;
    //int i2 = (int) lowBits;
}

使用 ConcurrentDictionary 进行测试，上面的速度是原来的两倍多。
锁定插入物是昂贵的。