Careful with ordsets

Help!
1

Shouldn’t ordset be faster:

?- numlist(1,10000,L), time((between(1,10000,_),
   union([500],L,_), fail; true)).
% 50,000 inferences, 0.156 CPU in 0.167 seconds (94% CPU, 320000 Lips)

?- numlist(1,10000,L), time((between(1,10000,_),
   ord_union([500],L,_), fail; true)).
% 15,030,000 inferences, 0.750 CPU in 0.727 seconds (103% CPU, 20040000 Lips)
2

Quick observation: It’s partly because union/3 is using memberchk, which is optimized in C.

Also, ord_union/3 is not taking advantage of the inherent order, as much as in ord_memberchk.

4

Works also with random data, single element insert via union/3
is faster than via ord_union/3. No C code involved, was using union4/3:

?- findall(X,(between(1,10000,_),random(1,10000,X)),L), 
     time((between(1,10000,_),
     random(1,10000,Y), union4([Y],L,_), fail; true)).
% 63,128,346 inferences, 3.250 CPU in 3.287 seconds (99% CPU, 19424106 Lips)

?- findall(X,(between(1,10000,_),random(1,10000,X)),L), sort(L,R), 
     time((between(1,10000,_),
     random(1,10000,Y), ord_union([Y],R,_), fail; true)).
% 96,026,708 inferences, 5.516 CPU in 5.564 seconds (99% CPU, 17409941 Lips)

Edit 16.08.2022
The library ordset pays off when you insert like 5 elements in a batch:

?- findall(X,(between(1,10000,_),random(1,10000,X)),L),
    time((between(1,10000,_),
    findall(Y,(between(1,5,_), random(1,10000,Y)), H), 
         union4(H,L,_), fail; true)).
% 315,183,160 inferences, 15.984 CPU in 15.991 seconds (100% CPU, 19718204 Lips)

?- findall(X,(between(1,10000,_),random(1,10000,X)),L),sort(L,R),
    time((between(1,10000,_),
    findall(Y,(between(1,5,_), random(1,10000,Y)), H),sort(H,J),
        ord_union(J,R,_), fail; true)).
% 157,835,640 inferences, 7.812 CPU in 7.814 seconds (100% CPU, 20202962 Lips)
5

Ok, Scryer Prolog, you got list_to_set/2. Woa! Was ticking
along with this O(n^2) version, not steadfast only mode (+,-):

/* Folklore Solution */
list_to_set([], R) :- append(R, [], _), !.
list_to_set([X|L], R) :- member(X, R), !,
   list_to_set(L, R).

Then I found nevertheless in Scryer Prolog this one:

/* Scryer Prolog Solution */
list_to_set(Ls0, Ls) :-
        maplist(lists:with_var, Ls0, LVs0),
        keysort(LVs0, LVs),
        same_elements(LVs),
        pick_firsts(LVs0, Ls).

Is the above faster than the SWI-Prolog version, which does two sorts?

Edit 19.08.2022
BTW: Theoretical Computer Science tells me that a hash table with an
input order overlay wouldn’t be so bad, basically O(n), faster than O(n*log(n)).
I had this in Jekejeke Prolog for ages, still have it, it works like that:

/* Jekejeke Prolog Solution */
?- sort([2,1,3,1], X).
X = [1, 2, 3]
?- sort([2,1,3,1], X, [type(hash)]).
X = [2, 1, 3]

The hash table with an input order overlay is the age old Java:
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
The O(n) complexity assumes amortized complexity O(1) of a hash table lookup.

Right? Yes or no?

6

(Nothing of Importance here)