2

我正在使用仿函数在 SWI-Prolog 中使用 arg/3 获取随机访问数组。我正在做的是将样本中的值加载到我创建的仿函数中并声明该数组以供将来使用。

加载后，随机访问确实是 O(1)，因为我已经使用 time/1 进行了验证。问题是从断言中加载函子需要很长时间（ time/1 表明它在数组的大小上是线性的）。有什么办法可以将其加速到恒定时间吗？

复制的最小代码：

:- dynamic
    current_sample/1.

xrange(L,R,X):-
    L < R,
    ( X = L;
    X1 is L+1, xrange(X1,R,X)
    ).


arraybase_from_list__set_arg_from_list([], _, _).
arraybase_from_list__set_arg_from_list([Head|Tail], I, ResArray):-
    I1 is I+1,
    nb_setarg(I1, ResArray, Head),
    arraybase_from_list__set_arg_from_list(Tail, I1, ResArray).

arraybase_from_list(List, ResArray):-
    length(List, L),
    functor(ResArray, custom_array_data, L),
    arraybase_from_list__set_arg_from_list(List, 0, ResArray ).


test_array_create( N ):- % Creates a dummy array of squares of numbers fromo [0,N)
    findall( X2, (xrange( 0,N,X), X2 is X*X), XList ),
    arraybase_from_list( XList, Arr ),
    assert( current_sample(Arr) ).

test_array_get(I,V):- % Unifies V with Ith element of Current sample
    I0 is I+1,
    current_sample(Arr), % Take turns timing this
    arg( I0, Arr, V ).   % And then timing this
4

1 回答 1

5

使用时您会看到线性开销，current_sample/1因为谓词的参数是在调用谓词时从数据库中复制的。

有几种方法可以消除这种线性开销，将其变成

于 2016-11-16T13:04:22.377 回答