Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.96 KB | None | 0 0
  1.  
  2.  
  3. class Node:
  4.     def __repr__(self):
  5.         return str(self.key) + ' ' + str(self.value)
  6.  
  7.     def __init__(self, key, value, next): # node = Node()
  8.         self.key = key
  9.         self.value = value
  10.         self.next = next
  11.  
  12.  
  13. class HashMap:
  14.     def __init__(self, init_capacity=4, loaf_factor=0.75): # hm = HashMap()
  15.         self.arr = [None] * init_capacity
  16.         self.load_factor = loaf_factor
  17.         self.size = 0
  18.         self.capacity = init_capacity
  19.  
  20.     def hash(self, string):
  21.         shash = 0
  22.         for i in string:
  23.             shash = ord(i) + shash * 31
  24.         return shash
  25.  
  26.     def index(self, key):
  27.         return self.hash(key) % self.capacity
  28.  
  29.     def get_all_nodes(self):
  30.         nodes = []
  31.         for i in self.arr:
  32.             node = i
  33.             while node is not None:
  34.                 nodes.append(node)
  35.                 node = node.next
  36.         return nodes
  37.  
  38.  
  39.     def resize(self):
  40.         if self.size >= int(self.load_factor*self.capacity):
  41.             self.capacity *= 3
  42.             nodes = self.get_all_nodes()
  43.             self.arr = [None] * self.capacity
  44.             self.size = 0
  45.             for node in nodes:
  46.                 index = self.index(node.key)
  47.                 self.arr[index] = Node(node.key, node.value, self.arr[index])
  48.                 self.size += 1
  49.  
  50.  
  51.  
  52.     def insert(self, key, value):
  53.         index = self.index(key)
  54.         #print(self.arr)
  55.         node = self.arr[index]
  56.  
  57.         while node is not None:
  58.             if node.key == key:
  59.                 node.value.append(value)
  60.                 return
  61.             node = node.next
  62.  
  63.         self.arr[index] = Node(key, value, self.arr[index])
  64.         self.size += 1
  65.         self.resize()
  66.  
  67.  
  68.     def __getitem__(self, item): # hashmap["anarchy"]
  69.         index = self.index(item)
  70.         node = self.arr[index]
  71.         while node is not None:
  72.             if node.key == item:
  73.                 return node.value
  74.             node = node.next
  75.         return -1
  76.  
  77.  
  78. class HashSet:
  79.     def __init__(self, key):
  80.         self.map = HashMap(10)
  81.         self.map.insert(key, "Present")
  82.  
  83.     def append(self, key):
  84.         try:
  85.             self.map.insert(key, "Present")
  86.         except Exception:
  87.             pass
  88.  
  89.     def get(self):
  90.         string = ""
  91.         nodes = self.map.get_all_nodes()
  92.         for node in nodes:
  93.             string += str(node.key) + " "
  94.         return string
  95.  
  96. class InvertedIndex:
  97.     def __init__(self): # ii = Iventdf(234,34)
  98.         self.map = HashMap()
  99.  
  100.  
  101.     def index_document(self, document, document_id):
  102.         for word in document.split(" "):
  103.           #  print(word, self.map.arr, document.split(" "))
  104.             if self.map[word] != -1:
  105.                 self.map.insert(word, str(document_id))
  106.             else:
  107.                 self.map.insert(word, HashSet(str(document_id)))
  108.  
  109.     def search(self, word):
  110.         hs_word = self.map[word]
  111.         if hs_word != -1:
  112.             documents = hs_word.get()
  113.             return documents
  114.         return hs_word
  115.  
  116.     def get_average(self):
  117.         nodes = self.map.get_all_nodes()
  118.         size = 0
  119.         counter = 0
  120.         for node in nodes:
  121.             size += node.value.map.size
  122.             counter+= 1
  123.         return int(round(size/counter ,0)) # 1.0
  124.  
  125.  
  126.  
  127. # !/bin/python3
  128.  
  129. import math
  130. import os
  131. import random
  132. import re
  133. import sys
  134.  
  135. if __name__ == '__main__':
  136.     num_documents = int(input().strip())
  137.  
  138.     documents = []
  139.  
  140.     for _ in range(num_documents):
  141.         documents_item = input()
  142.         documents.append(documents_item)
  143.  
  144.     num_queries = int(input().strip())
  145.  
  146.     queries = []
  147.  
  148.     for _ in range(num_queries):
  149.         queries_item = input()
  150.         queries.append(queries_item)
  151.  
  152.     # Write your code here
  153.     index = InvertedIndex()
  154.  
  155.     for i in range(len(documents)):
  156.         index.index_document(documents[i], i)
  157.  
  158.     for word in queries:
  159.         print(index.search(word))
  160.  
  161.     print(index.get_average())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement