4

だから私はErlangにとても興味があります。何か大きなことに使う言い訳がみつかりませんが、ときどきおもちゃの問題に使うようにしています。

現在、ローマ数字のトランスレーターを実装しています。私は今のところ「to」の部分をやっているところですが、コードが非常に反復的であることがわかりました。それは魅力のように機能しますが、まあ、それを見てください:

-module(roman).
-compile([export_all]).

toRoman(N) ->
    toRoman(N, []).

toRoman(0,Acc) ->
    lists:reverse(lists:flatten(Acc));

toRoman(N, Acc) when N >= 1000 ->
    toRoman(N-1000,["M"|Acc]);

toRoman(N,Acc) when N >= 900 ->
    toRoman(N-900,["CM" | Acc]);

toRoman(N,Acc) when N >= 500 ->
    toRoman(N-500,["D" | Acc]);

toRoman(N,Acc) when N >= 400 ->
    toRoman(N-400, ["CD" | Acc]);

toRoman(N,Acc) when N >= 100 ->
    toRoman(N-100, ["C" | Acc]);

toRoman(N,Acc) when N >= 90 ->
    toRoman(N-90, ["XC" | Acc]);

toRoman(N,Acc) when N >= 50 ->
    toRoman(N-50, ["L" | Acc]);

toRoman(N, Acc) when N >= 40 ->
    toRoman(N-40, ["XL" | Acc]);

toRoman(N, Acc) when N >= 10 ->
    toRoman(N-10, ["X" | Acc]);

toRoman(N, Acc) when N >= 9 ->
    toRoman(N-9, ["IX" | Acc]);

toRoman(N, Acc) when N >= 5 ->
    toRoman(N-5, ["V" | Acc]);

toRoman(N, Acc) when N >= 4 ->
    toRoman(N-4, ["IV" | Acc]);

toRoman(N, Acc) ->
    toRoman(N-1, ["I" | Acc]).

test() ->
    Test = fun(X) -> io:format("~p -> ~p~n", [X, toRoman(X)]) end,
    lists:map(Test, [0,1,3,6,23,43,75,87,13,23, 3999, 3998, 2531, 140]).

これを行うにはもっと良い方法があるように感じます。誰でも洞察を提供できますか?

4

8 に答える 8

6

実際、あなたのコードはそれほど反復的ではありません。テキストが繰り返しパターンを形成するため、そのように見えます。ただし、各句は特定のケースを処理し、それらの間で論理的な重複はほとんどありません。switch ステートメントで再実装することもできますが、同様の繰り返しが発生します。ローマ数字の翻訳にはあまりにも多くのケースがあり、それらの個々の決定が引き起こす反復的な感覚を避けることはできないと思います.

于 2009-11-05T05:24:22.020 に答える
5

以前にこれをrosettacode.orgに追加したので、ここに再投稿します。ソリューションは非常にエレガントであることがわかりました。

-module(roman).
-export([to_roman/1]).

to_roman(0) -> [];
to_roman(X) when X >= 1000 -> "M" ++ to_roman(X-1000);
to_roman(X) when X >= 100 -> digit(X div 100, $C,$D,$M) ++ to_roman(X rem 100);
to_roman(X) when X >= 10 -> digit(X div 10, $X,$L,$C) ++ to_roman(X rem 10);
to_roman(X) when X >= 1 -> digit(X, $I,$V,$X).

digit(1,X,_,_) -> [X];
digit(2,X,_,_) -> [X,X];
digit(3,X,_,_) -> [X,X,X];
digit(4,X,Y,_) -> [X,Y];
digit(5,_,Y,_) -> [Y];
digit(6,X,Y,_) -> [Y,X];
digit(7,X,Y,_) -> [Y,X,X];
digit(8,X,Y,_) -> [Y,X,X,X];
digit(9,X,_,Z) -> [X,Z].
于 2009-11-05T19:41:30.437 に答える
4

繰り返したくない場合は、コードゴルフ新年版 - 整数からローマ数字への 貢献からインスピレーションを得ることができます。

-module(n2).
-export([y/1]).
-define(D(V,S),n(N)when N>=V->[??S|n(N-V)];).
y(N)->io:format(n(N)).
?D(1000,M)?D(900,CM)?D(500,D)?D(400,CD)?D(100,C)?D(90,XC)?D(50,L)?D(40,XL)?D(10,X)?D(9,IX)?D(5,V)?D(4,IV)?D(1,I)n(0)->[10].

erlang でコードを書くのは良くないし、推奨される方法でもありません。マクロはダメです。できれば避けてください。デバッグが難しく、ホット コード スワップによって追跡されないモジュール間の依存関係が導入されます。「コードはデータ、データはコード」というより機能的なアプローチが好きな場合は、これを例として見てください。

-module(roman).

-compile([export_all]).

toRoman(N) when is_integer(N), N >= 0 ->
    toRoman(N,
        [{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"},
         {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"},
         {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}]).

toRoman(0, _) -> [];
toRoman(N, [{X, V} | _] = S) when N >= X ->
    [V | toRoman(N - X, S)];
toRoman(N, [_ | S]) -> toRoman(N, S).

test() ->
    F = fun (X) -> lists:flatten(toRoman(X)) end,
    "" = F(0),
    "I" = F(1),
    "III" = F(3),
    "VI" = F(6),
    "XXIII" = F(23),
    "XLIII" = F(43),
    "LXXV" = F(75),
    "LXXXVII" = F(87),
    "XIII" = F(13),
    "XXIII" = F(23),
    "MMMCMXCIX" = F(3999),
    "MMMCMXCVIII" = F(3998),
    "MMDXXXI" = F(2531),
    "CXL" = F(140),
    ok.

念のために言っておきますが、あなたのコードは私のコードよりもバイトコードで約 5% 速く、ネイティブで 5% 遅いです。Intel(R) Core(TM)2 Duo CPU T7500 @ 2.20GHz で、バイトコードでは 1.2us、ネイティブでは 370ns で 1 回の変換を実行します。

編集:再帰の深さが非常に小さいため、末尾再帰バージョンは使用していません。そのため、パフォーマンスの低下やメリットがあるかどうかに興味がありました。ネイティブでもバイトコードで私のアルゴリズムを測定することはできませんが、興味深いことが元のコードで起こります。元のアルゴリズムを単純な方法 (テール コール用に最適化されていない) で記述した場合、ネイティブ コードの場合よりも約 40% 高速です (約 250 ns で 1 つの変換)。バイトコードに測定可能な違いはありません。テール コールの最適化を行う価値がない興味深い例です。

toRoman(N) when N >= 1000 -> "M" ++ toRoman(N - 1000);
toRoman(N) when N >= 900 -> "CM" ++ toRoman(N - 900);
toRoman(N) when N >= 500 -> "D" ++ toRoman(N - 500);
toRoman(N) when N >= 400 -> "CD" ++ toRoman(N - 400);
toRoman(N) when N >= 100 -> "C" ++ toRoman(N - 100);
toRoman(N) when N >= 90 -> "XC" ++ toRoman(N - 90);
toRoman(N) when N >= 50 -> "L" ++ toRoman(N - 50);
toRoman(N) when N >= 40 -> "XL" ++ toRoman(N - 40);
toRoman(N) when N >= 10 -> "X" ++ toRoman(N - 10);
toRoman(N) when N >= 9 -> "IX" ++ toRoman(N - 9);
toRoman(N) when N >= 5 -> "V" ++ toRoman(N - 5);
toRoman(N) when N >= 4 -> "IV" ++ toRoman(N - 4);
toRoman(N) when N >= 1 -> "I" ++ toRoman(N - 1);
toRoman(0) -> [].

PS : リストのフラット化は、Erlang コードでは一般的な動作ではありません。上記の例のリターン構造はよく知られてio_listおり、通常は erlang io システムで受け入れられています。ソケット、ポートなどに直接送信できます。たとえば、それを書きたい場合は、io:put_chars(IOList)またはを使用できますio:format("Result: '~s'~n", [IOList])

EDIT2:演算子erlangコンパイラの左オペランドとして定数リストがある場合、++リスト連結を最適化["string" | L]するため、速度には必要ありません。結果のコードはより読みやすくなり、結果はパフォーマンスの低下なしに平坦化されます。個人的には、パフォーマンスに興味がある場合は、このバージョンを使用します。これは少し反復的ですが、私が知っている中で最速であり、バイトコードで 310ns、ネイティブで 210ns で 1 つの変換を実行します。

toRoman(N) when N >= 1000 -> "M" ++ toRoman(N - 1000);
toRoman(N) -> toRomanC(N div 100, N rem 100).

toRomanC(0, N) -> toRomanX(N);
toRomanC(1, N) -> "C" ++ toRomanX(N);
toRomanC(2, N) -> "CC" ++ toRomanX(N);
toRomanC(3, N) -> "CCC" ++ toRomanX(N);
toRomanC(4, N) -> "CD" ++ toRomanX(N);
toRomanC(5, N) -> "D" ++ toRomanX(N);
toRomanC(6, N) -> "DC" ++ toRomanX(N);
toRomanC(7, N) -> "DCC" ++ toRomanX(N);
toRomanC(8, N) -> "DCCC" ++ toRomanX(N);
toRomanC(9, N) -> "CM" ++ toRomanX(N).

toRomanX(N) -> toRomanX(N div 10, N rem 10).

toRomanX(0, N) -> toRomanI(N);
toRomanX(1, N) -> "X" ++ toRomanI(N);
toRomanX(2, N) -> "XX" ++ toRomanI(N);
toRomanX(3, N) -> "XXX" ++ toRomanI(N);
toRomanX(4, N) -> "XL" ++ toRomanI(N);
toRomanX(5, N) -> "L" ++ toRomanI(N);
toRomanX(6, N) -> "LX" ++ toRomanI(N);
toRomanX(7, N) -> "LXX" ++ toRomanI(N);
toRomanX(8, N) -> "LXXX" ++ toRomanI(N);
toRomanX(9, N) -> "XC" ++ toRomanI(N).

toRomanI(0) -> [];
toRomanI(1) -> "I";
toRomanI(2) -> "II";
toRomanI(3) -> "III";
toRomanI(4) -> "IV";
toRomanI(5) -> "V";
toRomanI(6) -> "VI";
toRomanI(7) -> "VII";
toRomanI(8) -> "VIII";
toRomanI(9) -> "IX".
于 2009-11-05T09:19:40.143 に答える
2

繰り返し部分は累積と関数呼び出しです。それらを 1 か所に移動すると、見栄えがよくなります。

%%% Roman numerals ruleset
r(N) when N >= 1000 -> {N-1000, "M"};
r(N) when N >= 900 -> {N-900, "CM"};
r(N) when N >= 500 -> {N-500, "D"};
r(N) when N >= 400 -> {N-400, "CD"};
r(N) when N >= 100 -> {N-100, "C"};
r(N) when N >= 90 -> {N-90, "XC"};
r(N) when N >= 50 -> {N-50, "L"};
r(N) when N >= 40 -> {N-40, "XL"};
r(N) when N >= 10 -> {N-10, "X"};
r(N) when N >= 9 -> {N-9, "IX"};
r(N) when N >= 5 -> {N-5, "V"};
r(N) when N >= 4 -> {N-4, "IV"};
r(N) when N > 0 -> {N-1, "I"}.

roman(N, Acc) ->
  case r(N) of
    {0, R} ->
      [R | Acc];
    {N2, R} ->
      roman(N2, [R | Acc])
  end.

roman(N) ->
  list_to_binary(lists:reverse(roman(N, ""))).

ちなみに、4 と 6 で同じ結果が得られます。

8> [roman:toRoman(N) || N <- lists:seq(1,10)].   
["I","II","III","VI","V","VI","VII","VIII","XI","X"]

同じバグにより、9 と 11 が等しく、40 と 60、90 と 110 が等しいことがわかります。

于 2009-11-05T11:37:20.843 に答える
2

このプロセスには 3 つの部分があります。どの記号がどの数字を表すかという規則のリスト、次の記号を見つけるためのこれらの規則の検索、および数値をゼロに減らす反復です。各部分は関数を取得し、次のものがあります。

ruleset() -> [
    {1000, "M"},
    {900, "CM"},
    {500, "D"},
    {400, "CD"},
    {100, "C"},
    {90, "XC"},
    {50, "L"},
    {40, "XL"},
    {10, "X"},
    {9, "IX"},
    {5, "V"},
    {4, "IV"},
    {1, "I"}].

find_next(N) -> find_next(ruleset(), N).

find_next([{V, Symbol}|_], N) when N >= V -> {N - V, Symbol};
find_next([_|T], N) -> find_next(T, N).

roman(N, Acc) ->
    case find_next(N) of
          {0, R}  -> [R | Acc];
          {N2, R} -> roman(N2, [R | Acc])
    end.

roman(N) ->
    lists:append(lists:reverse(roman(N, ""))).

おそらく、これをもう少し単純化するために、lists:foldl/3 を使用できます。

于 2009-11-05T13:06:26.980 に答える
1

とにかく「ロジック」を実装する必要があるため、これは繰り返しではありません。とにかく20〜30回以上の再帰を持たないので、あなたができることの1つは、それを非末尾再帰にすることです...

-module(roman).
-compile([export_all]).

to_roman(N) when N >= 1000 -> "M"  ++ to_roman(N-1000);
to_roman(N) when N >=  900 -> "CM" ++ to_roman(N- 900);
...
to_roman(N) when N >=    4 -> "IV" ++ to_roman(N-   4);
to_roman(N) when N >=    1 -> "I"  ++ to_roman(N-   1);
to_roman(_) -> [].

マクロを定義することで、さらに一部の文字を保存できます。私はマクロが嫌いですが、マクロは好きかもしれません:)。

-module(roman).
-compile([export_all]).

-define( TO_ROMAN(L, C) , to_roman(N) when N >= L -> C ++ to_roman(N-L) ).

?TO_ROMAN(1000,  "M");
?TO_ROMAN( 900, "CM");
...
?TO_ROMAN(   4, "IV");
?TO_ROMAN(   1,  "I");
to_roman(_) -> [].
于 2009-11-05T07:18:37.093 に答える
1

Excelのようにローマ数字のすべてのバリアントをサポートすると、少しファンキーになります が、基本的にコードは一連の大きなケース/パターン一致ヘッダーのままです...

于 2009-11-05T16:38:44.910 に答える
-1

ルックアップ テーブルを使用すると、どの言語でも短くて速くなります。

于 2009-11-05T05:57:37.880 に答える