c# - 在C#中设置允许快速插入/删除和随机选择

Question

我可以在 C# 中使用什么数据结构来允许快速插入/删除以及统一随机选择？ List 按元素删除很慢(因为每次都需要找到元素的索引)，而 HashSet 似乎不允许随机选择元素(不复制到列表。)

数据结构会不断更新，所以插入和删除需要在线处理。看来应该有办法让插入、删除、随机选择的复杂度都为O(log n)。

具有分配给对象的任意整数键的二叉搜索树可以解决所有这些问题，但我无法在 C# 标准库中找到合适的类。有没有一种规范的方法可以在不编写自定义二叉搜索树的情况下解决这个问题？

Answer 1

C# BCL 中已经有一个BST，它叫做SortedDictionary<TKey, TValue> ，如果您不想要键值对，而是想要单个项目，则可以使用 SortedSet<T> (SortedSet 在 .NET 4.0 中)。

从你的例子听起来你想要一个 SortedDictionary<int, WhateverValueType> .虽然当你说“均匀随机选择”时，我不确定你到底在追求什么。

当然，Dictionary<TKey, TValue>是 O(1) 这要快得多。因此，除非您需要键的排序顺序，否则我会使用它。

更新:根据您的需求，您将获得关于效率的第 22 条军规。为了能够跳入数据结构中的随机连续索引，您将多久插入/删除一次？如果不经常使用，您可以使用数组并在 (O(n log n)) 之后使用 Sort()，或者始终按顺序插入/删除 (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:从我们的持续讨论来看，如果绝对性能是您的要求，您可能会更幸运地推出自己的产品。不过想想很有趣，如果我想到其他任何事情，我会更新。