grep कितनी तेजी से दौड़ता है?

Question

मैं वास्तव में खोल में ग्रेप की कार्यक्षमता से चकित हूँ, पहले मैं जावा में स्ट्रिंग विधि का उपयोग करने के लिए इस्तेमाल, लेकिन अब मैं इसके लिए ग्रेप उपयोग करें और यह सेकंड के एक मामले में कार्यान्वित करता है, यह जावा कोड है कि मैं करने के लिए इस्तेमाल की तुलना में blazingly तेजी से होता है लिखें। (मेरे अनुभव मैं गलत हो सकता है के अनुसार, हालांकि)

कहा जा रहा है मैं इसे कैसे हो रहा है यह पता लगाने के लिए सक्षम नहीं किया गया? वेब पर भी बहुत कुछ उपलब्ध नहीं है।

किसी को भी इस के साथ मेरी मदद कर सकते हैं?

Answer 1

अपने प्रश्न मानते हुए GNU grep विशेष रूप से संबंध है। लेखक, माइक हार्टेल से एक नोट यहां दिया गया है:

जीएनयू grep तेज़ है क्योंकि यह प्रत्येक इनपुट BYTE पर देख रहा है। क्योंकि यह प्रत्येक बाइट है कि यह पर नज़र करता है के लिए कार्यान्वित बहुत कुछ निर्देश

जीएनयू ग्रेप तेज है।

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

जीएनयू ग्रेप भी बोयर-मूर के भीतरी पाश unrolls, और इस तरह से है कि यह हर unrolled कदम पर पाश से बाहर निकलें परीक्षण करना की जरूरत नहीं है में बोयर-मूर डेल्टा तालिका प्रविष्टियों सेट करता है। इसी का परिणाम है कि , सीमा में, जीएनयू ग्रेप औसत की तुलना में कम 3 एक्स 86 निर्देश प्रत्येक इनपुट बाइट यह वास्तव में पर लग रहा है के लिए मार डाला (और यह कई बाइट्स पूरी तरह से छोड़ देता है) है।

जीएनयू ग्रेप इसे पढ़ने के बाद कच्चे यूनिक्स इनपुट सिस्टम कॉल का उपयोग करता है और नकल डेटा बचा जाता है। इसके अलावा, जीएनयू grep लाइनों में इनपुट लागू करने से बचाता है। न्यूलाइन की तलाश में के कारक द्वारा कई बार grep को धीमा कर दिया जाएगा, क्योंकि न्यूलाइन ढूंढने के लिए इसे प्रत्येक बाइट देखना होगा!

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

इस उत्तर here से लिया जानकारी का एक सबसेट है।

Answer 2

स्टीव के उत्कृष्ट उत्तर में जोड़ने के लिए।

यह व्यापक रूप से ज्ञात नहीं हो सकता लेकिन ग्रेप, लगभग हमेशा तेजी जब एक अब एक छोटी एक से पैटर्न स्ट्रिंग के लिए grepping है, क्योंकि एक लंबे समय तक पैटर्न में, बोयर-मूर को छोड़ सकते हैं अब प्रगति में आगे और भी बेहतर प्राप्त करने के लिए sublinear गति:

उदाहरण:

# after running these twice to ensure apples-to-apples comparison 
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log 
28 
0.168u 0.068s 0:00.26 

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log 
28 
0.100u 0.056s 0:00.17 

लंबा फॉर्म 35% तेज है!

कैसे आते हैं? बॉयर-मूर पैटर्न-स्ट्रिंग से एक स्किप-फ़ॉरवर्ड टेबल तैयार करता है, और जब भी कोई मेल नहीं खाता है, तो यह स्किप में चार में इनपुट में एक सिंगल चार की तुलना करने से पहले सबसे लंबी छोड़ देता है (अंतिम चार से पहले तक) तालिका।

यहाँ a good video explaining Boyer Moore

एक अन्य आम धारणा (जीएनयू ग्रेप के लिए) है कि fgrepgrep की तुलना में तेजी है। ffgrep 'फास्ट' के लिए खड़ा नहीं है, यह 'निश्चित' (मैन पेज देखें) के लिए खड़ा है, और चूंकि दोनों एक ही प्रोग्राम हैं, और दोनों बॉयर-मूर का उपयोग करते हैं, तो उनके बीच गति में कोई अंतर नहीं होता है regexp विशेष वर्णों के बिना फिक्स्ड स्ट्रिंग की खोज। fgrep का उपयोग करने का एकमात्र कारण तब होता है जब रेगेक्सपी विशेष चार होता है (जैसे ., [], या *) मैं नहीं चाहता कि इसे इस तरह व्याख्या किया जाए। और फिर भी grep -F का अधिक पोर्टेबल/मानक रूप fgrep से अधिक पसंद किया जाता है।