C#/LINQ 比较两个列表和赋值的最快方法
C# / LINQ fastest way of comparing two lists and assigning value
我编写了一个代码,基本上比较了 C# 中的两个列表。第一个列表包含如下属性:
- 物品ID
- 总浏览量
第一个列表缺少 TotalViews 的值,所以我从具有这些道具的第二个列表中分配它们:
- 物品ID
- HitCount // 这是 属性 需要分配的 TotalViews
代码如下:
foreach (var item in parsedMerchantData)
{
var itemInB = HitCountItemIDS.FirstOrDefault(x => x.ItemID == item.ItemID);
if (itemInB != null)
{
if (itemInB.HitCount != -1)
{
item.TotalViews = itemInB.HitCount;
}
else
{
item.TotalViews = 0;
}
}
}
有没有更有效的方法来使用 LINQ 或实现自定义比较器来编写此代码,以便在有时包含 100000 个项目的较大列表上更快地工作?
代码如下所示。不确定 HitCountItemID 的类型是什么。如果它是匿名的,那么只需 'var dict' :
Dictionary<string, ABC_TYPE> dict = HitCountItemID.GropupBy(x => x.ItemID, y => y).ToDictionary(x => x.Key, y => y.FirstOrDefault())
foreach (var item in parsedMerchantData)
{
var itemInB = dict[item.ItemID];
if (itemInB != null)
{
if (itemInB.HitCount != -1)
{
item.TotalViews = itemInB.HitCount;
}
else
{
item.TotalViews = 0;
}
}
}
我假设您在程序 run/collecting 数据期间持有 2 个列表,因此您可以在插入期间对它们进行排序。或者,如果它们在数据库中并且 ID 上有一个索引,它也可能有效。
如果是这样,你应该能够通过每个数组只做一个 运行,这将优化程序非常高(现在你有大约 n^2 的复杂性取决于值),在你改变你之后会有 n.
int i = 0, j = 0;
while( i < parsedMerchantData.Count && j < HitCountItemIDS.Count)
{
var item = parsedMerchantData[i];
var itemInB = HitCountItemIDS[j];
if (itemInB.ItemID == item.ItemID)
{
item.TotalViews = (itemInB.HitCount > 0) ? itemInB.HitCount : 0;
i++;
j++;
}
else if(itemInB.ItemID < item.ItemID)
i++;
else //itemInB.ItemID > item.ItemID
j++;
}
代码应该类似于上面的代码,您应该添加更多关于它何时结束以及其余值应该发生什么的控制(这将停止一次 i
或 j
打到最后)。
这里是 pseudo-code:
var arr1 = parsedMerchantData.OrderBy(x => x.ItemID).ToArray();
var arr2 = HitCountItemID.OrderBy(x => x.ItemID).ToArray();
var i, j = 0;
while(i + j < arr1.Length() + arr2.Length()) // or similar condition
{
if (arr1[i].ItemID < arr2[j].ItemID) {
if (i < arr1.Length() - 1) {
i++;
}
continue;
}
if (arr1[i].ItemID > arr2[j].ItemID) {
if (j < arr2.Length() - 1) {
j++;
}
continue;
}
if (arr1[i].ItemID == arr2[j].ItemID) {
arr1[i].TotalViews = arr2[j].HitCount != -1 ? arr2[j].HitCount : 0;
}
// Make sure you do not let i and j grow higher then lengths of arrays
}
想法是应用 MergeSort 算法。
至于复杂性,您花费 O(n * log(n)) 对每个列表进行排序,然后 O(n) 遍历它们。总数是 O(n * log(n)) ,这是我看到的最快的方式。
这类似于 jdweng 的回答,但稍微简单一点,它不会因缺少项目 ID 而抛出异常:
var hitCountsById = HitCountItemIDS.ToDictionary(x => x.ItemID, x => x.HitCount);
foreach (var item in parsedMerchantData)
{
int hitCount;
// We don't care about the return value of TryGetValue here...
hitCountsById.TryGetValue(item.ItemID, out hitCount);
item.HitCount = hitCount == -1 ? 0 : hitCount;
}
这应该是 O(N+M),其中 N 是 HitCountItemIDs
的大小,M
是 parsedMerchantData
的大小...因此随着数据变大,它应该比 merge-sort 方法增长得更慢,并且代码绝对更简单。 (订购时也不需要比较商品 ID - 只是相等。)
我编写了一个代码,基本上比较了 C# 中的两个列表。第一个列表包含如下属性:
- 物品ID
- 总浏览量
第一个列表缺少 TotalViews 的值,所以我从具有这些道具的第二个列表中分配它们:
- 物品ID
- HitCount // 这是 属性 需要分配的 TotalViews
代码如下:
foreach (var item in parsedMerchantData)
{
var itemInB = HitCountItemIDS.FirstOrDefault(x => x.ItemID == item.ItemID);
if (itemInB != null)
{
if (itemInB.HitCount != -1)
{
item.TotalViews = itemInB.HitCount;
}
else
{
item.TotalViews = 0;
}
}
}
有没有更有效的方法来使用 LINQ 或实现自定义比较器来编写此代码,以便在有时包含 100000 个项目的较大列表上更快地工作?
代码如下所示。不确定 HitCountItemID 的类型是什么。如果它是匿名的,那么只需 'var dict' :
Dictionary<string, ABC_TYPE> dict = HitCountItemID.GropupBy(x => x.ItemID, y => y).ToDictionary(x => x.Key, y => y.FirstOrDefault())
foreach (var item in parsedMerchantData)
{
var itemInB = dict[item.ItemID];
if (itemInB != null)
{
if (itemInB.HitCount != -1)
{
item.TotalViews = itemInB.HitCount;
}
else
{
item.TotalViews = 0;
}
}
}
我假设您在程序 run/collecting 数据期间持有 2 个列表,因此您可以在插入期间对它们进行排序。或者,如果它们在数据库中并且 ID 上有一个索引,它也可能有效。
如果是这样,你应该能够通过每个数组只做一个 运行,这将优化程序非常高(现在你有大约 n^2 的复杂性取决于值),在你改变你之后会有 n.
int i = 0, j = 0;
while( i < parsedMerchantData.Count && j < HitCountItemIDS.Count)
{
var item = parsedMerchantData[i];
var itemInB = HitCountItemIDS[j];
if (itemInB.ItemID == item.ItemID)
{
item.TotalViews = (itemInB.HitCount > 0) ? itemInB.HitCount : 0;
i++;
j++;
}
else if(itemInB.ItemID < item.ItemID)
i++;
else //itemInB.ItemID > item.ItemID
j++;
}
代码应该类似于上面的代码,您应该添加更多关于它何时结束以及其余值应该发生什么的控制(这将停止一次 i
或 j
打到最后)。
这里是 pseudo-code:
var arr1 = parsedMerchantData.OrderBy(x => x.ItemID).ToArray();
var arr2 = HitCountItemID.OrderBy(x => x.ItemID).ToArray();
var i, j = 0;
while(i + j < arr1.Length() + arr2.Length()) // or similar condition
{
if (arr1[i].ItemID < arr2[j].ItemID) {
if (i < arr1.Length() - 1) {
i++;
}
continue;
}
if (arr1[i].ItemID > arr2[j].ItemID) {
if (j < arr2.Length() - 1) {
j++;
}
continue;
}
if (arr1[i].ItemID == arr2[j].ItemID) {
arr1[i].TotalViews = arr2[j].HitCount != -1 ? arr2[j].HitCount : 0;
}
// Make sure you do not let i and j grow higher then lengths of arrays
}
想法是应用 MergeSort 算法。 至于复杂性,您花费 O(n * log(n)) 对每个列表进行排序,然后 O(n) 遍历它们。总数是 O(n * log(n)) ,这是我看到的最快的方式。
这类似于 jdweng 的回答,但稍微简单一点,它不会因缺少项目 ID 而抛出异常:
var hitCountsById = HitCountItemIDS.ToDictionary(x => x.ItemID, x => x.HitCount);
foreach (var item in parsedMerchantData)
{
int hitCount;
// We don't care about the return value of TryGetValue here...
hitCountsById.TryGetValue(item.ItemID, out hitCount);
item.HitCount = hitCount == -1 ? 0 : hitCount;
}
这应该是 O(N+M),其中 N 是 HitCountItemIDs
的大小,M
是 parsedMerchantData
的大小...因此随着数据变大,它应该比 merge-sort 方法增长得更慢,并且代码绝对更简单。 (订购时也不需要比较商品 ID - 只是相等。)