0

我有以下二郎代码：

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

其中 TestCase 是一个数组。我正在尝试遍历缺少一个元素的列表/数组。

--问题是这段代码在最坏的情况下需要 O(N^2) 时间，因为每次调用TestCase 数组的副本。在非函数式语言中有一个明确的 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.

这个实现仍然是 O(length(List)^2)，因为lists:reverse/2调用仍然需要 O( length(Acc))。如果您可以修改somefunction/1以在分成两部分的列表上进行计算，那么您可以修改先前对somefunction(lists:reverse(Acc,Rest))withsomefunction(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 回答