Эффективность очень больших коллекций; итерация и сортировка

У меня есть синтаксический анализатор csv, который читает в 15+ миллион строк (со многими дубликатами) и после разбора в структуры должен быть добавлен в коллекцию. Каждая структура имеет свойства Key (int), A (datetime) и B (int) (и другие, которые здесь не актуальны).

Требование A: коллекция должна обеспечить уникальность ключа.

Требование B: На следующем этапе мне нужна коллекция, отсортированная по свойствам A (timestamp), затем B (int).

Ограничение. Структуры в конечном итоге должны проходить по порядку поочередно со ссылками на соседей (здесь LinkedList представляет собой самое чистое решение); точкой этой операции является разбиение множества. Предположим, что это самое раннее, что может произойти разбиение (т.е. Оно не может быть разделено на этапе синтаксического анализа).

Я обнаружил, что SortedSet работает достаточно хорошо для Требования A, и он довольно эффективен, даже если вставки O (log n) намного медленнее, чем с HashSet<T> O (1), хотя мне все равно о сортировке по ключу. HashSet<T> становится увязшим, когда коллекция становится огромной, что, по-видимому, является известной проблемой, в то время как SortedSet<T> не страдает этим недостатком.

Проблема. Когда я SortedSet<T> к шагу для требования B, сортировка коллекции (SortedSet<T> переданная методу как IEnumerable<T>) занимает слишком много времени (20+ минут шлифования, все в памяти, отсутствие использования файла страницы).

Вопрос: Какие коллекции лучше всего подходят для решения этой проблемы? Одна идея состоит в том, чтобы использовать две коллекции: одну для обеспечения уникальности (например, HashSet<int> или SortedSet<int>), а вторую SortedSet<T> - обработку сортировки на этапе синтаксического анализа (т. SortedSet<T> Как можно дальше вверх по течению). Но приложение уже интенсивно использует память, и штрафы за производительность, требуемые для файла подкачки, являются непомерно высокими.
Какие варианты оставляют меня для одной коллекции, которая обеспечивает уникальность по одной характеристике, но сортируется по другим несвязанным характеристикам? SortedSet<T> использует IComparer<T> (но не оба IComparer<T> и IEquitable<T>), поэтому, если он полагается на CompareTo для обеспечения уникальности, то он, похоже, не соответствует моим требованиям. Подклассы SortedSet, как идти?

Ответы

Ответ 1

Это может быть не прямой ответ, но: это способ, которым я успешно использовал аналогичную систему подобного масштаба. Это для "механизма тегов", который управляет списками вопросов здесь в Stack Overflow; По сути, у меня есть:

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

и в основном негабаритный Question[] (на самом деле я использую Question* в неуправляемой памяти, но это потому, что мне нужно иметь возможность делиться им с некоторым графическим процессором для несвязанных причин). Заполнение данных просто выводит последовательные строки в Question[]. Эти данные никогда не сортируются - они оставлены в покое как исходные данные - просто добавляются (новый ключ) или перезаписываются (тот же ключ); в худшем случае нам может потребоваться перераспределение и блокировка данных в новый массив, если мы достигнем максимальной емкости.

Теперь вместо сортировки этих данных я отдельно сохраняю int[] (фактически int* по той же причине, что и раньше, но... meh), где каждое значение в int[] является индексом фактических данных в Question[]. Поэтому изначально это может быть 0, 1, 2, 3, 4, 5,... (хотя я предварительно фильтрую это, поэтому он содержит только строки, которые я хочу сохранить - удаление "удалено" и т.д.).

используя либо модификатор параллельной быстрой сортировки (см. fooobar.com/info/50409/...), либо модифицированный "интроспективный вид" (например, здесь) - так что в конце сортировки у меня могло бы быть 0, 3, 1, 5,...

Теперь: чтобы перебирать данные, я просто перебираю int[] и использую это как поиск фактических данных в Question[]. Это минимизирует количество перемещений данных во время сортировки и позволяет мне очень эффективно сохранять несколько отдельных видов (возможно, с различными предварительными фильтрами). Требуется миллисекунды только для сортировки данных 15M (что происходит каждую минуту или около того, чтобы вносить новые вопросы в Qaru или замечать изменения существующих вопросов).

Чтобы сделать сортировку как можно быстрее, я пытаюсь написать свой код сортировки таким образом, чтобы составной вид мог быть представлен одним целочисленным значением, что позволяет очень эффективную сортировку (можно использовать для интроспективного сортировки). Например, здесь код для "последней даты действия, затем вопрос 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-битное целое число, LastActivityDate слева на 32 бита и составляющее его с Id как 32-битное целое число, что означает, что мы можем сравнить дату и идентификатор в одной операции.

Или для "оценки", затем ответьте на результат, затем 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[] содержит индексы элементов, на которые нужно смотреть.