非常大的收藏效率; 迭代和排序

Question

我有一个csv解析器读取超过1500万行(有许多重复),一旦解析成结构,需要添加到集合中.每个结构都有属性Key(int),A(datetime)和B(int)(以及其他与此无关的属性).

要求A:集合需要通过密钥强制执行唯一性.

要求B:在后面的步骤中,我需要按属性A(时间戳)和B(int)排序的集合.

约束:结构最终需要逐个遍历,并引用邻居(LinkedList在这里提供最干净的解决方案); 此操作的重点是对集合进行分区.请假设这是最早发生分区的(即,它不能在解析阶段进行分区).

我发现SortedSet在需求A中工作得很好,并且它也非常高效,即使O(log n)插入比使用HashSet<T>O(1)慢得多,尽管我不关心排序关键. HashSet<T>当集合变得庞大时,它会陷入困境,这显然是一个已知的问题,而SortedSet<T>不会遇到这个缺点.

问题:当我到达需求B的步骤时,对集合进行排序(SortedSet<T>传递给方法IEnumerable<T>)需要花费大量时间(磨削20分钟以上,所有内存中,没有页面文件使用).

问题:哪个(哪些)集合最适合解决此问题？一个想法是使用两个集合:一个用于强制唯一性(如一个HashSet<int>或SortedSet<int>一个键),另一个SortedSet<T>用于在解析阶段处理排序(即,尽可能向上游).但是应用程序已经占用大量内存,并且需要页面文件的性能损失令人望而却步.
对于一个通过一个特征强制实现唯一性但通过其他不相关特征排序的集合,我有什么选择？ SortedSet<T>使用IComparer<T>(但不能同时IComparer<T>和IEquitable<T>),所以如果它依靠的CompareTo强制唯一性,那么它似乎不适合我的要求.是继承SortedSet的方法吗？

编辑:排序代码:

SortedSet<Dto> parsedSet = {stuff};
var sortedLinkedStructs = new LinkedList<Dto>(parsedSet.OrderBy(t => t.Timestamp).ThenBy(i => i.SomeInt));

结构:

public readonly struct Dto: IEquatable<Dto>, IComparer<Dto>, IComparable<Dto>
{
     public readonly datetime Timestamp;
     public readonly int SomeInt;
     public readonly int Key;

     ctor(ts, int, key){assigned}

     public bool Equals(Dtoother) => this.Key == other.Key;
     public override int GetHashCode() => this.Key.GetHashCode();
     public int Compare(Dto x, Dto y) =>  x.Key.CompareTo(y.Key);
     public int CompareTo(Dto other) => this.Key.CompareTo(other.Key);
}

Answer 1

这可能不是一个直接的答案,但是:这是我成功用于类似规模的类似系统的一种方式.这是用于驱动Stack Overflow上的问题列表的"标记引擎"; 基本上,我有一个:

struct Question {
    // basic members - score, dates, id, etc - no text
}

并且基本上是一个超大的Question[](实际上我Question*在非托管内存中使用a ,但这是因为我需要能够与一些GPU代码共享它出于无关的原因).填充数据只是取出连续的行Question[].这个数据永远不会被排序 - 它只是作为源数据保留 - 只需附加(新密钥)或覆盖(相同密钥); 在最坏的情况下,如果达到最大容量,我们可能需要将数据重新分配并阻塞复制到新阵列.

现在,而不是整理这些数据,我分别保持了int[](实际上int*出于同样的原因和以前一样,但是... MEH),其中在每个值int[]是指数中的实际数据Question[].所以最初它可能是0, 1, 2, 3, 4, 5, ...(虽然我预先过滤它,所以它只包含我想要保留的行 - 删除"删除"等).

使用两种改性剂并行快速排序(见http://stackoverflow.com/questions/1897458/parallel-sort-algorithm)或修改的"内省排序"(喜欢这里) -所以在排序结束后,我可能有0, 3, 1, 5, ....

现在:迭代数据,我只是遍历int[],并使用它作为查找实际数据Question[].这最大限度地减少了排序期间的数据移动量,并允许我非常有效地保留多个单独的排序(可能具有不同的预过滤器).仅需要几毫秒来对15M数据进行排序(每分钟左右发生一次,以便将新问题引入Stack Overflow,或者记录对现有问题的更改).

为了尽可能快地进行排序,我尝试编写排序代码,使得复合排序可以由单个整数值表示,从而允许非常有效的排序(可以通过内省排序使用).例如,这里是"最后活动日期,然后问题ID"的代码排序:

public override bool SupportsNaturallySortableUInt64 => true;
public override unsafe ulong GetNaturallySortableUInt64(Question* question)
{
    // compose the data (MSB) and ID (LSB)
    var val = Promote(question->LastActivityDate) << 32
        | Promote(question->Id);
    return ~val; // the same as ulong.MaxValue - val (which reverses order) but much cheaper
}

这可以通过将LastActivityDate32位整数处理,左移32位并将其与Id32位整数组合,这意味着我们可以在单个操作中比较日期和id.

或者为"得分,然后回答得分,然后是id":

public override unsafe ulong GetNaturallySortableUInt64(Question* question)
{
    // compose the data
    var val = Promote(question->Score) << 48
        | Promote(question->AnswerScore) << 32
        | Promote(question->Id);
    return ~val; // the same as ulong.MaxValue - val (which reverses order) but much cheaper
}

请注意,GetNaturallySortableUInt64每个元素只调用一次 - 进入相同大小的ulong[](是,实际上是a ulong*)的工作区域,因此最初两个工作区类似于:

int[]    ulong[]
0        34243478238974
1        12319388173
2        2349245938453
...      ...

现在我可以通过查看a int[]和a 来完成整个排序ulong[],使得ulong[]向量以排序顺序结束,并int[]包含要查看的项的索引.