Hello, I just started learning Erlang and have already encountered performance disappointment when calculating math. Unfortunately, I don’t see ways to improve performance, and my hands have already dropped.
Such code:

% делится ли N на какое-нибудь число из списка % [] - делится, [N] - не делится del(N, [H|_]) when N rem H=:=0 -> []; del(N, [_|T]) -> del(N, T); del(N, []) -> [N]. % список простых чисел от 2 до N prosto(N) when is_integer(N), N>1 -> prosto(N, [], 2). prosto(N, Acc, St) when N+1=:=St -> lists:reverse(Acc); prosto(N, Acc, St) ->prosto(N, del(St, Acc)++Acc, St+1). 

When creating a list of up to 200,000, it takes an average of 39 seconds.
Java similar functionality code

 static boolean del(int N, ArrayList<Integer> L){ int size=L.size(); for (int i=0; i<size; i++) { if (N % L.get(i)==0) return true; } return false; } static ArrayList<Integer> prosto(int N){ ArrayList<Integer> res=new ArrayList<Integer>(); for (int i=2; i<=N; i++) { if (!del(i, res)) res.add(i); } return res; } 

When creating a list of the same length, it takes an average of 0.75 seconds. 52 times faster.
Question : Is it possible to create more efficient code on erlang?

  • PS Increase efficiency in the following way: prosto (N) when is_integer (N), N> 1 -> prosto (N, [], 3). prosto (N, Acc, St) when N + 1 =: = St -> lists: reverse (Acc); prosto (N, Acc, St) -> prosto (N, del (St, Acc) ++ Acc, St + 2). it is not considered, although it reduces the number of iterations by half. - ReinRaus
  • del(St, Acc)++Acc looks suspicious. [hd(del(St, Acc)]|Acc] or [St|Acc] may be better. - alexlz
  • @alexz, I tried to create a list in this way, only without mathematics. A list of 200,000 items is created very quickly, that is, this is not the bottleneck of the program. It looks like a lot of mathematics is slowing down, namely, finding the remainder. - ReinRaus
  • @RainRaus, I do not understand you (the text of the commentary is not clear). I understand that the changes I have proposed do not give effect? Or what? Considerations are as follows: the divisors of the majority of the tested numbers are small and, accordingly, are at the end of the list. Most of the tested numbers are eliminated, so the search for divisors takes a lot of time. If new numbers are added to the tail, then the search for dividers will speed up (due to an increase in the time of adding new simple ones). Like it or not - you need to look at the profiler. Well, you can use other data structures (eg array) instead of a unidirectional list. - alexlz
  • > faced with disappointment in performance in calculating mathematics

1 answer 1

Looks like he was wrong. Try adding to the end of the list.

  prosto(N, Acc, St) when N+1=:=St -> Acc; prosto(N, Acc, St) ->prosto(N, case del(St, Acc) of [] -> Acc; [N1] -> Acc++[N1] end, St+case St of 2 -> 1; _ -> 2 end ). 

As the main part of the screening goes at the top of the list: 2, 3 ...

Well, it does not work out - also a plus, learn to work with a profiler. He is in erlang'e like to eat.

  • And the truth: the codes for erlang and java are not similar. Since erlang selects dividers from large ones, and java from smaller ones. Such an edit: Acc ++ del (St, Acc) reduces the execution time to 8 seconds, and this is not so bad. I counted the number of iterations in the calculation (approximately 120 million), and so, rem performs so much erlang in 4 seconds, that is, half of the total time. The result is satisfied in general. I will learn erlang further. Thank you :) - ReinRaus
  • @RainRaus Please. But in the case of Acc++del(St, Acc) I do not know whether erlang does optimization for the case of del(St, Acc) =:= [] . If not, then superfluous viewing of Acc for each rejected number. - alexlz