Python: Как найти большой массив эффективным способом?

Question

Проблема:

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

Сначала я сгенерировал 4 списка и сохранил их в формате pickle на диске.

-rw-rw-r-- 1 malware_corpus malware_corpus 189M May  4 13:11 clean_a.pkl
-rw-rw-r-- 1 malware_corpus malware_corpus 183M May  4 13:12 clean_b.pkl
-rw-rw-r-- 1 malware_corpus malware_corpus 1.7M Apr 30 11:12 data_backup.csv
-rw-rw-r-- 1 malware_corpus malware_corpus 2.9M May  4 13:13 data.csv
-rw-rw-r-- 1 malware_corpus malware_corpus 231M May  4 13:12 mal_a.pkl
-rw-rw-r-- 1 malware_corpus malware_corpus 232M May  4 13:13 mal_b.pkl

Так что в моем коде всякий раз, когда появляется новая строка, я беру эти 4 списка и сравниваю подстроки в эти 4 списка и вычисляю оценку. Из-за всех этих 4 списков, хранящихся в памяти, программа работает медленно

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

Требуется решение:

• Любой эффективный способ сохранить 4 списка, чтобы они не заполняли мою память.
• Любой лучший способ поиска строки в 4 списках.
• Как получить доступ к большим спискам в Python.

Кодовая часть:

    def create_corpus(self):
    """corpus

    :param domain: Doamin passed will be split and words are stored in
    corpus.
    """
    with open(os.path.join(os.path.dirname(os.path.realpath(__file__)),'utils/x.txt'),'r') as f:
        for line in f:
            line = line.rstrip()

            self.line_x = self.calculate_xs(line)
            for i in self.line_x:
                self.clean_xs.append(i)
            self.line_y = self.calculate_ys(line)
            for i in self.line_y:
                self.clean_ys.append(i)
    with open(os.path.join(os.path.dirname(os.path.realpath(__file__)),'utils/y.txt'),'r') as f:
        for line in f:
            line = line.rstrip()
            self.line_x = self.calculate_x(line)
            for i in self.line_x:
                self.mal_xs.append(i)
            self.line_y = self.calculate_y(line)
            for i in self.line_y:
                self.mal_ys.append(i)

    # Store the Datasets in pickle Formats
    with open(os.path.join(os.path.dirname(os.path.realpath(__file__)),\
                           'utils/clean_x.pkl'),'wb') as f:
        pickle.dump(self.clean_xs , f)

    with open(os.path.join(os.path.dirname(os.path.realpath(__file__)),\
                           'utils/clean_ys.pkl'),'wb') as f:
        pickle.dump(self.clean_ys , f)
    with open(os.path.join(os.path.dirname(os.path.realpath(__file__)),\
                           'utils/mal_xs.pkl'),'wb') as f:
        pickle.dump(self.mal_xs , f)
    with open(os.path.join(os.path.dirname(os.path.realpath(__file__)),\
                           'utils/mal_ys.pkl'),'wb') as f:
        pickle.dump(self.mal_ys, f)
    return 1


def compare_score_function(self,domain):
    self.domain = domain
    self.g_freq = {}
    self.b_score = 0.0
    from collections import Counter
    for x in self.substrings_of_domain:
        self.g_freq[x] = {}
        self.g_freq[x]['occur'] = self.clean_x.count(x)
        self.g_freq[x]['freq']  = self.clean_x.count(x)/len(self.clean_x)
    for key,value in self.g_freq.iteritems():
        self.b_score += value['freq']
    return self.b_score

def calculate_x(self,domain):
    self.domain = self.clean_url(domain)
    self.bgrm = list(ngrams(self.domain,2))
    self.bgrm = [''.join(a) for a in self.bgrm ]
    return self.bgrm

def calculate_y(self,domain):
    self.domain = self.clean_url(domain)
    self.tgrm = list(ngrams(self.domain,3))
    self.tgrm = [''.join(a) for a in self.tgrm]
    return self.tgrm

Пример объяснения

• clean_x_list = ['ap', 'pp', 'pl', 'le', 'bo', 'xl', 'ap']
• clean_y_list = ['apa', 'ppa', 'fpl', 'lef', 'bfo', 'xdl', 'mpd']
• bad_x_list = ['ti', 'qw', 'zx', 'qa', 'qa', 'qa', 'uy']
• bad_y_list = ['zzx', 'zxx', 'qww', 'qww', 'qww', 'uyx', 'uyx']

Здесь предположим, что это мои 4 списка:

Пришла моя новая строка - предположим, яблоко - Теперь я буду вычислять x слов для apple => ['ap', 'pp', 'pl', 'le'] - Теперь я буду вычислять y слов для apple => ['app', 'ppl', 'ple', 'lea']

• Теперь я буду искать каждое x-слово яблока, т. Е. ['Ap', 'pp', 'pl', 'le'] как в clean_x_list, так и в bad_x_list

• тогда я буду рассчитывать частоту и количество появлений

• вхождение ap в clean_x_list = 2

• частота ap в clean_x_list = 2/7
• вхождение ap в bad_x_list = 0
• вхождение ap в bad_x_list = 0/7

Точно так же я вычисляю встречаемость и частоту других слов и, наконец, суммирую

Answer 1

Одним из вариантов экономии места является сохранение файлов слов в сжатом виде, но также не чтение всего файла слов в память. Для этого простой вариант - gzip.GzipFile , который позволяет вам работать с архивом gzip как обычный файл:

import gzip

with gzip.open('input.gz','rt') as text_f:
    for line in text_f:
        line = line.strip()
        print(line)

Таким образом, вы можете обрабатывать каждую строку в файле как элемент в списке и обрабатывать их соответствующим образом.

Обратите внимание на метод открытия rt (или wt), который заставляет его обрабатываться как текст, а не как двоичный файл - это будет зависеть от того, храните ли вы простой текст / json или используете двоичный формат для ваши данные (например, рассол).

Answer 2

Существует в основном три варианта: линейное сканирование списка в O (n), ...

>>> lst = random.sample(range(1, 1000000), 100000)
>>> x = lst[50000]
>>> %timeit x in lst
100 loops, best of 3: 2.12 ms per loop

... двоичный поиск в отсортированном списке в O (logn) с использованием модуля bisect, ...

>>> srt = sorted(lst)
>>> srt[bisect.bisect_left(srt, x)] == x
True
>>> %timeit srt[bisect.bisect_left(srt, x)] == x
1000000 loops, best of 3: 444 ns per loop

... и поиск в хэше set в O (1):

>>> st = set(lst)
>>> %timeit x in st
10000000 loops, best of 3: 38.3 ns per loop

Очевидно, что set является самым быстрым, но он также занимает немного больше памяти, чем подходы, основанные на list. Подход bisect может быть хорошим компромиссом: он уже в 5000 раз быстрее линейного сканирования в этом примере и требует только сортировки списка.

>>> sys.getsizeof(lst)
800064
>>> sys.getsizeof(srt)
900112
>>> sys.getsizeof(st)
4194528

Однако, если ваш компьютер не очень ограничен в памяти, это не должно быть проблемой. В частности, это не сделает код медленнее. Либо все это помещается в память, и все хорошо, либо нет, и ваша программа останавливается.

---

Если ваши списки хороших / плохих слов могут содержать дубликаты, то set не вариант, и bisect тоже не будет работать. В этом случае создайте Counter для каждого из этих списков. Затем вы можете получить количество вхождений и частоты для каждой из подстрок в вашем тексте. Будучи своего рода хэш-картой / словарем, поиск в Counter также будет O (1).

>>> clean_x_list = ['ap','pp','pl','le','bo','xl','ap']
>>> w = "apple"
>>> wx = [w[i:i+2] for i in range(len(w)-1)]
>>> ccx = collections.Counter(clean_x_list)

>>> occ_wx = {x: ccx[x] for x in wx}
>>> occ_wx
{'ap': 2, 'pp': 1, 'pl': 1, 'le': 1}

>>> freq_wx = {x: ccx[x] / len(clean_x_list) for x in wx}
>>> freq_wx
{'ap': 0.2857142857142857,
 'pp': 0.14285714285714285,
 'pl': 0.14285714285714285,
 'le': 0.14285714285714285}

И аналогично для clean_y_list, bad_x_list и т. Д.

Answer 3

Рассмотрите возможность сортировки списков и используйте bisect для поиска в ваших списках. В этом случае время поиска в худшем случае равно O (log n).