1. Zuhause
  2. Frage und Antwort
  3. Wie suche ich einen Artikel in einer Liste in Erlang?

Wie suche ich einen Artikel in einer Liste in Erlang?

2009-03-23 1 views
10

Ich schreibe einen Cache-Gen-Server für das Unternehmen Verwendung. Ich frage mich, wie man einen Gegenstand von der Liste sucht, da ich die Kosten für die Suche für den Vergleich verschiedener Datenstrukturen in Erlang wie dict, orddict, Liste, Tupel, Baum, Warteschlange usw. für das Cache-Programm verwenden möchte.Wie suche ich einen Artikel in einer Liste in Erlang?

Beispiel:

List = [{"A1",["ankit","sush", "Hover", "x4", "a3","nilesh","mike","erlang" | ...]}|...].

Jetzt mag ich für den Key A1 suchen und für 'Mike' in der Liste suchen. Was ist der beste Weg, um die obige Liste zu durchsuchen?

Bitte einige Beispiele angeben. Atleast Pseudo dafür.

Quelle

2009-03-23 iankits

Antwort

4

Danke für die Antworten. Ich habe einen Erlang-Code geschrieben, um die Zeiten für das Einfügen von & Datum in verschiedene Datenstrukturen wie LIST, DICT, QUEUE, SET und PARALLEL MAP der Datenstrukturen zu finden. Nur das Einfügen der Liste & fetch ist abgeschlossen, aber Rest hat eine parallele Karteneinfügung. Ich möchte den Code & Ergebnisse des Codes teilen. Im Anschluss wird das Modul test.erl

-module(test). 
-author('[email protected]'). 
-export ([ 
     %%list 
     create_list/1, fetch_list/2, test_list/1, parmap_create_list/1 , ins_list/3, parallel_list/1, 
     para_fetch_list/2, pfetch_list/1, 

     %%dict 
     create_dict/1, fetch_dict/2, test_dict/1, parmap_create_dict/1 , ins_dict/3, parallel_dict/1, 

     %queue 
     create_q/1, fetch_q/2, test_q/1, parmap_create_q/1, ins_q/3, parallel_q/1, 

     %set 
     create_set/1, fetch_set/2, test_set/1, parmap_create_set/1 , ins_set/3, parallel_set/1, 

     create/1, multi_create/0, 
     pcreate/1, parallel_multi_create/0 

     %test/1 , multi_test/0 
     ]). 

%%creation tests 

%% For List 
create_list(N) -> 
    lists:foldl (fun(X,Prev) -> Prev ++ [X] end, [] , lists:seq(1,N)). 

test_list(N) -> 
    {R1,List} = timer:tc(?MODULE, create_list, [N]), 
    %%Set = lists:foldl(fun(X,Prev) -> sets:add_element(X,Prev) end,SET, lists:seq(1,N)), 
    {R2,_} = timer:tc(?MODULE, fetch_list,[ N, List ]), 
    {list,inserT,R1,fetchT,R2}. 

%% For Dict 
create_dict(N) -> 
    lists:foldl(fun(X,Prev)-> dict:append([],X,Prev) end, dict:new(), lists:seq(1,N)). 

test_dict(N) -> 
    {R1,Dict} = timer:tc(?MODULE, create_dict, [N]), 
    %%Set = lists:foldl(fun(X,Prev) -> sets:add_element(X,Prev) end,SET, lists:seq(1,N)), 
    {R2,_} = timer:tc(?MODULE, fetch_dict,[ N, Dict ]), 
    {dict,inserT,R1,fetchT,R2}. 

%% For Queue 
create_q(N) -> 
    lists:foldl(fun(X,Prev) -> queue:in(X,Prev) end, queue:new() , lists:seq(1,N)). 

test_q(N)-> 
    {R1,Q} = timer:tc(?MODULE, create_q,[N]), 
    %%Q = lists:foldl(fun(X,Prev) -> queue:in(X,Prev) end,Q0, lists:seq(1,N)), 
    {R2,_} = timer:tc(?MODULE, fetch_q, [ N,Q ]), 
    {queue,inserT,R1,fetchT,R2}. 

%% For Set 
create_set(N) -> 
    SET = sets:new(), 
    lists:foldl(fun(X,Prev) -> sets:add_element(X,Prev) end,SET, lists:seq(1,N)). 

test_set(N) -> 
    {R1,Set} = timer:tc(?MODULE, create_set, [N]), 
    %%Set = lists:foldl(fun(X,Prev) -> sets:add_element(X,Prev) end,SET, lists:seq(1,N)), 
    {R2,_} = timer:tc(?MODULE, fetch_set,[ N, Set ]), 
    {set,inserT,R1,fetchT,R2}. 

create(N)-> 
    [ timer:tc(?MODULE, X , [N]) || X <- [ test_list, test_dict, test_q,test_set ] ]. 

xmulti_create()-> 
    [ ?MODULE:create(X) || X<- [10,100,1000,10000,100000] ]. 

multi_create() -> 
    InputRange = [10,100,1000,10000,100000], 
    lists:map(fun(X) -> 
       ?MODULE:create(X) 
      end,InputRange). 

%%fetching midpoint tests 
fetch_q(N,Q)-> 
    fetch_q(N,Q,100). 

fetch_q(N,Q,Find) -> 
    F = fun(I) -> queue:out_r(I) end, 
    R = lists:foldl(fun(_X,{Bool,PrevQ}) -> 
       {{value, Ele},QQ} = F(PrevQ), 
       Ret1 = case Ele of 
         Temp when Temp =:= Find -> 
         true; 
         _ -> 
         Bool 
        end, 
       Ret2 = QQ, 

       {Ret1,Ret2} 

      end,{false,Q}, 
      lists:seq(1,N)), 
    R. 

fetch_set(N,Set) -> 
    fetch_set(N,Set,100). 

fetch_set(_N,Set,Find) -> 
    Return = sets:is_element(Find,Set), 
    Return. 

fetch_list(N,List) -> 
    fetch_list(N,List,500). 

fetch_list(_N,List,Find) -> 
    Ret = lists:foldl(fun(X,Prev) when X =:= Find -> true; 
      (X, Prev) -> Prev 
       end,false,List), 
    Ret. 

fetch_dict(N,Dict) -> 
    {ok,List} = dict:find([],Dict), 
    fetch_dict(N,List,500). 

fetch_dict(_N,List,Find) -> 
    Ret = lists:foldl(fun(X,Prev) when X =:= Find -> true; 
      (X, Prev) -> Prev 
       end,false,List), 
    Ret. 

%% parallel operation 

%% Parallel Map for Queue 
parallel_q(N) -> 
    {R1,Set} = timer:tc(?MODULE, parmap_create_q, [N]), 
    {parallel_q,pcreate,R1}. 

parmap_create_q(N) -> 

    PID = spawn(fun() -> 
      ?MODULE:ins_q(queue:new(),0,N) end), 
    [PID ! {self(),X} || X <- lists:seq(1,N) ], 
    receive 
    {ok, Q} -> 
     %%io:format("~n Still insertin, Q till now ~p",[Q]), 
     ok; 
    {done, Q} -> 
     io:format("~n *******DONE*********~n ~p",[Q]); 
    _E -> 
     io:format("unexpected ~p",[_E]) 
    end. 

ins_q(Q,Ctr, Max) ->  
    receive 
    {From, N} -> 
     %%io:format("~n insert ~p, ctr ~p, Q ~p ~n",[N,Ctr,Q]), 
     NewQ = queue:in(N, Q) , 
     case Ctr 
     of Temp when Temp < Max -> 
      From ! {ok, NewQ}; 
     _-> 
      From ! {done, NewQ} 
     end, 
     ?MODULE:ins_q(NewQ,Ctr+1, Max); 
    _E -> 
     io:format("unexpected ~p",[_E]), 
     ?MODULE:ins_q(Q, Ctr, Max) 
    end. 

%% Parallel Map for set 
parallel_set(N) -> 
    {R1,Set} = timer:tc(?MODULE, parmap_create_set, [N]), 
    {parallel_set,pcreate,R1}. 

parmap_create_set(N) -> 

    PID = spawn(fun() -> 
      ?MODULE:ins_set(sets:new(),0,N) end), 
    [PID ! {self(),X} || X <- lists:seq(1,N) ], 
    receive 
    {ok, Sets} -> 
     %%io:format("~n Still insertin, Sets till now ~p",[Sets]), 
     ok; 
    {done, Sets} -> 
     io:format("~n *******DONE*********~n ~p",[Sets]); 
    _E -> 
     io:format("unexpected ~p",[_E]) 
    end. 

ins_set(Sets,Ctr, Max) ->  
    receive 
    {From, N} -> 
     %%io:format("~n insert ~p, ctr ~p, Sets ~p ~n",[N,Ctr,Sets]), 
     NewSets = sets:add_element(N,Sets), 

     case Ctr 
     of Temp when Temp < Max -> 
      From ! {ok, NewSets}; 
     _-> 
      From ! {done, NewSets} 
     end, 
     ?MODULE:ins_set(NewSets,Ctr+1, Max); 
    _E -> 
     io:format("unexpected ~p",[_E]), 
     ?MODULE:ins_set(Sets, Ctr, Max) 
    end. 

%% Parallel Map for dict 
parallel_dict(N) -> 
    {R1,Set} = timer:tc(?MODULE, parmap_create_dict, [N]), 
    {parallel_dict,pcreate,R1}. 

parmap_create_dict(N) -> 

    PID = spawn(fun() -> 
      ?MODULE:ins_dict(dict:new(),0,N) end), 
    [PID ! {self(),X} || X <- lists:seq(1,N) ], 
    receive 
    {ok, Dict} -> 
     %%io:format("~n Still insertin, Sets till now ~p",[Dict]), 
     ok; 
    {done, Dict} -> 
     io:format("~n *******DONE*********~n ~p",[Dict]); 
    _E -> 
     io:format("unexpected ~p",[_E]) 
    end. 

ins_dict(Dict,Ctr, Max) ->  
    receive 
    {From, N} -> 
     %%io:format("~n insert ~p, ctr ~p, Dict ~p ~n",[N,Ctr,Dict]), 
     NewDict = dict:append([],N,Dict), 

     case Ctr 
     of Temp when Temp < Max -> 
      From ! {ok, NewDict}; 
     _-> 
      From ! {done, NewDict} 
     end, 
     ?MODULE:ins_dict(NewDict,Ctr+1, Max); 
    _E -> 
     io:format("unexpected ~p",[_E]), 
     ?MODULE:ins_dict(Dict, Ctr, Max) 
    end. 

%% Parallel Map for list 
parallel_list(N) -> 
    {R1,List} = timer:tc(?MODULE, parmap_create_list, [N]), 
    {R2,_} = timer:tc(?MODULE, para_fetch_list, [N,List]), 
    {parallel_list,pCreate,R1,pFetch,R2}. 

parmap_create_list(N) -> 

    PID = spawn(fun() -> 
      ?MODULE:ins_list([],0,N) end), 
    [PID ! {self(),X} || X <- lists:seq(1,N) ], 
    receive 
    {ok, List} -> 
     %%io:format("~n Still insertin, List till now ~p",[List]), 
     ok; 
    {done, List} -> 
     io:format("~n *******DONE*********~n ~p",[List]); 
    _E -> 
     io:format("unexpected ~p",[_E]) 
    end. 

ins_list(List,Ctr, Max) ->  
    receive 
    {From, N} -> 
     %%io:format("~n insert ~p, ctr ~p, Sets ~p ~n",[N,Ctr,Dict]), 
     NewList = List ++ [N] , 

     case Ctr 
     of Temp when Temp < Max -> 
      From ! {ok, NewList}; 
     _-> 
      From ! {done, NewList} 
     end, 
     ?MODULE:ins_list(NewList,Ctr+1, Max); 
    _E -> 
     io:format("unexpected ~p",[_E]), 
     ?MODULE:ins_list(List, Ctr, Max) 
    end. 

para_fetch_list(List, FindN) -> 
    Pid = spawn(fun() -> 
      ?MODULE:pfetch_list(FindN) end), 
    Self = self(), 
    Now1 = now(), 
    lists:map (fun(X) -> 
      Pid ! {Self, X}, 
      receive 
       {true,Find} -> 
       io:format("~n Found ~p ",[Find]), 
       true; 
       {false,Find} -> 
       %io:format("~n NOT FOUND ~p ",[Find]), 
       false; 
       _E -> 
       io:format("para main unexpected ~p",[_E]) 
      after 4000 -> 
       io:format("timerout ",[]) 

      end 
     end, List) , 
    Now2 = now(), 
    timer:now_diff(Now2,Now1). 

pfetch_list(Find) ->  
    receive 
    {From, CurrN} -> 

     _Ret = case CurrN of 
       Temp when Temp =:= Find -> 
       From ! {true,Find}, 
       true; 
       _ -> 
       From ! {false,Find}, 
       false 
      end, 
     %%io:format("~n insert ~p, ctr ~p, Sets ~p ~n",[N,Ctr,Dict]), 
     ?MODULE:pfetch_list(Find); 
    _E -> 
     io:format("pfetch unexpected ~p",[_E]), 
     ?MODULE:pfetch_list(Find) 
    end.  

pcreate(N)-> 
    [ timer:tc(?MODULE, X , [N]) || X <- [ parallel_list ] ]. 

parallel_multi_create() -> 
    InputRange = [10,100,1000,10000], 
    lists:map(fun(X) -> 
       ?MODULE:pcreate(X) 
      end,InputRange).

Im Folgenden sind die Ergebnisse: Für parallele Karte DS

([email protected])2> test:pcreate(1000). 
[{5399,{parallel_list,pCreate,5352,pFetch,30}}, 
{9886,{parallel_dict,pcreate,9875}}, 
{87603,{parallel_q,pcreate,87593}}, 
{42271,{parallel_set,pcreate,42223}}]

Für DS

([email protected])3> test:multi_create(). 
%% For 10 
[[{38,{list,inserT,14,fetchT,8}}, 
     {91,{dict,inserT,67,fetchT,11}}, 
     {47,{queue,inserT,13,fetchT,21}}, 
     {81,{set,inserT,61,fetchT,7}}], 
%%for 100 
    [{234,{list,inserT,191,fetchT,30}}, 
     {690,{dict,inserT,642,fetchT,35}}, 
     {218,{queue,inserT,60,fetchT,144}}, 
     {559,{set,inserT,540,fetchT,6}}], 
%% for 1000 
    [{13746,{list,inserT,13452,fetchT,262}}, 
     {96137,{dict,inserT,96009,fetchT,116}}, 
     {967,{queue,inserT,284,fetchT,674}}, 
     {5562,{set,inserT,5547,fetchT,5}}], 
%% for 10000 
    [{438301,{list,inserT,437256,fetchT,1027}}, 
     {361450,{dict,inserT,360412,fetchT,1020}}, 
     {7937,{queue,inserT,2292,fetchT,5636}}, 
     {31293,{set,inserT,31279,fetchT,5}}], 
% for 100000 
    [{43750210,{list,inserT,43739956,fetchT,10238}}, 
     {51517971,{dict,inserT,51507134,fetchT,10819}}, 
     {92503,{queue,inserT,29676,fetchT,62811}}, 
     {682118,{set,inserT,682100,fetchT,5}}]]

hoffen, diese Informationen können Sie feststellen, Welches ist der beste DS für die Verwendung für verschiedene Zwecke. Ich werde es aktualisieren, wenn ich mit dem gesamten Code fertig bin.

Quelle

2009-03-25 17:26:54 iankits

3

Wenn Sie eine Liste suchen möchten, verwenden Sie die Funktionen in der list module, die Teil der extensive documentation ist, die mit Erlang kommt.

Wenn Sie die besten Datenstrukturen zu nutzen wissen wollen - das ist eine etwas andere Frage, die ein bisschen mehr Informationen benötigen.

Quelle

2009-03-23 13:12:52

2

Wenn Sie diese Art von „List“ möchten, können Sie einfach die Hand Ihre eigene Suche Handwerk:

search_key(Key, [{Key,_}=V|_]) -> {ok, V}; 
search_key(Key, [_|T]) -> search_key(Key, T); 
search_key(_, []) -> not_found. 

search_val(Val, [{_,L}=X|T]) -> 
    case _search_val(Val, L) of 
    ok -> {ok, X}; 
    not_found -> search_val(Val, T) 
    end; 
search_val(_, []) -> not_found. 

_search_val(Val, [Val|_])-> ok; 
_search_val(Val, [_|T])-> _search_val(Val, T); 
_search_val(_,[])-> not_found.

Aber ich bin nicht sicher, was genau Sie wollen. Wenn Sie zum Beispiel nach dem Schlüssel "A1" und dann nach dem Wert "mike" in der Liste suchen, wird es eine andere Lösung sein. Und wenn Sie wissen möchten, wie Sie diese Art in der besten Struktur speichern, ist es nur eine andere Frage. Sie sollten mehr Informationen bereitstellen.

Quelle

2009-03-23 22:35:18

3

Verwenden keyfind Funktion aus lists Modul. Zum Beispiel:

30> List = [{"A1",["ankit","sush", "Hover", "x4", "a3","nilesh","mike","erlang"]}]. 
[{"A1", 
    ["ankit","sush","Hover","x4","a3","nilesh","mike", 
    "erlang"]}] 
31> lists:keyfind("A1", 1, List). 
{"A1", 
["ankit","sush","Hover","x4","a3","nilesh","mike","erlang"]}

Quelle

2012-07-22 17:20:12

+0

OP fragte, wie man in der Liste nach "mike" 'sucht, nicht nach" A1 ". 'lists: keyfind/3' möchte eine Liste von Tupeln auf der Basis eines" Schlüssel "-Elements der Tupel durchsuchen, aber was OP will, sucht nach einem beliebigen Prädikat. Das heißt, er möchte 'hd (Element (1, Partition (Pred, List)))' außer, ohne diese zusätzlichen Listen zu erstellen. – Quuxplusone

1

Wenn Ihre Liste ein einfacher Ausdruck basierend Artikelliste ist, dann ist die einfachste Lösung ist:

listFind (Element, []) -> 
    false; 

listFind (Element, [ Item | ListTail ]) -> 
    case (Item == Element) of 
     true -> true; 
     false -> listFind(Element, ListTail) 
    end.

Die oben unter der Annahme arbeiten, dass, wie Sie die Gleichheit Ihre Artikel überprüfen in Die Liste ist mit dem Operator ==. Sie können diesen Operator ändern, um andere Arten von Vergleich/Gleichheit zu berücksichtigen.

Quelle

2013-03-23 13:54:50 gextra

 Verwandte Themen

  • Keine verwandten Themen^_^