एक परिपत्र बफर में शेष स्थान की गणना के लिए सरलीकृत एल्गोरिदम?

Question

मुझे आश्चर्य हुआ कि क्या सर्कुलर बफर में शेष स्थान की गणना करने के लिए एक सरल (एकल) तरीका है?

int remaining = (end > start) 
       ? end-start 
       : bufferSize - start + end; 

Answer 1

आप नीचे अपने CPU के पाइप लाइन को धीमा खराब भविष्यवाणी की सशर्त बारे में चिंतित हैं, तो आप इस इस्तेमाल कर सकते हैं:

int remaining = (end - start) + (-((int) (end <= start)) & bufferSize); 

लेकिन उस समय से पहले अनुकूलन होने की संभावना है (जब तक आप वास्तव में एक हॉटस्पॉट के रूप में इस की पहचान की है) । अपनी वर्तमान तकनीक के साथ चिपकाएं, जो बहुत अधिक पठनीय है।

Answer 2

खोना सशर्त:

int remaining = (end + bufferSize - start - 1) % bufferSize + 1 

संपादित करें: -1 और +1 मामला है जब end == start के लिए कर रहे हैं। उस स्थिति में, यह विधि मान लेगी कि बफर खाली है। अपने बफर के विशिष्ट कार्यान्वयन के आधार पर, आपको ऑफ-बाय-1 स्थिति से बचने के लिए इन्हें समायोजित करने की आवश्यकता हो सकती है।

Answer 3

सी ++ स्टैंडर्ड, खंड 5.6, अनुच्छेद 4 के अनुसार:

द्विआधारी/ऑपरेटर भागफल पैदावार, और बाइनरी% ऑपरेटर दूसरे से पहली अभिव्यक्ति के विभाजन से शेष अर्जित करता है। यदि दूसरा ऑपरेंड/या% शून्य है तो व्यवहार अपरिभाषित है; अन्यथा (ए/बी) * बी + एक% बी बराबर है। यदि दोनों ऑपरेशंस गैर-ऋणात्मक हैं तो शेष अनावश्यक है; यदि नहीं, शेष का संकेत कार्यान्वयन-परिभाषित है।

एक फुटनोट से पता चलता है कि शून्य की ओर भाग्य को गोल करना पसंद किया जाता है, जो शेष नकारात्मक छोड़ देता है।

इसलिए, (end - start) % bufferSize दृष्टिकोण विश्वसनीय रूप से काम नहीं करते हैं। सी ++ में मॉड्यूलर अंकगणित नहीं है (बिना हस्ताक्षर किए गए अभिन्न प्रकारों द्वारा प्रदान की गई भावना को छोड़कर)।

j_random_hacker द्वारा अनुशंसित दृष्टिकोण अलग है, और अच्छा लगता है, लेकिन मुझे नहीं पता कि यह सादगी या गति में कोई वास्तविक सुधार है। एक इंटीरियर के लिए एक बूलियन का रूपांतरण सरल है, लेकिन मानसिक पार्सिंग की आवश्यकता है, और यह कि कंपाइलर और मशीन के आधार पर फिडलिंग अधिक महंगा हो सकता है?

मुझे लगता है कि आपको वहां सबसे सरल और सर्वोत्तम संस्करण मिला है, और मैं इसे नहीं बदलूंगा।

Answer 4

हममम ....

int remaining = (end - start + bufferSize) % bufferSize; 

13 टोकन, मैं जीत सकता हूं?

Answer 5

यदि आपका गोलाकार बफर आकार दो की शक्ति है, तो आप start और end सर्कुलर बफर के संग्रहण में सूचकांक के बजाय वर्चुअल स्ट्रीम में स्थिति का प्रतिनिधित्व करके भी बेहतर कर सकते हैं। यह मानते हुए कि start और end अहस्ताक्षरित हैं, ऊपर हो जाता है:

int remaining= bufferSize - (end - start); 

बफर से बाहर वास्तव में हो रही तत्वों एक छोटे से अधिक जटिल है, लेकिन भूमि के ऊपर 2 आकार परिपत्र बफर की एक शक्ति के साथ काफी आम तौर पर छोटा है (बस मास्किंग bufferSize - 1 के साथ) अपने परिपत्र बफर के सभी अन्य तर्क को अधिक सरल और क्लीनर बनाने के लिए।इसके अलावा, आप सभी तत्वों का उपयोग करते हैं क्योंकि अब आप end==start के बारे में चिंता नहीं करते हैं!

Answer 6

पुराना धागा मुझे पता है लेकिन सोचा कि यह सहायक हो सकता है।

सुनिश्चित नहीं हैं कि इस कितनी तेजी से सी ++ में लेकिन rtl में लागू करता है हम ऐसा करता है, तो आकार n है^2

remaining = (end[n]^start[n]) 
      ? start[n-1:0] - end[n-1:0] 
      : end[n-1:0] - start[n-1:0]; 

या

remaining = if (end[n]^start[n]) { 
       start[n-1:0] - end[n-1:0] 
      } else { 
       end[n-1:0] - start[n-1:0] 
      };