在采访中有人问我这个问题，我不确定是否给出了正确的答案，所以我需要一些见解。
问题:有大量的用户和项目。每分钟，我会收到一个元组列表(用户，项目)，表示用户u消费了项目i。我需要找到过去一个小时内排名前100的热门商品，即计算有多少用户消费了每种商品并对其进行了排序。这里的窍门是，在过去的一个小时内，如果同一用户多次消费某个商品，则仅考虑一次消费。不允许同一用户重复消费。面试官说，我应该考虑很大，每小时会有数百万的消费。因此，他建议我做一个简化 map 的工作或可以处理每分钟大量数据的工作。
我想到的解决方案是:我说过，我可以维护一个消耗的user-item-timestamp元组的列表(或矩阵，如果您愿意的话)，就像有一个时间窗口在移动一样。就像是:
在每一分钟，当我收到这一分钟的用户项消耗流时，我首先进行map-reduce作业，以使用当前时间戳更新时间窗口矩阵。这个map-reduce作业可以由两个映射器完成(一个映射器用于流，另一个映射器用于时间窗口列表)，而reducer会简单地为每个映射器获取最大值。我所做的伪代码:
mapTimeWindow(line):
user, item, timestamp = line.split(" ")
context.write(key=(user,item), value=timestamp)
mapStream(line):
user, item = line.split(" ")
context.write(key=(user,item), value=now())
reducer(key, list):
context.write(key=(user,item), value=max(list))
接下来，我还通过计算每个用户出现在该列表中的时间来进行 map 归约计算。我的 map 读取更新的时间窗口列表并写入项目和1. reducer 为每个项目计算列表的总和。由于我存储了所有时间戳，因此我验证消耗量是否为过去一个小时。另一个map-reduce伪代码:
mapPopularity(line):
user, item, timestamp = line.split(" ")
if now()-60>timestamp:
return
context.write(key=item, value=1) # no repetition
reducerPopularity(key, list):
context.write(key=item, value=sum(list))
稍后，我们可以做另一个map-reduce来读取第二个作业的结果，并计算出前100个最大的项目。像this这样的事情。
我的问题:我接受的采访是否可以接受此解决方案？它包含三个map-reduce来解决该问题。但是，在我看来，每分钟执行的任务很多。由于需要每分钟更新一次，因此持续时间不能超过此时间。我的意思是，我付出了很多努力，但无论是否正确，面试官都没有给我反馈。我想知道:是否可以使其更快？还是有可能以其他方式处理这个问题？ (也许不是map-reduce)
最佳答案
告诉您解决方案是否可以接受，最终是一种意见。面试官可能会喜欢您的算法，或者您的问题解决过程和思维。最终，只有您的面试官才能说出来。如果您编写的算法以完整且正确的方式实现，则您的解决方案肯定会遵循逻辑并完成工作。
我的解决方案:
正如您所解释的，主要的性能是性能，因为我们拥有大数据，因此，通过将其保持在必要的最小数量，我们将减少空间复杂度，时间复杂度和执行次数。
空间复杂度
我将为每个项目保留一个[user，timestamp]列表(或更多性能收集器，具体取决于您使用的库，但在此将其保留为基本情况。请参阅 dict 末尾的注释)。每个新项目都有其自己的列表。这本质上比整体[user，timestamp，item]更好，因为这会由于额外的字段而导致内存使用情况更糟，并且需要进行额外的映射操作，或者可能只是过滤，因为您必须处理所有存在的关联才能提取这些“每项” ”。更容易地，您可以“通过哈希”或通过代码中的引用来获取该项目的列表。这种模型是极简主义的模型。
时间复杂度
就是说，有清除操作和受欢迎程度提取。由于我们想限制点击量，但是由于具体原因，每次计算当前流行度时，您都必须检查时间戳，因此必须滚动列表，要求复杂度为O(n)。
因此:按照当前时间
由于线性搜索成本是通过过滤支付的，因此如果您要计算未到期的条目而不进行清除，则reduce操作将支付类似的成本。当且仅当从列表中删除具有更大的开销时，您才可能希望对非删除算法进行基准测试，该算法将使“永久”关联保持不变，并手动安排清除操作。尽管先前的解决方案应该表现更好，但出于完整性考虑，值得一提。
插入
如果您使用字典，那么它是微不足道的(而且性能更高)。更新时间戳或插入(如果不存在)具有相同的代码:strawberry["Mike"]=timestamp。此外，整体关联集是一个具有key = item和value = per_item_dict的dict，而per_item_dict具有key = user value = timestamp的dict。因此data[strawberry]["Mike"]=timestamp
编辑:添加更多代码
清除
data[strawberry] = {k: v for k, v in data[strawberry].items() if your_time_condition_expression}
受欢迎程度检查
清除后:
len(data[strawberry])关于hadoop - 映射减少作业以在时间窗口中找到受欢迎的项目，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50147005/