День 1174. #ЗаметкиНаПолях #AsyncTips
Неизменяемые множества

Задача: нужна структура данных, не рассчитанная на хранение дубликатов, которая не слишком часто изменяется и допускает безопасные обращения из нескольких потоков. Например, индекс слов из файла может быть хорошим кандидатом для применения множества.

Решение
Существует два типа неизменяемых множеств: ImmutableHashSet<T> — коллекция уникальных элементов и ImmutableSortedSet<T> — отсортированная коллекция уникальных элементов. Эти типы из пространства имён System.Collections.Immutable обладают похожим интерфейсом:

var hs = ImmutableHashSet<int>.Empty;
hs = hs.Add(13);
hs = hs.Add(7);
// Выводит "7" и "13" в непредсказуемом порядке

foreach (int item in hs)
  Console.WriteLine(item);

hs = hs.Remove(7);

Отсортированное множество допускает индексирование по аналогии со списком:

var shs = ImmutableSortedSet<int>.Empty;
shs = shs.Add(13);
shs = shs.Add(7);
// Выводит "7", затем "13"

foreach (int item in shs)
  Console.WriteLine(item);

int smallest = shs[0]; // 7
shs = shs.Remove(7);

Несортированные и отсортированные множества обладают схожим быстродействием: O(log N) для добавления, удаления. Важное примечание: обращение по индексу в сортированном множестве также выполняется за время O(log N), а не O(1), как и у ImmutableList<T>. Это означает, что в данной ситуации действует та же рекомендация: используйте foreach вместо for там, где это возможно.

Рекомендую использовать несортированное множество, если только вы не уверены в том, что оно должно быть отсортированным. Это позволит использовать неизменяемое множество в большем количестве ситуаций.

Неизменяемые множества полезны, но заполнение большого неизменяемого множества может быть медленной операцией. У многих неизменяемых коллекций имеются специальные построители, которые могут использоваться для быстрого их построения в изменяемом виде с последующим преобразованием в неизменяемую коллекцию. Это относится ко многим неизменяемым коллекциям, но, на мой взгляд, они особенно полезны для неизменяемых множеств.

См. также:
- Неизменяемые стеки и очереди
- Неизменяемые списки

Источник: Стивен Клири “Конкурентность в C#”. 2-е межд. изд. — СПб.: Питер, 2020. Глава 9.