gpt4 book ai didi

prolog - 适用于大数的 positive_integer/1 谓词

转载 作者:行者123 更新时间:2023-12-04 18:23:27 24 4
gpt4 key购买 nike

在我的受 Prolog 启发的语言 Brachylog 中,有可能标记具有潜在无限域的 CLP(FD) 等效变量。可以在 here 中找到执行此标记的代码(感谢 Markus Triska @mat)。

此谓词需要存在谓词 positive_integer/1 ,该谓词必须具有以下行为:

?- positive_integer(X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;


这在我们当前的解决方案中是这样实现的:
positive_integer(N) :- length([_|_], N).

这有两个问题,我可以看到:
  • 这很快就会变慢:
    ?- time(positive_integer(100000)).
    % 5 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)

    ?- time(positive_integer(1000000)).
    % 5 inferences, 0.000 CPU in 0.008 seconds (0% CPU, Infinite Lips)

    ?- time(positive_integer(10000000)).
    % 5 inferences, 0.062 CPU in 0.075 seconds (83% CPU, 80 Lips)
  • 对于有点太大的数字,这最终会返回 Out of global stack 错误:
    ?- positive_integer(100000000).
    ERROR: Out of global stack

  • 这显然是因为 Prolog 需要实例化列表,如果它的长度很大,这很糟糕。

    我们如何改进这个谓词,使其即使对非常大的数字也有效,具有相同的行为?

    最佳答案

    已经发布了许多好的想法,并且它们在不同程度上起作用。

    附加测试用例

    @vmg 有正确的直觉:between/3 不能很好地与约束混合。为了看到这一点,我想使用以下查询作为额外的基准:

    ?- X #> 10^30, positive_integer(X).

    解决方案

    考虑到测试用例,我建议使用以下 解决方案 :
    positive_integer(I) :-
    I #> 0,
    ( var(I) ->
    fd_inf(I, Inf),
    ( I #= Inf
    ; I #\= Inf,
    positive_integer(I)
    )
    ; true
    ).

    关键思想是使用 CLP(FD) 反射谓词 fd_inf/2 来推理变量域中的最小元素。这是将解决方案移植到更多 Prolog 系统时需要更改的唯一谓词。例如,在 SICStus Prolog 中,谓词称为 fd_min/2

    主要特点
  • 可移植 到几个 Prolog 系统,更改最少
  • 快速 在所示情况下
  • 也适用于
  • 上面的测试用例中
  • 宣传 并使用 CLP(FD) 约束的全部功能。

  • 当然,这些点中哪一点最重要是很清楚的。

    示例查询

    创造 ex nihilo :
    ?- positive_integer(X).
    X = 1 ;
    X = 2 ;
    X = 3 .

    固定 整数:
    ?- X #= 12^42, time(positive_integer(X)).
    % 4 inferences, 0.000 CPU in 0.000 seconds (68% CPU, 363636 Lips)
    X = 2116471057875484488839167999221661362284396544.

    约束 整数:
    ?- X #> 10^30, time(positive_integer(X)).
    % 124 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 3647059 Lips)
    X = 1000000000000000000000000000001 ;
    % 206 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 2367816 Lips)
    X = 1000000000000000000000000000002 ;
    % 204 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 2428571 Lips)
    X = 1000000000000000000000000000003 .

    其他的建议
  • 首先,确保在 Code Golf 上查看 Brachylog 和最新的 Brachylog solutions。由于 Julien 的努力,受 Prolog 启发的语言现在越来越多地承载一些最简洁、最优雅的程序,这些程序发布在那里。很棒的工作朱利安!
  • 请不要使用 between/3 的特定于实现的异常:这些会破坏谓词的重要语义属性,并且不能移植到其他系统。
  • 如果您忽略 (2),请使用 infinite 而不是 inf 。在 CLP(FD) 的上下文中,inf 表示整数集的 infimum ,它与正无穷大正好相反。
  • 在 CLP(FD) 的上下文中,我建议使用 CLP(FD) 约束而不是 between/3 和其他不考虑约束的谓词。
  • 事实上,我建议使用 CLP(FD) 约束而不是 所有 对整数进行推理的低级谓词。这最多可以使您的程序更通用,而不是更具体。

  • 非常感谢您对这个问题和已发布的解决方案感兴趣!我希望您发现上面的测试用例对您的变体有用,并找到在您的版本中考虑 CLP(FD) 约束的方法,以便它们运行得更快,我们都可以为它们点赞!

    关于prolog - 适用于大数的 positive_integer/1 谓词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39253077/

    24 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com