5
\$\begingroup\$

I have a real-world problem involving finding the best known term from a string containing sets of terms. We have Term objects that are comparable in that they have a method a_term.is_better_than(other_term). This method is Boolean -- if it returns False, then a_term may be as good as other_term, but isn't better.

Using this method, I need to pare down a set of terms to the best ones. The best way I've been able to think about this is to compare pairs of terms and eliminate any terms when one isn't as good as the other, something like this:

def get_best_terms(terms: Set[Term]): Set[Term]
    best_terms = set()
    m_terms = list(terms)
    while m_terms:
        term = m_terms.pop()
        for i in reversed(range(len(m_terms))):
            if term.is_better_than(m_terms[i]):
                del m_terms[i]
            if m_terms[i].is_better_than(term):
                break
        else: # We never encountered the `break` statement 
            best_terms.add(term)
            break
    best_terms |= {a_term for a_term in m_terms
                   if not (term.is_better_than(a_term) or
                           a_term.is_better_than(term))}
    return best_terms

This approach is functional, but pretty gross in my opinion. For one thing, there's a lot of mutation going on here. For another, once I've identified a single best term, finding all the terms that are equally good is messy. The whole thing is hard to read.

What do you suggest?

Examples

A Term is a string with some metadata attached. For example,

a = AutoTerm(term='honda', term_span=1, term_range=(1, 2),
            original_term='CAR HONDA ACC...')
b = AutoTerm(term='2015 honda accord', term_span=2, term_range=(1, 3),
             original_term='2015 HONDA ACC...')
c = AutoTerm(term='2015 accord', ...)

Sometimes a term is a better choice because it's more specific, but there are other nuances, such as a match in a database. Let's say, arbitrarily, that b and c are equally good, but a is not as good. Then

assert get_best_terms({a, b, c}) == {b, c}

should pass.

\$\endgroup\$
  • \$\begingroup\$ Can you provide an example of Term and some example IO? \$\endgroup\$ – Peilonrayz Jul 31 '18 at 13:57
  • \$\begingroup\$ Is the ranking of Terms transitive? If Term A is better than Term B, and Term B is better than Term C, is Term A guaranteed to be better than Term C? \$\endgroup\$ – David Conrad Jul 31 '18 at 20:01
  • 1
    \$\begingroup\$ @DavidConrad yes. \$\endgroup\$ – kojiro Jul 31 '18 at 20:06
5
\$\begingroup\$
  1. You have a bug, if you remove an item in your for loop without breaking you get an IndexError. Instead use a worse set so that you know what to skip.
  2. What you seem to be doing is performing a sort, and so if you make a cmp function you can use sorted. To do this you need to use functools.cmp_to_key and then you can itertools.takewhile.

And so I'd use:

import functools
import itertools
from typing import Set, List


class Term(int):
    def is_better_than(self, other):
        return self // 2 > other // 2


def cmp(self: Term, other: Term):
    if self.is_better_than(other):
        return 1
    if other.is_better_than(self):
        return -1
    return 0


def get_best_terms(terms: Set[Term]) -> List[Term]:
    if not terms:
        return []
    terms = sorted(terms, key=functools.cmp_to_key(cmp), reverse=True)
    best = terms[0]
    return list(itertools.takewhile(lambda i: not best.is_better_than(i), terms))


print(get_best_terms(map(Term, [1, 2, 3, 4, 5])))
print(get_best_terms(map(Term, [1, 2, 3, 4])))
print(get_best_terms(map(Term, [5, 1, 2, 4, 3])))
print(get_best_terms(map(Term, [5, 1, 4, 3])))

This can however be simplified if Terms are comparable, as you won't need to use key and can remove the need for a lambda.

@functools.total_ordering
class Term(int):
    def __gt__(self, other: Term) -> bool:
        return self // 2 > other // 2

    def __eq__(self, other: Term) -> bool:
        return self // 2 == other // 2


def get_best_terms(terms: Set[Term]) -> List[Term]:
    if not terms:
        return []
    terms = sorted(terms, reverse=True)
    return list(itertools.takewhile(terms[0].__eq__, terms))
\$\endgroup\$
  • \$\begingroup\$ Yeah, this is great, thanks. I had thought about using total_ordering and sorting, but I was thinking I didn't actually need to sort. But in looking again, I think the gain in readability is worth every penny. \$\endgroup\$ – kojiro Jul 31 '18 at 15:19
  • \$\begingroup\$ "in your for without breaking" for loop? \$\endgroup\$ – Acccumulation Jul 31 '18 at 15:26
  • \$\begingroup\$ @Acccumulation Yes, I'll try make that clearer \$\endgroup\$ – Peilonrayz Jul 31 '18 at 15:27
  • \$\begingroup\$ @kojiro You didn't say in your question but is Term.is_better_than costly? Because you could make the code run in \$O(n)\$ time, with a worst case \$2n\$ calls to Term.is_best_terms if they are all equal. \$\endgroup\$ – Peilonrayz Jul 31 '18 at 15:34
  • \$\begingroup\$ It's not costly afaict. It is impossible to understand, though, which is why I am still having trouble writing a satisfactory __eq__ for total ordering. I'm also considering using max and a filter instead of takewhile, which trades the sorted for max 2x passes over the set. \$\endgroup\$ – kojiro Jul 31 '18 at 15:36
3
\$\begingroup\$

If all you want are the best terms, then it seems to me that you can just keep a list of the current best terms. Every time you find a term that at least as good as any one of the previous best terms, then, assuming transitivity, it must be at least as good as all the previous best terms. And since the previous best terms were at least as good as all the terms tested so far, the new term is at least as good as all the terms tested so for. Next you check whether the new term is strictly better than one of the current best terms. If so, then you can replace the list of best terms with a list containing just the new term. If not, then the current term is just as good as the current best terms, so you should append it to the list of best terms.

best_terms = []
for term in terms:
    if not best_terms:
        best_terms = [term]
        continue
    if not best_terms[0].is_better_than(term):
        if term.is_better_than(best_terms[0]):
            best_terms = [term]
        else
            best_terms.append(term)
\$\endgroup\$
  • 1
    \$\begingroup\$ Please tell me you changed your account name just to give this answer, because that'd be about perfect. \$\endgroup\$ – kojiro Jul 31 '18 at 15:47
  • \$\begingroup\$ Except "is_better_than" returns false if the terms are equally good. You seem to be considering otherwise... \$\endgroup\$ – coconochao Jul 31 '18 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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