1
\$\begingroup\$

I would appreciate to have your opinion on this code and whether I can refactor it and make it cleaner. I don't like the fact that I have 3 nested for loops, which makes the complexity of this code O(n³).

    categories = {}
    for k1, v1 in res["relationship_types"].items():
        for k2, v2 in res["remote_types"].items():
            count = 0
            for k3, v3 in RELATIONSHIPS_CATEGORIES.items():
                relationship_types = v3["relationship_types"]
                if k1 in relationship_types:
                    target_types = v3["target_types"]
                    if len(target_types) == 0:
                        count = v1
                        categories[k3] = count
                        break
                    elif k2 in target_types:
                        count = min(v1, v2)

                    if k3 in categories:
                        categories[k3] += count
                    else:
                        categories[k3] = count

This is my res:

res={'remote_types': {'identity': 2, 'location': 1, 'indicator': 2}, 'relationship_types': {'targets': 2, 'uses': 1, 'indicates': 2}}

And this is my RELATIONSHIP_CATEGORIES:

RELATIONSHIPS_CATEGORIES = {
    "campaigns": {
        "relationship_types": ["targets"],
        "target_types": ["identity"],
    },
    "ttps": {
        "relationship_types": ["uses"],
        "target_types": ["attack-pattern"],
    }
}

What I want to do is calculate how many categories I can construct based on my res dictionary.

For instance, for the category campaigns of RELATIONSHIPS_CATEGORIES I need to have at least one targets in my res["relationship_types"] and one identity in my res["remote_types"], but since I have 2 of each, my categories dictionary would look like:

categories = {
    "campaigns": 2,
}
\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Please check that I haven't misrepresented your code, and correct it if I have. \$\endgroup\$ Jan 24, 2022 at 13:37
  • \$\begingroup\$ The actual dictionary produced does not look like your example and also includes 'ttps': 0. Is this intended? \$\endgroup\$
    – Reinderien
    Jan 24, 2022 at 15:26

1 Answer 1

1
\$\begingroup\$

Your logic is pretty convoluted, not helped by your mystery k1, k2 (etc.) names. So far as I can tell, you shouldn't be doing any length comparison. Use more meaningful variable names, replace your confusing target_types mapping with direct reference to remote_types, and you have

res = {
    'remote_types': {'identity': 2, 'location': 1, 'indicator': 2},
    'relationship_types': {'targets': 2, 'uses': 1, 'indicates': 2},
}

RELATIONSHIPS_CATEGORIES = {
    'campaigns': {
        'relationship_types': ['targets'],
        'remote_types': ['identity'],
    },
    'ttps': {
        'relationship_types': ['uses'],
        'remote_types': ['attack-pattern'],
    },
}

categories = {
    rel_key: min(
        res_items.get(criterion, 0)
        for res_items, criteria in (
            (res.get(criterion_key, {}), criteria)
            for criterion_key, criteria in rel_criteria.items()
        )
        for criterion in criteria
    )
    for rel_key, rel_criteria in RELATIONSHIPS_CATEGORIES.items()
}
print(categories)

or perhaps more legibly

def count_criteria(rel_criteria: dict[str, list[str]]) -> Iterator[int]:
    for criterion_key, criteria in rel_criteria.items():
        res_items = res.get(criterion_key, {})
        for criterion in criteria:
            yield res_items.get(criterion, 0)

categories = {
    rel_key: min(count_criteria(rel_criteria))
    for rel_key, rel_criteria in RELATIONSHIPS_CATEGORIES.items()
}

both resulting in

{'campaigns': 2, 'ttps': 0}

It's not the fastest thing in the world, but strictly speaking this is not true:

the complexity of this code [is] O(n³)

because your iterations are iterating over dimensions of potentially different sizes. You have not given any hints as to the scale of your problem, so all optimisation may be premature, but if you really needed to run complexity analysis you'd find O(mnp) with m, n and p each a separate dimension. If enough of those dimensions stay constant and low you can effectively consider them to be 1.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.