0

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

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

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

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

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

我想到的实现这一目标的两种方法是

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

  2. 检索完第一个列表后，将其放入并发集合中，例如字典（在 .net 4.0 中提供），并在剩余列表可用时立即开始聚合（到并发集合中）。

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

也许还有另一种方法可以解决这个问题？此外，由于版本是使用 long 存储的，并且会有成千上万（可能是数百万）的元素，内存分配可能会引起关注（因为这些对象是短暂的，所以可能不是一个大问题）

4

2 回答 2

2

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

HashSet.UnionWith 方法

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

如果版本都是 v 那么数字可以使用数字来构建缺少为 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 进行测试，上面的速度是原来的两倍多。
在插入件上加锁是很昂贵的。

于 2012-10-18T13:26:33.800 回答
0

您的问题似乎适合基于事件的解决方案。基本上为每个来源的数据完成分配事件。保持一个类型为 的全局并发散列。在您的事件处理程序中检查已完成的数据源，如果您的并发哈希包含当前元素的键，则只需将其添加到列表中，如果不只是插入具有给定元素的新列表。

但是根据您的性能要求，这可能会使您的应用程序过于复杂。您的第一种方法将是最简单的方法。

于 2012-10-18T14:05:20.563 回答