अप्रत्याशित कार्यों का परीक्षण - परीक्षण, संभावना, खिलना-फ़िल्टर

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

require "zlib"

class BloomFilter
def initialize(size=100, hash_count=3)
raise(ArgumentError, "negative or zero buffer size") if size <= 0
raise(ArgumentError, "negative or zero hash count") if hash_count <= 0

@size = size
@hash_count = hash_count
@buffer = Array.new(size, false)
end

def insert(element)
hash(element).each { |i| @buffer[i] = true}
end

def maybe_include?(element)
hash(element).map { |i| @buffer[i] }.inject(:&)
end

private :hash
def hash(element)
hashes = []

1.upto(@hash_count) do |i|
hashes << Zlib.crc32(element, i)
end

hashes.map { |h| h % @size }
end
end

ब्लूम फ़िल्टर वाली समस्याओं में से एक यह है किइसमें फ़िल्टरों में कभी डाले गए तत्वों को शामिल करने के लिए गलत रूप से वापस लौटने से झूठी सकारात्मक वापसी की संभावना है।

कभी-कभी फिल्टर ऐसे तरीके से व्यवहार करता है जो आसानी से परीक्षण योग्य होता है:

b = BloomFilter.new(50, 5)

b.insert("hello")
puts b.maybe_include?("hello") # => true
puts b.maybe_include?("goodbye") # => false

हालांकि यह कभी-कभी प्रवृत्ति को कम करता है और एक अप्रत्याशित तरीके से व्यवहार करता है। (मैंने जल्दी ही एक संघर्ष खोजने के लिए बफर के आकार को कम कर दिया है।)

b = BloomFilter.new(5, 4)

b.insert("testing")
puts b.maybe_include?("testing") # => true
puts b.maybe_include?("not present") # => false
puts b.maybe_include?("false positive") # => true (oops)

तो अचानक हमारे पास स्ट्रिंग "झूठी सकारात्मक" है जो एक ... झूठी सकारात्मक है। मेरा सवाल यह है कि हम इसका परीक्षण कैसे कर सकते हैं?

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

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

क्या मैं ऊपर परीक्षण करने के दो तरीकों की प्रभावशीलता के बारे में निराशावादी हूं या क्या मुझे ब्लूम फ़िल्टर जैसी कक्षाओं का परीक्षण करने का कोई तरीका नहीं है, जो आउटपुट अप्रत्याशित है?

उत्तर:

जवाब के लिए 2 № 1

आप सही हैं कि मूल्यों का चयन करना अभी हुआ काम करने के लिए एक बुरा विचार है। हालांकि, आपका दूसरा विचार इतना बुरा नहीं है।

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

---

जवाब के लिए 0 № 2

परीक्षण आपकी अपेक्षाओं की पुष्टि करने के बारे में है। यदि आप अपने लिए कारण नहीं बना सकते कि ब्लूम फ़िल्टर क्या लौटाएगा (नाजुकता पर विचार करते हुए, जैसा कि आपने बताया है), आप उम्मीद नहीं कर सकते हैं। (मैं कसम खाता हूँ कि मैं एक पन बनाने की कोशिश नहीं कर रहा था: पी)

मेरी पहली आंत महसूस झूठी पुष्टि करने के लिए होगीसभी रोचक हैशिंग एल्गोरिदम पर एन जेनरेट किए गए इनपुट पर सकारात्मक प्रतिशत। यह आपको उतना ही सुरक्षा देता है जितना आप इन परीक्षणों को मैन्युअल रूप से कर सकते थे।

इसे प्राप्त करने के लिए, मैं आपके लिए पर्याप्त परीक्षण करने के लिए पर्याप्त परीक्षण कोड रखने की अनुशंसा करता हूं:

<चेतावनी> असत्यापित कोड </ चेतावनी>

class BloomFilterTestCase << TestCase
def bloom_incidence(alg, pop, false_positives)
define_method("test_bloom_incidence_${alg}_${pop}_${false_positives}") do
# code code code
end
end

bloom_incidence :naive, 50, 0.05
end

---

उत्तर № 3 के लिए -1

एक ब्लूम फ़िल्टर एक अंतरिक्ष-कुशल संभाव्य डेटा संरचना है जिसका प्रयोग यह जांचने के लिए किया जाता है कि कोई तत्व सेट का सदस्य है या नहीं। झूठी सकारात्मक संभव है, लेकिन झूठी नकारात्मक नहीं हैं।

ब्लूम के विवरण से बसफ़िल्टर करता है, यह स्पष्ट होना चाहिए कि झूठी सकारात्मक जांच के लिए इसका कोई मतलब नहीं है। यह स्वाभाविक रूप से अनिश्चित है कि सकारात्मक परीक्षण का नतीजा क्या है, इसलिए आप इसके लिए परीक्षण नहीं कर सकते हैं जो एक निश्चित परिणाम की अपेक्षा करता है। केवल एक चीज जो आप गारंटी दे सकते हैं और इसलिए परीक्षण कर रहे हैं:

• समारोह एक बुलियन मूल्य देता है
• फ़ंक्शन किसी भी त्रुटि को फेंक नहीं देता है
• कोई झूठी नकारात्मक नहीं हैं

---