python оптимизация count () для n-грамм - PullRequest
Новая
       20

python оптимизация count () для n-грамм

1 голос
/ 28 марта 2020

Я пытаюсь посчитать элементы в списке строк, используя функцию count() и сортируя результаты по наибольшим и самым маленьким. Хотя функция работает достаточно хорошо в небольших списках, она не очень хорошо масштабируется, как видно из небольшого эксперимента, приведенного ниже, всего с 5 циклами удвоения входной длины (6-й цикл занимал слишком много времени для ожидания). Есть ли способ оптимизировать понимание первого списка или, возможно, альтернативу count(), которая бы лучше масштабировалась? 

import nltk
from operator import itemgetter
import time

t = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. Curabitur pretium tincidunt lacus. Nulla gravida orci a odio. Nullam varius, turpis et commodo pharetra, est eros bibendum elit, nec luctus magna felis sollicitudin mauris. Integer in mauris eu nibh euismod gravida. Duis ac tellus et risus vulputate vehicula. Donec lobortis risus a elit. Etiam tempor. Ut ullamcorper, ligula eu tempor congue, eros est euismod turpis, id tincidunt sapien risus a quam. Maecenas fermentum consequat mi. Donec fermentum. Pellentesque malesuada nulla a mi. Duis sapien sem, aliquet nec, commodo eget, consequat quis, neque. Aliquam faucibus, elit ut dictum aliquet, felis nisl adipiscing sapien, sed malesuada diam lacus eget erat. Cras mollis scelerisque nunc. Nullam arcu. Aliquam consequat. Curabitur augue lorem, dapibus quis, laoreet et, pretium ac, nisi. Aenean magna nisl, mollis quis, molestie eu, feugiat in, orci. In hac habitasse platea dictumst."

unigrams = nltk.word_tokenize(t.lower())

for size in range(1, 6):

    unigrams = unigrams*size

    start = time.time()

    unigram_freqs = [unigrams.count(word) for word in unigrams]    
    freq_pairs = set((zip(unigrams, unigram_freqs)))
    freq_pairs = sorted(freq_pairs, key=itemgetter(1))[::-1]

    end = time.time()

    time_elapsed = round(end-start, 3)

    print("Runtime: " + str(time_elapsed) + "s for " + str(size) + "x the size")

# Runtime: 0.001s for 1x the size
# Runtime: 0.003s for 2x the size
# Runtime: 0.022s for 3x the size
# Runtime: 0.33s for 4x the size 
# Runtime: 8.065s for 5x the size

1 Ответ

3 голосов
/ 29 марта 2020

Используя счетчик из коллекций и сортировку с помощью функции-члена «most_common ()», я получаю почти 0 секунд независимо от размера: 

import nltk
nltk.download('punkt')


from operator import itemgetter
from collections import Counter
import time
t = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum. Curabitur pretium tincidunt lacus. Nulla gravida orci a odio. Nullam varius, turpis et commodo pharetra, est eros bibendum elit, nec luctus magna felis sollicitudin mauris. Integer in mauris eu nibh euismod gravida. Duis ac tellus et risus vulputate vehicula. Donec lobortis risus a elit. Etiam tempor. Ut ullamcorper, ligula eu tempor congue, eros est euismod turpis, id tincidunt sapien risus a quam. Maecenas fermentum consequat mi. Donec fermentum. Pellentesque malesuada nulla a mi. Duis sapien sem, aliquet nec, commodo eget, consequat quis, neque. Aliquam faucibus, elit ut dictum aliquet, felis nisl adipiscing sapien, sed malesuada diam lacus eget erat. Cras mollis scelerisque nunc. Nullam arcu. Aliquam consequat. Curabitur augue lorem, dapibus quis, laoreet et, pretium ac, nisi. Aenean magna nisl, mollis quis, molestie eu, feugiat in, orci. In hac habitasse platea dictumst."

unigrams = nltk.word_tokenize(t.lower())

for size in range(1, 5):

    unigrams = unigrams*size

    start = time.time()

    unigram_freqs = [unigrams.count(word) for word in unigrams]    
    freq_pairs = set((zip(unigrams, unigram_freqs)))
    freq_pairs = sorted(freq_pairs, key=itemgetter(1))[::-1]

    end = time.time()

    time_elapsed = round(end-start, 3)

    print("Slow Runtime: " + str(time_elapsed) + "s for " + str(size) + "x the size")

    start = time.time()
    a = Counter(unigrams).most_common()
    #print(a)
    end = time.time()

    time_elapsed = round(end-start, 3)

    print("Fast Runtime: " + str(time_elapsed) + "s for " + str(size) + "x the size")

Медленное время выполнения: 0,003 с для 1x размера

Быстрое время выполнения: 0,0 с для 1x размера

Медленное время выполнения: 0,006 с для 2x размера

Быстрое время выполнения: 0,0 с для 2x размера

Медленно Время выполнения: 0,157 с для 3-кратного размера

Быстрое время выполнения: 0,0 с для 3-кратного размера

Медленное время выполнения: 1,889 с для 4-кратного размера

Быстрое время выполнения: 0,001 с для 4x размер

...