Considera un sistema con un numero finito di utenti e un numero finito di gruppi.
Ad ogni gruppo corrisponde un insieme di utenti. (Diciamo che gli utenti "appartengono direttamente" a un gruppo.)
Gruppi di utenti formano un grafico diretto senza cicli. Se A & rightarrow; B per i gruppi A e B, allora io dico che B è un sottogruppo diretto di A.
Le seguenti operazioni sono definite:
- aggiungi un utente a un gruppo
- rimuovi un utente da un gruppo
- aggiungi un sottogruppo diretto a un gruppo
- rimuovi un sottogruppo diretto da un gruppo
Si noti che il tentativo di creare un ciclo nel grafico diretto dovrebbe generare un'eccezione.
Potrebbero essere creati anche nuovi utenti e gruppi e utenti e gruppi esistenti potrebbero essere cancellati.
Ho bisogno di memorizzare in modo efficiente queste informazioni, in modo che verificare se un utente (direttamente o indirettamente) appartiene a un gruppo (o ai suoi sottogruppi diretti o indiretti) dovrebbe essere un'operazione veloce. Il caching è fatto da un motore di cache come memcached.
Per favore, riferiscimi ad un efficiente algoritmo di caching. Penso di non essere il primo a risolvere questo problema e c'è un algoritmo noto.
Si noti che scriviamo in linguaggio di programmazione Python.