1

我有一个带有 pairs 的列表[[1, 2], [2, 1], [1, 3] ..]。如何以最快的方式获得独特的配对？我写了一个函数，但是太慢了。

-module(test).
-export([unique/1, unique/2, pairs/1]).

unique(L) -> unique(L, []).
unique([], UL) -> UL;
% L: list of lists
unique(L, UL) ->
    [X,Y] = hd(L),
    case lists:member([Y,X], L) of
        true ->
            unique(L--[[Y,X]], [[X,Y]|UL]);
        false ->
            unique(tl(L), UL)
    end.

pairs(L) -> [[X,Y] || X <- L, Y <- L, X=/=Y].

从外壳，

1> test:pairs([1,2,3]).
[[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]
2> test:unique(test:pairs)). %Very slow for large list. How to improve?
[[2,3],[1,3],[1,2]]

我有一个列表长度9900的对列表，其中一半是重复的。我正在使用对列表进行进一步计算。对于原始列表（具有重复对），时间是3.718s，如果我过滤掉唯一列表并使用 if 进行计算，时间7.375s会更糟。

我将功能更改为不使用--运算符。

unique(L, UL) ->
    [X,Y] = hd(L),
    case lists:member([Y,X], L) of
        true ->
            unique(tl(L), [[Y,X]|UL]);
        false ->
            unique(tl(L), UL)
    end.

即便如此，它仅对 进行了0.047s改进7.375s，这表明该算法不够快。

你能指出任何更好的算法吗？有没有为此的内置库函数？
谢谢。

4

2 回答 2

3

有几种方法可以做到这一点。v1最快但最脏的方式：

-module(uniq).

-export([v1/1, v2/1, v3/1, v4/1, gen/1]).

-compile({inline, [s/1]}).

s([X, Y]) when X > Y -> [Y, X];
s(L) -> L.

v1(L) ->
  erase(),
  [put(s(K), ok) || K <- L],
  [K || {K, _} <- erase() ].

v2(L) ->
  sets:to_list(sets:from_list([s(K) || K <- L])).

v3(L) ->
  T = ets:new(set, [private, set]),
  ets:insert(T, [{s(K)} || K <- L]),
  R = [K || {K} <- ets:tab2list(T)],
  ets:delete(T),
  R.

v4(L) ->
  lists:usort([s(K) || K <- L]).

gen(N) ->
  [[random:uniform(100), random:uniform(100)] || _ <- lists:seq(1, N)].

结果速度：

1> L = uniq:gen(1000000).
...
2> [ element(1, timer:tc(uniq,Alg,[L]))/1000000 || Alg <- [v1, v2, v3, v4]].
[0.243595,1.042272,0.35633,1.309971]
3> [ element(1, timer:tc(uniq,Alg,[L]))/1000000 || Alg <- [v1, v2, v3, v4]].
[0.236856,1.000818,0.359761,1.309743]
4> [ element(1, timer:tc(uniq,Alg,[L]))/1000000 || Alg <- [v1, v2, v3, v4]].
[0.242901,1.039107,0.357476,1.30691]

Notelists:usort/1版本v4是最慢的版本。在版本中使用进程字典v1是非常肮脏的事情，你应该避免它，但在特殊情况下它是可行的。ets在版本中使用v3具有良好的性能，您应该将此版本用于任何严肃的工作。对于较小的列表也是sets版本v2不错的选择。它很简短而且非常好。

避免处理器字典污染并仍然具有相同性能的技巧是使用子进程：

v1(L) ->
  Self = self(),
  PID = spawn_link(fun() ->
          [put(s(K), ok) || K <- L],
          Self ! {result, self(), [K || {K, _} <- erase() ]}
      end),
  receive
    {result, PID, Result} -> Result
  after 10000 -> error(timout)
  end.

通过将数据复制到单独的堆中（除非您使用二进制文件），您会损失一些性能，但它仍然是最快的选择。在这种情况下，它需要更多大约 50 毫秒，所以仍然是最快的。

于 2013-11-02T14:33:44.463 回答
1

你lists:usort([lists:sort(X) || X <- L])试过了吗，我用 9900 个元素列表试了一下，不到 1 秒。

18> F = fun(X,L) -> [[X,Y] || Y <- L] end.                     
#Fun<erl_eval.12.82930912>
19> L = lists:seq(1,100).                                      
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,
 23,24,25,26,27,28,29|...]
20> L1 = lists:foldl(fun(X,Acc) -> F(X,lists:delete(X,L)) ++ Acc end,[],L).                                                                  
[[100,1],
 [100,2],
 [100|...],
 [...]|...]
21> length(L1).                                                
9900                                                                            
22> io:format("~p~n",[erlang:now()]),lists:usort([lists:sort(X) || X <- L1]),io:format("~p~n",[erlang:now()]).                                 
{1383,395086,328000}
{1383,395086,515000}
ok
23> lists:usort([lists:sort(X) || X <- [[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]]).                                                                
[[1,2],[1,3],[2,3]]
24>

显示执行时间小于 0.2 秒，第 23 行的命令测试它是否有效。

于 2013-11-02T12:28:21.410 回答