एक बहुत बड़ी फ़ाइल

Question

में सबसे आम तीन-आइटम अनुक्रम ढूँढना मेरे पास वेबपृष्ठ विज़िट की कई लॉग फ़ाइलें हैं, जहां प्रत्येक विज़िट उपयोगकर्ता आईडी और टाइमस्टैम्प से जुड़ी होती है। मुझे सबसे लोकप्रिय (यानी अक्सर दौरा किया जाता है) तीन-पेज अनुक्रम की पहचान करने की आवश्यकता है। मुख्य फाइलों में एक बार में लॉग फाइलें बहुत बड़ी होती हैं।

नमूना लॉग फ़ाइल:

User ID  Page ID 
A          1 
A          2 
A          3 
B          2 
B          3 
C          1 
B          4 
A          4 

इसी परिणाम:

एक: 1-2-3, 2-3-4
बी: 2-3-4
2- 3-4 सबसे लोकप्रिय तीन-पेज अनुक्रम

मेरा विचार दो हैश तालिकाओं का उपयोग करना है। उपयोगकर्ता आईडी पर पहला हैश और इसके अनुक्रम को स्टोर करता है; दूसरा तीन पेज अनुक्रमों को हैश करता है और प्रत्येक व्यक्ति की संख्या कितनी बार प्रदर्शित होता है। यह ओ (एन) अंतरिक्ष और ओ (एन) समय लेता है।

हालांकि, चूंकि मुझे दो हैश टेबल का उपयोग करना है, इसलिए स्मृति एक ही समय में सब कुछ नहीं रख सकती है, और मुझे डिस्क का उपयोग करना होगा। डिस्क को अक्सर एक्सेस करने में सक्षम नहीं है।

मैं इसे बेहतर कैसे कर सकता हूं?

Answer 1

यदि आप अनुमानित परिणाम प्राप्त करना चाहते हैं, तो हैश टेबल का उपयोग करें, जैसा कि आप चाहते थे, लेकिन कम से कम हाल ही में उपयोग की जाने वाली प्रविष्टियों को कम करने के लिए प्रत्येक हैश तालिका में सीमित आकार की कतार जोड़ें।

यदि आप सटीक परिणाम चाहते हैं, तो उपयोगकर्ता आईडी द्वारा लॉग सॉर्ट करने के लिए बाहरी सॉर्ट प्रक्रिया का उपयोग करें, फिर प्रत्येक 3 लगातार प्रविष्टियों को गठबंधन करें और इस बार - पृष्ठ आईडी द्वारा क्रमबद्ध करें।

अद्यतन (टाइमस्टैम्प द्वारा तरह)

कुछ preprocessing ठीक से लॉगफ़ाइल 'टाइम स्टांप का उपयोग करने की जरूरत हो सकती:

• लॉगफ़ाइल पहले से ही टाइमस्टैम्प के अनुसार क्रमबद्ध रहे हैं, तो कोई पूर्व प्रसंस्करण की जरूरत है।
• यदि कई लॉग फाइलें हैं (संभवतः स्वतंत्र प्रक्रियाओं से आ रही हैं), और प्रत्येक फ़ाइल पहले से ही टाइमस्टैम्प द्वारा क्रमबद्ध की जाती है, तो इन सभी फ़ाइलों को खोलें और उन्हें पढ़ने के लिए विलय सॉर्ट का उपयोग करें।
• यदि फ़ाइलों को टाइमस्टैम्प द्वारा लगभग क्रमबद्ध किया जाता है (जैसे कि कई स्वतंत्र प्रक्रियाएं एकल फ़ाइल में लॉग लिखती हैं), सही क्रम में डेटा प्राप्त करने के लिए बाइनरी ढेर का उपयोग करें।
• यदि फ़ाइलों को टाइमस्टैम्प द्वारा क्रमबद्ध नहीं किया जाता है (जो अभ्यास में संभव नहीं है), टाइमस्टैम्प द्वारा बाह्य प्रकार का उपयोग करें।

Update2 LRU कतार बेतरतीब ढंग से वितरित डेटा के लिए काफी अच्छे परिणाम चाहिए साथ

लगभग विधि (अनुमानित विधि में सुधार)। लेकिन वेबपृष्ठ यात्राओं के दिन के अलग-अलग समय में अलग-अलग पैटर्न हो सकते हैं, या सप्ताहांत पर अलग हो सकते हैं। मूल दृष्टिकोण ऐसे डेटा के लिए खराब परिणाम दे सकता है। इसे सुधारने के लिए, पदानुक्रमित एलआरयू कतार का उपयोग किया जा सकता है।

विभाजन (एन) छोटी पंक्तियों में विभाजन एलआरयू कतार। आकार एन/2, एन/4, ... सबसे बड़े में किसी भी तत्व, अगले एक - तत्वों, कम से कम 2 बार देखा जाना चाहिए, अगले एक - कम से कम 4 बार, ...यदि कुछ उप-कतार से तत्व हटा दिया जाता है, तो इसे दूसरे में जोड़ा जाता है, इसलिए यह सभी उप-पंक्तियों में रहता है, जो पूरी तरह से हटाए जाने से पहले, पदानुक्रम में कम होते हैं। ऐसी प्राथमिकता कतार अभी भी ओ (1) जटिलता का है, लेकिन अधिकांश लोकप्रिय पृष्ठ के लिए बेहतर अनुमान लगाती है।

Answer 2

शायद सिंटैक्स त्रुटियां यहां बड़ी हैं, लेकिन इसमें लगभग असीमित लंबाई लॉग फ़ाइल के लिए सीमित मात्रा में रैम लेना चाहिए।

typedef int pageid; 
typedef int userid; 
typedef pageid[3] sequence; 
typedef int sequence_count; 

const int num_pages = 1000; //where 1-1000 inclusive are valid pageids 
const int num_passes = 4; 
std::unordered_map<userid, sequence> userhistory; 
std::unordered_map<sequence, sequence_count> visits; 
sequence_count max_count=0; 
sequence max_sequence={}; 
userid curuser; 
pageid curpage; 
for(int pass=0; pass<num_passes; ++pass) { //have to go in four passes 
    std::ifstream logfile("log.log"); 
    pageid minpage = num_pages/num_passes*pass; //where first page is in a range 
    pageid maxpage = num_pages/num_passes*(pass+1)+1; 
    if (pass==num_passes-1) //if it's last pass, fix rounding errors 
     maxpage = MAX_INT; 
    while(logfile >> curuser >> curpage) { //read in line 
     sequence& curhistory = userhistory[curuser]; //find that user's history 
     curhistory[2] = curhistory[1]; 
     curhistory[1] = curhistory[0]; 
     curhistory[0] = curhistory[curpage]; //push back new page for that user 
     //if they visited three pages in a row 
     if (curhistory[2] > minpage && curhistory[2]<maxpage) { 
      sequence_count& count = visits[curhistory]; //get times sequence was hit 
      ++count; //and increase it 
      if (count > max_count) { //if that's new max 
       max_count = count; //update the max 
       max_sequence = curhistory; //arrays, so this is memcpy or something 
      } 
     } 
    } 
} 
std::cout << "The sequence visited the most is :\n"; 
std::cout << max_sequence[2] << '\n'; 
std::cout << max_sequence[1] << '\n'; 
std::cout << max_sequence[0] << '\n'; 
std::cout << "with " << max_count << " visits.\n"; 

ध्यान दें कि आप pageid या useridstringint रों के बजाय रों हैं, तो आप एक महत्वपूर्ण गति/आकार/कैशिंग जुर्माना लगेगा।

[EDIT2] अब यह 4 (अनुकूलन) पास में काम करता है, जिसका अर्थ है कि यह कम स्मृति का उपयोग करता है, जिससे यह काम वास्तविक रूप से रैम में होता है। यह सिर्फ आनुपातिक रूप से धीमा हो जाता है।

Answer 3

यदि आपके पास 1000 वेब पेज हैं तो आपके पास 1 बिलियन संभव 3-पेज अनुक्रम हैं। यदि आपके पास 32-बिट काउंटर की एक साधारण सरणी है तो आप 4 जीबी मेमोरी का उपयोग करेंगे। जैसे ही आप जाते हैं, डेटा को छोड़कर इसे कम करने के तरीके हो सकते हैं, लेकिन यदि आप सही उत्तर प्राप्त करने की गारंटी देना चाहते हैं तो यह हमेशा आपका सबसे खराब मामला बन जाएगा - इसमें कोई टालना नहीं है, और स्मृति में सहेजने के तरीकों का आविष्कार करना औसत मामला सबसे खराब मामला और भी भूख लगी होगी।

उस पर, आपको उपयोगकर्ताओं को ट्रैक करना होगा। प्रत्येक उपयोगकर्ता के लिए आपको उनके द्वारा देखे गए अंतिम दो पृष्ठों को स्टोर करने की आवश्यकता होती है। मान लें कि उपयोगकर्ताओं को लॉग में नाम से संदर्भित किया जाता है, आपको उपयोगकर्ताओं के नामों को हैश तालिका में और साथ ही दो पृष्ठ संख्याओं में स्टोर करने की आवश्यकता होगी, तो आइए औसत पर 24 बाइट प्रति उपयोगकर्ता (शायद रूढ़िवादी - मैं मान रहा हूं लघु उपयोगकर्ता नाम)। 1000 उपयोगकर्ताओं के साथ जो 24 केबी होगा; 1000000 उपयोगकर्ता 24 एमबी के साथ।

स्पष्ट रूप से अनुक्रम काउंटर स्मृति समस्या पर हावी है।

यदि आपके पास केवल 1000 पृष्ठ हैं तो आधुनिक 64-बिट मशीन में 4 जीबी मेमोरी अनुचित नहीं है, खासकर डिस्क-बैक वर्चुअल मेमोरी की अच्छी मात्रा के साथ। यदि आपके पास पर्याप्त स्वैप स्पेस नहीं है, तो आप केवल एक एमएमएपी फाइल बना सकते हैं (लिनक्स पर - मुझे लगता है कि विंडोज़ में कुछ समान है), और हमेशा ओएस पर भरोसा करते हैं ताकि स्मृति में कैश किए जाने वाले सबसे अधिक इस्तेमाल किए जाने वाले मामलों का उपयोग किया जा सके।

तो, मूल रूप से, गणित यह निर्देश देते हैं कि यदि आपके पास ट्रैक करने के लिए बड़ी संख्या में पृष्ठ हैं, और आप सबसे बुरे मामले से निपटने में सक्षम होना चाहते हैं, तो आपको यह स्वीकार करना होगा कि आपके पास डिस्क फ़ाइलों का उपयोग करने के लिए।

मुझे लगता है कि एक सीमित क्षमता हैश तालिका शायद सही जवाब है। आप इसे उपलब्ध स्मृति के अनुसार इसे एक विशिष्ट मशीन के लिए अनुकूलित कर सकते हैं। यह समझने के बाद कि आपको उस मामले को संभालने की आवश्यकता है जहां तालिका क्षमता तक पहुंच जाती है। यदि संभवतः आप शायद ही कभी वहां पहुंच जाएं तो इसे बहुत कुशल होने की आवश्यकता नहीं हो सकती है। यहां कुछ सुझाव दिए है:

• बेदखल कम से कम आमतौर पर इस्तेमाल किया दृश्यों दायर करने के लिए, स्मृति में सबसे आम रखते हुए। मुझे औसत स्तर से नीचे का स्तर निर्धारित करने के लिए टेबल पर दो पास की आवश्यकता होगी, और फिर निष्कासन करने के लिए। किसी भी तरह आपको यह जानना होगा कि आप प्रत्येक प्रविष्टि कहां रखेंगे, जब भी आपको हैश-मिस मिलती है, जो मुश्किल साबित हो सकती है।

• बस पूरी तालिका को फ़ाइल में डंप करें, और स्क्रैच से नया बनाएं। दोहराएँ। अंत में, सभी तालिकाओं से मिलान प्रविष्टियों को पुनः संयोजित करें। अंतिम भाग भी मुश्किल साबित हो सकता है।

• तालिका का विस्तार करने के लिए एक एमएमएपी फ़ाइल का उपयोग करें। सुनिश्चित करें कि फ़ाइल का उपयोग प्राथमिक रूप से कम से कम उपयोग किए जाने वाले अनुक्रमों के लिए किया जाता है, जैसा कि मेरे पहले सुझाव में है।असल में, आप इसे वर्चुअल मेमोरी के रूप में उपयोग करेंगे - पतों को भूल जाने के बाद फ़ाइल बाद में व्यर्थ होगी, लेकिन आपको इसे लंबे समय तक रखने की आवश्यकता नहीं होगी। मुझे लगता है कि यहां पर्याप्त नियमित वर्चुअल मेमोरी नहीं है, और/या आप इसका उपयोग नहीं करना चाहते हैं। जाहिर है, यह केवल 64-बिट सिस्टम के लिए है।

Answer 4

मुझे लगता है कि आपको केवल प्रत्येक उपयोगकर्ता आईडी के लिए हाल ही में देखा गया ट्रिपल स्टोर करना होगा? तो आपके पास दो हैश टेबल हैं। उपयोगकर्ता आईडी की पहली युक्त कुंजी, हाल ही में देखे गए ट्रिपल के मूल्य में उपयोगकर्ता आईडी की संख्या के बराबर आकार है।

संपादित करें: पहले से ही टाइमस्टैम्प द्वारा क्रमबद्ध फ़ाइल मान लीजिए।

दूसरी हैश तालिका में उपयोगकर्ता आईडी की एक कुंजी है: पृष्ठ-ट्रिपल, और देखा गया समय की गिनती का मूल्य।

मैं जानता हूँ कि आप ने कहा C++, लेकिन यहाँ कुछ awk जो एक एकल पास में यह करता है (ग में बदलने के लिए ++ बहुत सीधी-सपाट होना चाहिए):

# $1 is userid, $2 is pageid 

{ 
    old = ids[$1];   # map with id, most-recently-seen triple 
    split(old,oldarr,"-"); 
    oldarr[1]=oldarr[2]; 
    oldarr[2]=oldarr[3]; 
    oldarr[3] = $2; 
    ids[$1]=oldarr[1]"-"oldarr[2]"-"oldarr[3]; # save new most-recently-seen 
    tripleid = $1":"ids[$1]; # build a triple-id of userid:triple 
    if (oldarr[1] != "") { # don't accumulate incomplete triples 
     triples[tripleid]++; } # count this triple-id 
} 
END { 
    MAX = 0; 
    for (tid in triples) { 
     print tid" "triples[tid]; 
     if (triples[tid] > MAX) MAX = tid; 
    } 
    print "MAX is->" MAX" seen "triples[tid]" times"; 
} 

Answer 5

आप यूनिक्स का उपयोग कर रहे हैं, तो sort आदेश कर सकते हैं मनमाने ढंग से बड़ी फाइलों का सामना करना पड़ता है।

1. sort -k1,1 -s logfile > sorted (ध्यान दें कि यह एक स्थिर प्रकार (-s) प्रथम स्तंभ पर है)
2. sorted की कुछ कस्टम प्रसंस्करण प्रदर्शन करना है कि एक और करने के लिए एक नई लाइन के रूप में प्रत्येक त्रिक आउटपुट: तो आप कुछ इस तरह कर सकता है फ़ाइल, triplets कहें, या तो सी ++ या शेल स्क्रिप्ट का उपयोग करें। तो उदाहरण में आपको तीन पंक्तियों वाली फ़ाइल मिलती है: 1-2-3, 2-3-4, 2-3-4। यह प्रसंस्करण त्वरित है क्योंकि चरण 1 का अर्थ है कि आप एक समय में केवल एक उपयोगकर्ता की विज़िट से निपट रहे हैं, ताकि आप एक समय में sorted फ़ाइल को एक पंक्ति में काम कर सकें।
3. sort triplets | uniq -c | sort -r -n | head -1 को सबसे आम तीन गुना और इसकी गिनती देना चाहिए (यह तीनों प्रकार की घटनाओं की गणना करता है, प्रत्येक की घटनाओं की गणना करता है, उन्हें गिनती के अवरोही क्रम में टाइप करता है और शीर्ष पर ले जाता है)।

इस दृष्टिकोण में इष्टतम प्रदर्शन नहीं हो सकता है, लेकिन इसे स्मृति से बाहर नहीं होना चाहिए।