Appengine データストアで N 個のランダムレコードをクエリする

https://stackoverflow.com/questions/1105004

12-09-2019
|

質問

特定の種類の N 個のランダムレコードを返す GQL クエリを作成しようとしています。現在の実装は機能しますが、データストアへの N 回の呼び出しが必要です。可能であれば、データストアへの呼び出しを 1 回にしたいと考えています。

現在、データストアに入れるすべての種類に乱数を割り当てています。ランダムなレコードをクエリするときは、別の乱数を生成し、レコード > rand ORDER BY asc LIMIT 1 をクエリします。

これは機能しますが、返されるレコードは 1 つだけなので、N 個のクエリを実行する必要があります。このクエリを作成する方法について何かアイデアはありますか?ありがとう。

解決

「ボンネットの下に」単一の検索クエリの呼び出しは、いくつかのインデックスからの連続した行のセットを返すことができます。これは、任意の使用を含め、なぜ一部のGQLクエリ、ある！=、複数のデータストアの呼び出しに展開されます。

N独立一様ランダム選択は、（一般に）任意のインデックスに連続していない。

QEDます。

あなたはおそらく、エンティティを保存するためにmemcacheを使用し、それらのNをつかむのコストを削減することができます。それとも、1つのクエリで（例えば）100のランダムに選択されたブロックを選択し、インデックスに近い一緒にいる「ランダム」の選択を気にしない場合は、それらの中からランダムにNを選びます。すでに無作為化だフィールドを持っているので、N個のアイテムが関連していることを部外者には直ちに明らかではありません。少なくとも、彼らは多くのサンプルを見て、彼らは無作為化インデックスに間隔を100以上だからアイテムAとZは、同じグループに表示されないことに気付かないまで。そして、性能が許すならば、あなたは時々あなたのエンティティを再ランダム化することができます。

他のヒント

どのようなトレードオフを探していますか?これらのエンティティの挿入時に多少のパフォーマンスの低下を許容できる場合は、N 個のエンティティを非常に迅速に取得するソリューションを作成できます。

行う必要があるのは次のとおりです。

エンティティを挿入するときに、キーを指定します。1 から始まり、そこから上の順にエンティティにキーを与える必要があります。(アプリエンジンには autoincrement() がないため、これにはある程度の努力が必要です。そのため、他のエンティティで最後に使用した ID を追跡する必要があります。これを IdGenerator と呼びます)

N 個のランダムなエンティティが必要な場合は、1 から最後に生成した ID までの N 個の乱数を生成します (IdGenerator はこれを認識します)。次に、N キーを使用してキーによるバッチ取得を実行できます。これには、データストアへのアクセスが 1 回だけ必要であり、私の知る限り、キーの取得は一般的にクエリよりも高速であるため、クエリよりも高速です。

この方法では、いくつかの面倒な詳細に対処する必要があります。

これらのアイテムをその場で (1 秒に数回以上) 大量に挿入すると、IdGenerator がボトルネックになる可能性があり、そのためには、ある種のシャード化された IdGenerator 実装が必要になります。これらすべてのデータが事前にロードされている場合、または大容量ではない場合は、簡単に実行できます。
削除したか、どこかで put() が失敗したために、一部の ID には実際にはエンティティが関連付けられていないことがわかる場合があります。これが起こった場合は、別のランダムなエンティティを取得する必要があります。(さらに工夫して、この可能性を減らしたい場合は、この ID を IdGenerator で利用できるようにして、「穴を埋める」ために再利用できるようにすることができます)

したがって、問題は、これらの N 個の項目がどれくらいの速さで必要になるか、その追加と削除の頻度はどれくらいか、そして、少し複雑にすることでパフォーマンスが向上する価値があるかどうかということになります。

唯一の方法は、各エンティティの特別なプロパティでランダムな整数値を記憶し、その上に照会することによってであるように見えます。あなただけ自動的に初期化プロパティを追加する場合、これは非常に自動的に行うことができます。

データストアがすでに満たされている場合は、

残念ながら、これは、一度すべてのエンティティの処理が必要になります。

これは奇妙だ、私は知ってます。

私は1つのクエリでNランダムな行を取得するには、そのような方法はありません、スティーブからの回答に同意します。

しかし、単一のエンティティを検索する方法であっても、通常、返される結果のprbabilityが均等に分散されるように働きません。特定のエンティティを返す確率は、それがランダム数と次に高い乱数を割り当てられているのギャップに依存します。例えば。乱数1,2、及び10は、割り当てられていない（と数字3-9のどれ）されている場合、アルゴリズムは、8倍より頻繁に「1」より「2」が返されます。

私はもう少しexpensiceの方法でこれを修正しました。誰かが興味を持っている場合、私は共有して幸せです。

私も同じ問題を抱えていました。すでにシャードカウンターから totalcount を取得していたため、データストア内の既存のエントリに ID を割り当てないことに決め、これを実行しました。

これにより、「totalcount」エントリから「count」エントリが選択され、並べ替えられます。鍵.

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

私にとって、これはやや複雑であり、off-by-one または off-by-x エラーがないことをまだ確信していないことに注意してください。

また、count が totalcount に近い場合、コストが非常に高くなる可能性があることに注意してください。また、数百万行の場合、Appengine の時間境界内では実行できない可能性があることに注意してください。

私が正しく理解していれば、

、あなたはNのランダムなインスタンスを取得する必要があります。

それは簡単です。ただ、キーのみでクエリを実行します。そして、キーのリスト結果にのrandom.choice のN回行います。そして、キーにフェッチすることで結果を得ることができます。

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.

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow

Appengine データストアで N 個のランダム レコードをクエリする

Appengine データストアで N 個のランダムレコードをクエリする