gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:03:11 25 4
gpt4 key购买 nike

我正在寻找一种方法来协调来自 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 存储的,并且会有成百上千(可能是数百万)个元素,内存分配可能是一个问题(可能不是一个大问题,因为这些对象是短暂的)

最佳答案

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 进行测试,上面的速度是原来的两倍多。
锁定插入物是昂贵的。

关于c# - 协调 3 个列表的最佳算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12955126/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com