mi_key() (src/expected_mi.cpp:156) narrows every block size to uint16_t
before hex-encoding it, so two partitions whose block sizes differ by a multiple
of 65 536 receive the same .ExpectedMICache key and the second one is served
the first one's expected mutual information.
TreeSearch:::mi_key(c(3L, 65597L), c(30L, 31L)) # "0003003d001e001f"
TreeSearch:::mi_key(c(3L, 61L), c(30L, 31L)) # "0003003d001e001f"
TreeSearch:::.ExpectedMI(c(3L, 61L), c(30L, 31L)) # 0.01537134 (correct)
TreeSearch:::.ExpectedMI(c(3L, 65597L), c(30L, 31L)) # 0.01537134 (cached)
expected_mi(c(3L, 65597L), c(30L, 31L)) # 4.044254e-07 (true)
38 000x wrong, silently. ClusteringConcordance(normalize = TRUE) would subtract
that as its chance correction.
Reachability is remote but not nil. A block of 65 536 requires a character
scored across at least 65 536 tips, and ClusteringConcordance() first builds
as.logical(as.Splits(tree)) — 65 533 x 65 536 logicals, 16 GB, which apply()
then copies. So it needs a tree of >= 65 536 tips on a machine with ~32 GB to
spare; runtime extrapolates to ~40 min for five characters. Nobody is hitting
this today. It is worth closing because the failure is silent and unbounded,
and because the fix is confined to the encoder.
uint32_t covers the whole non-negative range of an R integer, and the
int -> uint32_t conversion is injective over all of int, so widening the
encoding makes the collision impossible rather than merely unlikely.
The two sort invariances mi_key() relies on are sound and should stay: over
2 000 random partitions, expected_mi() agrees to 2.8e-13 when the two blocks
of ni are swapped and to 1.5e-15 when nj is permuted.
Found while fixing #91; deliberately left out of that PR because it is
pre-existing and independent.
mi_key()(src/expected_mi.cpp:156) narrows every block size touint16_tbefore hex-encoding it, so two partitions whose block sizes differ by a multiple
of 65 536 receive the same
.ExpectedMICachekey and the second one is servedthe first one's expected mutual information.
38 000x wrong, silently.
ClusteringConcordance(normalize = TRUE)would subtractthat as its chance correction.
Reachability is remote but not nil. A block of 65 536 requires a character
scored across at least 65 536 tips, and
ClusteringConcordance()first buildsas.logical(as.Splits(tree))— 65 533 x 65 536 logicals, 16 GB, whichapply()then copies. So it needs a tree of >= 65 536 tips on a machine with ~32 GB to
spare; runtime extrapolates to ~40 min for five characters. Nobody is hitting
this today. It is worth closing because the failure is silent and unbounded,
and because the fix is confined to the encoder.
uint32_tcovers the whole non-negative range of an R integer, and theint->uint32_tconversion is injective over all ofint, so widening theencoding makes the collision impossible rather than merely unlikely.
The two sort invariances
mi_key()relies on are sound and should stay: over2 000 random partitions,
expected_mi()agrees to 2.8e-13 when the two blocksof
niare swapped and to 1.5e-15 whennjis permuted.Found while fixing #91; deliberately left out of that PR because it is
pre-existing and independent.