Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Mild Shock <janburse@fastmail.fm> |
|---|---|
| Newsgroups | sci.math |
| Subject | Hopcroft and Karp’s is just Contraction (Re: The good thing is we have at least Mercio’s Algorithm) |
| Date | 2025-08-06 08:16 +0200 |
| Message-ID | <106urv9$3c5n2$6@solani.org> (permalink) |
| References | <106p0ct$3b6se$3@solani.org> <106u5h7$3bpia$3@solani.org> <106uria$3c5n2$2@solani.org> |
How could we speed it up any further. Well we can make at least the following observation. Let A and B be two lists of truncation pairs. Capital greek letters denote sublists: A = Γ, P, Δ, P, Π B = Γ, P, Δ, Π Then mercio2_iter(A) gives the same comparison like the shorter mercio2_iter(B). The truncation leafs obey a contraction law. So if we find methods to get smaller pair lists, then I guess we will also get faster Mercio’s Algorithm implementation. Possible methods to contract the pair list are at least either Naive HK based on same_term/2 or Non-Naive HK based on same_term/2: Hopcroft and Karp’s algorithm (HK) https://inria.hal.science/hal-00639716v2 But there is a twist, which stuns me, how to make contraction between levels? Is such an inter level optimization even somehow defined? It seems levels are still copied during expansion? Mild Shock schrieb: > > The good thing is we have at least Mercio’s > Algorithm. This can be used for Total Order Sorting > of Prolog terms, cyclic and acyclic. But how speed > > it up? Here is a take. The idea is sketched as follows: > > Sketch to determine (<) or (>): > > 1. Use a list of pairs. These are the leafs of > a truncation. > 2. Compare this list, if the result > differs from (=) you are done. > 3. Expand the list of pairs to get a new level, > and continue with step 1. > > The Prolog code reads as follows: > > Step 1: > > compare_truncs(C, []) :- !, C = (=). > compare_truncs(C, [X-Y|_]) :- > trunc(X, A), > trunc(Y, B), > compare(D, A, B), > D \== (=), !, C = D. > compare_truncs(C, [_|L]) :- > compare_truncs(C, L). > > trunc(X, A) :- var(X), !, A = X. > trunc(X, F/N) :- functor(X, F, N). > > Step 2: > > next_truncs([], []). > next_truncs([X-_|L], R) :- var(X), !, > next_truncs(L, R). > next_truncs([X-Y|L], R) :- > next_truncs(L, H), > X =.. [_|A], > Y =.. [_|B], > zip(A, B, J), > append(J, H, R). > > zip([], [], []). > zip([X|L], [Y|R], [X-Y|H]) :- > zip(L, R, H). > > Step 3: > > mercio2(C, X, Y) :- X == Y, !, C = (=). > mercio2(C, X, Y) :- mercio2_iter(C, [X-Y]). > > mercio2_iter(C, L) :- > compare_truncs(D, L), > D \== (=), !, C = D. > mercio2_iter(C, L) :- > next_truncs(L, R), > mercio2_iter(C, R). > > The new mercio2/3 is an itch faster than the old mercio/3: > > ?- X = s(s(X, 1), 0), Y = s(X, 1), > Z = s(s(1, s(Z, 1)), 1), > time((between(1,10000,_), mercio(C, X, Z), > mercio(D, Z, Y), fail; true)). > % Zeit 184 ms, GC 0 ms, Lips 11141728, Uhr 06.08.2025 07:39 > > ?- X = s(s(X, 1), 0), Y = s(X, 1), > Z = s(s(1, s(Z, 1)), 1), > time((between(1,10000,_), mercio2(C, X, Z), > mercio2(D, Z, Y), fail; true)). > % Zeit 145 ms, GC 0 ms, Lips 9379848, Uhr 06.08.2025 07:39 > > Mild Shock schrieb: > > > > Now question is whether compare_rat/2 can > > be extended to a total order or not. On > > the positive side we find that a partial > > > > order can always be extended: > > > > Szpilrajn Extension Theorem > > https://en.wikipedia.org/wiki/Szpilrajn_extension_theorem > > > > But what if compare_rat/2 by @kuniaki.mukai > > is not a partial order? What if it is only a > > preorder, or even worse only a binary relation. > > > > Returning 4 values doesn’t guarantee that it > > is a partial order. We have help from here: > > > > Szpilrajn, Arrow and Suzumura > > https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-999X.2011.04130.x > > > > A binary relation needs to be Suzumura > > consistent, so that it can be extended > > into a total order. And compare_rat/2 is > > > > not Suzumura consistent, as the following > > cycle a < c < b < a shows: > > > > /* Not SWI, Windows Console is SNAFU */ > > ?- repeat, fuzzy(A), fuzzy(C), > > compare_rat(_X, A, C), _X = (<), > > fuzzy(B), compare_rat(_Y, C, B), _Y = (<), > > compare_rat(_Z, B, A), _Z = (<). > > A = s(s(A, A), 1), _A = s(_A, s(_, 1)), C = s(_A, _), > > _B = s(1, _B), B = s(B, s(1, _B)) > > > > Was only testing with compare_rat/3, but > > the theorem applies also to other compare > > proposals, and can be used to exclude > > > > them, as soon as a Suzumura inconsistency is found.
Back to sci.math | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Mercio’s Algorithm for Rational Tree Compare in Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-04 02:54 +0200
The Original Ganster (OG) of Gameification: IEEE 1044.1-1995 (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-04 13:50 +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 13:57 +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:12 +0200
Szpilrajn Theorem and Suzumura Consistency (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-06 01:53 +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:09 +0200
Hopcroft and Karp’s is just Contraction (Re: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:16 +0200
Re: Hopcroft and Karp’s is just Contraction (Re: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:23 +0200
Mercios decidability was already attested in 2012 (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-14 20:40 +0200
Performance of Mercio’s Total Order (Re: Mercios decidability was already attested in 2012) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:51 +0200
Fuzzy Testing is your Swiss Knife (Was: Performance of Mercio’s Total Order) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:54 +0200
Yeah, we have another name! (Re: Fuzzy Testing is your Swiss Knife) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:40 +0200
Monte Carlo sampling the frontier version (Re: Yeah, we have another name!) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:44 +0200
An NPU could give 1000x more LIPS (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-11-27 14:23 +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:02 +0100
100% serious Giga Logical Inferences per Second (GLIPS) (Re: An NPU could give 1000x more LIPS (Re: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-11-28 14:53 +0100
csiph-web