返回访问量最大的5个网站(堆、哈希表)- Python

Question

设计并实现了一个web浏览器，该浏览器支持在任何给定的实例中，您可以根据的访问次数(按任何顺序)有效地告诉最受访问的5个网站的功能

在我的实现中，我没有使用网页类，因为我想不出一种有效的方法，我们可以根据访问来更新堆，除非我们再次修改。我不认为我能更新堆“在前进”。如果我使用网页类来跟踪访问，而不是hashtable，那么每次访问站点时，我仍然需要更新hashtable。

我想了解如何在PYTHON中优化这个解决方案。我已经看到了C++中的实现，但是我想知道我是否能够用我选择的语言来优化我当前的实现。任何洞察力都会很好。

class Webpage:
    def __init__(url):
      self.url = url
      self.numberOfVisits = 1
  
class History:
    def _init_():
      self.sites = {}
      
    def visit(url):
      if (url in self.sites):
        self.sites[url] += 1
      else:
        self.sites[url] = 1  

  
    def printTop5():
      heap = []
      heapq.heapify(heap)
      for key, value in self.sites:
        heap.heappush(heap, (-value, key))
      
      i = 0
      while (heap and i < 5):
        value, url = heapq.heappop(heap)
        print(url)
        i += 1


def main():
    History h = History();
    print("before visits\n")
    h.visit("www.google.com")
    h.visit("nytimes.com")
    h.visit("reddit.com") 
    h.visit("dev.ibm.com")
    h.visit("www.google.com")
    print("after visits\n")
    h.printTop5()
    h.visit("ig.com") 
    h.visit("ig.com") 
    h.visit("ig.com") 
    h.printTop5()

Answer 1

从技术上讲，在Python中实现这一功能的最佳方法是使用内置的collections.Counter数据类型。这是用高度优化的代码编写的，使用Python可能会产生最好的性能。您可以在文档here中阅读更多有关它的信息。

例如：

from collections import Counter

history = Counter()

#I made them one by one to signify individal browser requests
history["google.com"] += 1
history["yahoo.com"] += 1
history["spotify.com"] += 1
history["yahoo.com"] += 1
history["bing.com"] += 1
history["youtube.com"] += 1
history["amazon.com"] += 1
history["yahoo.com"] += 1
history["google.com"] += 1
history["wikipedia.com"] += 1
history["wikipedia.com"] += 1
history["yahoo.com"] += 1
history["yahoo.com"] += 1
history["amazon.com"] += 1

print(history.most_common(5))

这个结果是：

[('yahoo.com', 5), ('google.com', 2), ('amazon.com', 2), ('wikipedia.com', 2), ('spotify.com', 1)]

因为它附带了Python的标准安装，所以我认为这应该算作“纯”python。

Answer 2

可能的全局堆

我想知道是否有一种使用全局堆的有效方法

我不认为一个全局堆能够有效地工作。若要在条目更改(所谓的递增键操作或减少键操作)时更新堆，只需从更改的节点开始运行筛选或筛选操作即可。但是，首先必须找到堆中节点的位置，我们没有一种有效的方法来做到这一点。

替代数据结构

...或者别的什么？

还有另一种方法。创建一个具有表单链接的双链接列表，Link(prev, next, count, url)。跟踪两个变量，第一个和最后一个，以跟踪双链接列表的端点。使用字典(哈希表)从url映射到链接条目。

visit(url)代码负责更新结构。

如果之前还没有看到url，那么创建一个新的链接，Link(prev=last, next=None, count=1, url)，将链接保存在站点字典中并使用site[url] = new_link保存，将链接追加到双链接列表，最后用last = new_link更新。

如果以前见过url，请使用link = site[url]找到链接，并使用link.count += 1更新计数。为了维护最常见到最不常见的排序顺序，在link.count > link.prev.count时保持与以前的链接进行交换。

这可以通过在池中保持相同计数的链接来进一步优化，这样最多只会发生一个交换。

每当调用printTop5()时，只需遍历双链接列表中的前五个条目，从第一个开始。

工作代码

from dataclasses import make_dataclass

Link = make_dataclass('Link', ('prev', 'next', 'url', 'count'))        

class History:

    def __init__(self):
        self.site = {}
        self.root = root = Link(None, None, 'root', 0)
        root.prev = root.next = root

    def visit(self, url):
        root = self.root
        if url in self.site:
            link = self.site[url]
            link.count += 1
            while link.prev is not root and link.prev.count < link.count:
                prev = link.prev
                prev.prev.next = link
                link.next.prev = prev
                prev.next, link.next = link.next, prev
                prev.prev, link.prev = link, prev.prev
        else:
            last = root.prev
            link = Link(last, root, url, 1)
            self.site[url] = root.prev = last.next = link

    def printTop5(self):
        link = root = self.root
        for i in range(5):
            if link.next is not root:
                link = link.next
                print(link.count, link.url)