сравнить список с набором эффективно - PullRequest
Новая
       22

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

0 голосов
/ 24 апреля 2019

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

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

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

Ответы [ 2 ]

3 голосов
/ 24 апреля 2019

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

if s.symmetric_difference(l):
    print "bad list"
1 голос
/ 24 апреля 2019

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

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)
...