5
\$\begingroup\$

A binary relation \$R\$ on a set \$A\$ is called reflexive if and only if \$R(a, a)\$ for every element \$a \in A\$.

I want to know if there can be any improvements made on the function below to make it more efficient.

def reflexive(R):
    '''
    @param R : set containing homogenous elements
    '''
    result = []
    a = []
    y = []

    for a1, a2 in R:
        if (a1 == a2):
            result.append((a1,a2))
            y.append(a1)

        if (a1 not in a):
            a.append(a1) #contains list of a0

    if (set(a) == set(y)):
        print("Reflexive")
        return (result, True)

    print("Not Reflexive")
    return ([] , False)

Test case:

R2 = reflexive([(1, 3), (1, 5), (3, 1), (3, 5), (7, 5)])

Not Reflexive
[]
\$\endgroup\$
  • \$\begingroup\$ reflexive([(1, 1), (1, 2)]) prints "Reflexive". I would consider this a bug, since the input implies that the number 2 is an element of A and is not related to itself. \$\endgroup\$ – mkrieger1 Jan 12 '17 at 18:42
  • \$\begingroup\$ @mkrieger1 I believe that that is the intended behaviour, if you consider that the set A is {1}. \$\endgroup\$ – 200_success Jan 12 '17 at 19:27
  • \$\begingroup\$ @200_success But then, how would I be able to use the function if I wanted to consider the sets {1, 2}, or {1, 2, 3}, where still only (1, 1) and (1, 2) were related? \$\endgroup\$ – mkrieger1 Jan 12 '17 at 19:35
  • \$\begingroup\$ @mkrieger1 It is pretty weird, though, that reflexive([(1,1), (2,2), (1,3)]) is True, but reflexive([(1,1), (2,2), (3,1)]) is False. I think you are right that there is a fundamental problem with the function. \$\endgroup\$ – 200_success Jan 12 '17 at 20:01
  • \$\begingroup\$ @200_success That is exactly what I tried out after reading your docstring, but hesitated to post a comment, because I think I haven't understood it well enough ;) \$\endgroup\$ – mkrieger1 Jan 12 '17 at 20:03
8
\$\begingroup\$

Performance

It takes a very long time to conclude that reflexive((a, a) for a in range(100000)) is true. The main culprit is

if (a1 not in a):

Since a is a list, the not in test involves a linear scan, such that your entire function is \$\Omega(\left|R\right|^2)\$. Ideally, it should be \$O(\left|R\right|)\$.

Interface

The docstring is insufficient to describe what the function does. In addition to a better description, I recommend adding doctests.

A function like this shouldn't print anything as a side-effect.

It would be more conventional to return True/False as the first element of the result rather than the second.

I don't think that there is any benefit to returning an ordered list; a set would be more appropriate.

Suggested solution

I'd write it this way, taking advantage of generator expressions to make it shorter.

def reflexive(R):
    """
    Determine whether the binary relation R on a set A is reflexive, and if so,
    which elements of R are essential for it to be reflexive.

    R is an iterable of homogeneous pairs.

    >>> reflexive([(1, 1), (2, 2), (3, 1)])
    (False, set())

    >>> is_reflexive, essential = reflexive([(1, 1), (2, 2), (2, 1)])
    >>> is_reflexive
    True
    >>> essential == {(1, 1), (2, 2)}
    True

    >>> reflexive((a, a) for a in range(100000))[0]
    True
    """
    R = list(R)
    A = set(a for a, _ in R)
    result = set(ab for ab in R if ab[0] == ab[1])
    return (True, result) if len(A) == len(result) else (False, set())
\$\endgroup\$
  • \$\begingroup\$ Wow. This is clean! I got a long way to go \$\endgroup\$ – Joseph Jan 12 '17 at 19:52
  • \$\begingroup\$ Also, I didn't even notice that checking if an element is in the list was of O(n) time, like you said effectively making it O(n^2) \$\endgroup\$ – Joseph Jan 12 '17 at 19:53
  • \$\begingroup\$ what is this Ohm-notation? \$\endgroup\$ – cat Jan 12 '17 at 22:12
  • \$\begingroup\$ @cat Big-Omega is a stricter statement than Big-O. (Side note: I find "Big Omega" to be a funny name, since "omega" itself means "big O" in Greek.) \$\endgroup\$ – 200_success Jan 12 '17 at 22:43
  • 1
    \$\begingroup\$ Why not write as result = set((a, b) for a, b in R if a == b) \$\endgroup\$ – janos Jan 13 '17 at 7:08
10
\$\begingroup\$

Regardless of whether the function is actually correct or not, there are some issues that could be improved:

  1. I would expect a function that is supposed to determine whether a relation \$R\$ over a set \$A\$ is reflexive to take two arguments:

    • The relation \$R\$,
    • and the set \$A\$.

    Providing only the set \$\{(a, b) | a, b \in A, R(a,b)\}\$ and deducing \$A\$ from it is insufficient, because there could be elements in \$A\$ which are not related to any other element. This could lead to a false positive result.

  2. I would expect the function to only return a boolean value, and to have no side effects like printing its result. Leave that to the caller.

  3. The docstring of the function does not explain well enough what it expects as its argument, and does not explain at all what the function does.

  4. a and y are poorly named. What is their meaning?

  5. Instead of creating a and y a as lists to which is appended (needlessly checking if elements are already contained), only to convert them to sets at the end, why don't you just create them as sets in the first place and add to them?

  6. Parentheses are not needed around conditions in if statements:

    if a1 == a2:
    if a1 not in a:
    if set(a) == set(y):
    

    (also technically not around the returned tuples)

    return result, True
    return [], False
    
  7. This comment confuses me: What is a0?

    if (a1 not in a):
        a.append(a1) #contains list of a0
    

    You better just remove the comment.

\$\endgroup\$

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.