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

要求 A:集合需要通过键强制唯一性。

要求 B:在后面的步骤中，我需要按属性 A(时间戳)然后 B(整数)对集合进行排序。

约束结构最终需要按顺序遍历，一个接一个，并引用邻居(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);
}

最佳答案

这可能不是一个直接的答案，但是:这是我在类似规模的类似系统中成功使用的一种方式。这是用于在 Stack Overflow 上驱动问题列表的“标签引擎”；本质上，我有一个:

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

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

现在，我没有对数据进行排序，而是单独保留一个int[](实际上是int*，原因与之前相同，但是...嗯)，其中 int[] 中的每个值都是 Question[ 中实际数据的索引 ]。所以最初它可能是 0, 1, 2, 3, 4, 5, ...(虽然我预先过滤了这个，所以它只包含我想保留的行 - 删除“删除”等)。

使用 或者 修改器并行快速排序(参见 http://stackoverflow.com/questions/1897458/parallel-sort-algorithm )或修改后的“内省(introspection)排序”(如 here ) - 所以在排序结束时，我可能有 0, 3, 1, 5, ...。

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

为了尽可能快地进行排序，我尝试编写我的排序代码，以便可以用单个整数值表示复合排序，从而实现非常有效的排序(可用于内省(introspection)排序).例如，这里是“最后一个事件日期，然后是问题 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 位并将其与作为 32 位整数的 Id 组合，这意味着我们可以在单个操作中比较日期和 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[] 的工作区域(是的，实际上是 ulong* ) 大小相同，所以最初这两个工作区是这样的:

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

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

关于c# - 非常大的集合的效率；迭代和排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48345753/