प्रोलॉग: किसी निर्दिष्ट इंडेक्स

Question

पर किसी सूची में किसी तत्व को प्रतिस्थापित करें, मैं एक प्रोलॉग अनुमानित करना चाहता हूं जो निर्दिष्ट इंडेक्स पर किसी सूची में किसी तत्व को प्रतिस्थापित कर सकता है।

उदाहरण:

% replace(+List,+Index,+Value,-NewList). 
?- L=[a,b,c,d], replace(L,1,z,L2). 
L2 = [a,z,c,d] 

मैं ऐसा करने के तरीके पता नहीं है। आपकी सहायताके लिए धन्यवाद! Loïc।

Answer 1

मैं तुम्हें आधार मामले दे देंगे, मुझे लगता है कि आप आसानी से पुनरावर्ती मामले करने के लिए सक्षम होना चाहिए:

replace([_|T], 0, X, [X|T]). 

संपादित करें:

अब जब कि सेशन यह सुलझ गया है,

replace([H|T], I, X, [H|R]):- I > 0, I1 is I-1, replace(T, I1, X, R). 

EDIT2::

मैं पुनरावर्ती मामले जोड़ देंगे

यह सीमा स्थिति से बाहर में मूल सूची वापस आ जाएगी टिप्पणी में के रूप में @GeorgeConstanza पूछते हैं:

replace([_|T], 0, X, [X|T]). 
replace([H|T], I, X, [H|R]):- I > -1, NI is I-1, replace(T, NI, X, R), !. 
replace(L, _, _, L). 

यह मूल रूप से कटौती ऑपरेटर का लाभ ले रहा है तीसरा वापस आने खंड के लिए नहीं प्राप्त करने के लिए हो, तो एक अच्छा इन-बाउंड प्रतिस्थापन।

Answer 2

ठीक है स्पष्ट रूप से @fortran द्वारा रिकर्सन का उपयोग करके प्रतिस्थापित करने का तरीका है। लेकिन क्या यह वास्तव में उपयोग करने के लिए बहुत पागल/धीमा है?

replace(List, Idx, With, ListOut) :- 
    length(Idx, Before), 
    append(Before, After, List), 
    ( After=[_Discard|Rest] 
    -> true 
    ; Rest=[] 
    ), 
    append(Before, [With|Rest], ListOut). 

असल में आप आकार आईडीएक्स की एक खाली सरणी बनाते हैं और इनपुट सूची में बाध्य करते हैं। उसके बाद उस आइटम को छोड़ दें और दो सूचियों को एक साथ प्रतिस्थापित करें जिसमें प्रतिस्थापन तत्व सैंडविच किया गया है।

यदि आप एन तत्व सूची के आईडीएक्स एन (0 से अनुक्रमण) सेट करने का प्रयास करते हैं तो यह ठीक हो सकता है। ।

replace(List, Idx, With, ListOut) :- 
    length(Idx, Before), 
    append(Before, [_Discard|Rest], List), 
    append(Before, [With|Rest], ListOut). 

Answer 3

fortran से जवाब यह ठीक है, लेकिन यह काम में SWI-Prolog structs असीमित arity है, इसलिए चाहिए:

replace([_|T], 0, X, [X|T]). 
replace([H|T], I, X, [H|R]) :- 
    I > 0, 
    I1 is I - 1, 
    replace(T, I1, X, R). 

replace1(L, I, X, R) :- 
    Dummy =.. [dummy|L], 
    J is I + 1, 
    nb_setarg(J, Dummy, X), 
    Dummy =.. [dummy|R]. 

tr(Method, K) :- 
    length(L, K), 
    K1 is K - 1, 
    time(call(Method, L, K1, test, R)), 
    assertion(nth1(K, R, test)). 

लेकिन, मेरे आश्चर्य:

?- % /home/carlo/prolog/replace.pl compiled 0,00 sec, 2,280 bytes 
?- tr(replace,2000000). 
% 3,999,999 inferences, 2,123 CPU in 2,128 seconds (100% CPU, 1884446 Lips) 
true . 

?- tr(replace1,2000000). 
% 5 inferences, 1,410 CPU in 1,414 seconds (100% CPU, 4 Lips) 
true. 

?- tr(replace,4000000). 
% 7,999,999 inferences, 3,510 CPU in 3,520 seconds (100% CPU, 2279267 Lips) 
true . 

?- tr(replace1,4000000). 
% 5 inferences, 2,825 CPU in 2,833 seconds (100% CPU, 2 Lips) 
true. 

?- tr(replace,5000000). 
% 9,999,999 inferences, 3,144 CPU in 3,153 seconds (100% CPU, 3180971 Lips) 
true . 

?- tr(replace1,5000000). 
% 5 inferences, 4,476 CPU in 4,486 seconds (100% CPU, 1 Lips) 
ERROR: =../2: Arguments are not sufficiently instantiated 
^ Exception: (9) setup_call_catcher_cleanup(system:true, prolog_statistics:catch(user:call(replace1, [_G1, _G4, _G7, _G10|...], 4999999, test, _G15000005), _G15000021, (report(t(1324124267.2924964, 18.892632697, 28490132), 10), throw(_G15000021))), _G15000145, prolog_statistics: (_G15000032=true)) ? abort 
% Execution Aborted 

मेरे पहला प्रयास (के = 10000000 के साथ) प्रक्रिया को मार डाला! तो, मेरी नापसंद करने के लिए, कुछ प्रदर्शन प्राप्त करने का प्रयास है, मैं अंत SWI-Prolog मेलिंग सूची के लिए एक बग रिपोर्ट ...

संपादित भरने: SWI-Prolog मेलिंग सूची के लिए पोस्ट करने के बाद, और (तेज़!) सुधार, मैंने पुनर्निर्मित किया है, और यहां स्मृति उपयोग पर एक संकेत के लिए संस्करण लेखांकन है (अब यह सभी आईएसओ मानक कोड है!)।असामान्य बड़े मूल्यों के कारण, एक ढेर हो जाना अनुदेश की जरूरत है इससे पहले कि:

replace2(L, I, X, R) :- 
    Dummy =.. [dummy|L], 
    J is I + 1, 
    setarg(J, Dummy, X), 
    Dummy =.. [dummy|R]. 

और परीक्षण:

?- tr(replace,10000000). 
% 19,999,999 inferences, 5.695 CPU in 5.719 seconds (100% CPU, 3511942 Lips) 
true . 

?- tr(replace2,10000000). 
% 5 inferences, 2.564 CPU in 2.571 seconds (100% CPU, 2 Lips) 
true. 

कोड यह तेजी से है

?- prolog_stack_property(global,limit(L)), N is L*2, set_prolog_stack(global,limit(N)). 
N = 536870912. 

यहाँ अद्यतन प्रक्रिया है , लेकिन कृपया मेरे मेल पर जनवरी की टिप्पणी नोट करें:

= = (+, -) में खराब त्रुटि प्रबंधन के लिए उबाल जाता है। फिक्स्ड। B.t.w. मैं सोचता हूं कि यह नौकरी करने का बहुत ही भयानक तरीका है। भले ही आप चाहते हैं, ऐसा करने के लिए, बस nb_setarg/3 के बजाय setarg/3 का उपयोग करें। बाद में वास्तव में अंतिम उपाय होना चाहिए। यह विधि अधिक स्मृति का उपयोग करती है क्योंकि इसे विशाल शब्द और सूची दोनों की आवश्यकता होती है। अंत में, मज़दूर (नाम/धैर्य जोड़े) को वर्तमान में पुनः दावा नहीं किया गया है, इसलिए आप एक ऐसी सूची के प्रत्येक सूची के लिए ऐसी ऑब्जेक्ट बनाते हैं जिस पर यह कभी भी उपयोग नहीं किया गया था।

Answer 4

वास्तव में, कोई भी नहीं कभी इस IMO किसी भी काफी लंबी के मैदान सूचियों के साथ क्या करना चाहिए, के रूप में प्रत्येक अद्यतन O(n) नए स्थान ले जाएगा। setarg/nb_setarg के माध्यम से डायरेक्ट सेट_ऑन्स/अपडेट 0 नई जगह ले जाएगा, और सूचियों के बाइनरी पेड़ का प्रतिनिधित्व, O(log(n)) नई जगह ले जाएगा। प्रतिस्थापन एक अलग शब्दकोश में भी आयोजित किया जा सकता है, खुद को एक पेड़ के रूप में बनाए रखा जाता है (क्योंकि इसे बढ़ने की जरूरत है)। खंडित सूची (in here के रूप में) एक पेड़ में बड़े हिस्से को पकड़ सकता है, प्रत्येक निश्चित आकार के यौगिक शब्द को setarg/nb_setarg के माध्यम से सीधे सेटटेबल/अपडेट करने योग्य, और आवश्यकतानुसार पेड़ में नए हिस्से जोड़ें।

भी अद्यतन के बिना, बस सादा सूचियों तक पहुँचने एक पल में किसी भी एल्गोरिथ्म द्विघात मोड़, बुरी धीमी है O(n) समय,। सूचियां केवल वाकई कम होती हैं, या होमवर्क व्यायाम के रूप में होती हैं।

Answer 5

इस तरह से सीधे आगे बढ़ने के बारे में क्या?

 
:- use_module(library(clpfd)). 

list_nth0_item_replaced([_|Xs], 0, E, [E|Xs]). 
list_nth0_item_replaced([X|Xs], N, E, [X|Ys]) :- 
    N #> 0, 
    N #= N0+1, 
    list_nth0_item_replaced(Xs, N0, E, Ys). 

यहाँ यूज-केस ओपी निर्दिष्ट है:

?- list_nth0_item_replaced([a,b,c,d],1,z,Ls). 
    Ls = [a,z,c,d] 
; false. 

कोड से ऊपर शुद्ध है, इसलिए हम अधिक सामान्य प्रश्नों तार्किक ध्वनि जवाब पूछ सकते हैं — और उम्मीद:

?- list_nth0_item_replaced([a,b,c,d], N, X, Ls). 
    N = 0, Ls = [X,b,c,d] 
; N = 1, Ls = [a,X,c,d] 
; N = 2, Ls = [a,b,X,d] 
; N = 3, Ls = [a,b,c,X] 
; false. 

Answer 6

हैं हम same_length/2, append/3, और length/2 का उपयोग करते हैं, हमें रिकर्सिव कोड लिखने की आवश्यकता नहीं है:

 
list_nth0_item_replaced(Es, N, X, Xs) :- 
    same_length (Es, Xs), 
    append (Prefix, [_|Suffix], Es), 
    length (Prefix, N), 
    append(Prefix, [X|Suffix], Xs). 

नमूना ओपी द्वारा दिए गए क्वेरी:

?- list_nth0_item_replaced([a,b,c,d], 1, z, Xs). 
    Xs = [a,z,c,d] 
; false. 

यह काम करता है "दूसरी दिशा में" भी!

?- list_nth0_item_replaced(Xs, 1, z, [a,z,c,d]). 
    Xs = [a,_A,c,d] 
; false. 

भी अच्छी बात है, हम भी ठोस सूचकांक निर्दिष्ट करने की आवश्यकता नहीं है:

?- list_nth0_item_replaced(Es, N, X, [a,z,c,d]). 
    N = 0, X = a, Es = [_A, z, c, d] 
; N = 1, X = z, Es = [ a,_A, c, d] 
; N = 2, X = c, Es = [ a, z,_A, d] 
; N = 3, X = d, Es = [ a, z, c,_A] 
; false. 

?- list_nth0_item_replaced([a,b,c,d], N, X, Xs). 
    N = 0, Xs = [X,b,c,d] 
; N = 1, Xs = [a,X,c,d] 
; N = 2, Xs = [a,b,X,d] 
; N = 3, Xs = [a,b,c,X] 
; false. 

Answer 7

कोड प्रस्तुत in this previous answerclpfd को काफी बहुमुखी — धन्यवाद है।

क्या कोई नकारात्मक पक्ष है? हां, एक नकारात्मक पक्ष है: अक्षमता!

इस उत्तर में, हम प्रदर्शन और प्रदर्शनशीलता को बरकरार रखते हैं।

 
:- use_module(library(clpfd)). 

हम this previous answer की तरह आगे बढ़ना किया था जब वह विधेय fd_length/2 परिभाषित:

list_nth0_item_replaced__NEW(Es, N, X, Xs) :- 
    list_index0_index_item_replaced(Es, 0,N, X, Xs). 

list_index0_index_item_replaced([_|Es], I ,I, X, [X|Es]). 
list_index0_index_item_replaced([E|Es], I0,I, X, [E|Xs]) :- 
    I0 #< I, 
    I1 #= I0+1, 
    list_index0_index_item_replaced(Es, I1,I, X, Xs). 

तो ... यह किसी भी तेजी से हो गया है?

 
?- numlist(1,100000,Zs), time(list_nth0_item_replaced(Zs,99999,x,Xs)). 
% 14,499,855 inferences, 0.893 CPU in 0.893 seconds (100% CPU, 16237725 Lips) 
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...], 
Xs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; 
% 7 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 18377 Lips) 
false. 

?- numlist(1,100000,Zs), time(list_nth0_item_replaced__NEW(Zs,99999,x,Xs)). 
% 499,996 inferences, 0.049 CPU in 0.049 seconds (100% CPU, 10158710 Lips) 
Zs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...], 
Xs = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] ; 
% 6 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 213988 Lips) 
false. 

ठीक है, समझ तेज है। लेकिन क्या यह अभी भी बहुमुखी है?

 
?- list_nth0_item_replaced__NEW([a,b,c,d], 1, z, Xs). 
    Xs = [a,z,c,d] 
; false. 

?- list_nth0_item_replaced__NEW(Xs, 1, z, [a,z,c,d]). 
    Xs = [a,_A,c,d] 
; false. 

?- list_nth0_item_replaced__NEW(Es, N, X, [a,z,c,d]). 
    N = 0, X = a, Es = [_A, z, c, d], 
; N = 1, X = z, Es = [ a,_A, c, d] 
; N = 2, X = c, Es = [ a, z,_A, d], 
; N = 3, X = d, Es = [ a, z, c,_A] 
; false. 

?- list_nth0_item_replaced__NEW([a,b,c,d], N, X, Xs). 
    N = 0, Xs = [X,b,c,d] 
; N = 1, Xs = [a,X,c,d] 
; N = 2, Xs = [a,b,X,d] 
; N = 3, Xs = [a,b,c,X] 
; false. 

मुझे ठीक लगता है!

Answer 8

एक और तरीका जिस पर मैं आया, जो मुझे लगता है कि सही है (?)। मुझे रनटाइम जटिलता के बारे में पता नहीं है।

replace(I, L, E, K) :- 
    nth0(I, L, _, R), 
    nth0(I, K, E, R). 

उपयोग:

?- replace(2, [1, 2, 3, 4, 5], 10, X). 
X = [1, 2, 10, 4, 5].