Pandas Aggregation in Prolog

General
19

I don’ have tries in my system. But I recently introduced Okasaki tree,
but it turned out that they are totally useless. What works better in
my case was hash+keysort, as strange as it may sound.

I believe it depends on the grouping factor. If there is a high
grouping factor there is higher precentage of read from the
grouping datastructure and than write into the grouping datastructure.

So if read is only O(1) as in hash, you have better performance
than if read is O(log N) as in tree. And you can also afford a later
keysort. Here is the bagof/3 choker with hash+keysort compared to tree:

/* Dogelog Player 1.2.5, tree */
?- time(test3).
% Zeit 6073 ms, GC 1 ms, Lips 5182931, Uhr 10.11.2024 00:58
true.

/* Dogelog Player 1.2.5, hash+keysort */
?- time(test4).
% Zeit 3070 ms, GC 2 ms, Lips 9808736, Uhr 10.11.2024 00:58
true.

Quite amazing, if we compare to the traditional bagof/3:

/* Trealla Prolog 2.59.17, keysort */
?- time(test).
% Time elapsed 13.280s, 16158649 Inferences, 1.217 MLips
   true.

Edit 10.11.2024
How did I solve the variant key problem, which is present in the
bagof/3 choker? I went with numbervars/3 and unnumbervars/3.
But most likely if tries are used for tabling, they can already do the

same. I was looking a little bit at your trie_insert() C implementation
used in distinct/1. It seems distinct/1 can solve the variant key problem
by means of trie_insert/2 alone, since for ordinary terms it uses a no-op:

trieable(Term, ForTrie) :-
    acyclic_term(Term),
    term_attvars(Term, []),
    !,
    ForTrie = t(Term).

Not sure what is needed to enumerate variant key, turn them
back into ordinary terms together with the associated values.
I am also using the nb_linkarg/3 trick for findall/3 inside bagof/3.

So the values are basically these single linked lists. The same
approach for bagof/3, is also suitable for aggregate/3.