Início / coding / Perguntas / 78465614
Accepted
Vic F
Asked: 2024-05-12 02:05:03 +0800 CST

SortedSet.IsSubsetOf não funciona conforme esperado

  • 772

Não acredito que SortedSet.IsSubsetOfesteja funcionando como esperado. Dado este código, não deveria ss.IsSubsetOf(l)retornar True?

Suspeito que o problema esteja na minha CompareTofunção, mas não consigo ver o problema.

Também adicionei um loop separado pensando que o conjunto deveria ser encontrado classificado dentro de otherIEnumerable . . . mas isso também não funciona.

Alguém pode explicar por que esse comportamento está acontecendo?

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 respostas

  1. Best Answer

    Sim, isso é um bug no SortedSet.

    Pelo que entendi, o código errado é aquele que determina o tamanho do conjunto (que parece ser uma árvore rubro-negra) para depois ser usado como parte de alguma mágica:

    int originalLastIndex = Count;

    Enquanto o índice do elemento atual é determinado com o seguinte código :

    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;
}

    Que posteriormente é usado para marcar bits que representam o índice encontrado:

    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);
        }
    }
    // ...
}

    E BitHelperimplementação.

    O problema é que para casos desequilibrados (ou talvez a matemática do índice não seja "adequada" para tal uso) o índice calculado por InternalIndexOf"estouro" a capacidade de BitHelperresultar em perdas para itens duplicados desequilibrados.

    A reprodução mínima para mim é a seguinte:

    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

    Observe que se você usar o construtor para SortedSeto qual resulta em árvore balanceada (com base na implementação), o código funcionará:

    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);

    Demonstração @sharplab.io

    O mesmo problema surge para "balanceado" quando o número de elementos é divisível por 32 (tamanho em bits intusado nos cálculos). Demonstração @sharblab . E para alguns tamanhos de coleção 64+ eu verifiquei.

    PS

    Alguém relatou o problema @github

    • 10

relate perguntas