Closed Krastanov closed 2 months ago
Could you show me your source that explains how Set checks equality? I'm getting the following result:
julia> Set([dagger(X1)]) == Set([dagger(X1)])
false
julia> dagger(X1) == dagger(X1)
false
julia> isequal(dagger(X1), dagger(X1))
true
julia> X1 == X1
true
Ah, the hash changes each time dagger
is called:
julia> hash(X1)
0x00671145608bd477
julia> hash(X1)
0x00671145608bd477
julia> hash(dagger(X1))
0x44e2b6a69704df53
julia> hash(dagger(X1))
0xb846fec1d33c803b
I think a hash is not defined for these objects so it defaults to memory id as hash. Defining a hash function should take care of this (and they have a pretty simple standard definition in this case along the lines of hash(arguments(expr))
(but it should be the two-argument hash)).
we already have
Set uses hashing for quick (potentially false positive) equality check in inclusion (
log(n)
), followed byisequal
check to avoid false positive. Thus set equalities have cost ofn log(n)
instead ofn^2
without the use of a smart datastructure.Initially there was a worry that Set uses
==
, which would have broken its use with Symbolics (where==
is used to create a symbolic equation), but that does not seem to be the case.To avoid creating a new
Set
at every equality check, we should probably have it as part of the structure. E.g.It will take a bit more memory (not much given that the objects are not copied, only referenced), but it should speed up a lot of other code.
pinging @apkille as we had been discussing this in #40