3 ms·
Worst case is probably something like Warshall's algorithm (in-place mutation of a bit matrix for optimum performance). See warshall.c in BYacc or lib/bitsetv.c
by rbehrends 13y ago
Worst case is probably something like Warshall's algorithm (in-place mutation of a bit matrix for optimum performance). See warshall.c in BYacc or lib/bitsetv.c in Bison (relevant part reproduced below).
void
bitsetv_transitive_closure (bitsetv bsetv)
{
bitset_bindex i;
bitset_bindex j;
for (i = 0; bsetv[i]; i++)
for (j = 0; bsetv[j]; j++)
if (bitset_test (bsetv[j], i))
bitset_or (bsetv[j], bsetv[j], bsetv[i]);
}
While the algorithm can obviously be reproduced in a functional language, it does rely on destructive updates for its performance.
- judk 13y agoThis is why Haskell (ST) and Clojure (transients) provide local mutable state in the form of "linear types" where it is impossible to read a mutable value outside of tightly controlled conditions. As Guy Steele wrote, "Lambda, the ultimate imperative"