googles HashCode 2017 上展示的缓存分配练习

Question

我目前正在尝试找到一个有效的解决方案来解决本文 Hash Code 2017 - Streaming Videos 中所述的问题。

TLDR; To minimize latency of youtube videos, cache serves with limited capacity are used. However not every cache is connected to every endpoint and not every entpoint requests the same videos. The goal is to minimize overall latency of the whole network.

我的方法是简单地遍历每个端点和每个请求块，并找到每个视频大小具有最大延迟减少的最佳缓存（我会就叫它 请求密度).

当最佳缓存已经达到其容量时，我尝试将其存储以换取具有较少请求密度的视频，或者如果没有其他可能性，则使用不同的缓存（注意数据中心在我的模型中也是缓存）.

def distribute_video_requests(endpoint, excluding_caches=set()):
    caches = endpoint.cache_connections - excluding_caches

    for vr in endpoint.video_requests:
        optimal_cache = find_optimum(caches, vr)

        exchange = try_put(optimal_cache, vr)

        if exchange["conflicting"]:
            excluding_caches.add(optimal_cache)

            for elm in exchange["affected"]:
                distribute_video_requests(elm["from"], excluding_caches)


for ep in endpoints:
    distribute_video_requests(ep)

您可以将其形象化为 Brazil nut effect，其中视频请求是按堆栈排序的具有不同密度的片段。

我解释所有这些的原因是因为我无法真正判断我的解决方案是否合适，如果不是：有什么更好的方法？

Answer 1

如果有人给你一个建议的解决方案，你可以做的一件事是选择其中一个缓存服务器，清空它，然后尝试找出最好的方法来填充它，至少得到一个解决方案与建议的一样好。

我认为这是背包问题，所以要找到一个有效的精确解来解决这个问题或原始问题并不容易。

背包问题有不错的近似值，所以我认为可能值得对其进行编程并将其扔到您的方法的解决方案中。如果它不能对原始解决方案进行太多改进，那么恭喜！如果可以，你还有另一种解决方法——保持运行背包问题调整每个缓存服务器的内容，直到找不到更多的改进。

Answer 2

我实际上已经使用基本的 OOP、基于流的数据读写和基本循环解决了这个问题。

我的解决方案实际上可以在以下位置找到：https://github.com/TheBlackPlague/YouTubeCache .

解决方案在 PHP 中编码只是因为我想要一种解释语言而不是编译语言来快速完成此操作。然而，这可以很容易地扩展到任何语言以加快执行时间。

googles HashCode 2017 上展示的缓存分配练习

Cache distribution exercise as presented at googles HashCode 2017

sorting

algorithm

optimization

combinatorics