Consultando para N registos aleatórios no armazenamento de dados Appengine

StackOverflow https://stackoverflow.com/questions/1105004

Pergunta

Eu estou tentando escrever uma consulta GQL que os retornos N registros aleatórios de um tipo específico. Minha implementação atual funciona, mas requer N chamadas para o armazenamento de dados. Eu gostaria de torná-lo uma chamada para o armazenamento de dados, se possível.

Eu atualmente atribuir um número aleatório para cada tipo que eu coloquei para o armazenamento de dados. Quando eu consulta para um registro aleatório I gerar outro número aleatório e consulta para registros> rand ORDER BY asc LIMIT 1.

Isso funciona, no entanto, ele só retorna 1 registro assim que eu preciso fazer consultas N. Todas as ideias sobre como fazer esta consulta? Obrigado.

Foi útil?

Solução

"Sob o capô" uma única chamada de consulta de pesquisa só pode retornar um conjunto de linhas consecutivas de algum índice. É por isso que algumas consultas GQL, incluindo qualquer uso de! =, Expandir para várias chamadas do armazenamento de dados.

N independentes selecções aleatórias uniformes não são (em geral) consecutiva em qualquer índice.

QED.

Você provavelmente poderia usar memcache para armazenar as entidades, e reduzir o custo de pegar N deles. Ou se você não se importa as seleções "aleatórios" estar perto juntos no índice, selecione um bloco escolhido aleatoriamente de (digamos) 100 em uma consulta, em seguida, escolher N aleatoriamente entre aqueles. Desde que você tem um campo que já está randomizado, não vai ser imediatamente óbvio para um estranho que os itens N estão relacionados. Pelo menos, não até que olhar para um monte de amostras e aviso que os itens A e Z nunca aparecem no mesmo grupo, porque eles são mais de 100 além do índice randomizado. E se as licenças de desempenho, você pode re-randomise suas entidades ao longo do tempo.

Outras dicas

Que tipo de compensações que você está procurando? Se você está disposto a colocar-se com uma pequena queda de performance sobre a inserção dessas entidades, você pode criar uma solução para obter N deles muito rapidamente.

Aqui está o que você precisa fazer:

Quando você insere suas Entidades, especifique a chave. Você quer dar as chaves para suas entidades em ordem, começando com 1 e vai acima de lá. (Isso vai exigir algum esforço, como app engine não tem autoincrement (), de modo que você precisa para acompanhar o último id você usou em alguma outra entidade, vamos chamá-lo um IdGenerator)

Agora, quando você precisa N entidades aleatórios, gerar n números aleatórios entre 1 e qualquer que seja o último id você gerou foi (sua IdGenerator vai saber isso). Você pode então fazer um get lote pela chave usando as teclas N, que irá necessitar apenas de uma viagem para o armazenamento de dados, e será mais rápido do que uma consulta, bem como, desde chave recebe são geralmente mais rápido do que consultas, AFAIK.

Este método requer lidar com alguns detalhes irritantes:

  1. O seu IdGenerator pode se tornar um gargalo se você está inserindo muitos desses itens na mosca (mais de um segundo alguns), o que exigiria algum tipo de implementação IdGenerator Sharded. Se todos estes dados é pré-carregado, ou não é alto volume, você tem mais fácil.
  2. Você pode achar que alguns Id na verdade não tem uma entidade associada a ele mais, porque você excluiu-lo ou porque um put () falhou em algum lugar. Se isso aconteceu, você teria que pegar outra entidade aleatória. (Se você quiser começar a fantasia e reduzir as chances de isso você poderia fazer este Id disponível para o IdGenerator para reutilização para "preencher os buracos")

Portanto, a questão se resume a quão rápido você precisa desses itens N vs quantas vezes você estará adicionando e excluí-los, e se um pouco de complexidade extra vale a pena que aumento de desempenho.

Parece que o único método é armazenando o valor inteiro aleatório na propriedade especial de cada entidade e consultar sobre isso. Isso pode ser feito com bastante automaticamente se você acabou de adicionar uma propriedade inicializado automaticamente.

Infelizmente isso vai exigir o processamento de todas as entidades uma vez se seu armazenamento de dados já está preenchido.

É estranho, eu sei.

Eu concordo com a resposta de Steve, não existe maneira de recuperar N linhas aleatórias em uma consulta.

No entanto, mesmo o método de recuperação de uma única entidade não costuma funcionar de modo que a prbability dos resultados retornados é distribuído uniformemente. A probabilidade de retornar uma determinada entidade depende da diferença de que é atribuído aleatoriamente número e o número imediatamente superior aleatória. Por exemplo. se números aleatórios 1,2, e 10 foram atribuídos (e nenhum dos números 3-9), o algoritmo vai voltar "2" 8 vezes mais frequentemente do que "1".

Eu reparei isso de uma maneira um pouco mais expensice. Se alguém estiver interessado, eu estou feliz de compartilhar

Eu só tinha o mesmo problema. Eu decidi não IDs atribuir aos meus entradas já existentes no armazenamento de dados e fez isso, como eu já tinha o totalcount de um contador Sharded.

Isso seleciona "contar" entradas de entradas "totalCount", ordenadas por tecla . 

    # 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)

Tenha em atenção que isso para mim é um pouco complexo, e eu ainda não estou conviced que eu não tenho off-by-one ou off-by-x erros.

E cuidado que se a contagem está perto de TotalCount isso pode ser muito caro. E cuidado que sobre milhões de linhas pode não ser possível fazer dentro dos limites de tempo AppEngine.

Se bem entendi, você precisa recuperar N instância aleatória.

É fácil. Basta fazer consulta com apenas chaves. E fazer random.choice N vezes em resultado lista de chaves. Em seguida, obter resultados por buscar em chaves. 

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.
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top