Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #14768

Perfectly balanced , as all things should be! (Was: Should we use minimum_coa/3 ?)

Show all headers | View raw

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.

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Mercio’s Algorithm for Rational Tree Compare in Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-04 02:52 +0200
  The Original Ganster (OG) of Gameification: IEEE 1044.1-1995 (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-04 13:48 +0200
    The Bitrot called Math Stack Exchange (Re: The Original Ganster (OG) of Gameification: IEEE 1044.1-1995) Mild Shock <janburse@fastmail.fm> - 2025-08-04 14:00 +0200
      I guess its back to Hopcroft and Karp.Re: The Bitrot called Math Stack Exchange) Mild Shock <janburse@fastmail.fm> - 2025-08-04 14:11 +0200
  Szpilrajn Theorem and Suzumura Consistency (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-06 01:50 +0200
    The good thing is we have at least Mercio’s Algorithm (Re: Szpilrajn Theorem and Suzumura Consistency) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:10 +0200
      Hopcroft and Karp’s is just Contraction (Was: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:13 +0200
        Re: Hopcroft and Karp’s is just Contraction (Was: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:23 +0200
      Should we use minimum_coa/3 ? (Was: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-08 23:45 +0200
        Perfectly balanced , as all things should be! (Was: Should we use minimum_coa/3 ?) Mild Shock <janburse@fastmail.fm> - 2025-08-08 23:49 +0200
  Mercios decidability was already attested in 2012 (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-14 20:26 +0200
    Performance of Mercio’s Total Order (Was: Mercios decidability was already attested in 2012) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:49 +0200
      Fuzzy Testing is your Swiss Knife (Re: Performance of Mercio’s Total Order) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:55 +0200
        Yeah, we have another name! (Was: Fuzzy Testing is your Swiss Knife) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:38 +0200
        Monte Carlo sampling the frontier version (Was: Yeah, we have another name!) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:42 +0200
        AI most hated by formal verification (Was: Fuzzy Testing is your Swiss Knife) Mild Shock <janburse@fastmail.fm> - 2025-11-26 17:02 +0100
  An NPU could give 1000x more LIPS (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-11-27 14:19 +0100
    Neural Network based dif/2 respectively (#\=)/2 (Re: An NPU could give 1000x more LIPS) Mild Shock <janburse@fastmail.fm> - 2025-11-27 14:51 +0100
      Zeus: A Language for Expressing Algorithms in Hardware (Re: Neural Network based dif/2 respectively (#\=)/2) Mild Shock <janburse@fastmail.fm> - 2025-11-27 15:03 +0100
        Googles TPU muscle in 2017 [Prolog Community is Sleepy Joe] (Re: Zeus: A Language for Expressing Algorithms in Hardware) Mild Shock <janburse@fastmail.fm> - 2025-11-27 15:23 +0100
    100% serious Giga Logical Inferences per Second (GLIPS) (Was: An NPU could give 1000x more LIPS) Mild Shock <janburse@fastmail.fm> - 2025-11-28 14:50 +0100
      The tables have turned: GigaLIP on the Laptop? (Re: 100% serious Giga Logical Inferences per Second (GLIPS) Mild Shock <janburse@fastmail.fm> - 2025-11-28 15:12 +0100

csiph-web