heapsorting djangoオブジェクトを最適化/単純化する方法は？ （モジュールとデータベースのソートは使用できません）

Question

私はジャンゴのインターンシップのテストとして得た課題を頼む必要があります。私はウサギとそのニンジンを使って架空のAPIを作っていた。各ウサギにはニンジンがあると考えられていましたが、他の種類の野菜を簡単に追加できるように設計しなければなりませんでした。私は各野菜の整数フィールドを拒否し、代わりに野菜のタイプと価値を持つ野菜オブジェクトに行きました。

課題は、ニンジンで分類されたウサギを降順で列挙する問題も含まれます。彼らは私がヒープソートを実装することを望みました。データベースのソートは許可されておらず、外部ライブラリもありませんでした。私はそれには問題はありませんが、30秒以下、理想的には5秒で20,000匹のウサギを選別するという、彼らが考えていた時間的制約に問題があります。そして、すでに200のウサギで5秒かかる（ちょうどソートしてjsonにシリアライズする）。

私は「ニンジン」野菜を入れたウサギだけを持つクエリーセットを作っています。それから私はそれを通常のリストに強制し、それに対してheapsort関数を実行します。

もっと速くするにはどうすればいいですか？それも可能ですか？誰かが少しでも助けてくれたら、とても幸せになれます。前もって感謝します！

マイモデル：

class Bunny(models.Model): 
    """Bunny model for bunny usage""" 
    def __str__(self): 
     return self.name + " " + str(list(self.vegetables.all())) 

    name = models.CharField("Name", max_length=50) 
    userAccount = models.ForeignKey(User, on_delete=models.CASCADE) 

    def getVegetable(self, vegetableType): 
     for vegetable in self.vegetables.all(): 
      if vegetable.vegetableType == vegetableType: 
       return vegetable 
     return False 


class Vegetable(models.Model): 
    """Vegetable model for storing vegetable counts""" 
    def __str__(self): 
     return self.vegetableType + ":" + str(self.value) 

    vegetableType = models.CharField(max_length=30, choices=vegetableChoices) 
    value = models.PositiveIntegerField(default=0, validators=[MinValueValidator(0)]) 
    bunny = models.ForeignKey(Bunny, related_name="vegetables", on_delete=models.CASCADE) 

マイヒープソート機能：

def heapsort(bunnies, vegetableType): 
    """Heapsort function for bunnies, works in place, descending""" 

    for start in range((len(bunnies) - 2) // 2, -1, -1): 
     siftdown(bunnies, start, len(bunnies) - 1, vegetableType) 

    for end in range(len(bunnies) - 1, 0, -1): 
     bunnies[end], bunnies[0] = bunnies[0], bunnies[end] 
     siftdown(bunnies, 0, end - 1, vegetableType) 
    return bunnies 


def siftdown(bunnies, start, end, vegetableType): 
    """helper function for heapsort""" 
    root = start 
    while True: 
     child = root * 2 + 1 
     if child > end: 
      break 
     if child + 1 <= end and bunnies[child].vegetables.get(vegetableType=vegetableType).value > bunnies[ 
        child + 1].vegetables.get(vegetableType=vegetableType).value: 
      child += 1 
     if bunnies[root].vegetables.get(vegetableType=vegetableType).value > bunnies[child].vegetables.get(
       vegetableType=vegetableType).value: 
      bunnies[root], bunnies[child] = bunnies[child], bunnies[root] 
      root = child 
     else: 
      break 

そしてまた、性能試験、彼らは私がより良い方法を知っていません（を求めただけでウサギを作成するのに長い時間がかかります。 ）

def test_20000_rabbits_performance(self): 
    print("Creating bunnies") 
    register20000Bunnies() 

    print("Created bunnies") 
    timestart = time() 

    url = reverse("api:list", args=["carrots"]) 

    response = self.client.get(url) 
    timeMeasured = time() - timestart 
    print("Sorted. Took: " + str(timeMeasured)) 

    self.assertEqual(response.status_code, status.HTTP_200_OK) 

マイビュー：

@api_view(["GET"]) 
def bunnyList(request, vegetableType): 
""" Displays heap-sorted list of bunnies, in decreasing order. 
    Takes word after list ("/list/xxx") as argument to determine 
    which vegetable list to display""" 
    if vegetableType in vegetablesChoices: 
     bunnies = 
    Bunny.objects.filter(vegetables__vegetableType=vegetableType) 
     bunnies = list(bunnies) # force into normal list 

     if len(bunnies) == 0: 
      return Response({"No bunnies": "there is %d bunnies with this vegetable" % len(bunnies)}, 
         status=status.HTTP_204_NO_CONTENT) 

     heapsort(bunnies, vegetableType) 
     serialized = BunnySerializerPartial(bunnies, many=True) 
     return Response(serialized.data, status=status.HTTP_200_OK) 
    else: 
     raise serializers.ValidationError("No such vegetable. Available are: " + ", ".join(vegetablesChoices)) 

編集：ちょうど今チェックされていますが、現在はソートに1202秒かかります...私のマシンは2コア1.86GHzですが、まだです。

EDIT2、新しいコード：

@api_view(["GET"]) 
def bunnyList(request, vegetableType): 
""" Displays heap-sorted list of bunnies, in decreasing order. 
    Takes word after list ("/list/xxx") as argument to determine 
    which vegetable list to display""" 
if vegetableType in vegetablesChoices: 
    vegetables = Vegetable.objects.filter(vegetableType=vegetableType).select_related('bunny') 
    vegetables = list(vegetables) 

    if len(vegetables) == 0: 
     return Response({"No bunnies": "there is 0 bunnies with this vegetable"}, 
         status=status.HTTP_204_NO_CONTENT) 

    heapsort(vegetables) 

    bunnies = [vegetable.bunny for vegetable in vegetables] 
    serialized = BunnySerializerPartial(bunnies, many=True) 
    return Response(serialized.data, status=status.HTTP_200_OK) 
else: 
    raise serializers.ValidationError("No such vegetable. Available are: " + ", ".join(vegetablesChoices)) 

更新ヒープソート：

def heapsort(vegetables): 
"""Heapsort function for vegetables, works in place, descending""" 

for start in range((len(vegetables) - 2) // 2, -1, -1): 
    siftdown(vegetables, start, len(vegetables) - 1) 

for end in range(len(vegetables) - 1, 0, -1): 
    vegetables[end], vegetables[0] = vegetables[0], vegetables[end] 
    siftdown(vegetables, 0, end - 1) 
return vegetables 


def siftdown(vegetables, start, end): 
"""helper function for heapsort""" 
root = start 
while True: 
    child = root * 2 + 1 
    if child > end: 
     break 
    if child + 1 <= end and vegetables[child].value > vegetables[child+1].value: 
     child += 1 
    if vegetables[root].value > vegetables[child].value: 
     vegetables[root], vegetables[child] = vegetables[child], vegetables[root] 
     root = child 
    else: 
     break 

マイシリアライザ：

class BunnySerializerPartial(serializers.ModelSerializer): 
"""Used in list view, mirrors BunnySerializerFull but without account details""" 
    vegetables = VegetableSerializer(many=True) 

    class Meta: 
     model = Bunny 
     fields = ("name", "vegetables") 


class VegetableSerializer(serializers.ModelSerializer): 
"""Used for displaying vegetables, for example in list view""" 
    class Meta: 
     model = Vegetable 
     fields = ("vegetableType", "value") 

し、ツールバーからクエリ：

SELECT ••• FROM "zajaczkowskiBoardApi_vegetable" INNER JOIN "zajaczkowskiBoardApi_bunny" ON ("zajaczkowskiBoardApi_vegetable"."bunny_id" = "zajaczkowskiBoardApi_bunny"."id") WHERE "zajaczkowskiBoardApi_vegetable"."vegetableType" = '''carrots''' 


SELECT ••• FROM "zajaczkowskiBoardApi_vegetable" WHERE "zajaczkowskiBoardApi_vegetable"."bunny_id" = '141' 

第2の複製20000回

Answer 1

これは古典的なN + 1クエリの問題です。単一のクエリを実行してすべてのバニーを取得しますが、各バニーについてはbunnies[child].vegetables.get(vegetableType=vegetableType)を実行します。追加のクエリが実行され、バニーごとに追加のデータベースラウンドトリップが実行されます。したがって、N個のウサギに1つのクエリを実行し、さらにN個のクエリを実行してすべての野菜（したがってN + 1）を取得します。

データベースラウンドトリップは、Web開発者が利用できる最も高価なリソースの1つです。比較はナノ秒単位で行われますが、データベースのラウンドトリップはミリ秒単位で行われます。 〜20Kのクエリを実行すると、すぐに数分かかることになります。

ニンジンを得るにはprefetch_related('vegetables')を使用し、bunny.getVegetable('carrot')を使用するのが簡単な解決策です。 prefetch_related()は、すべての野菜をのすべてのバニーに取得するために1つのクエリを実行し、それらをキャッシュするので、self.vegetables.all()をgetVegetables()で繰り返すと、追加のクエリは実行されません。

---

もっと良い解決策があります。この場合、各バニーは、vegetableTypeという1つのVegetableオブジェクトを持つ必要があります。これをデータベースレベルで実施すると、誰かがというタイプの2番目のVegetableをバニーに追加することを決定したときに、ソートアルゴリズムのエラーを心配する必要はありません。代わりに、データベースは最初にその作業をやめます。

class Vegetable(models.Model): 
    ... 
    class Meta: 
     unique_together = [ 
      ('vegetableType', 'bunny'), 
     ] 

その後、むしろすべてのウサギをフェッチし、関連するすべての野菜をプリフェッチするよりも、あなたがタイプ「にんじん」のすべての野菜をフェッチすることができますし、join関連バニー：これを行うには、unique_together制約を必要としています。今、あなたは、単一のクエリがあります：vegetableTypeとbunnyの組み合わせがユニークであるので

carrots = Vegetable.objects.filter(vegetableType='carrot').select_related('bunny') 

を、あなたはどの重複バニーを取得することはありません、あなたはまだいくつかのニンジンを持っているすべてのウサギを取得します。

もちろん、ウサギではなく野菜を扱うようにアルゴリズムを調整する必要があります。