जंग

Question

में बंद और जीवनकाल के साथ संघर्ष करना मैं एफ # से जंग से थोड़ा बेंचमार्क बंद करने की कोशिश कर रहा हूं। एफ # कोड इस तरह दिखता है:

let inline iterNeighbors f (i, j) = 
    f (i-1, j) 
    f (i+1, j) 
    f (i, j-1) 
    f (i, j+1) 

let rec nthLoop n (s1: HashSet<_>) (s2: HashSet<_>) = 
    match n with 
    | 0 -> s1 
    | n -> 
     let s0 = HashSet(HashIdentity.Structural) 
     let add p = 
     if not(s1.Contains p || s2.Contains p) then 
      ignore(s0.Add p) 
     Seq.iter (fun p -> iterNeighbors add p) s1 
     nthLoop (n-1) s0 s1 

let nth n p = 
    nthLoop n (HashSet([p], HashIdentity.Structural)) (HashSet(HashIdentity.Structural)) 

(nth 2000 (0, 0)).Count 

यह एक संभावित अनंत ग्राफ में एक प्रारंभिक शिखर से n वें-निकटतम पड़ोसी गोले गणना करता है। मैंने असुरक्षित सामग्री का अध्ययन करने के लिए अपने पीएचडी के दौरान कुछ ऐसा ही इस्तेमाल किया।

मैंने जंग को यह बंद करने की कोशिश करने और विफल होने में कई घंटे बिताए हैं। मैंने एक संस्करण काम करने में कामयाब रहा है, लेकिन केवल बंद करने और स्थानीय म्यूटेबल (युक!) के साथ लूप में रिकर्सन को परिवर्तित करने के द्वारा ही परिवर्तित किया है।

fn iterNeighbors<F>(f: &F, (i, j): (i32, i32)) ->() 
    where F : Fn((i32, i32)) ->() { 
    f((i-1, j)); 
    f((i+1, j)); 
    f((i, j-1)); 
    f((i, j+1)); 
} 

मुझे लगता है कि एक समारोह है कि एक बंद स्वीकार करता है और एक जोड़ी और रिटर्न इकाई (जो स्वयं को एक जोड़ी और रिटर्न इकाई स्वीकार करता है) है:

use std::collections::HashSet; 

मैं इस तरह iterNeighbors समारोह लेखन की कोशिश की। मुझे ब्रैकेट चीजों को दोगुना करना प्रतीत होता है: क्या यह सही है?

fn nthLoop(n: i32, s1: HashSet<(i32, i32)>, s2: HashSet<(i32, i32)>) -> HashSet<(i32, i32)> { 
    if n==0 { 
     return &s1; 
    } else { 
     let mut s0 = HashSet::new(); 
     for &p in s1 { 
      if !(s1.contains(&p) || s2.contains(&p)) { 
       s0.insert(p); 
      } 
     } 
     return &nthLoop(n-1, s0, s1); 
    } 
} 

ध्यान दें कि मैं भी अभी तक iterNeighbors करने के लिए कॉल करने की चिंता नहीं है:

मैं इस तरह एक पुनरावर्ती संस्करण लेखन की कोशिश की।

मुझे लगता है कि मैं तर्कों के जीवनकाल को सही करने के लिए संघर्ष कर रहा हूं क्योंकि वे रिकर्सिव कॉल में घूमते हैं। अगर मुझे return एस से पहले s2 को हटा दिया जाना है, तो मुझे जीवनकाल को एनोटेट करना चाहिए और मुझे s1 वापस आने या रिकर्सिव कॉल में रहने के लिए जीवित रहने के लिए चाहिए?

फोन करने वाले कुछ इस तरह दिखेगा:

fn nth<'a>(n: i32, p: (i32, i32)) -> &'a HashSet<(i32, i32)> { 
    let s0 = HashSet::new(); 
    let mut s1 = HashSet::new(); 
    s1.insert(p); 
    return &nthLoop(n, &s1, s0); 
} 

मैं उस पर छोड़ दिया और बजाय परिवर्तनशील स्थानीय लोगों के साथ while पाश के रूप में यह लिखा है:

fn nth<'a>(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> { 
    let mut n = n; 
    let mut s0 = HashSet::new(); 
    let mut s1 = HashSet::new(); 
    let mut s2 = HashSet::new(); 
    s1.insert(p); 
    while n > 0 { 
     for &p in &s1 { 
      let add = &|p| { 
       if !(s1.contains(&p) || s2.contains(&p)) { 
        s0.insert(p); 
       } 
      }; 
      iterNeighbors(&add, p); 
     } 
     std::mem::swap(&mut s0, &mut s1); 
     std::mem::swap(&mut s0, &mut s2); 
     s0.clear(); 
     n -= 1; 
    } 
    return s1; 
} 

यह काम करता है अगर मैं बंद इनलाइन हाथ से लेकिन मैं यह नहीं समझ सकता कि बंद करने का आह्वान कैसे किया जाए। आदर्श रूप में, मुझे यहां स्थिर प्रेषण चाहिए। ... क्या मैं गलत कर रहा हूँ

fn main() { 
    let s = nth(2000, (0, 0)); 
    println!("{}", s.len()); 
} 

तो:

main समारोह तो है? :-)

इसके अलावा, मैंने केवल F12 में HashSet का उपयोग किया क्योंकि मुझे लगता है कि जंग पूरी तरह से कार्यात्मक Set को कुशल सेट-सैद्धांतिक संचालन (संघ, चौराहे और अंतर) प्रदान नहीं करता है। क्या मैं इसे मानने में सही हूं?

Answer 1

मुझे लगता है कि एक समारोह है कि एक बंद (स्वीकार करता है कि अपने आप में एक जोड़ी और रिटर्न स्वीकार करता है इकाई) और एक जोड़ी और रिटर्न इकाई। मुझे ब्रैकेट चीजों को दोगुना करना प्रतीत होता है: क्या यह सही है?

आपको डबल ब्रैकेट की आवश्यकता है क्योंकि आप बंद करने के लिए 2-टुपल पास कर रहे हैं, जो आपके मूल F # कोड से मेल खाता है।

मुझे लगता है कि मैं तर्कों के जीवनकाल को सही करने के लिए संघर्ष कर रहा हूं क्योंकि वे रिकर्सिव कॉल में घूमते हैं। अगर मैं रिटर्न से पहले एस 2 को डिलीकेट किया जाना चाहता हूं तो मुझे जीवनकाल को कैसे एनोटेट करना चाहिए और मैं चाहता हूं कि एस 1 लौटाए या रिकर्सिव कॉल में या तो जीवित रहे?

समस्या यह है कि आप HashSet रों के लिए संदर्भ का उपयोग कर रहे हैं जब आप बस HashSet रों सीधे का उपयोग करना चाहिए है। nthLoop के लिए आपका हस्ताक्षर पहले से ही सही है; आपको बस & की कुछ घटनाओं को हटाने की आवश्यकता है।

s2 को हटाने के लिए, आप drop(s2) लिख सकते हैं। ध्यान दें कि जंग के पास गारंटीकृत पूंछ कॉल नहीं है, इसलिए प्रत्येक रिकर्सिव कॉल अभी भी थोड़ा सा स्टैक स्पेस लेगा (आप देख सकते हैं कि mem::size_of फ़ंक्शन के साथ कितना है), लेकिन drop कॉल ढेर पर डेटा को शुद्ध करेगा।

फोन करने वाले कुछ इस तरह दिखेगा:

फिर, आप बस यहां & के दूर करने के लिए की जरूरत है।

ध्यान दें कि मैंने अभी तक कॉलर को कॉल करने से भी परेशान नहीं किया है।

---

यह काम करता है अगर मैं हाथ से बंद को रेखांकित करता हूं लेकिन मैं यह नहीं समझ सकता कि बंद करने का आह्वान कैसे किया जाए। आदर्श रूप में, मुझे यहां स्थिर प्रेषण चाहिए। Fn, FnMut और FnOnce:

जंग में बंद के तीन प्रकार के होते हैं। वे self तर्क के प्रकार से भिन्न होते हैं। भेद महत्वपूर्ण है क्योंकि यह बंद करने की अनुमति देने पर और कॉलर बंद करने का उपयोग कैसे कर सकता है, इस पर प्रतिबंध लगाता है। जंग किताब में a chapter on closures है जो पहले से ही इस अच्छी तरह से बताता है।

आपके बंद होने पर s0 को म्यूट करने की आवश्यकता है। हालांकि, iterNeighbors को Fn बंद होने की उम्मीद के रूप में परिभाषित किया गया है। आपका बंद Fn लागू नहीं कर सकता है क्योंकि Fn&self प्राप्त करता है, लेकिन s0 को म्यूट करने के लिए, आपको &mut self की आवश्यकता है। iterNeighborsFnOnce का उपयोग नहीं कर सकता है, क्योंकि इसे बंद से अधिक बार कॉल करने की आवश्यकता है। इसलिए, आपको FnMut का उपयोग करने की आवश्यकता है।

इसके अलावा, iterNeighbors के संदर्भ में बंद होने के लिए आवश्यक नहीं है। आप इसे मूल्य से पास कर सकते हैं; बंद करने के लिए प्रत्येक कॉल केवल बंद करने का उधार लेगा, इसे उपभोग नहीं करेगा।

इसके अलावा, मैंने केवल F # में हैशसेट का उपयोग किया क्योंकि मुझे लगता है कि जंग प्रतिरोधी सेट-सैद्धांतिक संचालन (संघ, चौराहे और अंतर) के साथ पूरी तरह से कार्यात्मक सेट प्रदान नहीं करता है। क्या मैं इसे मानने में सही हूं?

मानक लाइब्रेरी में कोई पूरी तरह कार्यात्मक सेट कार्यान्वयन नहीं है (शायद वहाँ crates.io पर एक है?)। जबकि जंग कार्यशील प्रोग्रामिंग को गले लगाती है, यह अनिवार्य प्रोग्रामिंग को सुरक्षित बनाने के लिए अपने स्वामित्व और उधार प्रणाली का लाभ भी लेती है। सेट में आइटम साझा करने के लिए एक कार्यात्मक सेट शायद संदर्भ गणना या कचरा संग्रह के कुछ रूपों का उपयोग करके लगाया जाएगा।

हालांकि, HashSet सेट-सैद्धांतिक संचालन को लागू करता है। (trait implementations for HashSet के रूप में सूचीबद्ध, |, &, ^, -) जो अनुक्रम lazily उत्पन्न iterators (difference, symmetric_difference, intersection, union), या ऑपरेटरों, जिनमें से क्लोन युक्त नए सेट का उत्पादन: वहाँ उन्हें इस्तेमाल करने के दो तरीके हैं स्रोत सेट से मूल्य।

use std::collections::HashSet; 

fn iterNeighbors<F>(mut f: F, (i, j): (i32, i32)) ->() 
    where F: FnMut((i32, i32)) ->() 
{ 
    f((i-1, j)); 
    f((i+1, j)); 
    f((i, j-1)); 
    f((i, j+1)); 
} 

fn nthLoop(n: i32, s1: HashSet<(i32, i32)>, s2: HashSet<(i32, i32)>) -> HashSet<(i32, i32)> { 
    if n == 0 { 
     return s1; 
    } else { 
     let mut s0 = HashSet::new(); 
     for &p in &s1 { 
      let add = |p| { 
       if !(s1.contains(&p) || s2.contains(&p)) { 
        s0.insert(p); 
       } 
      }; 
      iterNeighbors(add, p); 
     } 
     drop(s2); 
     return nthLoop(n-1, s0, s1); 
    } 
} 

fn nth(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> { 
    let mut s1 = HashSet::new(); 
    s1.insert(p); 
    let s2 = HashSet::new(); 
    return nthLoop(n, s1, s2); 
} 

fn main() { 
    let s = nth(2000, (0, 0)); 
    println!("{}", s.len()); 
} 

Answer 2

मुझे ब्रैकेट चीजों को दोगुना करना प्रतीत होता है: क्या यह सही है?

नहीं: डबल bracketes क्योंकि आप tuples उपयोग करने के लिए चुना है और एक समारोह है कि लेता है एक टपल पहले टपल बनाने की आवश्यकता है बुला लिया है कर रहे हैं, लेकिन एक बंद है कि F: Fn(i32, i32) जैसे कई तर्क ले, हो सकता है।

fn iterNeighbors<F>(i: i32, j: i32, f: F) 
    where F: Fn(i32, i32) 
{ 
    f(i-1, j); 
    f(i+1, j); 
    f(i, j-1); 
    f(i, j+1); 
} 

हालांकि, ऐसा लगता है कि tuples को बनाए रखना इस मामले के लिए समझ में आता है: यह एक है कि समारोह लिख सकता है के रूप में, है।

मुझे लगता है कि मैं तर्कों के जीवनकाल को सही करने के लिए संघर्ष कर रहा हूं क्योंकि वे रिकर्सिव कॉल में घूमते हैं। अगर मैं रिटर्न से पहले एस 2 को डिलीकेट किया जाना चाहता हूं तो मुझे जीवनकाल को कैसे एनोटेट करना चाहिए और मैं चाहता हूं कि एस 1 लौटाए या रिकर्सिव कॉल में या तो जीवित रहे?

संदर्भ के लिए कोई ज़रूरत नहीं है (और जीवन काल के लिए इसलिए कोई जरूरत नहीं), बस सीधे के माध्यम से डेटा पास:

fn nthLoop(n: i32, s1: HashSet<(i32, i32)>, s2: HashSet<(i32, i32)>) -> HashSet<(i32, i32)> { 
    if n==0 { 
     return s1; 
    } else { 
     let mut s0 = HashSet::new(); 
     for &p in s1 { 
      iterNeighbors(p, |p| { 
       if !(s1.contains(&p) || s2.contains(&p)) { s0.insert(p); } 
      }) 
     } 
     drop(s2); // guarantees timely deallocation 
     return nthLoop(n-1, s0, s1); 
    } 
} 

कुंजी यहाँ आप मूल्य से सब कुछ कर सकते हैं, और चीजों को मूल्य से चारों ओर से पारित कर दिया निश्चित रूप से उनके मूल्यों को चारों ओर रखेंगे।

बहरहाल, यह संकलन करने में विफल रहता है:

error: cannot borrow data mutably in a captured outer variable in an `Fn` closure [E0387] 
      if !(s1.contains(&p) || s2.contains(&p)) { s0.insert(p); } 
                 ^~ 
help: see the detailed explanation for E0387 
help: consider changing this closure to take self by mutable reference 
     iterNeighbors(p, |p| { 
      if !(s1.contains(&p) || s2.contains(&p)) { s0.insert(p); } 
     }) 

कहने के लिए, बंद मूल्यों यह कब्जा (s0) उत्परिवर्तित करने के लिए कोशिश कर रही है कि है, लेकिन Fn बंद विशेषता यह अनुमति नहीं है। उस विशेषता को अधिक लचीला तरीके से जोड़ा जा सकता है (जब साझा किया जाता है), लेकिन यह आंतरिक रूप से बंद होने पर अधिक प्रतिबंध लगाता है।

सौभाग्य से वहाँ एक आसान ठीक है: FnMut विशेषता है, जो कि बंद के केवल जब भी इसे करने के लिए अद्वितीय पहुँच गया है कहा जा सकता है की आवश्यकता है का उपयोग करते हुए, लेकिन: (http://huonw.github.io/blog/2015/05/finding-closure-in-rust/ आप रुचि रखते हैं, मैं इस बारे में और अधिक लिखा है) आंतरिक लोगों को चीजों को बदलने की अनुमति देता है।

fn iterNeighbors<F>((i, j): (i32, i32), mut f: F) 
    where F: FnMut((i32, i32)) 
{ 
    f((i-1, j)); 
    f((i+1, j)); 
    f((i, j-1)); 
    f((i, j+1)); 
} 

फोन करने वाले कुछ इस तरह दिखेगा:

मान भी यहां कार्य: उस मामले में एक संदर्भ लौटने s0 के लिए सूचक है, जो स्टैक फ्रेम कि किया जा रहा है रहता लौटने होगा समारोह के रूप में नष्ट हो गया। यही है, संदर्भ मृत डेटा को इंगित कर रहा है।

ठीक सिर्फ संदर्भ उपयोग कर रहा है नहीं:

fn nth(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> { 
    let s0 = HashSet::new(); 
    let mut s1 = HashSet::new(); 
    s1.insert(p); 
    return nthLoop(n, s1, s0); 
} 

यह काम करता है अगर मैं हाथ से बंद इनलाइन लेकिन मैं समझ नहीं बंद आह्वान करने के लिए कैसे। आदर्श रूप में, मुझे यहां स्थिर प्रेषण चाहिए।

(मुझे समझ नहीं आता कि इसका क्या मतलब, आप हमें आपकी मदद में मदद करता है के साथ समस्या हो संकलक त्रुटि संदेश भी शामिल है।)

इसके अलावा, मैं केवल में एफ # क्योंकि मैं HashSet इस्तेमाल किया मान लें कि जंग कुशल सेट-सैद्धांतिक परिचालन (संघ, चौराहे और अंतर) के साथ पूरी तरह से कार्यात्मक सेट प्रदान नहीं करता है। क्या मैं इसे मानने में सही हूं?

आप जो चाहते हैं उसके आधार पर, नहीं, उदा। HashSet और BTreeSet दोनों methods which return iterators के रूप में विभिन्न सेट-सैद्धांतिक संचालन प्रदान करते हैं।

---

कुछ छोटे अंक:

• स्पष्ट/नामित जीवन काल, संकलक डेटा के स्थिर वैधता के बारे में तर्क करने की अनुमति देते हैं कि वे इसे नियंत्रित नहीं करते हैं (यानी वे संकलक बाहर जब आप बात करने के लिए अनुमति देते हैं कुछ गलत करें, लेकिन भाषा में अभी भी एक ही प्रकार का स्थिर संसाधन उपयोग/जीवन चक्र गारंटी सी ++ के रूप में है)
• लूप वाला संस्करण लिखित रूप में अधिक कुशल होने की संभावना है, क्योंकि यह सीधे स्मृति का उपयोग करता है (सेट को स्वैप करता है, प्लस s0.clear(), हालांकि, वही लाभ एक पुनरावर्ती संस्करण के साथ महसूस किया जा सकता है s2 को छोड़ने के बजाए पुन: उपयोग के लिए नीचे जाकर।
• while पाश for _ in 0..n
• हो सकता है संदर्भ द्वारा बंद पारित करने के लिए कोई जरूरत नहीं है, लेकिन साथ या संदर्भ के बिना, वहां अभी भी स्थिर प्रेषण (बंद एक प्रकार पैरामीटर, नहीं एक विशेषता वस्तु है) है।
• पारंपरिक, बंद तर्क, पिछले है, और संदर्भ से नहीं लिया हैं क्योंकि इससे उन्हें (जैसे foo(&|y| bar(y + 1), x) की foo(x, |y| bar(y + 1)) बजाय) को पढ़ने के लिए इनलाइन गुजर आसान & को परिभाषित करता है

• return कीवर्ड रिटर्न अनुगामी के लिए आवश्यक (यदि नहीं है ; छोड़ दिया जाता है):

  fn nth(n: i32, p: (i32, i32)) -> HashSet<(i32, i32)> { 
      let s0 = HashSet::new(); 
      let mut s1 = HashSet::new(); 
      s1.insert(p); 
      nthLoop(n, s1, s0) 
  }