Searching for matching attributes

Question

My special objects have one list of attribute-values (that is a varying list of abbreviated strings of short but differing length meaning some capabilities of any object) → ['A', 'B', 'AC', 'BC', ...]

running the program I'm searching for at least one existing match out of a varying search-list → ['BC', 'BP', 'X', ...]

At the moment I solved that by iterating over each search-list element using an in-operation against every attribute-list-like:

for e in all_elements:
    for a in valid_attributes:
        if a in e.capabilities:
            handle_match(e, a)

For only a handful of attributes and few elements, it will be endurable in need of time, but...

The further problem: get all a-values at once and handle them in same moment and after that continuing with next e-element.

I thought for a moment about to give each a-value a bit-position inside a big word of currently around 320 bit width and check any occurrence by an and-operation; other idea to use an enumeration for attributes; but my tries hadn't been successful so far.

Does anyone have a better and easier idea? Currently my 1½ year knowledge of Python looks insufficient.

capabilties are strings of length 1,2 or 3 characters, all string-values are unique in elements as well in valid-attributes, 'A', 'B' vs. 'AB' or 'BA' has no common feature or meaning

score 0 · Accepted Answer · answered Apr 22 '22 at 00:07

0

If the attributes are not repeated you can store them as a set instead and calculate the intersection:

for e in all_elements:
    if len(valid_attributes.intersection(e.capabilities))>0:
        handle_match(e, a)

Or at a greater space sacrifice you can store the attribute list as a sparse binary list, where each element represents the existence of some attribute. Then you can check attributes in constant time.

answered Apr 22 '22 at 00:07

Stanley

321
2
6

thanks - the idea to use sets from @martineau and yours to use intersection soved it – Berthold Apr 23 '22 at 18:33

score 0 · Answer 2 · answered Apr 22 '22 at 00:16

If the attribute string values are unique, you could use sets to quickly determine which ones are value by handling the results of using the set & intersection operator:

class Element:
    def __init__(self, *capabilities):
        self.capabilities = set(capabilities)
    def __repr__(self):
        return f'Element({repr(self.capabilities)})'

VALID_ATTRIBUTES = {'A', 'B', 'AC', 'BC'}

all_elements = [Element('A', 'B'), Element('A', 'AC'), Element(),
                Element('D', 'BC')]

def handle_match(e, a):
    print(f'handle_match({e=!r}, {a=!r})')

for e in all_elements:
    for a in (e.capabilities & VALID_ATTRIBUTES):
        handle_match(e, a)

Results:

handle_match(e=Element({'B', 'A'}), a='B')
handle_match(e=Element({'B', 'A'}), a='A')
handle_match(e=Element({'AC', 'A'}), a='AC')
handle_match(e=Element({'AC', 'A'}), a='A')
handle_match(e=Element({'D', 'BC'}), a='BC')

the idea to use a set ( :-) that's my bit-array) instead of a list (I was a bit blocked by myself to put also strings of more than 1 character as an value of a set) is really the break through - but as like in next answer from @Stanley written; i prefer to compare sets with intersection, that will solve my problem not to handle an element more than one time with a single capability - thanks for help — Berthold, Apr 23 '22 at 18:31
My answer ***is*** using sets (not lists) to calculate the intersection of the set of capabilities and the set of valid attributes i`for a in (e.capabilities & VALID_ATTRIBUTES):` is because it looks like you want to handle of the elements in the intersection individually — as you're doing by calling `handle_match()` multiple times in the code in your question. — martineau, Apr 23 '22 at 20:08

Searching for matching attributes

2 Answers2