:- module(_,_).

% - Checking that two (ground) lists contain the same elements:

%   Naive:

same_elements_naive(L1, L2) :-
    \+ (member(X, L1), \+ member(X, L2)),
    \+ (member(X, L2), \+ member(X, L1)).

%   Sort and unify (sorting can be done in O(N log N)):

same_elements(L1, L2) :-
    sort(L1, Sorted),
    sort(L2, Sorted).

%   Try:
% ?- same_elements_naive([a,b,c],[c,a,b]).
% ?- same_elements([a,b,c],[c,a,b]).

% - The speedup, with lists of `N` elements in scrambled order (it
%   grows with `N`):

test(N) :-
    scrambled(N, L),
    reverse(L, R),
    speedup(same_elements_naive(L,R), same_elements(L,R)).

% ?- test(1000).
% ?- test(5000).

%   (The numbers 1 to `N`, scrambled: `N` must not be a multiple of 7919.)

scrambled(N, L) :-
    scrambled_from(0, N, L).

scrambled_from(N, N, []) :- !.
scrambled_from(I, N, [X|Xs]) :-
    X is (I * 7919) mod N + 1,
    I1 is I + 1,
    scrambled_from(I1, N, Xs).

% - `speedup/2` runs the two goals and compares their times, as in
%   the first example (`010_swap.pl`).

%! \begin{hide}
speedup(Slow, Fast) :-
    speedup_loop(true, Slow, Fast).

speedup_loop(Loop, Slow, Fast) :-
    time_of(Loop, Slow, TS),
    time_of(Loop, Fast, TF),
    show_speedup(TS, TF).

time_of(Loop, Goal, T) :-
    repeat_time(1, Loop, Goal, T).

repeat_time(N, Loop, Goal, T) :-
    loop_time(N, Goal, TG),
    (   TG >= 100
    ->  loop_time(N, Loop, TL),
        (   TG - TL > TG / 10        % (else too fast to tell
        ->  T is (TG - TL) / N       %  from the loop itself)
        ;   T = 0
        )
    ;   N1 is N * 10,
        repeat_time(N1, Loop, Goal, T)
    ).

loop_time(N, Goal, T) :-
    statistics(runtime, [T0, _]),
    ( between(1, N, _), once(Goal), fail ; true ),
    statistics(runtime, [T1, _]),
    T is T1 - T0.

show_speedup(TS, TF) :-
    format("Slow: ", []), show_time(TS),
    format(", fast: ", []), show_time(TF),
    (   TS > 0, TF > 0
    ->  S is TS / TF,
        format(", speedup: ~1f~n", [S])
    ;   nl
    ).

show_time(T) :-
    T > 0, !,
    format("~4f ms", [T]).
show_time(_) :-
    format("too fast to measure", []).

:- use_module(library(between)).
%! \end{hide}