Блог

Главная - Вопросы по программированию - Python: лучше использовать dictionary или hashmap для общих элементов массива

Python: лучше использовать dictionary или hashmap для общих элементов массива

#python #algorithm

#python #алгоритм

Вопрос:

Я должен найти список общих чисел из 2 неупорядоченных списков. У меня есть 2 подхода. Кто-нибудь может объяснить, какой из них лучше и почему

 def common_by_dictionary(a1,a2):
    d1 = {}
    for i in a1:
        if not(i in d1):
            d1[i]=1
    for i in a2:
        if (i in d1):
            d1[i]=0
    c = []
    for i in d1:
        if(d1[i]==0):
            c.append(i)
    print c

def common_by_hashmap(a1,a2):
    h = [0]*1000
    for i in a1:
        if not (i in h):
            h[i]=1
    c = []
    for i in a2:
        if(h[i]==1):
            c.append(i)
    print c



common_by_dictionary([1,3,4,6,7,9,12,5],[1,2,4,5,9,10,3])
common_by_hashmap([1,3,4,6,7,9,12,5],[1,2,4,5,9,10,3])

Комментарии:

1. Вы не используете hashmap в common_by_hashmap , вы используете list , который реализован как динамический массив. Действительно, a dict реализован как hashmap, поэтому вы используете hashmap в common_by_dictionary . Подход, основанный на словаре, более эффективен, чем подход, основанный на списке. Если вы собираетесь использовать вспомогательное хранилище, set был бы наиболее идиоматичным подходом с характеристиками производительности, аналогичными подходу на основе dict

Ответ №1:

Вы должны использовать set :

 def common(first, second):
    return set(first) amp; set(second)

Ответ №2:

В python нет хэш-карты. Словарь по сути является java-эквивалентом hash map. Вы просто используете list (массив) в своей common_by_hashmap функции

Ответ №3:

Первый вариант лучше. Во втором, эта часть:

     for i in a1:
        if not (i in h):
            h[i]=1

имеет сложность O (N ^ 2), потому что i in h требует O (N) операций. Хотя в этом случае N может быть константой 1000, это все равно значительно медленнее, чем запрос dict.

Но ИМО, правильный подход к вашей проблеме — использовать set, как указано Lim:

 def common_by_set(a1, a2):
    return list(set(a1) amp; set(a2))