时间戳

首页 > 解决方案 > Prolog中大型数组的全球化

arrays - Prolog中大型数组的全球化

问题描述

我想知道是否有办法在 Swi-Prolog 中创建全局数组。据我了解，GNU Prolog 通过g_array提供了这种可能性。我正在尝试创建一个使用非常大的数组（使用函子）的程序，因此将它们作为参数传递给谓词必须非常无效。

先感谢您 。

标签： arraysprologglobalswi-prolog

解决方案

评论中讨论了 SWI-Prolog 在将它们作为参数传递时是否复制术语。答案是它不能，因为术语共享是 Prolog 语义的核心特征。如果谓词接收到调用者术语的副本而不是共享结构，则统一将无法将信息从谓词内部传播到其调用者。

考虑：

a(X) :-
    b(f(X)).

b(f(X)) :-
    X = hello.

?- a(X).
X = hello.

相对：

c(X) :-
    copy_term(f(X), Copy),
    b(Copy).

?- c(X).
true.

但是，将具有大量元数的结构传递给被调用者可能还有其他一些成本吗？让我们写一个基准：

time_argument_passing(Arity, Calls) :-
    functor(Term, f, Arity),
    time(calls(Term, Calls)).

calls(Term, Calls) :-
    (   Calls = 0
    ->  true
    ;   Calls1 is Calls - 1,
        calls2(Calls1, Term) ).

calls2(Calls, Term) :-
    (   Calls = 0
    ->  true
    ;   Calls1 is Calls - 1,
        calls(Term, Calls1) ).

该程序分配给定的一个术语Arity，然后通过总共Calls调用传递它。只是为了让解释器更复杂一点，调用不是直接自递归的（但它们仍然是尾调用）。

让我们根据 arity 10 的小项来校准成本：

?- time_argument_passing(10, 1_000_000).
% 1,000,002 inferences, 0.039 CPU in 0.039 seconds (100% CPU, 25411210 Lips)
true.

?- time_argument_passing(10, 10_000_000).
% 10,000,001 inferences, 0.387 CPU in 0.387 seconds (100% CPU, 25860986 Lips)
true.

?- time_argument_passing(10, 100_000_000).
% 100,000,001 inferences, 3.733 CPU in 3.733 seconds (100% CPU, 26787034 Lips)
true.

?- time_argument_passing(10, 100_000_000).
% 100,000,001 inferences, 3.715 CPU in 3.715 seconds (100% CPU, 26918258 Lips)
true.

?- time_argument_passing(10, 100_000_000).
% 100,000,001 inferences, 3.719 CPU in 3.719 seconds (100% CPU, 26891604 Lips)
true.

事情似乎与调用次数成线性关系。现在我们知道 1 亿次调用的成本，术语为 10，让我们保持调用次数不变并缩放 arity：

?- time_argument_passing(1_000, 100_000_000).
% 100,000,001 inferences, 3.707 CPU in 3.707 seconds (100% CPU, 26974715 Lips)
true.

?- time_argument_passing(1_000, 100_000_000).
% 100,000,001 inferences, 3.751 CPU in 3.751 seconds (100% CPU, 26659983 Lips)
true.

?- time_argument_passing(1_000, 100_000_000).
% 100,000,001 inferences, 3.742 CPU in 3.741 seconds (100% CPU, 26726953 Lips)
true.

?- time_argument_passing(1_000_000, 100_000_000).
% 100,000,001 inferences, 3.928 CPU in 3.928 seconds (100% CPU, 25456692 Lips)
true.

?- time_argument_passing(1_000_000, 100_000_000).
% 100,000,001 inferences, 4.023 CPU in 4.023 seconds (100% CPU, 24854727 Lips)
true.

?- time_argument_passing(1_000_000, 100_000_000).
% 100,000,001 inferences, 3.962 CPU in 3.962 seconds (100% CPU, 25240284 Lips)
true.

?- time_argument_passing(10_000_000, 100_000_000).
% 100,000,001 inferences, 3.724 CPU in 3.724 seconds (100% CPU, 26853583 Lips)
true.

?- time_argument_passing(10_000_000, 100_000_000).
% 100,000,001 inferences, 3.865 CPU in 3.864 seconds (100% CPU, 25875446 Lips)
true.

?- time_argument_passing(10_000_000, 100_000_000).
% 100,000,001 inferences, 3.849 CPU in 3.848 seconds (100% CPU, 25982559 Lips)
true.

传递一千万个元素的数组几乎和传递一个十元素的数组一样快。

推荐阅读