Оптимизация максимальной последовательности Коллатца - PullRequest
Новая
       0

Оптимизация максимальной последовательности Коллатца

0 голосов
/ 23 декабря 2018

Я ищу, чтобы оптимизировать свое решение для максимальной проблемы последовательности Коллатца в Эрланге.Прямо сейчас я попробовал использовать ETS, и в следующем решении используются карты, но производительность у меня хуже, чем мне кажется.Есть ли какая-то оптимизация, которую я мог бы сделать, чтобы улучшить ее? 

-module(collatzMaps).

-export([start/2, s/4]).

collatz(0, Map) -> 
    {0, Map};
collatz(M, Map) ->

    Exists = maps:is_key(M, Map),
    case Exists of    
        false ->

            case M rem 2 == 0 of
                true ->
                    Result = collatz(M div 2, Map),
                    Val = (1 + element(1, Result)),
                    Map1 = maps:put(M, Val, element(2, Result)),
                    {maps:get(M, Map1), Map1};

                false ->
                    Result = collatz((3 * M + 1), Map),
                    Val = (1 + element(1, Result)),
                    Map2 = maps:put(M, Val, element(2, Result)),
                    {maps:get(M, Map2), Map2}
            end;
        true ->

            {maps:get(M, Map), Map}
    end.

s(N, M, Max, Map) ->

    if
        N =< M ->

            Result = collatz(N, Map),
            if
                element(1, Result) > Max ->
                    NextMax = element(1, Result),
                    MapNext = element(2, Result),
                    s(N + 1, M, NextMax, MapNext);
                true ->
                    MapNext = element(2, Result),
                    s(N + 1, M, Max, MapNext)
            end;
        true ->
            Max
    end.

start(N, M)->

    statistics(runtime),
    statistics(wall_clock),
    Map = maps:new(),
    Map1 = maps:put(1, 1, Map),
    G = s(N, M, 0, Map1),
    {_, Time2} = statistics(wall_clock),
    U2 = Time2 / 1000,
    io:format("~p seconds~n", [U2]),
    G.

1 Ответ

0 голосов
/ 27 декабря 2018

Ну, во-первых, давайте настроим вызов, который позволит нам сделать простую статистику и сравнить различные подходы 

-export([start/2, max_collatz/2]).

...

max_collatz(N, M) ->
    Map = maps:new(),
    Map1 = maps:put(1, 1, Map),
    s(N, M, 0, Map1).

start(N, M)->
    {T, Result} = timer:tc( fun() ->  max_collatz(N, M) end),
    io:format("~p seconds~n", [T / 1000000]),
    Result.

Итак, давайте напишем это более ирландским способом Erlang 

-module(collatz).

-export([start/2, max_collatz/2]).

collatz_next(N) when N rem 2 =:= 0 ->
    N div 2;
collatz_next(N) ->
    3 * N + 1.

collatz_length(N, Map) ->
    case Map of
        #{N := L} -> {L, Map};
        _ ->
            {L, Map2} = collatz_length(collatz_next(N), Map),
            {L + 1, Map2#{N => L + 1}}
    end.

max_collatz(N, M) ->
    Map = lists:foldl(fun(X, Map) -> {_, Map2} = collatz_length(X, Map), Map2 end,
                      #{1 => 1}, lists:seq(N, M)),
    lists:max(maps:values(Map)).

start(N, M) ->
    {T, Result} = timer:tc(fun() -> max_collatz(N, M) end),
    io:format("~p seconds~n", [T / 1000000]),
    Result.

Затеммы можем сравнить скорость, используя, например, eministat .

Clone in 

git clone https://github.com/jlouis/eministat.git
cd eministat
make

Если вы столкнетесь с такой проблемой, как 

 DEPEND eministat.d
 ERLC   eministat.erl eministat_analysis.erl eministat_ds.erl eministat_plot.erl eministat_report.erl eministat_resample.erl eministat_ts.erl
compile: warnings being treated as errors
src/eministat_resample.erl:8: export_all flag enabled - all functions will be exported
erlang.mk:4940: recipe for target 'ebin/eministat.app' failed
make[1]: *** [ebin/eministat.app] Error 1
erlang.mk:4758: recipe for target 'app' failed
make: *** [app] Error 2

Вы можетеисправить это 

diff --git src/eministat_resample.erl src/eministat_resample.erl
index 1adf401..0887b2c 100644
--- src/eministat_resample.erl
+++ src/eministat_resample.erl
@@ -5,7 +5,7 @@
 -include("eministat.hrl").

 -export([resample/3, bootstrap_bca/3]).
--compile(export_all).
+-compile([nowarn_export_all, export_all]).

 %% @doc resample/3 is the main resampler of eministat
 %% @end

Итак, запустите его 

$ erl -pa eministat/ebin/
Erlang/OTP 21 [erts-10.1] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:1] [hipe]

Eshell V10.1  (abort with ^G)
1> c(collatzMaps), c(collatz).                                                                                                                                  
{ok,collatz}
2> eministat:x(95.0, eministat:s(orig, fun() -> collatzMaps:max_collatz(1, 100000) end, 30), eministat:s(new, fun() -> collatz:max_collatz(1, 100000) end, 30)).
x orig
+ new
+--------------------------------------------------------------------------+
|+    ++++++++ +++++   * +  +x+**+xxxx**x xxx xx+x xxx *x  x  +   x       x|
|        +   + +                   x x xx            x                     |
|        +                                                                 |
|                               |_______M___A__________|                   |
|      |________M_____A______________|                                     |
+--------------------------------------------------------------------------+
Dataset: x N=30 CI=95.0000
Statistic     Value     [         Bias] (Bootstrapped LB‥UB)
Min:         1.76982e+5
1st Qu.      1.81610e+5
Median:      1.82954e+5
3rd Qu.      1.87030e+5
Max:         1.94944e+5
Average:     1.84280e+5 [      8.00350] (   1.82971e+5 ‥    1.85749e+5)
Std. Dev:       3999.87 [     -102.524] (      3128.74 ‥       5431.13)

Outliers: 0/0 = 0 (μ=1.84288e+5, σ=3897.35)
        Outlier variance:    3.22222e-2 (slight)

------

Dataset: + N=30 CI=95.0000
Statistic     Value     [         Bias] (Bootstrapped LB‥UB)
Min:         1.69179e+5
1st Qu.      1.72501e+5
Median:      1.74614e+5
3rd Qu.      1.79850e+5
Max:         1.90638e+5
Average:     1.76517e+5 [      3.11862] (   1.74847e+5 ‥    1.78679e+5)
Std. Dev:       5343.46 [     -147.802] (      4072.99 ‥       7072.53)

Outliers: 0/0 = 0 (μ=1.76520e+5, σ=5195.66)
        Outlier variance:    9.43164e-2 (slight)

Difference at 95.0% confidence
        -7762.60 ± 2439.69
        -4.21240% ± 1.32391%
        (Student's t, pooled s = 4719.72)
------

ok

Так что теперь это кажется на 4% быстрее, что не так много.Во-первых, мы можем встроить collatz_next/1, что в основном соответствует функции collatz/2.Мне нравится быть конкретным, поэтому я ставлю между -export и первой функцией 

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

Это имеет очень небольшой эффект 

Difference at 95.0% confidence
        -9895.27 ± 5524.91
        -5.24520% ± 2.92860%
        (Student's t, pooled s = 1.06882e+4)

Тогда мы можем попробовать развернуть lists:fold/2, lists:seq/2 и lists:max/1 как в вашей s/4 функции, но давайте сделаем это более идиотским способом. 

max_collatz(N, M) ->
    max_collatz(N, M, 1, #{1 => 1}).

max_collatz(M, M, Max, _) -> Max;
max_collatz(N, M, Max, Map) ->
    case collatz_length(N + 1, Map) of
        {L, Map2} when L > Max ->
            max_collatz(N + 1, M, L, Map2);
        {_, Map2} ->
            max_collatz(N + 1, M, Max, Map2)
    end.

Ну, это лучше, но все же немного 

Difference at 95.0% confidence
        -1.78775e+4 ± 1980.35
        -9.66832% ± 1.07099%

Теперь, когда мыудалил все вызовы внешнего кода, стоит попробовать нативную компиляцию (вызов внешней функции обычно сводит на нет все преимущества нативной компиляции)Мы также могли бы добавить небольшую подсказку типа для HiPE, но она, похоже, не дает никакого эффекта (обычно стоит попробовать арифметику с плавающей запятой, что не в данном случае, и интенсивное использование карт, вероятно, также создает проблему здесь). 

max_collatz(N, M) when N < M, is_integer(N), is_integer(M) ->
    max_collatz(N, M, 1, #{1 => 1}).

Не намного лучше 

c(collatz, [native]).
...
Difference at 95.0% confidence
        -2.26703e+4 ± 2651.32
        -12.1721% ± 1.42354%
        (Student's t, pooled s = 5129.13)

Так что пора попробовать его грязным.Словарь процессов не является рекомендуемым местом для хранения ваших данных, но если он находится внутри специального процесса, это приемлемое решение. 

collatz_length(N) ->
    case get(N) of
        undefined -> 
            L = collatz_length(collatz_next(N)),
            put(N, L + 1),
            L + 1;
        L -> L
    end.

max_collatz(N, M) when N < M, is_integer(N), is_integer(M) ->
    P = self(),
    W = spawn_link(fun() ->
                           put(1, 1),
                           P ! {self(), max_collatz(N, M, 1)}
                   end),
    receive {W, Max} -> Max end.

max_collatz(M, M, Max) -> Max;
max_collatz(N, M, Max) ->
    case collatz_length(N + 1) of
        L when L > Max ->
            max_collatz(N + 1, M, L);
        _ ->
            max_collatz(N + 1, M, Max)
    end.

Да, это грязное, но рабочее решение и оно того стоит (даже без native) 

Difference at 95.0% confidence
        -1.98173e+5 ± 5450.92
        -80.9384% ± 2.22628%
        (Student's t, pooled s = 1.05451e+4)

Итак, здесь мы перешли от 3,6 до 0,93 с использованием некоторых грязных трюков, но в любом случае, если бы вы выполняли такого рода задачи, вы, вероятно, использовали бы NIF, написанный на C. Это нетип задачи, где Erlang Shine. 

> collatzMaps:start(1, 1000000).
3.576669 seconds
525
> collatz:start(1, 1000000).                                                                                                                                   
0.931186 seconds
525
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...