AngouriMath
SortHash(AngouriMath.Functions.TreeAnalyzer.SortLevel)
Method (no overloads)
Summary
Hash that is convenient to sort with
Remarks
Spelt once per instance and level, as InnerSimplified and
SimplifiedRate are computed once. The key of a node is built out of the
keys of every node below it, and the sort asks for the key of every operand of every
chain it orders, so without the memo one sort of a tree walked and re-spelt each
subtree once per ancestor -- and the simplifier sorts what it registers at every pass.
OnSimplifyHard that was 174 MB of one run's 735, some 2.6 MB per sort of a
tree a few hundred nodes wide. A candidate shares most of its subtrees with the
candidates before it, and a shared subtree's key is now spelt once.
Three things about the shape of the memo, each measured. It is one reference per node
and an array made on the first sort, not a lazy slot per level: three slots cost
every node some fifty bytes, which the gate saw as +4-6% on every solve and derivative
entry for a saving only the sort ever sees. It is on the instance and not in a
dictionary kept for the run: keyed by reference the dictionary saved the same bytes
and cost a lookup per node per sort, 369 ms against 266 for the same input. And the
array names its owner, because awith copy -- WithCodomain(AngouriMath.Core.Domain), a
re-differentiation -- carries the original's fields while a number's key spells its
codomain: a copy finds an array that is not its own and starts one of its own.
https://github.com/asc-community/AngouriMath/issues/746
SimplifiedRate are computed once. The key of a node is built out of the
keys of every node below it, and the sort asks for the key of every operand of every
chain it orders, so without the memo one sort of a tree walked and re-spelt each
subtree once per ancestor -- and the simplifier sorts what it registers at every pass.
On
tree a few hundred nodes wide. A candidate shares most of its subtrees with the
candidates before it, and a shared subtree's key is now spelt once.
and an array made on the first sort, not a lazy slot per level: three slots cost
every node some fifty bytes, which the gate saw as +4-6% on every solve and derivative
entry for a saving only the sort ever sees. It is on the instance and not in a
dictionary kept for the run: keyed by reference the dictionary saved the same bytes
and cost a lookup per node per sort, 369 ms against 266 for the same input. And the
array names its owner, because a
re-differentiation -- carries the original's fields while a number's key spells its
codomain: a copy finds an array that is not its own and starts one of its own.
https://github.com/asc-community/AngouriMath/issues/746
Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4862 pages online