Как найти количество уникальных слов в массиве (python), учитывая ограничение 5 Мб памяти и 5 секунд времени? - PullRequest
Новая
       12

Как найти количество уникальных слов в массиве (python), учитывая ограничение 5 Мб памяти и 5 секунд времени?

0 голосов
/ 22 февраля 2019

Добрый день всем, кто дошел до моего вопроса.Я пытался решить проблему нахождения количества уникальных слов, которые будут вводиться в качестве ввода, и первым вводом будет количество слов, которые будут набраны.Например:
5
дорожка
потеря
масштаб
потеря
таблица
Правильный ответ должен быть следующим: 4
Я пытался решить вопрос в Python,как это: 

a=set()
x = int(input())
a.add(x)
for i in range(x):
    y = input()
    a.add(y)
print(len(a)-1)

Кажется, что он работает просто отлично, только неэффективно с точки зрения памяти (это превышает ограничения памяти, на высоких входах).Есть ли более эффективный способ решения этой проблемы?

Ответы [ 3 ]

0 голосов
/ 22 февраля 2019

Экономия памяти Cheapo доступна, потому что вы используете Python 3.6+: используйте dict, а не set.Несмотря на необходимость хранить значение для каждого элемента, dict s часто использовали немного меньше памяти даже в старых версиях Python (они оптимизированы для разных целей; set имеет тенденцию перераспределять сегменты, чтобы уменьшить риск столкновений блоков,но это стоит больше памяти);в версии 3.6+ они перешли к более компактному dict дизайну, который экономит еще больше, пока уникальные данные не велики (set s может начать выигрывать снова для некоторых размеров, когда количество уникальных предметов превышает 2**15/ 32768, так как прирост компактности резко падает в этой точке).

Чтобы изменить его, просто сделайте: 

a = {}
x = int(input())
for _ in range(x):
    a[input()] = None
print(len(a))

Кроме того, для скорости, если вам не нужноиспользуйте input, вам, вероятно, следует избегать этого и просто читать из sys.stdin напрямую;input выполняет много ненужной очистки выходов и другой работы, которая вам здесь не нужна.Так что, скорее всего, это будет еще быстрее: 

import itertools, sys

x = int(input())
a = dict.fromkeys(itertools.islice(sys.stdin.buffer, x))
print(len(a))

, который просто тянет линии без изменений и толкает их прямо в dict на уровне C для дополнительной скорости.Измените sys.stdin на sys.stdin.buffer, чтобы вообще не расшифровывать строки, и добавьте map(str.rstrip, ...) или map(bytes.rstrip, ...) для sys.stdin.buffer, чтобы удалить новые строки (если последняя строка может не заканчиваться новой строкой, это необходимо для правильностии, я полагаю, это экономит тривиальный объем памяти).

Если входные данные могут быть огромными (более пятизначные уникальные входные данные), то dict, скорее всего, не поможет, поэтому просто придерживайтесь set, но вы все равно можете использовать sys.stdin оптимизации, что приведет к окончательной форме, такой как: 

x = int(input())
a = set(itertools.islice(map(bytes.rstrip, sys.stdin.buffer), x))
print(len(a))
0 голосов
/ 22 февраля 2019

В зависимости от ожидаемого характера данных:

  • для словарных слов, особенно похожих, используйте три
  • для длинных текстов, используйте сжатие без потерь

Пример для zlib сжатия: 

import zlib

a = set()
x = int(input())
for _ in range(x):
    a.add(zlib.compress(input().encode()))
    #a.add(input())

print("unique: ", len(a))

print("memory: ", sum(len(b) for b in a))

Несжатого: 

> echo -e "3\naaaaaaaaaaaaaaaa\nbbbbbbbbbbbbbbbb\naaaaaaaaaaaaaaaa" | python3 c.py
unique:  2
memory:  32

Сжатого: 

> echo -e "3\naaaaaaaaaaaaaaaa\nbbbbbbbbbbbbbbbb\naaaaaaaaaaaaaaaa" | python3 c.py
unique:  2
memory:  22
0 голосов
/ 22 февраля 2019

Мне пришло 2 решения.Первый - использовать структуру JSON.Структура JSON использует уникальный ключ, затем вы можете создать эту структуру и затем проверить, сколько у вас ключей.

Код будет выглядеть примерно так

Для обоих примеров я буду считать васиметь массив со всеми словами, этот массив будет words_array

unique_words = {}
for word in words_array:
  unique_words[word.lower().strip()] = 1 
  # this  one could be any value
  # i just need to create the key value

print len(unique_words)

Я использовал lower и strip, чтобы убедиться, что это слово уникально, независимо от того, в верхнем регистре или пробелах в слове.

Другой метод заключается в проверке в массиве, если слово уже существует, этот метод работает, но он менее эффективен 

unique_words = []
for word in words_array:
  w = word.lower().strip()
  if not w in unique_words:
    unique_words.append(w)

print len(unique_words)

Я думаю, что если вы ищете эффективность памяти, я предложу другиеальтернатива, например, использование C

...