python - 如何优化/简化堆排序 Django 对象？ (不能使用模块和数据库排序)

Question

我必须寻求一些帮助来完成我作为 django 实习测试的作业。我不得不用兔子和它们的胡萝卜制作和想象 api。每只兔子都应该有一些胡萝卜，但 api 的设计必须允许轻松添加其他种类的蔬菜。我拒绝了每种蔬菜的整数字段，而是使用类型和值为蔬菜的蔬菜对象。

问题是，作业还包括列出按胡萝卜排序的兔子，降序。他们要我实现堆排序，不允许数据库排序，也不允许外部库。虽然我对此没有问题，但我在他们想到的时间限制方面遇到了麻烦 - 在 30 秒内对 20 000 只兔子进行分类，最好是 5 秒。 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'

第二个复制了 20 000 次

Answer 1

这是经典的 N+1 查询问题。您执行单个查询来获取所有兔子，但随后您继续为每个兔子执行 bunnies[child].vegetables.get(vegetableType=vegetableType)，这将执行一个额外的查询，因此每个兔子的额外数据库往返。因此，您对 N 只兔子执行 1 次查询，再加上大约 N 次查询以获取所有蔬菜(因此是 N+1)。

数据库往返是 Web 开发人员可用的最昂贵的资源之一。虽然比较需要纳秒级，但数据库往返需要毫秒级。进行约 20K 次查询，这很快就会加起来花费几分钟。

快速解决方案是使用 prefetch_related('vegetables') 并专门使用 bunny.getVegetable('carrot') 来获取胡萝卜。 prefetch_related() 将执行单个查询以获取所有 兔子的所有蔬菜并缓存它们，因此迭代 self.vegetables.all()在 getVegetables() 中不会执行任何额外的查询。

---

不过，还有更好的解决方案。在这种情况下，似乎每只兔子最多应该有 1 个特定 vegetableType 的 Vegetable 对象。如果您在数据库级别强制执行此操作，则当有人决定添加类型为 'carrot' 的第二个 Vegetable 时，您不必担心排序算法中的错误一只兔子。相反，数据库将首先阻止他们这样做。为此，您需要一个 unique_together 约束:

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

然后，您可以获取类型为“胡萝卜”和join 的所有蔬菜，而不是获取所有兔子和预取所有相关蔬菜。相关的兔子。现在您将只有一个查询:

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

由于 vegetableType 和 bunny 的组合是唯一的，您不会得到任何重复的兔子，而且您仍然会得到所有带有胡萝卜的兔子。

当然，您必须调整算法以处理蔬菜而不是兔子。