Утверждение и использование быстрых, больших массивов в прологе

Question

Я использую функторы для получения массивов с произвольным доступом с использованием arg/3 в SWI-Prolog. Что я делаю, это загрузка значений из образца в созданный мной функтор и утверждение массива для будущего использования.

После загрузки, случайный доступ действительно является O (1), как я проверял, используя время/1. Проблема в загрузке функтора из утверждения занимает много времени (время/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).

Хороший способ

А хороший способ сделать это, чтобы нести вокруг весь массив, явно или неявно, throghout все предикаты, которые должны получить к нему доступ.

Вы можете использовать semicontext notation, чтобы сделать это неявно (см. dcg) или написать собственные правила расширения. Это похоже на монеты в Haskell.

Рассмотрите это!

---

Гораздо хуже способ

Гораздо хуже, и только на поверхности простой способ заключается в использовании глобальных переменных вместо глобальной базы данных хранить этот термин.

Избегайте этого!

Некоторые причины:

• это не портативный
• он вводит глобальное состояние, что делает ваш предикат трудно читать и отлаживать
• это не значительно более эффективным, чем просто используя дополнительные аргументы для переноса массива через (неявно или явно)
• это ошибкам
• т.д.