Пролог Binary Алгоритм поиска

Question

так пытается сделать бинарный алгоритм поиска в прологе

%checks to see if a value is contained in a list of integers, 
%using binary search tactics 

%success base case 
%A list contains a value if its center is the value 
contains(List, Value):- even_division(_, [Value|_], List). 

%case that Value is large 
%A list contains a value if the value is larger than the center, 
%and the second half of the list contains the value 
contains(List, Value):- even_division(_, [Center|SecondHalf], List), 
         Center<Value, SecondHalf \= [], 
         contains(SecondHalf, Value). 

%case that Value is small 
%A list contains a value if the value is smaller than the center, 
%and the first half of the list contains the value 
contains(List, Value):- even_division(FirstHalf, [Center|_], List), 
         Center>Value, FirstHalf\=[], 
         contains(FirstHalf, Value). 

%even_division(First, Second, Xs) is true when 
% Xs is the concatenation of First and Second, 
% and First and Second are either the same length 
% or Second is one element longer than first. 
even_division(First, Second, Xs) :- append(First, Second, Xs), 
            length(First,F), length(Second,S), 
            S>=F, S-F=<1. 

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

Answer 1

Ваш код кажется довольно неэффективным, точно не отображается поведение журнала (N). Я тестировал его с помощью numlist/3, и time/1

?- numlist(1,10,L),contains(L,7). 
% 279,957 inferences, 1.701 CPU in 1.706 seconds (100% CPU, 164557 Lips) 
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] 

?- numlist(1,100000,L),time(contains(L,17)). 
% 2,800,016 inferences, 258.828 CPU in 262.601 seconds (99% CPU, 10818 Lips) 
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] 

это линейное по числу выводов, но квадратичный по времени выполнения. Вероятно, накладные расходы памяти, представленные расщеплением списков, серьезны. numlist/3 - это генератор списка, например ваш диапазон/3.