2008-09-18 18 views
6

मैं एर्लांग में प्रोग्राम करने के तरीके के बारे में जानने के लिए projecteuler.net पर समस्याओं के माध्यम से जा रहा हूं, और मुझे एक प्रमुख जनरेटर बनाने में सबसे कठिन समय है जो 2 मिलियन से कम सभी प्राइम बना सकता है, कम से कम एक मिनट। अनुक्रमिक शैली का उपयोग करके, मैंने पहले से ही तीन प्रकार के जेनरेटर लिखे हैं, जिनमें से इरेटोस्टेनेस की सिलाई भी शामिल है, और इनमें से कोई भी पर्याप्त प्रदर्शन नहीं करता है।समवर्ती प्राइम जनरेटर

मुझे लगा कि एक समवर्ती चाइव बहुत अच्छा काम करेगा, लेकिन मुझे बुराई संदेश मिल रहा है, और मुझे यकीन नहीं है कि क्यों। मुझे कोई समस्या क्यों है, या इसे ठीक से कैसे कोड करें?

 
-module(primeserver). 
-compile(export_all). 

start() -> 
    register(primes, spawn(fun() -> loop() end)). 

is_prime(N) -> rpc({is_prime,N}). 

rpc(Request) -> 
    primes ! {self(), Request}, 
    receive 
     {primes, Response} -> 
      Response 
    end. 

loop() -> 
    receive 
     {From, {is_prime, N}} -> 
      if 
       N From ! {primes, false}; 
       N =:= 2 -> From ! {primes, true}; 
       N rem 2 =:= 0 -> From ! {primes, false}; 
       true -> 
        Values = is_not_prime(N), 
        Val = not(lists:member(true, Values)), 
        From ! {primes, Val} 
      end, 
      loop() 
    end. 

for(N,N,_,F) -> [F(N)]; 
for(I,N,S,F) when I + S [F(I)|for(I+S, N, S, F)]; 
for(I,N,S,F) when I + S =:= N -> [F(I)|for(I+S, N, S, F)]; 
for(I,N,S,F) when I + S > N -> [F(I)]. 

get_list(I, Limit) -> 
    if 
     I 
      [I*A || A 
      [] 
    end. 

is_not_prime(N) -> 
    for(3, N, 2, 
     fun(I) -> 
      List = get_list(I,trunc(N/I)), 
      lists:member(N,lists:flatten(List)) 
     end 
     ). 

    %%L = for(1,N, fun() -> spawn(fun(I) -> wait(I,N) end) end), 
    %%SeedList = [A || A 
    %%  lists:foreach(fun(X) -> 
    %%    Pid ! {in_list, X} 
    %%    end, SeedList) 
    %%  end, L). 

%%wait(I,N) -> 
%% List = [I*A || A lists:member(X,List) 
%% end. 
+0

आपने मार्कडाउन के अनुचित वाक्यविन्यास रंग को कैसे दबाया? –

उत्तर

3

'बुडारिटी' त्रुटि का अर्थ है कि आप गलत के साथ 'मजेदार' कॉल करने का प्रयास कर रहे हैं तर्कों की संख्या। इस मामले में ...

%% एल = (1, एन, मज़ा() -> अंडे (मज़ा (आई) -> प्रतीक्षा (मैं, एन) अंत) अंत) के लिए,

के लिए/3 कार्य धर्मार्थ 1 के मजे की अपेक्षा करता है, और स्पॉन/1 फ़ंक्शन धर्मार्थ 0 के मजे की अपेक्षा करता है।बजाय इस प्रयास करें:

L = for(1, N, fun(I) -> spawn(fun() -> wait(I, N) end) end), 

मज़ा अंडे देने के लिए पारित कर दिया की जरूरत अपने पर्यावरण के कुछ हिस्सों को विरासत में (अर्थात् मैं), तो यह स्पष्ट रूप से पारित करने के लिए कोई आवश्यकता नहीं है।

प्राइम की गणना करना हमेशा अच्छा मजेदार होता है, कृपया ध्यान रखें कि यह समस्या हल करने के लिए डिज़ाइन की गई समस्या नहीं है। Erlang बड़े अभिनेता-शैली समेकन के लिए डिजाइन किया गया था। यह डेटा-समांतर गणना के सभी उदाहरणों पर अधिकतर खराब प्रदर्शन करेगा। कई मामलों में, a sequential solution in, say, ML इतनी तेजी से होगा कि एरलंग को पकड़ने के लिए किसी भी संख्या में कोर पर्याप्त नहीं होंगे, और उदा। F# and the .NET Task Parallel Library निश्चित रूप से इस तरह के संचालन के लिए एक बेहतर वाहन होगा।

-1

मैं परियोजना यूलर प्यार:

यहाँ मेरी कोड, बाहर टिप्पणी की वर्गों जहां मैं चीजों को समवर्ती करने की कोशिश की हैं।

प्राइम जेनरेटर के विषय पर, मैं एराटोस्टेनेस की चलनी का एक बड़ा प्रशंसक हूं।

2,000,000 से कम संख्या के प्रयोजनों के लिए आप एक सरल हैप्रिम जांच कार्यान्वयन का प्रयास कर सकते हैं। मुझे नहीं पता कि आप इसे एरलांग में कैसे करेंगे, लेकिन तर्क सरल है।

For Each NUMBER in LIST_OF_PRIMES 
    If TEST_VALUE % NUMBER == 0 
      Then FALSE 
END 
TRUE 

if isPrime == TRUE add TEST_VALUE to your LIST_OF_PRIMES 

iterate starting at 14 or so with a preset list of your beginning primes. 

C# 1 मिनट निशान के नीचे अच्छी तरह से में 2,000,000 के लिए इस प्रकार की सूची भाग गया

संपादित करें:एक तरफ ध्यान दें पर, एरेटोस्थेनेज की चलनी आसानी से लागू किया जा सकता है और जल्दी से चलाता है, लेकिन हो जाता है जब आप बड़ी सूचियों में शामिल होना शुरू करते हैं तो अनावश्यक। एक बुलियन सरणी और int मानों का उपयोग करके सबसे सरल कार्यान्वयन अत्यंत तेज़ी से चलता है। समस्या यह है कि आप अपने मूल्य के आकार के साथ-साथ अपनी सरणी की लंबाई के लिए सीमाओं में चलना शुरू करते हैं। - स्ट्रिंग या बिटरएयर कार्यान्वयन में स्विचिंग में मदद मिलती है, लेकिन आपको अभी भी बड़ी सूची में आपकी सूची के माध्यम से पुनरावृत्ति की चुनौती है।

-1

प्रोजेक्ट यूलर की समस्याएं (मैं कहूंगा कि अधिकतर 50 में से अधिकतर नहीं तो अधिकतर कहते हैं) अधिकतर आपकी सीमाओं को चुनने में सरलता के स्पलैश के साथ ब्रूट फोर्स के बारे में हैं।

एन अगर प्राइम (ब्रूट फोर्स द्वारा) है तो किसी भी प्राइम अप फर्श (वर्ग (एन)) + 1, एन/2 के द्वारा विभाजित होने की आवश्यकता है, तो किसी को भी जांचना याद रखें।

गुड लक

0

एरेटोस्थेनेज की चलनी लागू करने के लिए काफी आसान है, लेकिन है - के रूप में आप की खोज की है - सबसे कारगर नहीं। क्या आपने एटकिन की चाकू की कोशिश की है?

Sieve of Atkin @ Wikipedia

+0

मैं कई कोरों पर एसओई को स्केल करने में असफल रहा लेकिन सोए http://alicebobandmallory.com/articles/2010/01/14/prime-factorization-in-parallel के साथ बड़ी सफलता मिली –

1

एक अन्य विकल्प पर विचार करने के probabalistic प्रधानमंत्री पीढ़ी का प्रयोग है। जो की पुस्तक ("प्राइम सर्वर") में इसका एक उदाहरण है जो मिलर-राबिन मुझे लगता है ...

1

आप प्राइम नंबर खोजने के लिए चार अलग-अलग एरलांग कार्यान्वयन पा सकते हैं (जिनमें से दो एरेटोस्टेनेस की चलनी पर आधारित हैं) here। इस लिंक में 4 समाधानों के प्रदर्शन की तुलना में ग्राफ भी शामिल हैं।

-1

यहाँ

'Sieve of Eratosthenes 
'http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 
'1. Create a contiguous list of numbers from two to some highest number n. 
'2. Strike out from the list all multiples of two (4, 6, 8 etc.). 
'3. The list's next number that has not been struck out is a prime number. 
'4. Strike out from the list all multiples of the number you identified in the previous step. 
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list). 
'6. All the remaining numbers in the list are prime. 
Private Function Sieve_of_Eratosthenes(ByVal MaxNum As Integer) As List(Of Integer) 
    'tested to MaxNum = 10,000,000 - on 1.8Ghz Laptop it took 1.4 seconds 
    Dim thePrimes As New List(Of Integer) 
    Dim toNum As Integer = MaxNum, stpw As New Stopwatch 
    If toNum > 1 Then 'the first prime is 2 
     stpw.Start() 
     thePrimes.Capacity = toNum 'size the list 
     Dim idx As Integer 
     Dim stopAT As Integer = CInt(Math.Sqrt(toNum) + 1) 
     '1. Create a contiguous list of numbers from two to some highest number n. 
     '2. Strike out from the list all multiples of 2, 3, 5. 
     For idx = 0 To toNum 
      If idx > 5 Then 
       If idx Mod 2 <> 0 _ 
       AndAlso idx Mod 3 <> 0 _ 
       AndAlso idx Mod 5 <> 0 Then thePrimes.Add(idx) Else thePrimes.Add(-1) 
      Else 
       thePrimes.Add(idx) 
      End If 
     Next 
     'mark 0,1 and 4 as non-prime 
     thePrimes(0) = -1 
     thePrimes(1) = -1 
     thePrimes(4) = -1 
     Dim aPrime, startAT As Integer 
     idx = 7 'starting at 7 check for primes and multiples 
     Do 
      '3. The list's next number that has not been struck out is a prime number. 
      '4. Strike out from the list all multiples of the number you identified in the previous step. 
      '5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list). 
      If thePrimes(idx) <> -1 Then ' if equal to -1 the number is not a prime 
       'not equal to -1 the number is a prime 
       aPrime = thePrimes(idx) 
       'get rid of multiples 
       startAT = aPrime * aPrime 
       For mltpl As Integer = startAT To thePrimes.Count - 1 Step aPrime 
        If thePrimes(mltpl) <> -1 Then thePrimes(mltpl) = -1 
       Next 
      End If 
      idx += 2 'increment index 
     Loop While idx < stopAT 
     '6. All the remaining numbers in the list are prime. 
     thePrimes = thePrimes.FindAll(Function(i As Integer) i <> -1) 
     stpw.Stop() 
     Debug.WriteLine(stpw.ElapsedMilliseconds) 
    End If 
    Return thePrimes 
End Function 
0

दो त्वरित एकल प्रक्रिया erlang प्रधानमंत्री जनरेटर एक vb संस्करण है; स्पिम्स सभी प्राइम्स को ~ 2.7 सेकेंड में 2 मीटर के नीचे उत्पन्न करता है, मेरे कंप्यूटर पर fprimes ~ 3 सेकंड (2.4 गीगाहर्ट्ज कोर 2 डुओ के साथ मैकबुक)। दोनों एराटोस्टेनेस की चलनी पर आधारित हैं, लेकिन चूंकि एरलांग सरणी के बजाए सूचियों के साथ सबसे अच्छा काम करता है, दोनों गैर-उन्मूलित प्राइम्स की एक सूची रखते हैं, वर्तमान सिर द्वारा विभाज्यता की जांच करते हैं और सत्यापित प्राइम के जमाकर्ता को रखते हैं। दोनों सूची में प्रारंभिक कमी करने के लिए एक प्राइम व्हील भी लागू करते हैं।

-module(primes). 
-export([sprimes/1, wheel/3, fprimes/1, filter/2]).  

sieve([H|T], M) when H=< M -> [H|sieve([X || X<- T, X rem H /= 0], M)]; 
sieve(L, _) -> L. 
sprimes(N) -> [2,3,5,7|sieve(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), math:sqrt(N))]. 

wheel([X|Xs], _Js, M) when X > M -> 
    lists:reverse(Xs); 
wheel([X|Xs], [J|Js], M) -> 
    wheel([X+J,X|Xs], lazy:next(Js), M); 
wheel(S, Js, M) -> 
    wheel([S], lazy:lazy(Js), M). 

fprimes(N) -> 
    fprimes(wheel(11, [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10], N), [7,5,3,2], N). 
fprimes([H|T], A, Max) when H*H =< Max -> 
    fprimes(filter(H, T), [H|A], Max); 
fprimes(L, A, _Max) -> lists:append(lists:reverse(A), L). 

filter(N, L) -> 
    filter(N, N*N, L, []). 
filter(N, N2, [X|Xs], A) when X < N2 -> 
    filter(N, N2, Xs, [X|A]); 
filter(N, _N2, L, A) -> 
    filter(N, L, A). 
filter(N, [X|Xs], A) when X rem N /= 0 -> 
    filter(N, Xs, [X|A]); 
filter(N, [_X|Xs], A) -> 
    filter(N, Xs, A); 
filter(_N, [], A) -> 
    lists:reverse(A). 

आलसी: आलसी/1 और आलसी: अगला/1 छद्म आलसी अनंत सूचियों का एक सरल कार्यान्वयन का संदर्भ लें:

lazy(L) -> 
    repeat(L). 

repeat(L) -> L++[fun() -> L end]. 

next([F]) -> F()++[F]; 
next(L) -> L. 

चलनी द्वारा प्रधानमंत्री पीढ़ी संगामिति लिए एक महान जगह नहीं है (लेकिन यह विभाज्यता की जांच में समांतरता का उपयोग कर सकता है, हालांकि ऑपरेशन अब तक लिखे गए सभी समानांतर फ़िल्टरों के अतिरिक्त ओवरहेड को उचित ठहराने के लिए पर्याप्त जटिल नहीं है)।

`

7

मैं एक Eratosthenesque समवर्ती प्रधानमंत्री चलनी जाओ और चैनलों का उपयोग कर लिखा था। http://github.com/aht/gosieve

मैं यहाँ यह के बारे में ब्लॉग: http://blog.onideas.ws/eratosthenes.go

कार्यक्रम के बारे में 10 सेकंड में पहली मिलियन अभाज्य संख्या (15,485,863 तक के सभी अभाज्य संख्या) बाहर छलनी कर सकते हैं

यहाँ कोड है। चलनी समवर्ती है, लेकिन एल्गोरिदम मुख्य रूप से तुल्यकालिक है: गोरोटाइन्स ("अभिनेता" - यदि आपको पसंद है) के बीच बहुत अधिक सिंक्रनाइज़ेशन पॉइंट आवश्यक हैं और इस प्रकार वे समानांतर में स्वतंत्र रूप से घूम नहीं सकते हैं।

संबंधित मुद्दे