我有 2 个包含 Bar 对象的时间序列,每个 Bar 对象包含一个 long 类型的成员变量,每个时间序列都存储在它自己的 BlockingCollection 中。时间序列按 long 值的升序排序。
我想设计一个合并算法,允许我删除包含相对于另一个 BlockingCollection 中相同比较元素的最低值的 long 成员变量的 Bar。
例如,如果BlockingCollection1中第一个Bar(bar1)包含的long值低于BlockingCollection2中第一个Bar(bar2)包含的long值,则Take()从BlockingCollection1和Add()到一个MasterBlockingCollection,基本上以按每个 Bar 的 long 成员变量的值排序的 Bar 对象的合并流结束。
我想稍后扩展到 n 个 BlockingCollections,而不仅仅是 2 个。我尝试使用保存长值的数组以使映射更容易,但我认为在使用与此特定目标算法相关的指针时,数组更方便。
我想知道是否有人可以向我指出 Linq 实现并评论这种方法的计算开销有多大。我问是因为吞吐量很重要,因为有数亿个 Bar 对象流经集合。如果有人有比使用 Linq 更聪明的想法,那将非常受欢迎。前段时间我在 DrDobbs 遇到了一些重新合并算法的想法,但再也找不到这篇文章了。如果现在还不明显,我的目标是 C# (.Net4.0)
非常感谢
编辑:我忘了提到合并过程应该与将新项目添加到阻塞集合(在不同任务上运行)的工作人员同时发生
最佳答案
这是 Merge 的一个实现。它应该在 O(cN) 时间内运行,其中 c 是集合的数量。这是您要找的吗?
public static BlockingCollection<Bar> Merge(IEnumerable<BlockingCollection<Bar>> collections)
{
BlockingCollection<Bar> masterCollection = new BlockingCollection<Bar>();
LinkedList<BarWrapper> orderedLows = new LinkedList<BarWrapper>();
foreach (var c in collections)
OrderedInsert(new BarWrapper { Value = c.Take(), Source = c }, orderedLows);
while (orderedLows.Any())
{
BarWrapper currentLow = orderedLows.First.Value;
orderedLows.RemoveFirst();
BlockingCollection<Bar> collection = currentLow.Source;
if (collection.Any())
OrderedInsert(new BarWrapper { Value = collection.Take(), Source = collection }, orderedLows);
masterCollection.Add(currentLow.Value);
}
return masterCollection;
}
private static void OrderedInsert(BarWrapper bar, LinkedList<BarWrapper> orderedLows)
{
if (!orderedLows.Any())
{
orderedLows.AddFirst(bar);
return;
}
var iterator = orderedLows.First;
while (iterator != null && iterator.Value.Value.LongValue < bar.Value.LongValue)
iterator = iterator.Next;
if (iterator == null)
orderedLows.AddLast(bar);
else
orderedLows.AddBefore(iterator, bar);
}
class BarWrapper
{
public Bar Value { get; set; }
public BlockingCollection<Bar> Source { get; set; }
}
class Bar
{
public Bar(long l)
{
this.LongValue = l;
}
public long LongValue { get; set; }
}
关于c# - Merge 2排序时间序列算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10433203/