Struttura dati Python per efficiente add, remove e random.choice

Question

Sto cercando una struttura dati Python incorporata che possa add un nuovo elemento, remove un elemento esistente, e scegliere un elemento casuale, tutto in meglio di Puntuale.

Speravo che set potesse farlo, ma AFAIK, l'unico modo per scegliere un elemento casuale da un set Python è random.choice(list(my_set)), che richiede O (n) tempo.

Preferisco di gran lunga una soluzione incorporata in Python, poiché richiede efficienza e facilità di implementazione. Sfortunatamente, Python non sembra avere tipi di dati ad albero incorporati.

Answer 1

Python non ha una struttura dati integrata che soddisfi tutti e 3 i requisiti.

Detto questo, è abbastanza banale implementare un albero da soli.

---

Un'altra opzione sarebbe quella di combinare un dizionario con una lista per creare quello che è effettivamente un set che mantiene anche un elenco delle sue voci:

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) 

Dal momento che le uniche operazioni effettuate sulla lista sono .pop() e .append(), non dovrebbero richiedere più di un tempo costante (nella maggior parte delle implementazioni Python, almeno).