非常大的集合的效率；迭代和排序

Question

我有一个 csv 解析器，它读取 15+ 百万行（有很多重复项），一旦解析为结构，就需要添加到集合中。每个结构都有属性 Key (int)、A(datetime) 和 B(int)（以及此处不相关的其他属性）。

要求 A： 集合需要通过 Key 强制唯一性。

要求 B: 在后面的步骤中，我需要按属性 A(timestamp) 然后 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 上驱动问题列表的 "tag engine"；本质上，我有一个：

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

和基本上一个超大的Question[]（实际上我在非托管内存中使用Question*，但那是因为我需要能够与一些 GPU 代码出于不相关的原因）。填充数据只是取出 Question[] 中的连续行。此数据永远不会排序 - 它作为源数据单独保留 - 只需附加（新键）或覆盖（相同键）； 在最坏的情况下如果我们达到最大容量，我们可能需要重新分配数据并将数据块复制到新数组。

现在，我单独保留一个 int[]（实际上 int* 的原因与之前相同，但... meh），其中 int[] 中的每个值都是 Question[] 中 actual 数据的 index。所以最初它可能是 0, 1, 2, 3, 4, 5, ...（虽然我预先过滤了它，所以它只包含我想保留的行 - 删除 "deleted" 等）。

使用或者修饰符并行快速排序（参见) or a modified "introspective sort" (like here）——所以在排序结束时，我可能有0, 3, 1, 5, ....

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

为了尽可能快地进行排序，我尝试编写我的排序代码，以便可以用单个整数值表示复合排序，从而实现非常有效的排序（内省排序可用）。例如，下面是 "last activity date, then question 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
}

这通过将 LastActivityDate 视为 32 位整数，左移 32 位并将其与 Id 组合为 32 位整数来工作，这意味着我们可以比较日期和 id 在一次操作中。

或 "score, then answer score, then 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[]（是的，实际上是 ulong*）的工作区域，因此最初两个工作区类似于：

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

现在我可以通过只查看一个 int[] 和一个 ulong[] 来完成整个排序，这样 ulong[] 向量就会按排序顺序结束，而 int[] 包含要查看的项目的索引。

非常大的集合的效率；迭代和排序

Efficiency of very large collections; iteration and sort

c#

sorting

sortedset