test_chains.test_allc fails because of set ordering

[mihailescum]

I moved to a different system, and when I try to run the tests pytest always fails in test_chains.test_allc.

The reason for this is that allc returns a set which is converted to a np.array for the test assertion. But a set is unordered and on my particular machine it somehow as a different order than what is actually expected. I don't know why this happens, I installed all dependencies.

What I propose to solve this issue is to change S_left to a set and have assert S_left == S_right instead of npt.assert_equal

[mihailescum]

The solution wasn't that easy because numpy arrays are not hashable, but this little helper function does the job:

def assert_equal_unsorted(left, right):
    def arreq_in_list(a, b):
        return next((True for elem in b if np.array_equal(elem, a)), False)

    left_list = list(left)
    right_list = list(right)
    difference = [
        x
        for x in left_list + right_list
        if not arreq_in_list(x, left_list) or not arreq_in_list(x, right_list)
    ]
    assert len(difference) == 0

[seanlaw]

@mexxexx Great catch! Since the test is small and should run quickly, may I propose a simpler solution?

@pytest.mark.parametrize("Value, IR, IL", test_data)
def test_allc(Value, IR, IL):
    j = 2
    S_left = [
        np.array([1, 7, 11], dtype=np.int64),
        np.array([0], dtype=np.int64),
        np.array([3], dtype=np.int64),
        np.array([9], dtype=np.int64),
        np.array([2, 4, 6, 8, 10], dtype=np.int64),
        np.array([5], dtype=np.int64),
    ]
    C_left = np.array([2, 4, 6, 8, 10], dtype=np.int64)
    S_right, C_right = allc(IL, IR)
    # Apply length sorting followed by lexicographic sorting 
    S_left = sorted(S_left, key=lambda x: (len(x), x))
    S_right = sorted(S_right, key=lambda x: (len(x), x))
    npt.assert_equal(S_left, S_right)
    npt.assert_equal(C_left, C_right)

I have not tested this yet!

[seanlaw]

So, after sorting, the arrays should look like:

[array([0]),
 array([3]),
 array([5]),
 array([9]),
 array([ 1,  7, 11]),
 array([ 2,  4,  6,  8, 10])]

[mihailescum]

That's even better, thank you.

[seanlaw]

No, thank you! I was certainly trying to be "cute" by using set and forgot the fact that order is not guaranteed. It is wonderful to have another pair of eyes on these things! I appreciate your eye for detail 😄

[mihailescum]

Well, it was rather that my tests where failing and I was confused why 😄
Do we have to sort C too or is the order here stable? I haven't really looked into the algorithm.

[mihailescum]

Oh I just noticed that your approach doesn't work if you have two arrays of the same size but with more than one element:

>>> x = [np.arange(3), np.arange(4), np.arange(1, 4)]
[array([0, 1, 2]), array([0, 1, 2, 3]), array([1, 2, 3])]
>>> sorted(x, key=lambda x: (len(x), x))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

[seanlaw]

That is perplexing because it does work for the original input from the test case:

S_left = [
        np.array([1, 7, 11], dtype=np.int64),
        np.array([0], dtype=np.int64),
        np.array([3], dtype=np.int64),
        np.array([9], dtype=np.int64),
        np.array([2, 4, 6, 8, 10], dtype=np.int64),
        np.array([5], dtype=np.int64),
    ]
sorted(S_left, key=lambda x: (len(x), x))

[seanlaw]

Are you planning to add a new test? Otherwise, this should be sufficient since the input is known apriori

[mihailescum]

It works for this test yes and I didn't plan anything new. I just thought that a general solution might be better.

[seanlaw]

Agreed. I have some time this afternoon and I can try to dig around to see if there is a more robust solution.

[seanlaw]

What about:

sorted(x, key=lambda x: (len(x), x.tolist()))

[seanlaw]

It sounds like Python list defaults to sorting lexicographically so I am exploiting that here and sorting in list space while returning objects in numpy space

[mihailescum]

I think we should do list(x) instead of x.tolist() in case that x is not an array (which isn't the case here, but you never know what happens in the future), but other than that this seems like a good solution to me.

[seanlaw]

Sounds good!