Cercare gli N record casuali su datastore AppEngine

Question

Sto cercando di scrivere una query GQL che restituisce i record N casuali di un tipo specifico. Il mio attuale implementazione funziona, ma richiede N chiama al datastore. Mi piacerebbe farlo 1 chiamata al datastore, se possibile.

Io attualmente assegnare un numero casuale per ogni tipo che ho messo nel datastore. Quando ho query per un record a caso ho generare un altro numero casuale e query per i record> rand ORDER BY asc LIMIT 1.

Questo funziona, però, restituisce solo 1 record di così ho bisogno di fare N query. Tutte le idee su come rendere questo una query? Grazie.

Answer 1

"sotto il cofano" una singola chiamata query di ricerca può restituire solo un insieme di righe consecutive di qualche indice. È per questo che alcune query GQL, incluso qualsiasi utilizzo di! =, Espandere alle chiamate datastore multipli.

selezioni casuali uniformi indipendente N non sono (in generale) consecutiva in alcun indice.

QED.

Si potrebbe forse usare memcache per memorizzare le entità, e ridurre i costi di afferrare N di loro. Oppure, se non ti dispiace le selezioni "casuali" di essere vicino insieme nell'indice, selezionare un blocco scelto casualmente di (diciamo) 100 in una query, quindi scegliere N a caso da quelli. Dal momento che si dispone di un campo che è già randomizzati, non sarà immediatamente evidente a un estraneo che gli elementi N sono correlate. Almeno, non fino a quando guardano un sacco di campioni e notare che gli elementi A e Z non appaiono mai nello stesso gruppo, perché sono più di 100 a parte nell'indice randomizzato. E se i permessi di prestazioni, è possibile ri-randomizzare i vostri soggetti di volta in volta.

Answer 2

Che tipo di compromessi stai cercando? Se siete disposti a mettere in su con un piccolo calo di prestazioni sull'inserimento di queste entità, è possibile creare una soluzione per ottenere N di loro molto rapidamente.

Ecco cosa dovete fare:

Quando si inserisce il tuo Entità, specificare la chiave. Si vuole dare le chiavi per le entità in ordine, iniziando con 1 e andare da lì. (Ciò richiederà un certo sforzo, come motore di applicazione non ha autoincrement () quindi è necessario tenere traccia degli ultimi id è stato utilizzato in qualche altra entità, chiamiamolo un IdGenerator)

Ora, quando è necessario N entità casuali, generare N numeri casuali tra 1 e qualunque sia l'ultimo ID generato era (il vostro IdGenerator saprà questo). È quindi possibile fare un batch ottenere dai chiave utilizzando i tasti N, che richiederanno un solo viaggio al datastore, e sarà più veloce di una query e, dal momento chiave si sono generalmente più veloce di query, per quanto ne so.

Questo metodo non richiede che fare con alcuni dettagli fastidiosi:

1. Il tuo IdGenerator potrebbe diventare un collo di bottiglia, se si sta inserendo un sacco di questi elementi al volo (più di qualche secondo), che richiederebbe un qualche tipo di implementazione IdGenerator sharded. Se tutti questi dati è precaricato, o non è elevato il volume, lo avete facile.
2. Si potrebbe scoprire che alcuni Id in realtà non hanno un'entità ad essa più, perché si è eliminato o perché una put () fallito da qualche parte. Se questo è accaduto che ci si deve afferrare un'altra entità casuale. (Se si voleva ottenere l'immaginazione e ridurre le probabilità di questo si potrebbe fare questo ID a disposizione del IdGenerator di riutilizzare a "riempire i buchi")

Quindi la domanda si riduce a quanto velocemente avete bisogno di questi elementi N vs quante volte vi sarà l'aggiunta e di cancellarli, e se un po 'di complessità in più vale la pena che incremento delle prestazioni.

Answer 3

appare come l'unico metodo è memorizzando il valore intero casuale in particolare proprietà di ogni entità e l'interrogazione su questo. Questo può essere fatto abbastanza automaticamente se si aggiunge solo una proprietà inizializzato automaticamente.

Purtroppo ciò richiederà l'elaborazione di tutte le entità una volta se il datastore è già compilato.

E 'strano, lo so.

Answer 4

Sono d'accordo per la risposta di Steve, non v'è alcun modo per recuperare N righe casuali in una query.

Tuttavia, anche il metodo di recupero di una singola entità di solito non funziona in modo tale che l'prbability dei risultati restituiti è distribuito uniformemente. La probabilità di restituzione una data entità dipende il divario di esso è numero e il successivo numero casuale superiore assegnato in modo casuale. Per esempio. Se i numeri casuali 1,2, e 10 sono stati assegnati (e nessuno dei numeri 3-9), l'algoritmo torneranno "2" 8 volte più spesso di "1".

Ho fissato questo in un modo un po 'più expensice. Se qualcuno è interessato, io sono felice di condividere

Answer 5

Ho appena avuto lo stesso problema. Ho deciso di non assegnare ID ai miei voci già esistenti in archivio dati e ha fatto questo, come ho già avuto la totalCount da un contatore sharded.

Questo seleziona le voci "Count" da voci "totalCount", in ordine di chiave .

    # select $count from the complete set
    numberlist = random.sample(range(0,totalcount),count)
    numberlist.sort()

    pagesize=1000

    #initbuckets
    buckets = [ [] for i in xrange(int(max(numberlist)/pagesize)+1) ]
    for k in numberlist:
        thisb = int(k/pagesize)
        buckets[thisb].append(k-(thisb*pagesize))
    logging.debug("Numbers: %s. Buckets %s",numberlist,buckets)

    #page through results.

    result = []
    baseq =  db.Query(MyEntries,keys_only=True).order("__key__")
    for b,l in enumerate(buckets):
        if len(l) > 0: 
            result += [ wq.fetch(limit=1,offset=e)[0] for e in l ]

        if b < len(buckets)-1: # not the last bucket
            lastkey  = wq.fetch(1,pagesize-1)[0]
            wq = baseq.filter("__key__ >",lastkey)

Attenzione che questo per me è un po 'complessa, e io sono ancora non conviced che io non sono errori di off-by-one o off-by-x.

E attenzione che se il conteggio è vicino a TotalCount questo può essere molto costoso. E attenzione che in milioni di righe potrebbe non essere possibile fare all'interno dei confini di tempo AppEngine.

Answer 6

Se ho capito bene, è necessario recuperare N esempio casuale.

E 'facile. Basta interrogare solo con la chiave. E fare random.choice N volte sul risultato elenco di chiavi. Quindi ottenere i risultati per il recupero sui tasti.

keys = MyModel.all(keys_only=True)

n = 5 # 5 random instance

all_keys = list(keys)
result_keys = []

for _ in range(0,n) 
    key = random.choice(all_keys)
    all_keys.remove(key)
    result_keys.append(key)

# result_keys now contain 5 random keys.