Transpose on Steroids

[Degski]

I saw the developments in Git and matrix transpose...

 

I thought I'd try and speed it up, given that it's basic and worth the trouble...

 

This is what I came up with:

 

 

transpose(Ms, Ts) :-
        Ms = [F|_], transpose(F, Ms, Ts).

 

transpose([], _, []).
transpose([_|Rs], Ms, [Ts|Tss]) :-
        lists_firsts_rests(Ms, Ts, Ms1),
        transpose(Rs, Ms1, Tss).

 

lists_firsts_rests([], [], []).

=====NEW=====

lists_firsts_rests([[F1|O1s],[F2|O2s],[F3|O3s],[F4|O4s],[F5|O5s],[F6|O6s],
                   [F7|O7s],[F8|O8s]|Rest], [F1,F2,F3,F4,F5,F6,F7,F8|Fs],
                   [O1s,O2s,O3s,O4s,O5s,O6s,O7s,O8s|Oss]) :-
        lists_firsts_rests(Rest, Fs, Oss).
lists_firsts_rests([[F1|O1s],[F2|O2s],[F3|O3s],[F4|O4s]|Rest], [F1,F2,F3,F4|Fs],
                    [O1s,O2s,O3s,O4s|Oss]) :-
        lists_firsts_rests(Rest, Fs, Oss).
lists_firsts_rests([[F1|O1s],[F2|O2s]|Rest], [F1,F2|Fs], [O1s,O2s|Oss]) :-
        lists_firsts_rests(Rest, Fs, Oss).
=====NEW=====

 

lists_firsts_rests([[F|Os]|Rest], [F|Fs], [Os|Oss]) :-
        lists_firsts_rests(Rest, Fs, Oss).

 

On a 20x20 matrix the above addition results in a 100% speedup, or half the

time... No, it's not pretty, but it's faster! This can obviously be extended ad infinitum,

if and when one uses big (or hugh) matrices... and will have bigger improvements...

 

I hope it comes across the mail properly!

 

BR

 

 

 

Degski

[Degski]

Forgot the test file!

[Markus Triska-2]

Hi Degski,

Degski <degski@...> writes:

> On a 20x20 matrix the above addition results in a 100% speedup, or
> half the time... No, it's not pretty, but it's faster! This can
> obviously be extended ad infinitum, if and when one uses big (or hugh)
> matrices... and will have bigger improvements...

Yet on the following test case with only a 6x6 matrix, your version is
millions of times slower than the version currently in git:

   length_(L, Ls) :- length(Ls, L).

   %?- N = 6, length(Lists, N), maplist(length_(N), Lists), time((transpose(Lists,_),false)).
   %@ % 152,054,647 inferences, 37.250 CPU in 38.063 seconds (98% CPU, 4082004 Lips)
   %@ false.

   %?- N = 6, length(Lists, N), maplist(length_(N), Lists), time((transpose2(Lists,_),false)).
   %@ % 51 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
   %@ false.

In addition, it leaves unnecessary choicepoints:

   ?- transpose([[_],[_]], _).
   %@ true ;
   %@ true.

whereas the current version does not:

   ?- transpose2([[_],[_]], _).
   %@ true.

While I'm all for improving transpose/2, non-determinism and such a
slowdown for trivial and often needed cases is clearly unacceptable.

By the way, again we see that time/1 is broken and misleading. It should
always report all solutions instead of committing to the first one!

All the best,
Markus
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Bart Demoen-2]

> By the way, again we see that time/1 is broken and misleading.

Your statement is misleading: time/1 is not broken.

       ?- help(time/1).
       time(:Goal)
           Execute  Goal just  like once/1  ...

You might argue that there is a better predicate than time/1, or that
its specs should be different, but time/1 conforms to the spec and this
spec is actually quite clear about not reporting the time for all
solutions.


To get rid of the unnecessary choicepoints: put cuts in the NEW
clauses by Degski (I guess [s]he intended there to be only one
solution to transpose/2 anyway) and then it looks as if (s)he really
improved (for large input) the speed of the original. However, this
seems only true in SWI-Prolog: every other Prolog system I checked
(SICStus, Yap, hProlog) executes the original faster than the variant
by Degski.  This is not an uncommon phenomenon: it is hard to reason
about performance (improvements) in Prolog in general, and in
particular, very often SWI behaves contrary to the reasoning :-)

Cheers

Bart Demoen

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog