Количество уникальных запросов

Question

Добрый день.

Помогите, пожалуйста, решить задачу. Если хранить все запросы в списке или множестве, например:

N = int(input())
unique_strings = set()

for _ in range(N):
    unique_strings.add(input().strip())

print(len(unique_strings))

Решение не засчитывается, т.к программа должна не превышать по объёму 5МБ. Как можно оптимизировать код, чтобы программа была более быстрой и ёмкой?

Answer 1

import hashlib
import math
x = int(input())
class CompactHyperLogLog:
    def __init__(self, b):
        self.b = b
        self.m = 1 << b
        self.alphaMM = (0.7213 / (1 + 1.079 / self.m)) * self.m * self.m
        self.registers = [0] * self.m
    
    def _hash(self, value):
        return int(hashlib.md5(value.encode('utf8')).hexdigest(), 16)
    
    def add(self, value):
        x = self._hash(value)
        j = x & (self.m - 1)
        w = x >> self.b
        self.registers[j] = max(self.registers[j], self._rho(w))
    
    def _rho(self, w):
        return (w & -w).bit_length()
    
    def count(self):
        Z = 1.0 / sum([2 ** -reg for reg in self.registers])
        E = self.alphaMM * Z
        if E <= 2.5 * self.m:
            V = self.registers.count(0)
            if V > 0:
                E = self.m * math.log(self.m / V)
        elif E > 1 / 30.0 * (1 << 32):
            E = -(1 << 32) * math.log(1 - E / (1 << 32))
        return int(E)
    
    def merge(self, other):
        if self.m != other.m:
            raise ValueError("Cannot merge HLLs with different number of registers")
        self.registers = [max(self.registers[i], other.registers[i]) for i in range(self.m)]


hll = CompactHyperLogLog(b=8)

# Добавление данных
for i in range(x):
 hll.add(input())

# Получение количества уникальных элементов
count = hll.count()
print(f"{count}")

Answer 2

Заведём массив на четыре миллиона бит примерно. От всех строк вычислим номер бита в этом массиве и установим соответствующий бит. Сосчитаем установленные биты. Прикидка доли коллизий показывает что этого хватит:

k = 3_999_971 # простое число близкое к 4_000_000
b = bytearray((k + 7) // 8) # около 500KiB

for _ in range(int(input())):
    i, j = divmod(hash(input()) % k, 8)
    b[i] |= 1 << j

print(sum(map(int.bit_count, b)))

БЛОГ НА HUSL

Количество уникальных запросов

Добрый день.

Ответы (2 шт):