是否有Python设计决策(PEP)阻止将已排序的容器添加到Python中？
(OrderedDict不是已排序的容器,因为它是按插入顺序排序的.)
我有一个使用Comparable <>定义'自然排序顺序'的对象.这些存储在TreeSet中.
除了删除和重新添加对象之外,还有另一种方法可以在更新用于定义排序顺序的成员时更新排序吗？
在.NET 4.0+中,类SortedSet<T>有一个名为的方法GetViewBetween(l, r),它返回树部件上的接口视图,其中包含指定的两个之间的所有值.鉴于它SortedSet<T>是作为红黑树实现的,我自然希望它能够及时运行O(log N).C++中的类似方法是std::set::lower_bound/upper_boundJava TreeSet.headSet/tailSet,它们是对数的.
然而,事实并非如此.以下代码在32秒内运行,而等效O(log N)版本GetViewBetween将使该代码在1-2秒内运行.
var s = new SortedSet<int>();
int n = 100000;
var rand = new Random(1000000007);
int sum = 0;
for (int i = 0; i < n; ++i) {
s.Add(rand.Next());
if (rand.Next() % 2 == 0) {
int l = rand.Next(int.MaxValue / 2 - 10);
int r = l + rand.Next(int.MaxValue / 2 - 10);
var t = s.GetViewBetween(l, …我有一个csv解析器读取超过1500万行(有许多重复),一旦解析成结构,需要添加到集合中.每个结构都有属性Key(int),A(datetime)和B(int)(以及其他与此无关的属性).
要求A:集合需要通过密钥强制执行唯一性.
要求B:在后面的步骤中,我需要按属性A(时间戳)和B(int)排序的集合.
约束:结构最终需要逐个遍历,并引用邻居(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 …我正在使用a TreeSet<Integer>,我只是想在集合中找到数字的索引.有没有一种很好的方法来实际使用二叉树的O(log(n))复杂度？
(如果没有,我该怎么做,有谁知道为什么不呢？我很好奇为什么这样的类会被包含在Java中而没有类似搜索功能的东西.)
MSDN声明以下SortedSet(T).Add方法:
如果Count小于内部阵列的容量,则此方法是O(1)操作.
有人可以解释"怎么样"？我的意思是在添加新值时,我们需要找到一个正确的位置来添加一个值(将其与另一个值进行比较),内部实现看起来像一个具有O(log N)插入复杂度的"红黑树".
如果我有一个Ints列表,如:
val myList = List(3,2,1,9)
从List或Seq of Ints创建SortedSet的正确/首选方法是什么,其中项目从最小到最大排序？
如果你把枪拿到我头上,我会说:
val itsSorted = collection.SortedSet(myList)
但是我得到一个错误,即没有为List [Int]定义隐式排序.
我需要一个关于如何在a上使用类似的类HashSet来获得升序的示例.假设我有HashSet这样一个:
HashSet<String> hs = new HashSet<String>();
我怎样才能hs按升序排列？
TreeSet将元素放入SortedSet或提供NavigableSet?.
A NavigableSets也使元素保持自然顺序
但他们和他们之间有什么区别 TreeSet
哪里SortedSet有用？一些示例显示它的使用对初学者来说会很好.
我对SortedSet的行为有点疑惑,请看下面的例子:
public class Blah
{
public double Value { get; private set; }
public Blah(double value)
{
Value = value;
}
}
public class BlahComparer : Comparer<Blah>
{
public override int Compare(Blah x, Blah y)
{
return Comparer<double>.Default.Compare(x.Value, y.Value);
}
}
public static void main()
{
var blahs = new List<Blah> {new Blah(1), new Blah(2),
new Blah(3), new Blah(2)}
//contains all 4 entries
var set = new HashSet<Blah>(blahs);
//contains only Blah(1), Blah(2), Blah(3)
var sortedset = new SortedSet<Blah>(blahs, new BlahComparer()); …