@fridary

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

Никак не могу решить задачу, может кто знает. На вход подается 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)))


Есть идеи что еще можно сделать?
  • Вопрос задан
  • 178 просмотров
Пригласить эксперта
Ответы на вопрос 4
@deliro
Агрессивное программирование
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))
Ответ написан
longclaps
@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)
Ответ написан
Astrohas
@Astrohas
Python/Django Developer
Множества использовать не пробовали? Есть пример входных данных?
Если принципиально использование памяти а время не важно, то можно хешировать строки и сохранять хеши в множестве. По памяти должно быть меньше 5 мб. По времени 2 - 3 секунды
Ответ написан
moonz
@moonz
junior
Задача на знание алгоритмов) попробуй Counter
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы