Как уменьшить расход памяти

@vovashininov · Регистрация: 17.03.2019

Студворк — интернет-сервис помощи студентам

Добрый день,
Я проверяю уникальность строк, для этого я делаю из них множество(set) и потом вычисляю его длину, однако расход памяти в этом случае вдвое больше чем нужно. Скажите, пожалуйста, как его можно сократить?

Python
1
2
3
4
N = int(input())
a = [[(i) for i in input().split()] for _ in range(N)]
a1 = set([item for sublist in a for item in sublist])
print(len(a1))

@Semen-Semenich · 29.04.2019, 13:41

Сообщение от vovashininov

Я проверяю уникальность строк

если строк то соберите строки в множество сразу

Python
1
2
3
4
5
N = int(input())
a = set()
for _ in range(N):
    a. add(input())
print(len(a))

если уникальность слов

Python
1
2
3
4
5
N = int(input())
a = set()
for _ in range(N):
    a = a.union(set(input().split()))
print(len(a))

@ioprst · 29.04.2019, 13:43

Если у вас есть список строк lst можно просто проверить количество вхождений каждой строки в этот список. Больше 1 => повторяющаяся строка.

Python
1
2
3
lst = ['1', '2', '1']
for item in lst:
    print(lst.count(item))

@vovashininov · 29.04.2019, 15:21 **[ТС]**

Semen-Semenich, При проверке уникальности слов все равно превышение памяти на 1 Mb(максимум 5 Mb разрешено)

@prct1 · 30.04.2019, 22:28

Если нужно только узнать сколько уникальных строк, тогда можно хранить не строки, а "хеши" для этих строк. Если строки длинные, то может быть будет экономия памяти, попробуйте.

@vovashininov · 06.05.2019, 15:26 **[ТС]**

prct1, Какую можно выбрать хэш функцию для этого?

Добавлено через 10 минут
prct1, И я правильно понял - вначале в цикле мы поочередно переводим строки в значения хэша при этом из цикла мы выводим и сохраняем только эти значения, а строку снова обновляем?

Добавлено через 15 минут
prct1, Попробую уточнить свой вопрос - допустим использую полиноминальную функцию я получил набор хэшей, но как их лучше сохранить, чтобы быстро к ним обращаться и искать похожие? сохранить их как список чисел?

@prct1 · 09.05.2019, 17:26

Если расход памяти больше в два раза, то для начала можно попробовать не сохранять строки в промежуточный список - из входного файла читаются данные по одной строке, затем в "set" добавляется нужная строка. Если результат не изменится, то можно использовать и хеш-функцию. Вот пример:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/env python3
 
import hashlib
import sys
 
def get_hash(string):
    return hashlib.md5(string.encode('utf-8'))
 
s = set()
N = int(sys.stdin.readline())
for _ in range(N):
    s.add(get_hash(sys.stdin.readline()))
print(len(s))

Если используется хеш-функция, то значение результата может быть неточным, т.к. могут быть коллизии. Значит функция выбирается так, чтобы их вероятность была маленькой.

Рыжий Лис · 09.05.2019, 17:53

prct1, хеши займут в памяти больше места, чем сами слова. Впрочем, идея читать понемножку из stdin стоящая.

@prct1 · 09.05.2019, 18:19

Хеш-функция в предыдущем сообщении с ошибкой. Делаем так:

Python
1
2
def get_hash(string):
    return int(hashlib.md5(string.encode('utf-8')).hexdigest(), 16)

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@vovashininov 0 / 0 / 0 Регистрация: 17.03.2019 Сообщений: 15
	29.04.2019, 15:21 [ТС]
	Semen-Semenich, При проверке уникальности слов все равно превышение памяти на 1 Mb(максимум 5 Mb разрешено) 0

@prct1 10 / 8 / 3 Регистрация: 10.04.2019 Сообщений: 43
	30.04.2019, 22:28
	Если нужно только узнать сколько уникальных строк, тогда можно хранить не строки, а "хеши" для этих строк. Если строки длинные, то может быть будет экономия памяти, попробуйте. 0

@vovashininov 0 / 0 / 0 Регистрация: 17.03.2019 Сообщений: 15
	06.05.2019, 15:26 [ТС]
	prct1, Какую можно выбрать хэш функцию для этого? Добавлено через 10 минут prct1, И я правильно понял - вначале в цикле мы поочередно переводим строки в значения хэша при этом из цикла мы выводим и сохраняем только эти значения, а строку снова обновляем? Добавлено через 15 минут prct1, Попробую уточнить свой вопрос - допустим использую полиноминальную функцию я получил набор хэшей, но как их лучше сохранить, чтобы быстро к ним обращаться и искать похожие? сохранить их как список чисел? 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	09.05.2019, 17:53
	prct1, хеши займут в памяти больше места, чем сами слова. Впрочем, идея читать понемножку из stdin стоящая. 0