क्या किसी को डेटा संरचना के बारे में पता है जो दो परिचालनों को कुशलता से समर्थन देता है?यादृच्छिक तत्वों को चुनने के लिए डेटा संरचना?
- डेटा संरचना में कोई मान डालें।
- डेक्यू और समान रूप से यादृच्छिक संभावना के साथ डेटा संरचना से एक प्रविष्टि वापस करें।
यह कैनोनिकल "पत्थर के थैले" की तरह है जो हमेशा प्रारंभिक संभावना वर्गों में आता है। आप बैग में मनमाने ढंग से पत्थर डाल सकते हैं, और फिर यादृच्छिक रूप से पत्थर को कुशलतापूर्वक हटा सकते हैं।
मेरे पास सबसे अच्छा समाधान निम्नानुसार है - तत्वों को संग्रहीत करने के लिए एक स्व-संतुलन बाइनरी खोज पेड़ (एवीएल, एए, लाल/काला, आदि) का उपयोग करें। यह ओ (एलजी एन) सम्मिलन समय देता है। एक यादृच्छिक तत्व को हटाने के लिए, एक यादृच्छिक अनुक्रमणिका I चुनें, फिर पेड़ से ith तत्व का पता लगाएं और हटा दें। यदि आपने संरचना को उचित रूप से बढ़ाया है, तो इसे ओ (एलजी एन) समय में भी चलाने के लिए बनाया जा सकता है।
यह रनटाइम निश्चित रूप से बुरा नहीं है, लेकिन अगर मैं बेहतर करना संभव है तो शायद उत्सुक हूं - शायद ओ (1) सम्मिलन के लिए और ओ (एलजी एन) डेक्यू के लिए? या शायद में चलने वाली कुछ चीज ओ (1) हैश फ़ंक्शंस का उपयोग करके डालें और हटाएं? या शायद एक मजबूत amortized बाध्य?
क्या किसी के पास यह असंवेदनशील रूप से तेज़ बनाने के बारे में कोई विचार है?
जिज्ञासा से बाहर: क्या किसी को पता है कि इस डेटा संरचना का नाम है या नहीं? यह स्पष्ट रूप से 'बैग' और/या 'मल्टीसेट' का एक प्रकार है। 'रैंडमबैग', हो सकता है? वास्तव में, ऐसे डेटा संरचनाएं क्या हैं (यानी डेटा संरचनाएं जहां 'पॉप' रिटर्न और एक यादृच्छिक तत्व हटा देता है) * सामान्य * में कहा जाता है? –
मैंने बैग और रैंडमबैग शब्द को यहां इस्तेमाल किया है, लेकिन मुझे लगता है कि रैंडमबैग शायद उचित शब्द है; बैग आमतौर पर मल्टीसेट के लिए समानार्थी है। – templatetypedef