कुशल जोड़ने, निकालने और यादृच्छिक.चॉइस

Question

के लिए पाइथन डेटा संरचना मैं एक अंतर्निहित पायथन डेटा संरचना की तलाश में हूं जो add एक नया तत्व, remove एक मौजूदा तत्व, और एक यादृच्छिक तत्व चुन सकता है, सब कुछ बेहतर से बेहतर समय पर।

मुझे उम्मीद थी कि set ऐसा कर सकता है, लेकिन AFAIK, पायथन सेट से यादृच्छिक तत्व चुनने का एकमात्र तरीका random.choice(list(my_set)) है, जो ओ (एन) समय लेता है।

मैं पाइथन में निर्मित एक समाधान को बहुत पसंद करता हूं, क्योंकि मुझे दक्षता और आसान तैनाती की आवश्यकता होती है। दुर्भाग्य से, पाइथन में अंतर्निहित पेड़ डेटा प्रकार प्रतीत नहीं होते हैं।

Answer 1

पायथन में अंतर्निहित डेटा संरचना नहीं है जो आपकी सभी आवश्यकताओं को पूरा करती है।

उसने कहा, यह एक पेड़ को स्वयं लागू करने के लिए काफी छोटा है।

import random 

class ListDict(object): 
    def __init__(self): 
     self.item_to_position = {} 
     self.items = [] 

    def add_item(self, item): 
     if item in self.item_to_position: 
      return 
     self.items.append(item) 
     self.item_to_position[item] = len(self.items)-1 

    def remove_item(self, item): 
     position = self.item_to_position.pop(item) 
     last_item = self.items.pop() 
     if position != len(self.items): 
      self.items[position] = last_item 
      self.item_to_position[last_item] = position 

    def choose_random_item(self): 
     return random.choice(self.items) 

के बाद से ही संचालन सूची पर किया हैं:

---

एक अन्य विकल्प बनाने के लिए क्या प्रभावी ढंग से एक सेट है कि भी अपने आइटम की एक सूची रखता है एक सूची के साथ एक शब्दकोश गठबंधन करने के लिए किया जाएगा .pop() और .append(), उन्हें निरंतर समय से अधिक नहीं लेना चाहिए (कम से कम पायथन कार्यान्वयन में)।