有一种最常见的浪费——对整个序列进行排序只是为了得到最大的项目。在linq2sql中,这种sin会被优化掉,但在linq2sql对象中,情况并非如此。你肯定应该习惯在你的工具集中有一些MaxBy,并在每次你需要最大的物品时使用它。
作为旁注,你用了一种错误的方式使用了Random。您不应该为每个随机数创建这个类的新实例。只需创建一个实例,并继续从中提取数字。
你也应该避免多次计算同一件事。我甚至不会称之为优化。写代码是不会浪费时间的,我认为大多数时候你应该习惯性地去做。
如果你需要最大的速度,你必须牺牲一切。扔掉抽象层,展开所有东西,抄近路。如果这1%的时间关键型代码真的需要它,它是可以做到的,但这并不漂亮。绝对不应该经常这样做。你已经被警告了。
我实现了两种方法。第一种是使用哈希字典来实现的。它消除了重复计算,生成的迭代器更少,因为它可以一次性计算所有子项。请注意。群比。ToDictionary大致相当于。ToLookup,但Dictionary提供TryGetValue,而lookup总是返回空序列。第二种方法使用merge-join。它对两个序列进行排序并合并它们。您可以方便地融合合并和subsum计算。事实证明,这是我在这里找到的最快的方法。如果你能得到已经排序的序列,它会更快。
我做了一些细微的修改,函数返回命名类实例的列表,而不是匿名的,所以我可以验证结果。对于mjwills代码,我必须添加ToList,这基本上消除了他提供的加速。结果就在这里
JoinTestClassOrig avg[ms]: 1161 / rounds[ms]: 1158, 1160, 1158, 1170
JoinTestClassHash_mjwills avg[ms]: 1158 / rounds[ms]: 1169, 1152, 1162, 1151
JoinTestClassHashMe avg[ms]: 857 / rounds[ms]: 865, 841, 840, 883
JoinTestClassMergeMe avg[ms]: 633 / rounds[ms]: 632, 631, 634, 636
密码呢
class Program
{
static void Main(string[] args)
{
var testCases = new List<TestClass>()
{
new JoinTestClassOrig(),
new JoinTestClassHash_mjwills(),
new JoinTestClassHashMe(),
new JoinTestClassMergeMe(),
};
Stopwatch stopwatch = new Stopwatch();
List<List<ProductPurchaseOutp>> results = new List<List<ProductPurchaseOutp>>();
for (int i = 0; i < 5; i++)
{
foreach (var testClass in testCases)
{
testClass.GenerateRandomObjects(1);
GCSettings.LargeObjectHeapCompactionMode = GCLargeObjectHeapCompactionMode.CompactOnce;
GC.Collect();
GC.WaitForFullGCComplete();
stopwatch.Restart();
var res = (testClass.ComputeMatches());
stopwatch.Stop();
if (i > 0)
{
results.Add(res);
testClass.results.Add(stopwatch.ElapsedMilliseconds);
}
}
}
Console.WriteLine("Checking results...");
int cnt = results
.Select(r => r
.OrderBy(o => o.ProductID)
.ThenBy(o => o.ROQ)
.ThenBy(o => o.RPQ)
.ThenBy(o => o.RUQ)
.ThenBy(o => o.RV)
.ToList()
)
.Aggregate((a, b) =>
{
for (int i = 0; i < a.Count; ++i)
{
if (!a[i].IsEqualTo(b[i])) { throw new Exception("Sequences are not equal"); }
}
return a;
}).Where(m => m.WAP != 0).Count();
Console.WriteLine("Count: " + cnt.ToString());
foreach (var test in testCases)
{
Console.WriteLine(test.name() + " avg[ms]: " + (int)test.results.Average() + " / rounds[ms]: " + string.Join(", ", test.results));
}
Console.ReadLine();
}
}
public abstract class TestClass
{
protected List<ProductPurchase> ListOne = new List<ProductPurchase>();
protected List<ProductPurchase> ListTwo = new List<ProductPurchase>();
public List<long> results = new List<long>();
public void GenerateRandomObjects(int seed)
{
Random rnd = new Random(seed);
ListOne.Clear();
ListTwo.Clear();
for (int i = 0; i < 500000; i++)
{
ListOne.Add(new ProductPurchase
{
ProductID = rnd.Next(1, 300000),
Price = rnd.Next(1, 100),
Quantity = rnd.Next(1, 30),
GlobalQuantity = rnd.Next(1, 5000)
});
ListTwo.Add(new ProductPurchase
{
ProductID = rnd.Next(1, 300000),
Price = rnd.Next(1, 100),
Quantity = rnd.Next(1, 30),
GlobalQuantity = rnd.Next(1, 10000)
});
}
}
public abstract List<ProductPurchaseOutp> ComputeMatches();
public string name()
{
return this.GetType().Name;
}
}
public class JoinTestClassOrig : TestClass
{
public override List<ProductPurchaseOutp> ComputeMatches()
{
var matched = (from listOne in ListOne
join listTwo in ListTwo on listOne.ProductID equals listTwo.ProductID into matches
select new ProductPurchaseOutp
{
ProductID = listOne.ProductID,
ROQ = listOne.Price,
RUQ = listOne.Quantity,
RPQ = listOne.GlobalQuantity,
RV = listOne.Price * listOne.Quantity * listOne.GlobalQuantity,
BMPProduct = matches.OrderBy(m => m.Price).FirstOrDefault(),
WAP = (matches.IsEmpty() || matches.Sum(m => m.Quantity * m.GlobalQuantity) == 0) ? 0 : matches.Sum(m => m.Quantity * m.GlobalQuantity * m.Price) / matches.Sum(m => m.Quantity * m.GlobalQuantity)
})
.ToList();
return matched;
}
}
public class JoinTestClassHash_mjwills : TestClass
{
public override List<ProductPurchaseOutp> ComputeMatches()
{
var dicTwo = ListTwo.ToLookup(z => z.ProductID);
var matched = (from listOne in ListOne
let matches = dicTwo[listOne.ProductID]
let sum = matches.Sum(m => m.Quantity * m.GlobalQuantity)
select new ProductPurchaseOutp
{
ProductID = listOne.ProductID,
ROQ = listOne.Price,
RUQ = listOne.Quantity,
RPQ = listOne.GlobalQuantity,
RV = listOne.Price * listOne.Quantity * listOne.GlobalQuantity,
BMPProduct = matches.OrderBy(m => m.Price).FirstOrDefault(),
WAP = sum == 0 ? 0 : matches.Sum(m => m.Quantity * m.GlobalQuantity * m.Price) / sum
});
return matched.ToList();
}
}
public class JoinTestClassMergeMe : TestClass
{
private IEnumerable<ProductPurchaseOutp> matched()
{
var l1 = ListOne
.OrderBy(p => p.ProductID);
var l2 = ListTwo
.OrderBy(p => p.ProductID);
bool eo2 = false;
using (var en1 = l1.GetEnumerator())
using (var en2 = l2.GetEnumerator())
{
if (!en1.MoveNext()) { yield break; }
var cur1 = en1.Current;
ProductPurchase cur2 = null;
if (en2.MoveNext())
{
cur2 = en2.Current;
}
else
{
eo2 = true;
}
do
{
int ID = cur1.ProductID;
long qsum = 0;
decimal psum = 0;
decimal min = decimal.MaxValue;
decimal wap = 0;
ProductPurchase minp = null;
while (!eo2 && cur2.ProductID <= ID)
{
if (cur2.ProductID == ID)
{
long quantity = (long)cur2.Quantity * cur2.GlobalQuantity;
var price = cur2.Price;
qsum += quantity;
psum += quantity * price;
if (price < min)
{
minp = cur2;
min = price;
}
}
if (en2.MoveNext())
{
cur2 = en2.Current;
}
else
{
eo2 = true;
}
};
if (qsum != 0)
{
wap = psum / qsum;
}
do
{
yield return new ProductPurchaseOutp()
{
ProductID = cur1.ProductID,
ROQ = cur1.Price,
RUQ = cur1.Quantity,
RPQ = cur1.GlobalQuantity,
RV = cur1.Price * cur1.Quantity * cur1.GlobalQuantity,
BMPProduct = minp,
WAP = wap
};
} while (en1.MoveNext() && (cur1 = en1.Current).ProductID == ID);
if (cur1.ProductID == ID) { yield break; }
} while (true);
}
}
public override List<ProductPurchaseOutp> ComputeMatches()
{
return matched().ToList();
}
}
public class JoinTestClassHashMe : TestClass
{
public override List<ProductPurchaseOutp> ComputeMatches()
{
var l2 = ListTwo
.GroupBy(l => l.ProductID)
.ToDictionary(p => p.Key);
return ListOne
.Select(listOne =>
{
decimal wap = 0;
ProductPurchase minp = null;
if (l2.TryGetValue(listOne.ProductID, out var matches))
{
long qsum = 0;
decimal psum = 0;
decimal min = decimal.MaxValue;
foreach (var m in matches)
{
long quantity = (long)m.Quantity * m.GlobalQuantity;
var price = m.Price;
qsum += quantity;
psum += quantity * price;
if (price < min)
{
minp = m;
min = price;
}
}
if (qsum != 0)
{
wap = psum / qsum;
}
}
return new ProductPurchaseOutp
{
ProductID = listOne.ProductID,
ROQ = listOne.Price,
RUQ = listOne.Quantity,
RPQ = listOne.GlobalQuantity,
RV = listOne.Price * listOne.Quantity * listOne.GlobalQuantity,
BMPProduct = minp,
WAP = wap
};
})
.ToList();
}
}
public static class Extensions
{
public static bool IsEmpty<T>(this IEnumerable<T> source)
{
return !source.Any();
}
}
public class ProductPurchase
{
public int ProductID
{
get;
set;
}
public decimal Price
{
get;
set;
}
public int Quantity
{
get;
set;
}
public int GlobalQuantity
{
get;
set;
}
}
public class ProductPurchaseOutp
{
public int ProductID
{
get;
set;
}
public decimal ROQ
{
get;
set;
}
public int RUQ
{
get;
set;
}
public int RPQ
{
get;
set;
}
public decimal RV
{
get;
set;
}
public ProductPurchase BMPProduct { get; set; }
public decimal WAP { get; set; }
public bool IsEqualTo(ProductPurchaseOutp b)
{
return this.ProductID == b.ProductID
&& this.ROQ == b.ROQ
&& this.RPQ == b.RPQ
&& this.RUQ == b.RUQ
&& this.RV == b.RV
&& this.WAP == b.WAP
&& (this.BMPProduct == null && b.BMPProduct == null ||
this.BMPProduct != null && b.BMPProduct != null
&& this.BMPProduct.GlobalQuantity == b.BMPProduct.GlobalQuantity
&& this.BMPProduct.Price == b.BMPProduct.Price
&& this.BMPProduct.ProductID == b.BMPProduct.ProductID
&& this.BMPProduct.Quantity == b.BMPProduct.Quantity);
}
}
