CODEWITHSUNDEEP
pythoniteration
Johnny Metz
Johnny Metz

Reputation: 5965

python: determine if list A contains a value different from list B

I'm trying to determine if a list A contains a value different from two other values, which make up list B (0 and 1):

[0, 1, 0, 1, 0]  # False
[0, 0, 0, 0, 0]  # False
[1, 1, 1, 1, 1]  # False
[0, 1, 0, 2, 0]  # True

Here's what I have so far but I feel like there's a nice one-liner or a generally much more efficient way:

indicator = False
A = [0, 1, 0, 2, 0]
B = [0, 1]
for i in A:
    if i not in B:
        indicator = True

Upvotes: 1

Views: 330

Answers (2)

user1620443
user1620443

Reputation: 794

The complexity of a solution is at best linear, meaning that in the worst case you will have to check all the items in the list. That's, however, the worst case. So, if performance is the issue, you can just stop when you find the first different value:

for i in A:
    if i not in B:
       indicator = True
       break

If in a very long list of 20 billion values the first item is already not in B, the outer loop will execute only one time and exit, instead of 20 billion! It will not guarantee you to run faster -the algorithm is still linear, if you can stop earlier depends on the values in the list- but with a bit of luck you may end up saving a significant amount of time.

Also note that the i not in B, as it is, is linear in complexity. Every time you execute that line, it will implicitly iterate on the B list values. If A contains N elements and B contains M elements, the total number of operations will be N*M in the worst case scenario. For very small M is ok, but for large lists of values you could consider a set. If B is a set, the check i not in B would be executed in constant time, so that the total number of operations will scale only with N.

If your problem is having a one-liner, as previous answer pointed out, a set is a collection of unique items, so using them you can obtain elegant one-liners with linear complexity. My version:

indicator = not(set(array) == set(allowed_values))

Generating the set, however, requires to read all the input array, which again could be slower than the first solution when you have very large arrays and you're in a lucky situation: for example when the first number of the array is not in your accepted values.

Upvotes: 1

utengr
utengr

Reputation: 3355

You can use set.issubset() for this purpose. 

if not set(A).issubset(B):
    print("True")
else:
    print("False")

Input: 

A = [0, 1, 0, 2, 0]
B = [0, 1]

Output: True

Input:

A = [0, 1, 0, 1, 0]
B = [0, 1]

Output: False

Upvotes: 3

Related Questions