यह टिप्पणी लेख के लेखन से प्रेरित थी। इससे भी सटीक, एक वाक्यांश।

... अरबों डॉलर में वस्तुओं पर मेमोरी या प्रोसेसर चक्र खर्च करना अच्छा नहीं है ...

ऐसा हुआ कि हाल ही में मुझे ऐसा करना पड़ा। और, हालांकि, लेख में मैं जिस मामले पर विचार करूंगा, वह विशेष है - निष्कर्ष और लागू किए गए समाधान किसी के लिए उपयोगी हो सकते हैं।

थोड़ा सा संदर्भ

IFunny एप्लिकेशन ग्राफिक और वीडियो सामग्री की एक बड़ी मात्रा से संबंधित है, और डुप्लिकेट के लिए फ़ज़ी खोज बहुत महत्वपूर्ण कार्यों में से एक है। यह अपने आप में एक बड़ा विषय है जो एक अलग लेख के योग्य है, लेकिन आज मैं इस खोज के संबंध में संख्याओं की बहुत बड़ी सरणियों की गणना करने के लिए कुछ दृष्टिकोणों के बारे में बात करूंगा। बेशक, सभी को "बहुत बड़े सरणियों" की एक अलग समझ है, और हैड्रॉन कोलाइडर के साथ प्रतिस्पर्धा करना मूर्खतापूर्ण होगा, लेकिन फिर भी। :)

यदि एल्गोरिथ्म बहुत संक्षेप में है, तो प्रत्येक छवि के लिए 968 पूर्णांक से इसका डिजिटल हस्ताक्षर (हस्ताक्षर) बनाया जाता है, और तुलना दो हस्ताक्षरों के बीच "दूरी" को खोजने के द्वारा की जाती है। यह देखते हुए कि पिछले दो महीनों में सामग्री की मात्रा अकेले लगभग 10 मिलियन छवियों की है, फिर एक चौकस पाठक आसानी से अपने दिमाग में यह पता लगाएगा - ये बिलकुल "अरबों संस्करणों में तत्व" हैं। कौन परवाह करता है - बिल्ली में आपका स्वागत है।

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

मुझे मानना ​​होगा कि मैं थोड़ा चालाक था। एल्गोरिथम के प्रारंभिक विश्लेषण में, 968 से 420 तक प्रत्येक हस्ताक्षर में मूल्यों की संख्या को कम करना संभव था। यह पहले से ही दो बार अच्छा है, लेकिन परिमाण का क्रम समान रहता है।

यद्यपि, यदि आप इसके बारे में सोचते हैं, तो यह इतना नहीं है कि मैं धोखा दे रहा था, और यह पहला निष्कर्ष होगा: कार्य के साथ आगे बढ़ने से पहले, यह सोचने योग्य है - क्या किसी तरह अग्रिम में इसे सरल करना संभव है?

तुलना एल्गोरिथ्म काफी सरल है: दो हस्ताक्षरों के अंतर के वर्गों के योग की जड़ की गणना, पहले से गणना किए गए मानों के योग से विभाजित की जाती है (यानी, प्रत्येक पुनरावृत्ति में योग अभी भी होगा और सभी पर एक स्थिर होने के लिए बाहर नहीं निकाला जा सकता है) और दहलीज मूल्य के साथ तुलना की जाती है। यह ध्यान देने योग्य है कि हस्ताक्षर तत्व -2 से +2 तक मूल्यों तक सीमित हैं, और, तदनुसार, अंतर का पूर्ण मान 0 से 4 तक के मूल्यों तक सीमित है।


कुछ भी जटिल नहीं है, लेकिन मात्रा तय करती है।

पहला दृष्टिकोण, भोला

//  const val d = 0.3 // 10.000.000 . //      , //        val collection: MutableList<Signature> = mutableListOf() // signature —   420   Byte class Signature(val signature: Array<Byte>, val norma: Double) fun getSimilar(signature: Signature) = collection .filter { calculateDistance(it, signature) < d } fun calculateDistance(first: Signature, second: Signature): Double = Math.sqrt(first.signature.mapIndexed { index, value -> Math.pow((value - second.signature[index]).toDouble(), 2.0) }.sum()) / (first.norma + second.norma) 

आइए गणना करें कि हमारे पास ऑपरेशन की संख्या के साथ यहां क्या है:

10M स्क्वायर रूट्स Math.sqrt
10M परिवर्धन और विभाजन / (first.norma + second.norma)
4.200M घटा और Math.pow((value - second.signature[index]).toDouble(), 2.0)
4.200M परिवर्धन .sum()

हमारे पास क्या विकल्प हैं:

1. इस तरह के संस्करणों के साथ, पूरे Byte खर्च करना (या, भगवान ना करे, किसी ने Int का उपयोग करने का अनुमान लगाया होगा) तीन महत्वपूर्ण बिट्स को स्टोर करने के लिए एक अक्षम्य बेकार है।
2. शायद, गणित की मात्रा कैसे कम करें?
3. लेकिन क्या कुछ प्रारंभिक फ़िल्टरिंग करना संभव है, जो इतना कम्प्यूटेशनल रूप से महंगा नहीं है?

दूसरा तरीका, हम पैक करते हैं

वैसे, अगर कोई सुझाव देता है कि आप इस तरह की पैकेजिंग के साथ गणना को कैसे सरल बना सकते हैं, तो आपको कर्म में एक बड़ा धन्यवाद और प्लस मिलेगा। हालांकि एक, लेकिन मेरे पूरे दिल से :)

एक Long 64 बिट्स है, जो हमारे मामले में, हमें इसमें 21 मानों को संग्रहीत करने की अनुमति देगा (और 1 बिट अप्रचलित रहेगा)।

 //   20   Long class Signature(val signature: Array<Long>, val norma: Double) fun calculateDistance(first: Signature, second: Signature): Double = Math.sqrt(first.signature.mapIndexed { index, value -> calculatePartial(value, second.signature[index]) }.sum()) / (first.norma + second.norma) fun calculatePartial(first: Long, second: Long): Double { var sum = 0L (0..60 step 3).onEach { val current = (first.ushr(it) and 0x7) - (second.ushr(it) and 0x7) sum += current * current } return sum.toDouble() } 

यह मेमोरी से बेहतर है ( 4.200M बनाम 1.600M बाइट्स, यदि मोटे तौर पर), लेकिन गणना के बारे में क्या?

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

तीसरा दृष्टिकोण, उप-उप के साथ फिर से पैक

सुबह मैं इसे सूंघ सकता हूं, यहां आप बिट जादू का उपयोग कर सकते हैं!

मानों को तीन नहीं, बल्कि चार बिट्स में स्टोर करें। इस तरह से:

हाँ, हम पिछले संस्करण की तुलना में पैकिंग घनत्व खो देंगे, लेकिन हमें एक ही समय में XOR के ओम के साथ 16 (काफी नहीं) अंतर के साथ Long प्राप्त करने का अवसर मिलेगा। इसके अलावा, प्रत्येक अंतिम कुतरना में बिट्स के वितरण के लिए केवल 11 विकल्प होंगे, जो आपको मतभेदों के वर्गों के पूर्व-गणना मूल्यों का उपयोग करने की अनुमति देगा।

 //   27   Long class Signature(val signature: Array<Long>, val norma: Double) // -1    val precomputed = arrayOf(0, 1, 1, 4, 1, -1, 4, 9, 1, -1, -1, -1, 4, -1, 9, 16) fun calculatePartial(first: Long, second: Long): Double { var sum = 0L val difference = first xor second (0..60 step 4).onEach { sum += precomputed[(difference.ushr(it) and 0xF).toInt()] } return sum.toDouble() } 

मेमोरी से यह 2.160M बनाम 1.600M - अप्रिय हो गया, लेकिन अभी भी शुरुआती 4.200M से बेहतर है।

चलो संचालन की गणना करते हैं:

10M वर्गमूल, परिवर्धन और विभाजन (कहीं नहीं गए)
270M XOR का
4.320 जोड़, बदलाव, तार्किक 4.320 , और सरणी से अर्क।

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

चौथा दृष्टिकोण, बड़ी छलनी

यदि आप गणना सूत्र को थोड़ा बदल देते हैं, तो आप यह असमानता (गणना की गई दूरी से कम, बेहतर) प्राप्त कर सकते हैं:


यानी अब हमें यह पता लगाने की आवश्यकता है कि Long के बिट्स की संख्या के आधार पर असमानता के बाईं ओर के न्यूनतम संभावित मूल्य की गणना हम कैसे करें। फिर बस उन सभी हस्ताक्षरों को त्याग दें जो उसे संतुष्ट नहीं करते हैं।
मुझे याद दिलाएं कि x _i 0 से 4 तक मान ले सकता है (संकेत महत्वपूर्ण नहीं है, मुझे लगता है कि यह स्पष्ट है कि क्यों)। यह देखते हुए कि प्रत्येक शब्द चुकता है, एक सामान्य पैटर्न प्राप्त करना आसान है:


अंतिम सूत्र इस तरह दिखता है (हमें इसकी आवश्यकता नहीं है, लेकिन मैंने इसे लंबे समय के लिए काट लिया है और यह केवल किसी को भूल जाने और नहीं दिखाने के लिए शर्म की बात होगी):


जहां B बिट्स सेट की संख्या है।

वास्तव में, एक केवल 64 बिट्स में, 64 संभावित परिणाम पढ़ें। और वे पहले से पूरी तरह से गणना की जाती हैं और पिछले अनुभाग के साथ सादृश्य द्वारा, एक सरणी में जोड़ा जाता है।

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

 fun getSimilar(signature: Signature) = collection .asSequence() //     !? .filter { estimate(it, signature) } .filter { calculateDistance(it, signature) < d } val estimateValues = arrayOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 58, 61, 64, 69, 74, 79, 84, 89, 94, 99, 104, 109, 114, 119, 124, 129, 134, 139, 144, 151, 158, 165, 172, 179, 186, 193, 200, 207, 214, 221, 228, 235, 242, 249, 256) fun estimate(first: Signature, second: Signature):Boolean{ var bitThreshold = Math.pow(d * (first.norma + second.norma), 2.0).toLong() first.signature.forEachIndexed { index, value -> bitThreshold -= estimateValues[java.lang.Long.bitCount(value xor second.signature[index])] if (bitThreshold <= 0) return false } return true } 

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

पांचवां दृष्टिकोण, अनुक्रम से छुटकारा

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

 fun getSimilar(signature: Signature) = collection .filter { estimate(it, signature) } .filter { calculateDistance(it, signature) < d } 

ऐसा लगता है कि यहां यह खुशी है, लेकिन मैं "इसे सुंदर बनाना चाहता था।" यहाँ हम वादा किया हुआ शिक्षाप्रद कहानी पर आते हैं।

छठा दृष्टिकोण, हम सबसे अच्छा चाहते थे

हम कोटलिन पर लिखते हैं, और यहाँ कुछ विदेशी java.lang.Long.bitCount ! और हाल ही में, अहस्ताक्षरित प्रकारों को भाषा में लाया गया। हमला!

जल्दी से नहीं कहा। सभी ULong को ULong द्वारा बदल दिया जाता है, ULong जावा स्रोत से ULong और ULong लिए एक विस्तार समारोह के रूप में फिर से लिखा जाता है।

 fun ULong.bitCount(): Int { var i = this i = i - (i.shr(1) and 0x5555555555555555uL) i = (i and 0x3333333333333333uL) + (i.shr(2) and 0x3333333333333333uL) i = i + i.shr(4) and 0x0f0f0f0f0f0f0f0fuL i = i + i.shr(8) i = i + i.shr(16) i = i + i.shr(32) return i.toInt() and 0x7f } 

हम शुरू करते हैं और ... कुछ गलत है। कोड ने धीमी गति से काम करना शुरू कर दिया। हम प्रोफाइलर शुरू करते हैं और कुछ अजीब देखते हैं (लेख की bitCount() देखें): bitCount() को एक मिलियन कॉल से थोड़ा कम bitCount() लगभग 16 मिलियन कॉल Kotlin.ULong.constructor-impl । वॉट?

पहेली को बस समझाया गया है - बस क्लास कोड ULong

 public inline class ULong @PublishedApi internal constructor(@PublishedApi internal val data: Long) : Comparable<ULong> { @kotlin.internal.InlineOnly public inline operator fun plus(other: ULong): ULong = ULong(this.data.plus(other.data)) @kotlin.internal.InlineOnly public inline operator fun minus(other: ULong): ULong = ULong(this.data.minus(other.data)) @kotlin.internal.InlineOnly public inline infix fun shl(bitCount: Int): ULong = ULong(data shl bitCount) @kotlin.internal.InlineOnly public inline operator fun inc(): ULong = ULong(data.inc())  .. } 

नहीं, मैं सब कुछ समझता हूं, ULong अब experimental है, लेकिन यह कैसे है?
सामान्य तौर पर, हम दृष्टिकोण को विफल मानते हैं, जो एक दया है।

ठीक है, लेकिन फिर भी, शायद कुछ और सुधार किया जा सकता है?

वास्तव में, आप कर सकते हैं। मूल java.lang.Long.bitCount कोड सबसे इष्टतम नहीं है। यह सामान्य मामले में एक अच्छा परिणाम देता है, लेकिन अगर हम पहले से जानते हैं कि हमारा आवेदन किस प्रोसेसर पर काम करेगा, तो हम अधिक इष्टतम तरीका चुन सकते हैं - यहाँ हैबे पर इसके बारे में एक बहुत अच्छा लेख है। मैं पूरी तरह से सिंगल बिट्स की गिनती करने की सलाह देता हूं, मैं इसे अत्यधिक सलाह देता हूं।

मैंने "कंबाइंड मेथड" का इस्तेमाल किया

 fun Long.bitCount(): Int { var n = this n -= (n.shr(1)) and 0x5555555555555555L n = ((n.shr(2)) and 0x3333333333333333L) + (n and 0x3333333333333333L) n = ((((n.shr(4)) + n) and 0x0F0F0F0F0F0F0F0FL) * 0x0101010101010101).shr(56) return n.toInt() and 0x7F } 

तोते की गिनती करना

स्थानीय मशीन पर विकास के दौरान सभी मापों को बेतरतीब ढंग से बनाया गया था और स्मृति से पुन: पेश किया जाता है, इसलिए किसी भी सटीकता के बारे में बात करना मुश्किल है, लेकिन आप प्रत्येक दृष्टिकोण के अनुमानित योगदान का अनुमान लगा सकते हैं।

निष्कर्ष

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

आपका ध्यान के लिए धन्यवाद! :)

और हाँ, जारी रखा जाना है।