Adding unique items to list. Do I need to be concerned of performance?

user_11129123 0
Viewed 73

I want to check whether new items have appeared in the list B in each iteration of a simulation and if so append the new value(s) to A. From my research, I have come to the conclusion that this is the most common way to solve this (not using sets, I want to keep the list ordered):

A = ['aa', 'bb', 'cc']
B = ['aa', 'bb', 'cc', 'dd','ee'] # Read only

[A.append(b) for b in B if not b in A]

However, this approach seems quite computationally heavy and I wonder if this concern is justified? And if so, is there another approach with better performance?

I know that B will not be updated that often (probably in much less than 1% of the iterations), and that A might hold more values that are not present in B but should be kept.

python-3.x list python
3 Answers

You could only do it for new items added to B, rather than all, by intercepting the append/insert/extend calls. Then just apply your logic to only incoming elements.

Should more or less fit with your requirements as B doesn't get frequent updates but is apparently liable to grow quite large. If you wanted to get really fancy, you could even manage a set to hold already-in-A values, but that's trading memory for speed and I'd wait to see actual profiling to see if the complexity was worthwhile.

A = ['aa', 'bb', 'cc']
B = ['aa', 'bb', 'cc', 'dd','ee'] # Read only

[A.append(b) for b in B if not b in A]

class myB:

    def __init__(self, A, B):
        self.li = B
        self.A = A

    def insert(self, i, x):
        self.li.insert(i, x)
        if not x in self.A:
            self.A.append(x)

    def append(self, x):
        self.li.append(x)

        if not x in self.A:
            self.A.append(x)

    #override extend...


#set up intercept
B2 = myB(A, B)

print(f"ante:{A=}")
print(f"ante:{B=}")

B2.append("xx")
B2.append("ee")

print(f"\npost:{A=}")

You could have also use class myB(list):, i.e. subclassing rather than decorating.

output:

ante:A=['aa', 'bb', 'cc', 'dd', 'ee']
ante:B=['aa', 'bb', 'cc', 'dd', 'ee']

post:A=['aa', 'bb', 'cc', 'dd', 'ee', 'xx']

p.s. not to be too nitpicky, but Python naming conventions strongly discourage capitalized variable names like A, Bcd, those generally signal you're dealing with class variables.

user_13943530

Don't use list where set is more appropriate (and much faster in terms of O(n)). As a simple example,

a_list, b_list = ['aa', 'bb'], ['aa', 'cc']
a_set = set(a_list)
for b in b_list:
    if b in a_set:
        continue
    a_set.add(b)
    a_list.append(b)

Check the docs for more details.

P.S. That's a classical trade-off: you sacrifice RAM for performance sake.

user_74938400

Updating a dict with dummy values may be faster and the list (of keys) remains ordered. This works, however, in Python >=3.6. For previous versions you could use from collections import OrderedDict.

unique_elems = {'aa': None, 'bb': None, 'ee': None}
unique_elems.update({'aa': None, 'cc': None, })
list(unique_elems.keys())

['aa', 'bb', 'ee', 'cc']
user_141756010
Related