Erlang में हजारों संदेशों के लिए प्राप्त पाश को कैसे अनुकूलित करें?

Question

अध्याय प्रोग्रामिंग Erlang पुस्तक के "प्रोग्रामिंग मल्टीकोर CPUs" में, जो आर्मस्ट्रांग एक नक्शे के समारोह के साथ में चलाना का एक अच्छा उदाहरण देता है:

pmap(F, L) -> 
    S = self(), 
    %% make_ref() returns a unique reference 
    %% we'll match on this later 
    Ref = erlang:make_ref(), 
    Pids = map(fun(I) -> 
     spawn(fun() -> do_f(S, Ref, F, I) end) 
    end, L), 
    %% gather the results 
    gather(Pids, Ref). 

do_f(Parent, Ref, F, I) -> 
    Parent ! {self(), Ref, (catch F(I))}. 

gather([Pid|T], Ref) -> 
    receive 
     {Pid, Ref, Ret} -> [Ret|gather(T, Ref)] 
    end; 

gather([], _) -> 
    []. 

यह अच्छी तरह से काम करता है, लेकिन मेरा मानना ​​है कि के कारण इसमें एक अड़चन है यह 100,000+ तत्वों के साथ सूचियों पर वास्तव में धीमी गति से काम करने के लिए काम करता है।

जब gather() फ़ंक्शन निष्पादित किया जाता है, तो यह मुख्य प्रक्रिया मेलबॉक्स में किसी संदेश के साथ Pids सूची से पहले Pid से मेल खाता है। लेकिन क्या होगा यदि मेलबॉक्स में सबसे पुराना संदेश इस Pid से नहीं है? फिर यह अन्य सभी संदेशों को तब तक कोशिश करता है जब तक कि यह एक मैच न मिल जाए। ऐसा कहा जा रहा है कि, एक निश्चित संभावना है कि gather() फ़ंक्शन निष्पादित करते समय हमें के साथ एक मिलान खोजने के लिए सभी मेलबॉक्स संदेशों के माध्यम से लूप करना होगा जिसे हमने Pids सूची से लिया है।

gather([Pid|T], Ref) -> 
    receive 
     {Pid, Ref, Ret} -> [Ret|gather(T, Ref)]; 
     %% Here it is: 
     Other -> io:format("The oldest message in the mailbox (~w) did not match with Pid ~w~n", [Other,Pid]) 
    end; 

मैं इस टोंटी से बच सकते हैं: यह आकार एन की एक सूची

मैं भी इस टोंटी के अस्तित्व को साबित करने में कामयाब रहे है एन * एन सबसे खराब स्थिति है?

Answer 1

इस मामले में आप dict (मूल सूची में इंडेक्स में मूल प्रक्रिया के सूचकांक से) का उपयोग कर सकते हैं Pids के बजाय।

Answer 2

समस्या आप अभी भी करने के लिए है कि यदि आप एक सही समाधान करना चाहते है:

• जांच कर लें कि किसी दिए गए जबाब प्रक्रियाओं आप में से एक से आता है पैदा की
• उचित परिणाम आदेश
सुनिश्चित

यहां एक समाधान है जो सूचियों के बजाय काउंटरों का उपयोग करता है - इससे कई बार इनबॉक्स को पार करने की आवश्यकता समाप्त हो जाती है। Ref का मिलान यह सुनिश्चित करता है कि हमारे द्वारा प्राप्त किए जा रहे संदेश हमारे बच्चों से हैं। pmap के बहुत अंत में परिणाम lists:keysort/2 के साथ परिणाम क्रमबद्ध करके उचित आदेश सुनिश्चित किया जाता है, जो कुछ ओवरहेड जोड़ता है, लेकिन यह O(n^2) से कम होने की संभावना है।

-module(test). 

-compile(export_all). 

pmap(F, L) -> 
    S = self(), 
    % make_ref() returns a unique reference 
    % we'll match on this later 
    Ref = erlang:make_ref(), 
    Count = lists:foldl(fun(I, C) -> 
           spawn(fun() -> 
               do_f(C, S, Ref, F, I) 
             end), 
           C+1 
         end, 0, L), 
    % gather the results 
    Res = gather(0, Count, Ref), 
    % reorder the results 
    element(2, lists:unzip(lists:keysort(1, Res))). 


do_f(C, Parent, Ref, F, I) -> 
    Parent ! {C, Ref, (catch F(I))}. 


gather(C, C, _) -> 
    []; 
gather(C, Count, Ref) -> 
    receive 
     {C, Ref, Ret} -> [{C, Ret}|gather(C+1, Count, Ref)] 
    end. 

Answer 3

जो का उदाहरण साफ है, लेकिन व्यावहारिक रूप से आप अपनी समस्या के लिए एक अधिक हेवीवेट समाधान चाहते हैं। उदाहरण के लिए http://code.google.com/p/plists/source/browse/trunk/src/plists.erl पर एक नज़र डालें।

1. एक काम इकाई है जो "काफी बड़ा है" चुनें:

   सामान्य में, वहाँ तीन चीजें आप क्या करना चाहते हैं। यदि कार्य इकाई बहुत छोटी है, तो आप ओवरहेड प्रोसेसिंग से मर जाते हैं। यदि यह बहुत बड़ा है, तो आप श्रमिकों द्वारा निष्क्रिय होने से मर जाते हैं, खासकर यदि आपका काम सूची में तत्व गणना द्वारा समान रूप से विभाजित नहीं होता है।

2. ऊपरी श्रमिकों की संख्या को ऊपरी सीमाबद्ध करें। Psyeugenic शेड्यूलर द्वारा इसे विभाजित करने का प्रस्ताव है, मैं नौकरी गिनती सीमा से इसे विभाजित करने का प्रस्ताव करता हूं, 100 नौकरियां कहती हैं। यही है, आप 100 नौकरियां शुरू करना चाहते हैं और तब तक प्रतीक्षा करें जब तक कि आप अधिक नौकरियां शुरू करने से पहले उनमें से कुछ पूरा नहीं कर लेते।

3. यदि संभव हो तो तत्वों के क्रम को खराब करने पर विचार करें।यदि आपको ऑर्डर लेने की आवश्यकता नहीं है तो यह बहुत तेज़ है। कई समस्याओं के लिए यह संभव है। यदि ऑर्डर मायने रखता है, तो सामान को स्टोर के रूप में स्टोर करने के लिए dict का उपयोग करें। यह बड़े-तत्व सूचियों के लिए तेज़ है।

बुनियादी नियम है कि जैसे ही आप समानांतर चाहते हैं, तो आप शायद ही कभी अपने डेटा की एक सूची के आधार पर प्रतिनिधित्व करना चाहते हैं। सूची में एक अंतर्निहित रैखिकता है, जिसे आप नहीं चाहते हैं। गाय स्टीइल द्वारा बहुत विषय पर एक बात है: http://vimeo.com/6624203