主页 / coding / 问题 / 78465614
Accepted
Vic F
Asked: 2024-05-12 02:05:03 +0800 CST

SortedSet.IsSubsetOf 未按预期工作

  • 772

我不相信这SortedSet.IsSubsetOf会按预期工作。给出这段代码，不应该ss.IsSubsetOf(l)返回 True 吗？

我怀疑问题出在我的CompareTo函数中，但我看不到问题所在。

我还添加了一个单独的循环，认为必须在otherIEnumerable 内找到该集合并进行排序。。。但这也行不通。

谁能解释为什么会发生这种行为？

List<Point> l = new();
SortedSet<Point> ss = new();
HashSet<Point> h = new();

for (int i = 0; i < 100; i++)
{
    var p = new Point(i, i);
    l.Add(p);
    l.Add(p);
    h.Add(p);
    h.Add(p);
    ss.Add(p);
    ss.Add(p);
}

// additional loop to get a sorted set.
for (int i = 0; i < 100; i++)
{
    l.Add(new Point(i, i));
}

Console.WriteLine(l.Count); // 300
Console.WriteLine(h.Count); // 100
Console.WriteLine(ss.Count); // 100
Console.WriteLine(h.IsSubsetOf(l));  // True (as expected)
Console.WriteLine(h.IsProperSubsetOf(l)); // False

// This is the line in question
Console.WriteLine(ss.IsSubsetOf(l)); // False ?????????

Console.WriteLine(ss.IsProperSubsetOf(l)); // False

readonly struct Point : IComparable<Point>, IEquatable<Point>
{
    public Point(double x, double y)
    {
        X = x;
        Y = y;
    }

    public double X { get; }
    public double Y { get; }

    public int CompareTo(Point other)
    {
        if (X == other.X)
        {
            return Y.CompareTo(other.Y);
        }
        else
        {
            return X.CompareTo(other.X);
        }
    }

    public bool Equals(Point other)
    {
        return X == other.X && Y == other.Y;
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(X, Y);
    }
}
c#

1 个回答

  1. Best Answer

    是的，这是SortedSet.

    据我了解，错误的代码是确定集合（似乎是一棵红黑树）大小的代码，稍后将用作某些位魔法的一部分：

    int originalLastIndex = Count;

    而当前元素的索引是通过以下代码确定的：

    internal virtual int InternalIndexOf(T item)
{
    Node? current = root;
    int count = 0;
    while (current != null)
    {
        int order = comparer.Compare(item, current.Item);
        if (order == 0)
        {
            return count;
        }

        current = order < 0 ? current.Left : current.Right;
        count = order < 0 ? (2 * count + 1) : (2 * count + 2);
    }

    return -1;
}

    稍后用于标记表示遇到的索引的位：

    int intArrayLength = BitHelper.ToIntArrayLength(originalLastIndex);

Span<int> span = stackalloc int[StackAllocThreshold];
BitHelper bitHelper = intArrayLength <= StackAllocThreshold ?
    new BitHelper(span.Slice(0, intArrayLength), clear: true) :
    new BitHelper(new int[intArrayLength], clear: false);

// ...

foreach (T item in other)
{
    int index = InternalIndexOf(item);
    if (index >= 0)
    {
        if (!bitHelper.IsMarked(index))
        {
            // item hasn't been seen yet
            bitHelper.MarkBit(index);
        }
    }
    // ...
}

    并BitHelper实施。

    问题是，对于不平衡的情况（或者索引数学可能不“适合”这种用法），通过InternalIndexOf“溢出”计算的索引会BitHelper导致不平衡的重复项丢失。

    对我来说最小的重现如下：

    SortedSet<int> ss = new();
HashSet<int> h = new();

var num = 18;
for (int i = 0; i < num; i++)
{
    h.Add(i);
    ss.Add(i);
}

var data = Enumerable.Range(0, num).Append(17);
var hashSetEquals = h.SetEquals(data); // True
var sortedSetEquals = ss.SetEquals(data); // False

    SortedSet请注意，如果您使用导致平衡（基于实现）树的构造函数，则代码将起作用：

    HashSet<int> h = new();
var num = 18;
for (int i = 0; i < num; i++)
{
    h.Add(i);
}
SortedSet<int> ss = new(h); // will balance the tree
var data = Enumerable.Range(0, num).Append(17);
var hashSetEquals = h.SetEquals(data);
var sortedSetEquals = ss.SetEquals(data);

    演示@sharplab.io

    当元素数量可以被 32（int计算中使用的位大小）整除时，“平衡”也会出现同样的问题。演示@sharplab。对于一些 64+ 大小的集合，我已经检查过。

    聚苯乙烯

    有人已经报告了这个问题@github

    • 10

相关问题