arrays - 在 prolog 中断言和使用快速、大型数组

Question

我正在使用仿函数在 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

Answer 1

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

有几种方法可以消除这种线性开销，将其变成𝒪(1)。

好方法

一个好的方法是携带整个数组，无论是显式的还是隐式的，通过所有需要访问它的谓词。

您可以使用半上下文表示法隐式执行此操作(请参阅 dcg )，或编写您自己的自定义扩展规则。这类似于 Haskell 中的 monad。

Consider doing this!

---

更糟糕的方式

一个更糟糕且只是表面上更简单的方法是使用全局变量而不是全局数据库来存储术语。

Avoid this!

一些原因:

• 它不可携带
• 它引入了全局状态，使您的谓词难以阅读和调试
• 它并不比简单地使用附加参数(隐式或显式)传递数组更高效
• 容易出错
• 等等