Утверждение и использование быстрых БОЛЬШИХ массивов в прологе

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

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

arrays prolog swi-prolog prolog-directive-dynamic
person 2bigpigs    schedule 16.11.2016    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Вы видите линейные накладные расходы при использовании current_sample/1, поскольку аргументы предикатов копируются из базы данных при вызове предиката.

Есть несколько способов избавиться от этих линейных накладных расходов, превратив их в (1).

Хороший путь

Хороший способ сделать это — перенести весь массив, явно или неявно, через все предикаты, которым требуется доступ к нему.

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

Подумайте об этом!

Гораздо худший способ

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

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

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

  • это не переносимо
  • он вводит глобальное состояние, что затрудняет чтение и отладку вашего предиката.
  • это не намного эффективнее, чем простое использование дополнительных аргументов для переноса массива (неявно или явно)
  • это подвержено ошибкам
  • и т. д.
person mat    schedule 16.11.2016
comment
Спасибо. К сожалению, у меня мало времени, поэтому я собираюсь найти простое решение с использованием глобальной переменной здесь. DCG - это то, чем я скоро займусь. - person 2bigpigs; 16.11.2016
comment
Спасибо, что нашли время, чтобы сказать мне это! - person mat; 16.11.2016