Não acredito que SortedSet.IsSubsetOf
esteja funcionando como esperado. Dado este código, não deveria ss.IsSubsetOf(l)
retornar True?
Suspeito que o problema esteja na minha CompareTo
função, mas não consigo ver o problema.
Também adicionei um loop separado pensando que o conjunto deveria ser encontrado classificado dentro de other
IEnumerable . . . 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);
}
}
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:
Enquanto o índice do elemento atual é determinado com o seguinte código :
Que posteriormente é usado para marcar bits que representam o índice encontrado:
E
BitHelper
implementaçã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 deBitHelper
resultar em perdas para itens duplicados desequilibrados.A reprodução mínima para mim é a seguinte:
Observe que se você usar o construtor para
SortedSet
o qual resulta em árvore balanceada (com base na implementação), o código funcionará:Demonstração @sharplab.io
O mesmo problema surge para "balanceado" quando o número de elementos é divisível por 32 (tamanho em bits
int
usado nos cálculos). Demonstração @sharblab . E para alguns tamanhos de coleção 64+ eu verifiquei.PS
Alguém relatou o problema @github