gb_sets.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 709 行 · 第 1/2 页

    {Key, {S - 1, Larger}}.

take_smallest1({Key, nil, Larger}) ->
    {Key, Larger};
take_smallest1({Key, Smaller, Larger}) ->
    {Key1, Smaller1} = take_smallest1(Smaller),
    {Key1, {Key, Smaller1, Larger}}.

smallest({_, T}) ->
    smallest_1(T).

smallest_1({Key, nil, _Larger}) ->
    Key;
smallest_1({_Key, Smaller, _Larger}) ->
    smallest_1(Smaller).

take_largest({S, T}) ->
    {Key, Smaller} = take_largest1(T),
    {Key, {S - 1, Smaller}}.

take_largest1({Key, Smaller, nil}) ->
    {Key, Smaller};
take_largest1({Key, Smaller, Larger}) ->
    {Key1, Larger1} = take_largest1(Larger),
    {Key1, {Key, Smaller, Larger1}}.

largest({_, T}) ->
    largest_1(T).

largest_1({Key, _Smaller, nil}) ->
    Key;
largest_1({_Key, _Smaller, Larger}) ->
    largest_1(Larger).

to_list({_, T}) ->
    to_list(T, []).

to_list_1(T) -> to_list(T, []).

to_list({Key, Small, Big}, L) ->
    to_list(Small, [Key | to_list(Big, L)]);
to_list(nil, L) -> L.

iterator({_, T}) ->
    iterator(T, []).

%% The iterator structure is really just a list corresponding to the
%% call stack of an in-order traversal. This is quite fast.

iterator({_, nil, _} = T, As) ->
    [T | As];
iterator({_, L, _} = T, As) ->
    iterator(L, [T | As]);
iterator(nil, As) ->
    As.

next([{X, _, T} | As]) ->
    {X, iterator(T, As)};
next([]) ->
    none.


%% Set operations:


%% If |X| < |Y|, then we traverse the elements of X. The cost for
%% testing a single random element for membership in a tree S is
%% proportional to log(|S|); thus, if |Y| / |X| < c * log(|Y|), for some
%% c, it is more efficient to scan the ordered sequence of elements of Y
%% while traversing X (under the same ordering) in order to test whether
%% elements of X are already in Y. Since the `math' module does not have
%% a `log2'-function, we rewrite the condition to |X| < |Y| * c1 *
%% ln(|X|), where c1 = c / ln 2.

-define(c, 1.46).    % 1 / ln 2; this appears to be best

%% If the sets are not very different in size, i.e., if |Y| / |X| >= c *
%% log(|Y|), then the fastest way to do union (and the other similar set
%% operations) is to build the lists of elements, traverse these lists
%% in parallel while building a reversed ackumulator list, and finally
%% rebuild the tree directly from the ackumulator. Other methods of
%% traversing the elements can be devised, but they all have higher
%% overhead.

union({N1, T1}, {N2, T2}) when N2 < N1 ->
    union(to_list_1(T2), N2, T1, N1);
union({N1, T1}, {N2, T2}) ->
    union(to_list_1(T1), N1, T2, N2).

%% We avoid the expensive mathematical computations if there is little
%% chance at saving at least the same amount of time by making the right
%% choice of strategy. Recall that N1 < N2 here.

union(L, N1, T2, N2) when N2 < 10 ->
    %% Break-even is about 7 for N1 = 1 and 10 for
    %% N1 = 2
    union_2(L, to_list_1(T2), N1 + N2);
union(L, N1, T2, N2) ->
    X = N1 * round(?c * math:log(N2)),
    if N2 < X ->
	    union_2(L, to_list_1(T2), N1 + N2);
       true ->
	    union_1(L, {N2, T2})
    end.


%% If the length of the list is in proportion with the size of the
%% target set, this version spends too much time doing lookups, compared
%% to the below version.

union_1([X | Xs], S) ->
    union_1(Xs, add(X, S));
union_1([], S) ->
    S.


%% If the length of the first list is too small in comparison with the
%% size of the target set, this version spends too much time scanning
%% the element list of the target set for possible membership, compared
%% with the above version.

%% Some notes on sequential scanning of ordered lists
%%
%% 1) We want to put the equality case last, if we can assume that the
%% probability for overlapping elements is relatively low on average.
%% Doing this also allows us to completely skip the (arithmetic)
%% equality test, since the term order is arithmetically total.
%%
%% 2) We always test for `smaller than' first, i.e., whether the head of
%% the left list is smaller than the head of the right list, and if the
%% `greater than' test should instead turn out to be true, we switch
%% left and right arguments in the recursive call under the assumption
%% that the same is likely to apply to the next element also,
%% statistically reducing the number of failed tests and automatically
%% adapting to cases of lists having very different lengths. This saves
%% 10-40% of the traversation time compared to a "fixed" strategy,
%% depending on the sizes and contents of the lists.
%%
%% 3) A tail recursive version using `lists:reverse/2' is about 5-10%
%% faster than a plain recursive version using the stack, for lists of
%% more than about 20 elements and small stack frames. For very short
%% lists, however (length < 10), the stack version can be several times
%% faster. As stack frames grow larger, the advantages of using
%% `reverse' could get greater.

union_2(Xs, Ys, S) ->
    union_2(Xs, Ys, [], S).    % S is the sum of the sizes here

union_2([X | Xs1], [Y | _] = Ys, As, S) when X < Y ->
    union_2(Xs1, Ys, [X | As], S);
union_2([X | _] = Xs, [Y | Ys1], As, S) when X > Y ->
    union_2(Ys1, Xs, [Y | As], S);
union_2([X | Xs1], [_ | Ys1], As, S) ->
    union_2(Xs1, Ys1, [X | As], S - 1);
union_2([], Ys, As, S) ->
    {S, balance_revlist(push(Ys, As), S)};
union_2(Xs, [], As, S) ->
    {S, balance_revlist(push(Xs, As), S)}.

push([X | Xs], As) ->
    push(Xs, [X | As]);
push([], As) ->
    As.

balance_revlist(L, S) ->
    {T, _} = balance_revlist_1(L, S),
    T.

balance_revlist_1(L, S) when S > 1 ->
    Sm = S - 1,
    S2 = Sm div 2,
    S1 = Sm - S2,
    {T2, [K | L1]} = balance_revlist_1(L, S1),
    {T1, L2} = balance_revlist_1(L1, S2),
    T = {K, T1, T2},
    {T, L2};
balance_revlist_1([Key | L], 1) ->
    {{Key, nil, nil}, L};
balance_revlist_1(L, 0) ->
    {nil, L}.


union([S | Ss]) ->
    union_list(S, Ss);
union([]) -> empty().

union_list(S, [S1 | Ss]) ->
    union_list(union(S, S1), Ss);
union_list(S, []) -> S.


%% The rest is modelled on the above.


intersection({N1, T1}, {N2, T2}) when N2 < N1 ->
    intersection(to_list_1(T2), N2, T1, N1);
intersection({N1, T1}, {N2, T2}) ->
    intersection(to_list_1(T1), N1, T2, N2).

intersection(L, _N1, T2, N2) when N2 < 10 ->
    intersection_2(L, to_list_1(T2));
intersection(L, N1, T2, N2) ->
    X = N1 * round(?c * math:log(N2)),
    if N2 < X ->
	    intersection_2(L, to_list_1(T2));
       true ->
	    intersection_1(L, T2)
    end.


%% We collect the intersecting elements in an ackumulator list and count
%% them at the same time so we can balance the list afterwards.

intersection_1(Xs, T) ->
    intersection_1(Xs, T, [], 0).

intersection_1([X | Xs], T, As, N) ->
    case is_member_1(X, T) of
	true ->
	    intersection_1(Xs, T, [X | As], N + 1);
	false ->
	    intersection_1(Xs, T, As, N)
    end;
intersection_1([], _, As, N) ->
    {N, balance_revlist(As, N)}.


intersection_2(Xs, Ys) ->
    intersection_2(Xs, Ys, [], 0).

intersection_2([X | Xs1], [Y | _] = Ys, As, S) when X < Y ->
    intersection_2(Xs1, Ys, As, S);
intersection_2([X | _] = Xs, [Y | Ys1], As, S) when X > Y ->
    intersection_2(Ys1, Xs, As, S);
intersection_2([X | Xs1], [_ | Ys1], As, S) ->
    intersection_2(Xs1, Ys1, [X | As], S + 1);
intersection_2([], _, As, S) ->
    {S, balance_revlist(As, S)};
intersection_2(_, [], As, S) ->
    {S, balance_revlist(As, S)}.


intersection([S | Ss]) ->
    intersection_list(S, Ss).

intersection_list(S, [S1 | Ss]) ->
    intersection_list(intersection(S, S1), Ss);
intersection_list(S, []) -> S.


%% Note that difference is not symmetric. We don't use `delete' here,
%% since the GB-trees implementation does not rebalance after deletion
%% and so we could end up with very unbalanced trees indeed depending on
%% the sets. Therefore, we always build a new tree, and thus we need to
%% traverse the whole element list of the left operand.

subtract(S1, S2) ->
    difference(S1, S2).

difference({N1, T1}, {N2, T2}) ->
    difference(to_list_1(T1), N1, T2, N2).

difference(L, N1, T2, N2) when N2 < 10 ->
    difference_2(L, to_list_1(T2), N1);
difference(L, N1, T2, N2) ->
    X = N1 * round(?c * math:log(N2)),
    if N2 < X ->
	    difference_2(L, to_list_1(T2), N1);
       true ->
	    difference_1(L, T2)
    end.


difference_1(Xs, T) ->
    difference_1(Xs, T, [], 0).

difference_1([X | Xs], T, As, N) ->
    case is_member_1(X, T) of
	true ->
	    difference_1(Xs, T, As, N);
	false ->
	    difference_1(Xs, T, [X | As], N + 1)
    end;
difference_1([], _, As, N) ->
    {N, balance_revlist(As, N)}.


difference_2(Xs, Ys, S) ->
    difference_2(Xs, Ys, [], S).    % S is the size of the left set

difference_2([X | Xs1], [Y | _] = Ys, As, S) when X < Y ->
    difference_2(Xs1, Ys, [X | As], S);
difference_2([X | _] = Xs, [Y | Ys1], As, S) when X > Y ->
    difference_2(Xs, Ys1, As, S);
difference_2([_X | Xs1], [_Y | Ys1], As, S) ->
    difference_2(Xs1, Ys1, As, S - 1);
difference_2([], _Ys, As, S) ->
    {S, balance_revlist(As, S)};
difference_2(Xs, [], As, S) ->
    {S, balance_revlist(push(Xs, As), S)}.


%% Subset testing is much the same thing as set difference, but
%% without the construction of a new set.

is_subset({N1, T1}, {N2, T2}) ->
    is_subset(to_list_1(T1), N1, T2, N2).

is_subset(L, _N1, T2, N2) when N2 < 10 ->
    is_subset_2(L, to_list_1(T2));
is_subset(L, N1, T2, N2) ->
    X = N1 * round(?c * math:log(N2)),
    if N2 < X ->
	    is_subset_2(L, to_list_1(T2));
       true ->
	    is_subset_1(L, T2)
    end.


is_subset_1([X | Xs], T) ->
    case is_member_1(X, T) of
	true ->
	    is_subset_1(Xs, T);
	false ->
	    false
    end;
is_subset_1([], _) ->
    true.


is_subset_2([X | _], [Y | _]) when X < Y ->
    false;
is_subset_2([X | _] = Xs, [Y | Ys1]) when X > Y ->
    is_subset_2(Xs, Ys1);
is_subset_2([_ | Xs1], [_ | Ys1]) ->
    is_subset_2(Xs1, Ys1);
is_subset_2([], _) ->
    true;
is_subset_2(_, []) ->
    false.


%% For compatibility with `sets':

is_set({0, nil}) -> true;
is_set({N, {_, _, _}}) when is_integer(N), N >= 0 -> true;
is_set(_) -> false.

filter(F, S) ->
    from_ordset([X || X <- to_list(S), F(X)]).

fold(F, A, S) ->
    lists:foldl(F, A, to_list(S)).