эффективно сравнивать список с набором

#python #list #set #compare

#python #Список #набор #Сравнить

Вопрос:

Есть ли более эффективный способ убедиться, что a list содержит все и только элементы set другого, а затем создает другой set из list ?

Например. что-то, что позволяет избежать копирования и сортировки списка а-ля

 s = set([ 1, 2, 3, 4 ])
l = [ 1, 2, 3, 5 ]
if s!=set(l):
    print "bad list"

1. поэтому я предполагаю, что у меня могут быть дубликаты. Если вы действительно заботитесь о том, чтобы не создавать новый объект, тогда просто выполните итерацию по списку и сделайте его недействительным, если какого-либо элемента нет в наборе. набор __contains__ выполняется быстро, но, вероятно, не быстрее, чем новый набор

2. я имею в виду, это довольно эффективно. наборы отлично подходят для сравнения. Если пространство действительно не критично, ваш выигрыш в лучшем случае будет незначительным. Итак, действительно ли пространство так важно?

3. @modesitt Возможно, я захочу разрешить дубликаты. @Paritosh Ну, как я уже сказал, я ищу способ избежать копирования и сортировки, которые выполнялись бы set конструктором. Считайте это теоретическим вопросом с этими требованиями.

Ответ №1:

Вы можете избежать создания другого набора из списка, вызвав symmetric_difference метод набора со списком:

 if s.symmetric_difference(l):
    print "bad list"

Ответ №2:

Если вы хотите разрешить дубликаты, вам понадобится какое-то дополнительное пространство для отслеживания вещей. Однако теперь выбор можно упростить, либо повторив пробел для списка, либо для набора. Если список обычно больше, чем набор, первая функция может сэкономить некоторое пространство. Но осторожно: это займет больше места, если набор больше, чем список.

 s = set([ 1, 2, 3, 4 ])
l = [ 1, 2, 3, 5 ]

Подход 1: создает счетчик в порядке набора

 def low_space_compare(some_set, some_list):        
    from collections import Counter
    state = Counter(some_set)    
    for item in some_list:
        if item not in state:
            print("bad")
            return "bad"
        state[item] -= 1
    if any(val > 0 for val in state.values()): #change to val != 0 if duplicates not allowed
        print("bad")
        return "bad"
    return "good"

С другой стороны, если дубликаты также не разрешены, вы могли бы просто выполнить итерацию по списку и удалить из набора, вообще не требуя дополнительного места. Но это изменяет набор!!!

Подход 2: нет дополнительного пространства, не может обрабатывать дубликаты

 def low_space_compare_no_dupes(some_set, some_list):
    #need to create a copy of some_set if you (hopefully) take offense to mutating the original set
    for item in some_list:
        if item not in some_set:
            print("bad")
            return "bad"
        else:
            some_set.remove(item) #this makes a dupe value fail when you see it again
    if some_set:
        print("bad, set had extra stuff")
        return "bad"
    return "good"

low_space_compare(s, l) #bad
low_space_compare_no_dupes(s, l) #bad
print(s) #{4} uh oh.

Редактировать: Подход 3: наихудший случай аналогичен созданию нового набора из списка n в случае, когда его допустимое соответствие, но короткое замыкание:

 def low_space_compare_no_counters(some_set, some_list):
    new_set = set()
    #need to create a copy of some_set if you (hopefully) take offense to mutating the original set
    for item in some_list:
        if item not in some_set:
            if item not in new_set:
                print("bad")
                return "bad"
            else:
                pass #ah, a dupe, keep going           
        else:
            some_set.remove(item)
            new_set.add(item)

    if some_set:
        print("bad, set had extra stuff")
        return "bad"
    return "good"

low_space_compare_no_counters(s, l)