Реализация Python HashTable быстрее, чем итерация списка? - PullRequest
Новая
       7

Реализация Python HashTable быстрее, чем итерация списка?

0 голосов
/ 15 мая 2018

Это проблема от HackerRank . Моя реализация, показанная ниже, проходит большую часть теста, но для тестов, которые она провалила, говорится, что она занимает слишком много времени. Посмотрев другие материалы, я обнаружил, что реализация другого пользователя (кредит saikiran9194 ) почти сразу проходит все тесты. Мне действительно трудно понять, почему его решение является наиболее эффективным в масштабе.

Моя реализация: 

m, n = map(int, input().strip().split(' '))
magazine = input().strip().split(' ')
ransom = input().strip().split(' ')
yesNo = "Yes"
for i in ransom:
    if(ransom.count(i) > magazine.count(i)):
        yesNo = "No"
print(yesNo)

Более эффективное по времени внедрение 

def ransom_note(magazine, ransom):
    rc = {} # dict of word: count of that word in the note
    for word in ransom:
        if word not in rc:
            rc[word] = 0
        rc[word] += 1

    for word in magazine:
        if word in rc:
            rc[word] -= 1
            if rc[word] == 0:
                del rc[word]
                if not rc:
                    return True
    return False

m, n = map(int, input().strip().split(' '))
magazine = input().strip().split(' ')
ransom = input().strip().split(' ')
answer = ransom_note(magazine, ransom)
if(answer):
    print("Yes")
else:
    print("No")

Ответы [ 2 ]

0 голосов
/ 15 мая 2018

list.count имеет линейную сложность, поэтому ваш код имеет квадратичную сложность в целом, выполняя линейную работу на каждой итерации цикла.Если сначала поместить списки в dict, то нужно только O (1), чтобы получить счет для определенной буквы.

Вы можете просто обернуть эти списки в collections.Counter (не проверено): 

m, n = map(int, input().strip().split())
magazine = Counter(input().strip().split())
ransom = Counter(input().strip().split())
yesNo = "Yes"
for i in ransom:
    if(ransom[i] > magazine[i]):
        yesNo = "No"
print(yesNo)

или короче, используя any

yesno = "No" if any(random[i] > magazine[i] for i in ransom) else "Yes"
0 голосов
/ 15 мая 2018

Это разница между list.count и dict.__getitem__ (rc[word]).list.count равно O(n), тогда как dict.__getitem__ равно O(1) из-за, как вы упоминаете, хеширования.

Источник: https://wiki.python.org/moin/TimeComplexity

...