मैं एक फ़ाइल से यादृच्छिक रेखा कैसे वापस कर सकता हूं? साक्षात्कार प्रश्न

Question

मैं एक फोन साक्षात्कार की तैयारी कर रहा हूं। मैं इंटरनेट पर इन सवालों पर आया था। क्या कोई मुझे इनके लिए कुछ अच्छे जवाब बता सकता है?

1. मान लीजिए मैं तुम्हें एक पाठ फ़ाइल देने के लिए और आप एक पूछना एक प्रोग्राम है जो फ़ाइल से एक यादृच्छिक लाइन वापस आ जाएगी (सभी लाइनों समान प्रायिकता वापस करने होनी चाहिए)

2. एक ही हिस्से के रूप में लिखने के लिए 1, इस समय को छोड़कर पूरी पाठ फ़ाइल मुख्य स्मृति में फिट नहीं हो सकती

3. भाग 2 के समान ही, सिवाय इसके कि आपके पास फ़ाइल की बजाय स्ट्रीम है।

कृपया मदद करें।

ठीक है ... @ हर कोई, मुझे यह पूछने से पहले मेरे mintod में वास्तव में कुछ विचार थे ... मेरे साथी सॉर्स द्वारा निरंतर हमले को देखते हुए, मैं अपने उत्तरों पोस्ट कर रहा हूं। कृपया उन्हें भी हमला करने के लिए स्वतंत्र महसूस करें ...

1: फ़ाइल में '\ n' की संख्या की गणना करें। 1 और संख्या के बीच एक यादृच्छिक संख्या उत्पन्न करें और संख्या -1 '\ n' के बाद लाइन वापस करें।

2: फ़ाइल को मुख्य मेमोरी भाग में भागकर लाएं और उपर्युक्त प्रक्रिया का पालन करें।

3: मुझे इसके बारे में ज्यादा जानकारी नहीं है और किसी भी इनपुट की सराहना करेंगे।

इसकी अद्भुत है कि तुम लोग वास्तव में आगे बढ़ाने के लिए एक प्रेरणा दे .....

Answer 1

पुन 1: उपयोग समाधान करने के लिए 2

पुन 2: आप एक RandomAccessFile का उपयोग कर पूरी फ़ाइल स्कैन करना चाहते हैं लाइनों की संख्या और (संभवतः) लाइन की प्रत्येक शुरुआत के लिए फ़ाइल पॉइंटर्स को कैश करने के लिए उपयोग करें। फिर आप यादृच्छिक रूप से एक चुन सकते हैं (मुझे लगता है कि यह प्रश्न यादृच्छिक संख्याएं उत्पन्न करने के बारे में नहीं है) और उस प्रारंभ बिंदु पर वापस जाएं, रेखा पढ़ें और इसे वापस करें। यदि आप इसे तेज़ी से चाहते हैं तो सुनिश्चित करें कि आप पढ़ रहे हैं (राफ v v अन्यथा धीमा है)।

पुन: यदि स्ट्रीम स्मृति में फिट नहीं होती है (यानी आप पूरी चीज को कैश नहीं कर सकते हैं) और आप नहीं जानते कि पूरी धारा को पढ़ने के बिना स्ट्रीम में कितनी लाइनें हैं (मान लीजिए कि आपको केवल पढ़ने के लिए मिलता है यह एक बार) तो मैं एक समाधान नहीं देख सकता। मैं भी जवाब के लिए इंतजार कर रहा हूं ...

Answer 2

1. एक सरणी में सभी पंक्तियां पढ़ें, 1 की सीमा और रेखाओं की मात्रा में एक यादृच्छिक रेखा वापस करें।

2. सबसे सरल: रेखाओं की गणना करें, यादृच्छिक रूप से एक लाइन नंबर चुनें, फ़ाइल को दूसरी बार जाएं और इसे वापस करें।

3. आपको बस एक पंक्ति याद रखना है। प्रत्येक नई लाइन में 1/एन की संभावना है (एन लाइनों को पढ़ा जा रहा है)।

   स्यूडोकोड:

   i = 1 
   chosen_line = "" 
   for line in lines: 
       if random() < 1/i: # random returns a uniform random number in [0,1) 
        chosen_line = line 
       i += 1 
   return chosen_line 
   

एल्गोरिथ्म नंबर 3 भी 1 और 2 के लिए इस्तेमाल किया जा सकता है।

Answer 3

# 3: डिस्क पर फ़ाइल को स्ट्रीम लिखें और समाधान का उपयोग करें 2. बिल्कुल सबसे कुशल समाधान नहीं, लेकिन बहुत सरल है।

Answer 4

आप स्मृति में सभी लाइनों को पढ़ने के बिना ऐसा कर सकते हैं, इस प्रकार बड़ी फ़ाइलों के लिए अच्छी तरह से काम कर रहे हैं। स्यूडोकोड:

linenum := 0 
ret := '' 
while more lines to read: 
    line := readline() 
    linenum := linenum + 1 
    r := uniform_random(0, linenum) 
    if r < 1: 
     ret := line 

return ret 

सबूत: हम ध्यान देने योग्य बात है कि हम हमेशा ret में पहली पंक्ति को बचाने के द्वारा शुरू करते हैं। अगर फ़ाइल में एक पंक्ति है, तो आप इसे चुनने जा रहे हैं, और आप कर चुके हैं।

दो लाइन फ़ाइल के लिए, ret पहली पंक्ति को 100% समय बचाएगा, और दूसरी पंक्ति लूप के दूसरे पुनरावृत्ति के दौरान ret 50% समय में सहेजी जाएगी। इस प्रकार, प्रत्येक पंक्ति में चयनित होने के 0.5 की संभावना है।

अब, मान लीजिए कि यह विधि ≤ N लाइनों की फ़ाइलों के लिए काम करती है। यह साबित करने के लिए कि इसका मतलब यह है कि यह N+1 के लिए काम करता है, (N+1) लूप के वें पुनरावृत्ति में, 1/(N+1) की संभावना है कि अंतिम पंक्ति का चयन किया जाएगा (random(0, N+1) < 1 में वह संभावना है)। इस प्रकार, अंतिम पंक्ति में 1/(N+1) चयनित होने की संभावना है। चुनी जा रही सभी अन्य लाइनों की संभावना अभी भी एक-दूसरे के बराबर होगी, चलिए इसे x पर कॉल करें। फिर, N*x + 1/(N+1) == 1, जिसका अर्थ है कि x = 1/(N+1)।

प्रेरण द्वारा सबूत पूरा हो गया है।

संपादित करें: ओह, जवाब देने से पहले पहले उत्तर की तीसरी विधि नहीं देखी गई। फिर भी, अगर मैं केवल सबूत के लिए, और अन्य लोगों के लिए इसका कोई मौका होने पर इसे सही करने का अवसर यहां इस पोस्ट को रखूंगा।