prolog - Why is arg3 faster when its third argument is an unbound variable? - Stack Overflow

admin管理员组

文章数量:1023263

Predicates ksort/3 and fksort/3 sort lists of Key-Value pairs, where Key is a value between 1 and a small integer MaxKey.

% first version

ksort(MaxKey, List, Sorted) :-
    create(MaxKey, Buckets),
    scatter(List, Buckets),
    gather(Buckets, Sorted).

scatter([], _).
scatter([Key-Val|Pairs], Buckets) :-
    arg(Key, Buckets, Head-[Key-Val|Tail]),
    setarg(Key, Buckets, Head-Tail),
    scatter(Pairs, Buckets).

% second version

fksort(MaxKey, List, Sorted) :-
    create(MaxKey, Buckets),
    fscatter(List, Buckets),
    gather(Buckets, Sorted).

fscatter([], _).
fscatter([Key-Val|Pairs], Buckets) :-
    arg(Key, Buckets, Bucket),        % <= third argument is an unbound variable
    setarg(Key, Buckets, Head-Tail),
    Bucket = Head-[Key-Val|Tail],
    fscatter(Pairs, Buckets).

% predicates used in both versions

create(MaxKey, Buckets) :-
    findall(L-L, between(1, MaxKey, _), Dlists),
    Buckets =.. [buckets|Dlists].

gather(Buckets, Sorted) :-
    Buckets =.. [buckets|Dlists],
    join(Dlists, Sorted).

join([], []).
join([Head-Tail|Dlists], Head) :-
    join(Dlists, Tail).

comparison :-
    K = 100,
    format('size keysort ksort fksort\n'),
    forall( between(15, 22, I),
            (   garbage_collect,
                N is 2^I,
                randpairs(N, K, L),
                timeit(10, keysort,   L, S1, T1),
                timeit(10, ksort(K),  L, S2, T2),
                timeit(10, fksort(K), L, S3, T3),
                S1 = S2,
                S2 = S3,
                format('2^~w    ~2f  ~2f   ~2f\n', [I, T1, T2, T3]) ) ).

randpairs(N, K, Pairs) :-
    findall(Key-Val,
            ( between(1, N, _),
              random_between(1, K, Key),
              random(Val) ),
            Pairs).

timeit(R, P, L, S, T) :-
    garbage_collect,
    Start is cputime,
    forall(between(1, R, _), call(P, L, S)),
    T is (cputime - Start)/R.

In this specific scenario, both predicates run faster than the ISO built-in predicate keysort/2.

?- comparison.
size keysort ksort fksort
2^15    0.01  0.01   0.00
2^16    0.02  0.02   0.01
2^17    0.05  0.03   0.02
2^18    0.12  0.06   0.03
2^19    0.30  0.12   0.06
2^20    0.69  0.23   0.13
2^21    1.56  0.42   0.26
2^22    3.56  0.93   0.52
true.

The only difference between ksort/3 and fksort/3 is how they call the predicate arg/3. My question is: why fksort/3 is faster than ksort/3?

Predicates ksort/3 and fksort/3 sort lists of Key-Value pairs, where Key is a value between 1 and a small integer MaxKey.

% first version

ksort(MaxKey, List, Sorted) :-
    create(MaxKey, Buckets),
    scatter(List, Buckets),
    gather(Buckets, Sorted).

scatter([], _).
scatter([Key-Val|Pairs], Buckets) :-
    arg(Key, Buckets, Head-[Key-Val|Tail]),
    setarg(Key, Buckets, Head-Tail),
    scatter(Pairs, Buckets).

% second version

fksort(MaxKey, List, Sorted) :-
    create(MaxKey, Buckets),
    fscatter(List, Buckets),
    gather(Buckets, Sorted).

fscatter([], _).
fscatter([Key-Val|Pairs], Buckets) :-
    arg(Key, Buckets, Bucket),        % <= third argument is an unbound variable
    setarg(Key, Buckets, Head-Tail),
    Bucket = Head-[Key-Val|Tail],
    fscatter(Pairs, Buckets).

% predicates used in both versions

create(MaxKey, Buckets) :-
    findall(L-L, between(1, MaxKey, _), Dlists),
    Buckets =.. [buckets|Dlists].

gather(Buckets, Sorted) :-
    Buckets =.. [buckets|Dlists],
    join(Dlists, Sorted).

join([], []).
join([Head-Tail|Dlists], Head) :-
    join(Dlists, Tail).

comparison :-
    K = 100,
    format('size keysort ksort fksort\n'),
    forall( between(15, 22, I),
            (   garbage_collect,
                N is 2^I,
                randpairs(N, K, L),
                timeit(10, keysort,   L, S1, T1),
                timeit(10, ksort(K),  L, S2, T2),
                timeit(10, fksort(K), L, S3, T3),
                S1 = S2,
                S2 = S3,
                format('2^~w    ~2f  ~2f   ~2f\n', [I, T1, T2, T3]) ) ).

randpairs(N, K, Pairs) :-
    findall(Key-Val,
            ( between(1, N, _),
              random_between(1, K, Key),
              random(Val) ),
            Pairs).

timeit(R, P, L, S, T) :-
    garbage_collect,
    Start is cputime,
    forall(between(1, R, _), call(P, L, S)),
    T is (cputime - Start)/R.

In this specific scenario, both predicates run faster than the ISO built-in predicate keysort/2.

?- comparison.
size keysort ksort fksort
2^15    0.01  0.01   0.00
2^16    0.02  0.02   0.01
2^17    0.05  0.03   0.02
2^18    0.12  0.06   0.03
2^19    0.30  0.12   0.06
2^20    0.69  0.23   0.13
2^21    1.56  0.42   0.26
2^22    3.56  0.93   0.52
true.

The only difference between ksort/3 and fksort/3 is how they call the predicate arg/3. My question is: why fksort/3 is faster than ksort/3?

• prolog
• swi-prolog

Share Improve this question Follow edited Nov 19, 2024 at 12:01 slago asked Nov 19, 2024 at 11:51 slagoslago 5,51922 gold badges1212 silver badges2525 bronze badges

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 3

In the scatter/2 predicate, the third argument in the arg/3 call, Head-[Key-Val|Tail], requires traversing a compound term to access four sub-terms, which is more computationally expensive than a variable argument as in the call from the fscatter/3 predicate. The fscatter/3 moves the argument unification from arg/3 to an explicit unification, Bucket = Head-[Key-Val|Tail], which seems to have a performance advantage.

Predicates ksort/3 and fksort/3 sort lists of Key-Value pairs, where Key is a value between 1 and a small integer MaxKey.

% first version

ksort(MaxKey, List, Sorted) :-
    create(MaxKey, Buckets),
    scatter(List, Buckets),
    gather(Buckets, Sorted).

scatter([], _).
scatter([Key-Val|Pairs], Buckets) :-
    arg(Key, Buckets, Head-[Key-Val|Tail]),
    setarg(Key, Buckets, Head-Tail),
    scatter(Pairs, Buckets).

% second version

fksort(MaxKey, List, Sorted) :-
    create(MaxKey, Buckets),
    fscatter(List, Buckets),
    gather(Buckets, Sorted).

fscatter([], _).
fscatter([Key-Val|Pairs], Buckets) :-
    arg(Key, Buckets, Bucket),        % <= third argument is an unbound variable
    setarg(Key, Buckets, Head-Tail),
    Bucket = Head-[Key-Val|Tail],
    fscatter(Pairs, Buckets).

% predicates used in both versions

create(MaxKey, Buckets) :-
    findall(L-L, between(1, MaxKey, _), Dlists),
    Buckets =.. [buckets|Dlists].

gather(Buckets, Sorted) :-
    Buckets =.. [buckets|Dlists],
    join(Dlists, Sorted).

join([], []).
join([Head-Tail|Dlists], Head) :-
    join(Dlists, Tail).

comparison :-
    K = 100,
    format('size keysort ksort fksort\n'),
    forall( between(15, 22, I),
            (   garbage_collect,
                N is 2^I,
                randpairs(N, K, L),
                timeit(10, keysort,   L, S1, T1),
                timeit(10, ksort(K),  L, S2, T2),
                timeit(10, fksort(K), L, S3, T3),
                S1 = S2,
                S2 = S3,
                format('2^~w    ~2f  ~2f   ~2f\n', [I, T1, T2, T3]) ) ).

randpairs(N, K, Pairs) :-
    findall(Key-Val,
            ( between(1, N, _),
              random_between(1, K, Key),
              random(Val) ),
            Pairs).

timeit(R, P, L, S, T) :-
    garbage_collect,
    Start is cputime,
    forall(between(1, R, _), call(P, L, S)),
    T is (cputime - Start)/R.

In this specific scenario, both predicates run faster than the ISO built-in predicate keysort/2.

?- comparison.
size keysort ksort fksort
2^15    0.01  0.01   0.00
2^16    0.02  0.02   0.01
2^17    0.05  0.03   0.02
2^18    0.12  0.06   0.03
2^19    0.30  0.12   0.06
2^20    0.69  0.23   0.13
2^21    1.56  0.42   0.26
2^22    3.56  0.93   0.52
true.

The only difference between ksort/3 and fksort/3 is how they call the predicate arg/3. My question is: why fksort/3 is faster than ksort/3?

Predicates ksort/3 and fksort/3 sort lists of Key-Value pairs, where Key is a value between 1 and a small integer MaxKey.

% first version

ksort(MaxKey, List, Sorted) :-
    create(MaxKey, Buckets),
    scatter(List, Buckets),
    gather(Buckets, Sorted).

scatter([], _).
scatter([Key-Val|Pairs], Buckets) :-
    arg(Key, Buckets, Head-[Key-Val|Tail]),
    setarg(Key, Buckets, Head-Tail),
    scatter(Pairs, Buckets).

% second version

fksort(MaxKey, List, Sorted) :-
    create(MaxKey, Buckets),
    fscatter(List, Buckets),
    gather(Buckets, Sorted).

fscatter([], _).
fscatter([Key-Val|Pairs], Buckets) :-
    arg(Key, Buckets, Bucket),        % <= third argument is an unbound variable
    setarg(Key, Buckets, Head-Tail),
    Bucket = Head-[Key-Val|Tail],
    fscatter(Pairs, Buckets).

% predicates used in both versions

create(MaxKey, Buckets) :-
    findall(L-L, between(1, MaxKey, _), Dlists),
    Buckets =.. [buckets|Dlists].

gather(Buckets, Sorted) :-
    Buckets =.. [buckets|Dlists],
    join(Dlists, Sorted).

join([], []).
join([Head-Tail|Dlists], Head) :-
    join(Dlists, Tail).

comparison :-
    K = 100,
    format('size keysort ksort fksort\n'),
    forall( between(15, 22, I),
            (   garbage_collect,
                N is 2^I,
                randpairs(N, K, L),
                timeit(10, keysort,   L, S1, T1),
                timeit(10, ksort(K),  L, S2, T2),
                timeit(10, fksort(K), L, S3, T3),
                S1 = S2,
                S2 = S3,
                format('2^~w    ~2f  ~2f   ~2f\n', [I, T1, T2, T3]) ) ).

randpairs(N, K, Pairs) :-
    findall(Key-Val,
            ( between(1, N, _),
              random_between(1, K, Key),
              random(Val) ),
            Pairs).

timeit(R, P, L, S, T) :-
    garbage_collect,
    Start is cputime,
    forall(between(1, R, _), call(P, L, S)),
    T is (cputime - Start)/R.

In this specific scenario, both predicates run faster than the ISO built-in predicate keysort/2.

?- comparison.
size keysort ksort fksort
2^15    0.01  0.01   0.00
2^16    0.02  0.02   0.01
2^17    0.05  0.03   0.02
2^18    0.12  0.06   0.03
2^19    0.30  0.12   0.06
2^20    0.69  0.23   0.13
2^21    1.56  0.42   0.26
2^22    3.56  0.93   0.52
true.

The only difference between ksort/3 and fksort/3 is how they call the predicate arg/3. My question is: why fksort/3 is faster than ksort/3?

• prolog
• swi-prolog

Share Improve this question Follow edited Nov 19, 2024 at 12:01 slago asked Nov 19, 2024 at 11:51 slagoslago 5,51922 gold badges1212 silver badges2525 bronze badges

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 3

In the scatter/2 predicate, the third argument in the arg/3 call, Head-[Key-Val|Tail], requires traversing a compound term to access four sub-terms, which is more computationally expensive than a variable argument as in the call from the fscatter/3 predicate. The fscatter/3 moves the argument unification from arg/3 to an explicit unification, Bucket = Head-[Key-Val|Tail], which seems to have a performance advantage.

本文标签： prologWhy is arg3 faster when its third argument is an unbound variableStack Overflow