क्या स्मृति के दो ब्लॉक की तुलना करने का कोई तरीका है, और पता है कि वे किस बिंदु पर भिन्न हैं (memcmp() इस आवश्यकता को पूरा नहीं करता है)? मैं महंगा लूप प्रदर्शन नहीं करना चाहता। अग्रिम में धन्यवाद।मेमोरी तुलना (अंतर स्थिति के साथ)
सादर, Neo_b
और जो कुछ भी आप कर रहे हैं की तुलना में, एक पाश सस्ती है: बड़ा लागत पहली जगह में राम से डेटा प्राप्त हो जाएगा (या डिस्क!)।
आप कुछ बाइट्स से अधिक की स्मृति तुलना के साथ लूपिंग से बच नहीं सकते हैं। एल्गोरिदम लिखें क्योंकि आप इसे कल्पना कर सकते हैं। यह काफी आसान है और आप आश्चर्यचकित हो सकते हैं कि संकलक इस तरह के कोड को कितनी अच्छी तरह अनुकूलित करता है।
std::mismatch आपके लिए std::distance संयोजन के साथ ऐसा करेगा।
आपने माना कि वह एसटीएल इटरेटर का उपयोग कर रहा है, और इसके अलावा उसे पता होना चाहिए कि किस बिंदु पर स्मृति अलग है। – Doomsday
मेरे पास std :: बराबर पहले था जो स्पष्ट रूप से गलत था इसलिए मैंने इसे सही किया है। एल्गोरिदम पॉइंटर्स के साथ-साथ (पूर्ण उड़ाए गए) इटरेटर्स के साथ बहुत अच्छी तरह से काम करते हैं। –
@ डूमडेडे: 'char *' * * एक इटरेटर प्रकार है, और 'मिस्चैच' अंतर को इंगित करने वाले दो इटरेटर लौटाता है। +1 – Potatoswatter
memcmp बस बाइट के लिए "महंगा लूप" बाइट करता है। उदाहरण के लिए, यहां माइक्रोसॉफ्ट का कार्यान्वयन है:
EXTERN_C int __cdecl memcmp(const void *Ptr1, const void *Ptr2, size_t Count)
{
INT v = 0;
BYTE *p1 = (BYTE *)Ptr1;
BYTE *p2 = (BYTE *)Ptr2;
while(Count-- > 0 && v == 0) {
v = *(p1++) - *(p2++);
}
return v;
}
अधिकांश अन्य कार्यान्वयन एक ही चीज़ करते हैं। आपकी ज़रूरतों के लिए, आप ऐसा कुछ कर सकते हैं:
long my_memcmp(const void *Ptr1, const void *Ptr2, size_t Count)
{
INT v = 0;
long pos = 0;
BYTE *p1 = (BYTE *)Ptr1;
BYTE *p2 = (BYTE *)Ptr2;
while(Count-- > 0 && v == 0)
{
v = *(p1++) - *(p2++);
if (v == 0)
pos++;
else
break;
}
return pos;
}
बाइट-प्रति-बाइट वास्तव में महंगा है। 32-बिट 'int' ऑपरेशंस उनके 8-बिट समकक्षों की तुलना में तेज़ हो सकते हैं। – mvds
मैंने अपना खुद का कार्यान्वयन बनाया (मैंने सोचा कि मैं इसे अंततः किसी अन्य चीज़ से बदल सकता हूं)। मेरी जरूरतों को 10 000 000 पुनरावृत्तियों की आवश्यकता है। सिस्टम कभी-कभी जम जाता है, लेकिन यह काम करता है। यह भी कहता है कि पहले गैर-मैच अवसर के बाद कितने बाइट मेल नहीं खाते हैं। –
@Neo_b: 10 मिलियन पुनरावृत्तियों इतना अधिक नहीं है - अधिकांश कोई भी प्रणाली एक या दूसरी तिमाही में ऐसा करेगी। मैं आपकी इनपुट बफरिंग योजना को देख रहा हूं, या इस समस्या पर हमला कर रहा हूं कि पुनर्विचार पर विचार कर रहा हूं। यदि आप तारों की खोज कर रहे हैं, उदाहरण के लिए, बॉयर मूर एल्गोरिदम शायद आपको यहां से कहीं भी बेहतर कर देगा। –
आपको हमेशा एक लूप की आवश्यकता होगी। लेकिन यदि आप 4 बाइट्स (int to cast *) या 8 बाइट्स (uint64_t या long long int) द्वारा लूपिंग करते हैं तो आप बेंचमार्क कर सकते हैं। बेवकूफ प्रति-बाइट समाधान से तेज़ है।
लम्बाई (कहें,> 1 केबी) के आधार पर भी बेहतर, आप लूप को अनलॉक कर सकते हैं, जिसका अर्थ है कि आप उदा। प्रति 8 int/uint64_t और एक विसंगति पर पहली भिन्न बाइट pinpoint।
uint64_t *bigsteps1 = (uint64_t*)m1;
uint64_t *bigsteps2 = (uint64_t*)m2;
int steps = min(m1_len,m2_len)/sizeof(uint64_t);
int i;
for (i=0; i<steps; i+=8)
{
if (bigsteps1[i] != bigsteps2[i]
|| bigsteps1[i+1] != bigsteps2[i+1]
/// ....
|| bigsteps1[i+7] != bigsteps2[i+7]) break;
}
// i<steps tells if we found a difference
// end game is trivial, left as an excercise to the reader.
पाश उतारना भी उल्टी हो सकती है, तुम वहाँ में इन सभी + N बातें और मैं + = 8 के साथ-साथ हो लिए। सुनिश्चित करने के लिए बेंचमार्क।
ps भी जांच स्मृति संरेखण: यह सबसे तेजी से होगा, जब m1&0xff == m2&0xff == 0
सलाह के लिए धन्यवाद, मैं निश्चित रूप से इसे लागू कर दूंगा, हालांकि मुझे पूरी तरह से यकीन नहीं है कि एम 1 और 0xff == m2 और 0xff == 0 क्या करना है, जो मुझे एम 1 और 0xff == m1 पता है, क्या यह सही नहीं है? –
कुछ मामलों में यह तेजी से होगा, लेकिन इसके परिणामस्वरूप कुछ समस्याएं हो सकती हैं। सबसे पहले, यह आपके प्लेटफ़ॉर्म पर निर्भर करता है जिसमें 64 बिट पूर्णांक के लिए समान संरेखण होता है क्योंकि यह वर्णों के लिए होता है, जो प्रायः मामला नहीं होता है। (कोई भी नहीं कहता कि चरित्र सरणी का आधार 8 बाइट सीमा पर होना चाहिए) दूसरा, एक अंतर्निहित आंतरिक या असेंबलर शायद तेज़ होगा। X86 पर, मेमोरी संरेखण समस्या केवल चीजों को धीमा कर देगी, और अन्य आर्किटेक्चर पर, यह प्रोसेसर को बाधा डालने का कारण बन जाएगी। –
@Neo_b: 'm1 और 0xff == 0' एक परीक्षण है यदि पता 'm1'' 00' के साथ समाप्त होता है। @ बिली: निश्चित रूप से इस तरह के अनुकूलन में आपको सीमाओं के साथ थोड़ा सा झुकाव करना चाहिए, इसलिए जब तक आप पहले गठबंधन ब्लॉक को धीमा न करें, तब तक जितना संभव हो सके उतने ब्लॉक का परीक्षण करें, और शेष धीमी गति से परीक्षण करें। (जैसा कि कहा गया है कि ये चीजें केवल सकारात्मक रूप से काम करती हैं यदि ब्लॉक काफी बड़े हैं) एक अंतर्निहित आंतरिक या असेंबलर शायद तेज़ होगा * यदि यह अस्तित्व में होगा * जो मुझे लगता है कि समस्या के मामले में मामला नहीं है। – mvds
अगर कोई स्मृति के दो ब्लॉकों की तुलना में एक बेहतर तरीका था, memcmp ऐसा करने के लिए reimplemented किया जाएगा।
यह कहकर कि अक्सर, एमएमसीएमपी मानक सी लाइब्रेरी में एक डिफ़ॉल्ट पोर्टेबल कार्यान्वयन है लेकिन अक्सर कंपाइलर द्वारा एक बिल्टिन फ़ंक्शन के रूप में लागू किया जाता है। इस बिल्टिन फ़ंक्शन को लक्ष्य आर्किटेक्चर के लिए अत्यधिक अनुकूलित किया जाना चाहिए। इसलिए पुस्तकालय कार्यान्वयन को नमक के चुटकी से लें।
प्रति-cpu अनुकूलित memcmp कार्यान्वयन के बारे में http://stackoverflow.com/questions/855895/intrinsic-memcmp भी देखें। यदि आप सीपीयू को जानते हैं तो आप अपनी आवश्यकताओं के लिए जीसीसी के __builtin_memcmp() कार्यों में से एक को ट्यून कर सकते हैं। – mvds
ध्यान दें कि आपके पास जो कुछ भी है, उसे लूप * कहीं * के रूप में कार्यान्वित किया जा रहा है * - बिना किसी के यहां आप जो चाहते हैं उसे करने का कोई जादू तरीका नहीं है। –