Как подсчитать число уникальных строк больше 1 млн. при вводе?

Question

[fridary]

Никак не могу решить задачу, может кто знает. На вход подается N < 1м (одного миллиона) число и далее N строк длиной меньше 1к.
Мне нужно в результате вывести число уникальных строк. Но важное ограничение, что можно только numpy использовать библиотеку, время не более 5с работы и 5 Мб памяти (!)

Скрипт ниже у меня взял 97мс и 12 Мб памяти:

import numpy as np

N = int(input())
a = np.array([])
for i in range(N):
    x = input()
    if not np.any(a == x):
        a = np.append(a, x)

print(len(a))

Этот код взял 10 Мб памяти:

N = int(input())
results = np.empty(N, dtype=object)
for i in range(N):
    results[i] = input()

print(len(np.unique(results)))

Есть идеи что еще можно сделать?

Comments

[Anton Kuzmichev]

На вход подается N < 1м (одного миллиона) число и далее N строк длиной меньше 1к.

Что это значит? Что за "далее"?
Или всё это понимать просто как "на вход подаётся N строк, каждая из которых длиной не более 1 килобайта", где N <= 1 000 000?

Язык обязательно Python? Что-то из стандартных библиотек можно использовать? (помимо numpy, которая ставится отдельно)

Answer 1

[Roman K]

N = int(input())
s = set()
for i in range(N):
    s.add(input())
print(len(s))

UPD
Более оптимальный по памяти — сами строки не хранятся, хранятся только их хэши:

N = int(input())
s = set()
for i in range(N):
    s.add(hash(input()))
print(len(s))

Comments

[Roman K]

Кстати, можно попробовать лайфхак в виде фильтра Блума. Памяти занимает мало, но есть небольшой шанс упасть на тестах)

Вроде такого https://gist.github.com/deliro/cc00aca6b8b3ef0a9fd...

[longclaps]

Roman Kitaev, хотелось бы хоть краем глаза взглянуть хоть на блок-схему решения этой задачи с этим Блумом )

[Roman K]

longclaps, вот так, например. Оптимизировать лень, поэтому воткнул lru кэш. Но высчитывание проб можно оптимизировать лучше. Сейчас получается большая экономия памяти, но на два порядка дольше по времени. Можно оптимизировать ещё хэш-функцию (например, заменить на hash(obj)) и добиться чего-то более вменяемого

from math import log
from array import array
from struct import unpack
from hashlib import sha512
from time import monotonic_ns
from statistics import median
from functools import lru_cache


class Bits:
    __slots__ = ('data',)

    def __init__(self, cap):
        self.data = array('Q', (0 for _ in range((cap // 64) + 1)))

    def __setitem__(self, i, x):
        byte, bit = divmod(i, 64)
        self.data[byte] |= 1 << bit

    def __getitem__(self, i):
        byte, bit = divmod(i, 64)
        return (self.data[byte] & (1 << bit)) >> bit


class Bloom:
    __slots__ = ('bit_num', 'probes', 'bits', 'stored')

    def __init__(self, capacity, error=0.001):
        self.bit_num = int(-(capacity * log(error)) / 0.4804)
        self.probes = int(0.6931 * (self.bit_num / capacity))
        self.bits = Bits(self.bit_num)
        self.stored = 0

    @lru_cache()
    def _hash(self, obj):
        if not isinstance(obj, str):
            obj = str(obj)

        hashes = unpack('Q'*8, sha512(obj.encode()).digest())
        m = 0
        l = len(hashes)

        for i in range(self.probes):
            h = hashes[i % l]
            if i and i % l == 0:
                m += 1
            yield (h >> m) % self.bit_num

    def add(self, item):
        if item in self:
            return
        self.stored += 1
        for h in self._hash(item):
            self.bits[h] = 1

    def __contains__(self, item):
        return all(self.bits[h] for h in self._hash(item))


if __name__ == '__main__':
    b = Bloom(10**6)
    set_for_making_sure = set()
    actual_lines_count = 0
    times_bloom = []
    times_set = []
    for line in open("..."):
        start_bloom = monotonic_ns()
        b.add(line)
        times_bloom.append(monotonic_ns() - start_bloom)
        
        start_set = monotonic_ns()
        set_for_making_sure.add(line)
        times_set.append(monotonic_ns() - start_set)
        actual_lines_count += 1
    print(b.stored, "in the bloom filter")
    print(len(set_for_making_sure), "in the set")
    print(actual_lines_count, "non-unique lines in the file")
    print(b.bits.data.__sizeof__() / 2**20, "megabytes for the bit field")
    print(set_for_making_sure.__sizeof__() / 2**20, "megabytes for the set (only hash table, not actual values)")
    print(median(times_bloom), "nanoseconds to add in the bloom filter")
    print(median(times_set), "nanoseconds to add in the set")

[Anton Kuzmichev]

Ваше изначальное решение не впишется по памяти всего-то после 5000 килобайтных строк, а их там миллион

[Roman K]

Anton Kuzmichev, ох боже, ну почему вы такие тугие? Окей, храни хэши строк вместо самих строк.

[Anton Kuzmichev]

Ваше изначальное решение

Roman Kitaev, тут тебе не пикабу, во всех смыслах. В том числе и в том, что ответ можно дополнять и исправлять.

[longclaps]

Roman Kitaev, спасибо, оказывается я недопонимал и недооценивал этого Блума. Он неплохо ведет себя до тех пор, пока его не перекормишь, но дальше, конечно, кошмар.

[Roman K]

longclaps, у меня достаточно тупая реализация, тем более на питоне. Просто тренировался и понимал его суть. Есть продвинутые, вроде они даже могут расширяться. Правда всего лишь создавая пустые фильтры при заполнении) https://github.com/jaybaird/python-bloomfilter/blo...

Answer 2

[longclaps]

Задача не имеет решения в заявленых ограничениях. Если чьи-то решения прокатывают - значит редакция мухлюет с тестовыми данными. Вот демка на этот счет. Можешь допилить её, выбросив лишнее и заменив randrange на hash(input()), и попробовать пропихнуть как решение.

from numpy import zeros, uint32
from random import randrange
from sys import getsizeof


N = 10 ** 6
hashes = zeros(N, uint32)
print(f'hashes занимает  {getsizeof(hashes)} байт')
control = set()  # здесь считаем по-честному
for i in range(N):
    # вместо строк я использую большие случайные числа
    r = randrange(0x4000000000000000)
    control.add(r)
    # сохраняем последние 4 байта r - больше не лезет
    hashes[i] = r & 0xffffffff
hashes.sort()
a, cnt = hashes[0], 1
for b in hashes:
    if a != b:
        a = b
        cnt += 1
print(f'control - целых {getsizeof(control)} байт (для строк длиной до 1к было бы больше)')
print(f'{cnt:8} разных хэшей\n{len(control):8} разных чисел')

Слишком короткий хэш (32 бита) на 10^6 строк порождает слишком много коллизий (смотри парадокс дней рождения). Нельзя впихнуть невпихуемое.

UPDATE
Roman Kitaev предложил использовать фильтр Блума, вот решение на этой идее. Оно несёт в себе недостатки фильтра Блума: работает медленно и ошибается; так же возможно, что мои упрощения убили фильтр, но авось прокатит.

bitmap, cnt = bytearray(0x400000), 0
for _ in range(int(input())):
    h, f = hash(input()), 0
    for _ in range(16):
        m = b'\x01\x02\x04\x08\x10\x20\x40\x80'[h & 7]
        h = ((h >> 4) ^ i) | ((h & 15) << 60)
        if not bitmap[h & 0x3fffff] & m:
            bitmap[h & 0x3fffff] |= m
            f = 1
    cnt += f
print(cnt)

Comments

[fridary]

5.77 Mb занимает, если hash(input()) поставить

[longclaps]

fridary, кто?

[Roman K]

В фильтре Блума суть была в том, что один элемент отображается на несколько битов. Здесь как будто ложноположительные начнутся очень быстро. Тестировал?

[longclaps]

Roman Kitaev, тестировал, вроде работает. Тут, конечно, плохой алгоритм "разных хэш-функций": один и тот же фингерпринт из 16 бит даст и 0x0123456789abcdef, и 0xfedcba9876543210, и любая другая перестановка (т.е. имеем группу из 16! членов-"близнецов"). Это можно порушить, например, так:

for i in range(16):
    h = ((h >> 4) ^ i) | ((h & 15) << 60)

Но раз и так срабатывает - плюнул; битовые операции небыстрые.

[Roman K]

longclaps, Вот будет уморительно, если окажется, что 5мб ограничение памяти ОЗУ, а диск не ограничен и можно просто унести сет в файл по mmap.

[longclaps]

Roman Kitaev, на самом деле все еще проще: тот первый код из моего ответа, если в нем поменять uint32 на uint64, всё порешает, вероятность коллизий станет ничтожной. Он и быстрее гораздо. В общем, ограничения очень надуманные.

Answer 3

[Astrohas]

Множества использовать не пробовали? Есть пример входных данных?
Если принципиально использование памяти а время не важно, то можно хешировать строки и сохранять хеши в множестве. По памяти должно быть меньше 5 мб. По времени 2 - 3 секунды

Answer 4

[Михаил]

Задача на знание алгоритмов) попробуй Counter

Comments

[longclaps]

Сказал гений, отмеченый знанием волшебного алгоритма "Counter".

[Михаил]

longclaps, а чего это мы на личности переходим? Я где-то сказал что это алгоритм, или решение с помощью алгоритма? Это просто была подсказка с помощью чего можно попробовать решить задачу.

[longclaps]

Задача на знание алгоритмов) попробуй Counter
Я где-то сказал что это алгоритм, или решение с помощью алгоритма?

Михаил, твои фразы слишком далеко разнесены, и я специально их поставил рядом: так они смотрятся еще убедительнее.
К твоей же личности я отношусь с глубоким почтением и ничего против неё не имею. Поверь.