What is worth looking into, is whether your
“frontier pair list” variant of mercio/3 has
some merit. It might be an improvement of what
I have posted on comp.lang.prolog 06.08.2025,
by fusing compare_truncs/2 and next_truncs/2
into a single predicate. This is quite possible,
but is it necessary? Does it give some speed
advantage? I guess no, because
you will do next_truncs/2 even when not needed,
when compare_truncs/2 gives (<) or (>). So
my guess your fpl_compare/4 is slower than
this, which has
a fast failure feature builtin-in, no unnecessary
add_pair_of_args/5 if the current level is
different. What one could learn from fpl_compare/4
is doing the code more DCG-ish
and for example fuse zip/3 and append/3.
Mild Shock schrieb:
You have the habit to post incomplete code:
bfs_sort(X, Y):- minimum_coa(X, Is, Mcoa),
My friend, where did you hide the predicate
minimum_coa/3 ? Also its irrelevant to mercio/3
or any frontier method. The TRUNCATIONS are
the same either with
or without a canonical form as input. The
only thing that might be a little faster is
the (==)/2 pretest in mercio/3, and short cuts
like here profit also:
fpl_compare(C, [I-J|F], FPL, FPL0, Mcoa):-
( I = J -> fpl_compare(C, F, FPL, FPL0, Mcoa)
But practically one could also use same_term/2
and gain some speed. But given that minimum_coa/3
can be quite expensive, I don’t count this as the
real mercio/3 sorting method. If sorting is O(N * log(N))
for a fast compare but minimum_coa/3 is O(N^2),
not much is gained, rather contra productive.
Thats basically why bisimiliarity was invented
by Hopcroft and Carp and reported in their 1971
paper to avoid the trap of doing equality via
expensive canonical form.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)