Установка, позволяющая быструю вставку / удаление и случайный выбор в C #

Question

Какую структуру данных я могу использовать в C #, чтобы обеспечить быструю вставку / удаление, а также равномерный случайный выбор?Список медленно удаляется по элементам (поскольку ему необходимо каждый раз находить индекс элемента), в то время как HashSet, по-видимому, не допускает случайного выбора элемента (без копирования в список).

структура данных будет постоянно обновляться, поэтому вставка и удаление должны выполняться в режиме онлайн.Кажется, что должен быть способ сделать вставку, удаление и случайный выбор всех O (log n).

Бинарное дерево поиска с произвольными целочисленными ключами, назначенными объектам, решило бы все эти проблемы,но я не могу найти соответствующий класс в стандартной библиотеке C #.Есть ли канонический способ решить эту проблему без написания собственного бинарного дерева поиска?

Answer 1

Двоичные деревья поиска и производные структуры, такие как SortedDictionary или SortedSet, работают с помощью , сравнивая ключи.

Ваши объекты сами по себе несопоставимы, но они предлагают идентичность объекта и значение хеш-функции.Следовательно, HashSet - это правильная структура данных.Примечание: A Dictionary<int,YourType> не подходит, потому что удаление становится линейным поиском (O (n)) и не решает случайную проблему после удаления.

• Вставка - O (1)
• Удалить - O (1)

• Случайный элемент - O (n).Его легко реализовать, например,

  set.ElementAt(random.Next(set.Count))
  

  Копирование в промежуточный список не требуется.

Answer 2

В C # BCL уже есть BST, он называется SortedDictionary<TKey, TValue>, если вам не нужны пары значений ключей, но вместо этого вам нужны отдельные элементы, вы можете использовать SortedSet<T> (SortedSet находится в .NET 4.0 ).

Звучит так, будто из вашего примера вы хотите SortedDictionary<int, WhateverValueType>. Хотя я не совсем уверен, что вы ищете, когда говорите «равномерный случайный выбор».

Конечно, Dictionary<TKey, TValue> - это O (1), что намного быстрее. Поэтому, если вам не нужен отсортированный порядок ключей, я бы использовал это.

ОБНОВЛЕНИЕ : Судя по вашим потребностям, вы поймете, как повысить эффективность. Как часто вы будете вставлять / удалять, чтобы иметь возможность перейти к случайному смежному индексу в структуре данных? Если не часто, вы можете использовать массив и просто Sort () после (O (n log n)), или всегда вставлять / удалять по порядку (O (n)).

Или вы можете обернуть Dictionary<int, YourType> и сохранить параллель List<int> и обновлять его после каждого добавления / удаления:

_dictionary.Add(newIndex, newValue);
_indexes.Add(newIndex);

А затем просто получите случайный индекс из списка при поиске. Приятно то, что в этом методе действительно Add () будет ~ O (1) (если только List не изменяет размеры, но вы можете установить начальную емкость, чтобы избежать некоторых из этого), но вы бы понесли затраты O (n) на удаление .

Боюсь, проблема в том, что вы либо жертвуете временем при поиске, либо при удалении / вставке. Проблема в том, что все лучшие контейнеры времени доступа не являются смежными. Однако с двойной комбинацией List<int>/Dictionary<int, YourValue> вы получите довольно хороший микс.

ОБНОВЛЕНИЕ 2 : По нашему постоянному обсуждению звучит так, что, если это абсолютное качество - ваше требование, вам, возможно, повезет больше. Хотя было интересно подумать, я обновлю, если что-нибудь еще придумаю.

Answer 3

Я понимаю, что этому вопросу более 3 лет, но только для людей, которые сталкиваются с этой страницей:

Если вам не нужно сортировать элементы в наборе данных, вы можете просто использовать List<ItemType>.

Вставка и случайный выбор O (1). Вы можете сделать удаление в O (1), просто переместив последний элемент в положение элемента, который вы хотите удалить, и удалив его с конца.

Код:

using System; // For the Random
using System.Collections.Generic; // The List

// List:
List<ItemType> list = new List<ItemType>();

// Add x:
ItemType x = ...; // The item to insert into the list
list.Add( x );

// Random selection
Random r = ...; // Probably get this from somewhere else
int index = r.Next( list.Count );
ItemType y = list[index];

// Remove item at index
list[index] = list[list.Count - 1]; // Copy last item to index
list.RemoveAt( list.Count - 1 ); // Remove from end of list

РЕДАКТИРОВАТЬ: Конечно, чтобы удалить элемент из List<ItemType>, вам нужно знать его индекс. Если вы хотите удалить случайный элемент, вы можете использовать случайный индекс (как это сделано в примере выше). Если вы хотите удалить данный элемент, вы можете оставить Dictionary<ItemType,int>, который сопоставляет элементы с их индексами. Добавление, удаление и обновление этих индексов может быть выполнено в O (1) (амортизировано).

Вместе это приводит к сложности O (1) (амортизируется) для всех операций.