upper Python-verificar se uma lista é um subconjunto da outra




upper python (12)

Eu preciso verificar se uma lista é um subconjunto de outro - um retorno booleano é tudo que eu procuro.
Está testando igualdade na lista menor após uma interseção a maneira mais rápida de fazer isso?
O desempenho é de extrema importância, dada a quantidade de conjuntos de dados que precisam ser comparados.
Adicionando mais fatos com base em discussões:

  1. Alguma das listas será a mesma para muitos testes?
    Faz como um deles é uma tabela de pesquisa estática
  2. Precisa ser uma lista?
    Não - a tabela de pesquisa estática pode ser qualquer coisa que tenha melhor desempenho.
    A dinâmica é um dict do qual extraímos as chaves para realizar uma pesquisa estática.

Qual seria a solução ideal dada a situação?


A teoria dos conjuntos é inadequada para listas, pois as duplicatas resultarão em respostas erradas usando a teoria dos conjuntos.

Por exemplo:

a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
set(b) > set(a)

não tem significado. Sim, dá uma resposta falsa, mas isso não está correto, já que a teoria dos conjuntos está apenas comparando: 1,3,5 versus 1,3,4,5. Você deve incluir todas as duplicatas.

Em vez disso, você deve contar cada ocorrência de cada item e fazer um valor maior que o equivalente a verificar. Isso não é muito caro, porque não está usando operações O (N ^ 2) e não requer classificação rápida.

#!/usr/bin/env python

from collections import Counter

def containedInFirst(a, b):
  a_count = Counter(a)
  b_count = Counter(b)
  for key in b_count:
    if a_count.has_key(key) == False:
      return False
    if b_count[key] > a_count[key]:
      return False
  return True


a = [1, 3, 3, 3, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

a = [1, 3, 3, 3, 4, 4, 5]
b = [1, 3, 3, 4, 5]
print "b in a: ", containedInFirst(a, b)

Então, executando isso, você obtém:

$ python contained.py 
b in a:  False
b in a:  True

A função de desempenho que o Python fornece para isso é set.issubset . Ele tem algumas restrições que não deixam claro se é a resposta à sua pergunta, no entanto.

Uma lista pode conter itens várias vezes e tem um pedido específico. Um conjunto não. Para obter conjuntos de alto desempenho, trabalhe somente em objetos hashable .

Você está perguntando sobre subconjunto ou subsequência (o que significa que você vai querer um algoritmo de busca de string)? Alguma das listas será a mesma para muitos testes? Quais são os tipos de dados contidos na lista? E para isso, precisa ser uma lista?

Sua outra postagem cruzou um dicionário e uma lista tornou os tipos mais claros e obteve uma recomendação de usar as principais exibições de dicionário para sua funcionalidade funcional. Nesse caso, sabia-se que funcionava porque as chaves do dicionário se comportavam como um conjunto (tanto que, antes de configurarmos o Python, usamos dicionários). Alguém se pergunta como a questão ficou menos específica em três horas.


Eu sei que está atrasado, mas só queria atualizar a resposta com o que funcionou para mim (Python 3)

# var 1
x = [1,2,3,4]
#  var 2
y = [1,2]

# check if var2 is subset of var1
all([z in x for z in y])

Felicidades.


Perdoe-me se estiver atrasado para a festa. ;)

Para verificar se um set A é set A subconjunto do set B , o Python possui A.issubset(B) e A <= B Ele funciona apenas no set e funciona muito bem, mas a complexidade da implementação interna é desconhecida. Referência: https://docs.python.org/2/library/sets.html#set-objects

Eu criei um algoritmo para verificar se a list A é um subconjunto da list B com as seguintes observações.

  • Para reduzir a complexidade de encontrar um subconjunto, considero apropriado sort duas listas antes de comparar elementos para se qualificar para o subconjunto.
  • Isso me ajudou a break o loop quando o valor do elemento da segunda lista B[j] é maior que o valor do elemento da primeira lista A[i] .
  • last_index_j é usado para iniciar o loop over da list B última vez que foi interrompido. Isso ajuda a evitar iniciar comparações a partir do início da list B (que é, como você pode imaginar desnecessário, iniciar a list B do index 0 em iterations subseqüentes).
  • A complexidade será O(n ln n) para ordenar ambas as listas e O(n) para verificar o subconjunto.
    O(n ln n) + O(n ln n) + O(n) = O(n ln n) .

  • O código tem muitas instruções de print para ver o que está acontecendo em cada iteration do loop . Estes são destinados apenas para compreensão.

Verificar se uma lista é um subconjunto de outra lista

is_subset = True;

A = [9, 3, 11, 1, 7, 2];
B = [11, 4, 6, 2, 15, 1, 9, 8, 5, 3];

print(A, B);

# skip checking if list A has elements more than list B
if len(A) > len(B):
    is_subset = False;
else:
    # complexity of sorting using quicksort or merge sort: O(n ln n)
    # use best sorting algorithm available to minimize complexity
    A.sort();
    B.sort();

    print(A, B);

    # complexity: O(n^2)
    # for a in A:
    #   if a not in B:
    #       is_subset = False;
    #       break;

    # complexity: O(n)
    is_found = False;
    last_index_j = 0;

    for i in range(len(A)):
        for j in range(last_index_j, len(B)):
            is_found = False;

            print("i=" + str(i) + ", j=" + str(j) + ", " + str(A[i]) + "==" + str(B[j]) + "?");

            if B[j] <= A[i]:
                if A[i] == B[j]:
                    is_found = True;
                last_index_j = j;
            else:
                is_found = False;
                break;

            if is_found:
                print("Found: " + str(A[i]));
                last_index_j = last_index_j + 1;
                break;
            else:
                print("Not found: " + str(A[i]));

        if is_found == False:
            is_subset = False;
            break;

print("subset") if is_subset else print("not subset");

Saída

[9, 3, 11, 1, 7, 2] [11, 4, 6, 2, 15, 1, 9, 8, 5, 3]
[1, 2, 3, 7, 9, 11] [1, 2, 3, 4, 5, 6, 8, 9, 11, 15]
i=0, j=0, 1==1?
Found: 1
i=1, j=1, 2==1?
Not found: 2
i=1, j=2, 2==2?
Found: 2
i=2, j=3, 3==3?
Found: 3
i=3, j=4, 7==4?
Not found: 7
i=3, j=5, 7==5?
Not found: 7
i=3, j=6, 7==6?
Not found: 7
i=3, j=7, 7==8?
not subset

Assumindo que os itens são hashable

>>> from collections import Counter
>>> not Counter([1, 2]) - Counter([1])
False
>>> not Counter([1, 2]) - Counter([1, 2])
True
>>> not Counter([1, 2, 2]) - Counter([1, 2])
False

Se você não se importa com itens duplicados, por exemplo. [1, 2, 2] e [1, 2] depois é só usar:

>>> set([1, 2, 2]).issubset([1, 2])
True

Está testando igualdade na lista menor após uma interseção a maneira mais rápida de fazer isso?

.issubset será a maneira mais rápida de fazer isso. Verificar o tamanho antes de testar o issubset não aumentará a velocidade porque você ainda tem itens O (N + M) para percorrer e verificar.


>>> a = [1, 3, 5]
>>> b = [1, 3, 5, 8]
>>> c = [3, 5, 9]
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

>>> a = ['yes', 'no', 'hmm']
>>> b = ['yes', 'no', 'hmm', 'well']
>>> c = ['sorry', 'no', 'hmm']
>>> 
>>> set(a) <= set(b)
True
>>> set(c) <= set(b)
False

Se a2 is subset of a1 , então Length of set(a1 + a2) == Length of set(a1)

a1 = [1, 2, 3, 4, 5];
a2 = [1, 2, 3];

len(set(a1)) == len(set(a1 + a2))

Se você está perguntando se uma lista está "contida" em outra lista, então:

>>>if listA in listB: return True

Se você está perguntando se cada elemento na lista A tem um número igual de elementos correspondentes em listB tente:

all(True if listA.count(item) <= listB.count(item) else False for item in listA)

Aqui está como eu sei se uma lista é um subconjunto de outra, a seqüência é importante para mim no meu caso.

def is_subset(list_long,list_short):
    short_length = len(list_short)
    subset_list = []
    for i in range(len(list_long)-short_length+1):
        subset_list.append(list_long[i:i+short_length])
    if list_short in subset_list:
        return True
    else: return False

Tente bit a bit E

>>> set([1,2]) & set([1,2,3])
set([1, 2])
>>> set([0]) & set([1,2,3])
set([])

Ainda não o perfilei.


Mais uma solução seria usar uma intersection .

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one).intersection(set(two)) == set(one)

A intersecção dos conjuntos conteria do set one

(OU)

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(one) & (set(two)) == set(one)

one = [1, 2, 3]
two = [9, 8, 5, 3, 2, 1]

set(x in two for x in one) == set([True])

Se list1 estiver na lista 2:

  • (x in two for x in one) gera uma lista de True .

  • quando fazemos um set(x in two for x in one) tem apenas um elemento (True).





list