在prolog中断言和使用快速的LARGE数组

Question

我使用函子在wi - prolog中使用arg/3获得随机访问数组。我正在做的是加载值从一个样本到一个函子我创建和断言数组供将来使用。

一旦加载，随机访问确实是O(1)，因为我已经使用时间/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中的单子。

考虑这样做!

---

更糟糕的方式

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

避免这种情况!

一些原因:

• 不可移植
• 它引入了全局状态，使谓词难以读取和调试
• 不是比简单地使用额外的参数(隐式或显式)携带数组要有效得多
• 容易出错
• 等。