return top 5 most visited websites (heap, hashtable) - Python

user_12393927 0
Viewed 316

Design and implement a web browser that supports the functionality that at any given instance you can efficiently tell the top 5 visited websites on basis of the number of visits (in any order)

In my implementation, I did not use the Webpage class as I can't think of an efficient way we could update the heap based on visits unless we did heapify again. I don't think I can update the heap "on the go". If I use the Webpage class to track visits instead of the hashtable I would still need to update the hashtable every time I visit a site.

I want to understand how I can optimize this solution in PYTHON. I have seen implementations in C++, but I want to know if I can optimize my current implementation in my language of choice. Any insight would be great.

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()
heap python
2 Answers

Technically, the best way to implement this in Python is to use the built in collections.Counter datatype. This is written in highly optimized code and will probably yield the best performance possible with Python. You can read more about it in the documentation [here] (https://docs.python.org/3/library/collections.html#collections.Counter).

So for example:

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))

And this returns:

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

Since this comes with a standard installation of Python, I think this should count as "pure" python.

user_149700070

Possible global heap

I am wondering if there is an efficient way to use a global heap

I don't think a global heap could work efficiently. To update a heap when an entry changes (so-called increase-key or decrease-key operations), it suffices to run siftup or siftdown starting at the changed node. However, you first have to find the position of then node within the heap, and we don't have an efficient way to do that.

Alternative data structure

... or something?

There is another way. Create a doubly linked list with links in the form, Link(prev, next, count, url). Track two variables, first and last, to track the endpoints of the doubly linked list. Use a dictionary (hash table) to map from the url to the link entry.

The visit(url) code is responsible for updating the structure.

If the url hasn't been seen before, create a new link, Link(prev=last, next=None, count=1, url), save the link in your site dictionary with site[url] = new_link, append the link the doubly linked list, and update last with last = new_link.

If the url has been seen before, find with link with link = site[url] and update the count with link.count += 1. To maintain the most-common-to-least common sort order, keeping swapping with previous links while link.count > link.prev.count.

This can be optimized further by keeping links with the same count in a pool so that at most one swap will occur.

Whenever printTop5() is called, just traverse the first five entries in the doubly-linked list starting with first.

Working code

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)
user_4244990
Related