0

私は次のアーランコードを持っています:

lists:all(fun(Element) -> somefunction(TestCase -- [Element]) end, TestCase).

TestCase は配列です。1 つの要素が欠落しているリスト/配列を反復処理しようとしています。

問題は、呼び出されるたびに TestCase 配列のコピーが作成されるため、最悪の場合、このコードが O(N^2) 時間かかることです--。非関数型言語には明確な O(N) ソリューションがあります。

saved = TestCase[0]
temp = 0
NewTestCase = TestCase[1:] 
for a in range(length(NewTestCase)):
  somefunction(NewTestCase)
  temp = NewTestCase[a]
  NewTestCase[a] = saved
  saved = temp

...またはそのようなもの。

erlang に O(N) ソリューションはありますか?

4

2 に答える 2

1

もちろんありますが、少し複雑です。私はそれsome_function/1が実際にブール関数であり、すべてのサブリストに対して true を返すかどうかをテストしたいと考えています。

test_on_all_but_one([], _Acc) -> true;
test_on_all_but_one([E|Rest], Acc) ->
  case somefunction(lists:reverse(Acc,Rest)) of
    true  -> test_on_all_but_one(Rest, [E|Acc]);
    false -> false
  end.

lists:reverse/2呼び出しには引き続き O( ) が必要なため、この実装は依然として O(length(List)^2)length(Acc)です。somefunction/12 つの部分に分割されたリストで計算を行うように変更できる場合は、以前の with または類似の呼び出しを変更して、somefunction(lists:reverse(Acc,Rest))再somefunction(Acc, Rest)構築を回避できます。

修正は の内部動作に依存しsomefunction/1ます。さらにヘルプが必要な場合は、コードを提供してください。

于 2012-06-10T08:32:06.607 に答える
0

もちろん許容できる場合は、リストを2つのサブリストに分割できます。

witerate(Fun, [Tail], Acc) ->
  Fun([], Acc);

witerate(Fun, [Head | Tail], Acc) ->
  Fun(Tail, Acc),
  witerate(Fun, Tail, [Head | Acc]).
于 2012-06-10T08:23:01.457 に答える