Sorting array of objects by row using custom dtype

This actually works fine

In [16]: selection = np.array(list(string.ascii_lowercase))

In [17]: arr = np.random.choice(selection, size=(5, 3))

In [18]: arr
Out[18]:
array([['x', 'l', 'i'],
       ['k', 'h', 'b'],
       ['y', 'h', 'w'],
       ['i', 'u', 't'],
       ['v', 'u', 'k']], dtype='<U1')

In [19]: np.ndarray(arr.shape[0], dtype=[('', arr.dtype, arr.shape[1])], buffer=arr).sort()

In [20]: arr
Out[20]:
array([['i', 'u', 't'],
       ['k', 'h', 'b'],
       ['v', 'u', 'k'],
       ['x', 'l', 'i'],
       ['y', 'h', 'w']], dtype='<U1')

The issue is with using dtype object for selection.

In [21]: selection = np.array(list(string.ascii_lowercase), dtype = object)

In [22]: arr = np.random.choice(selection, size=(5, 3))

In [23]: arr
Out[23]:
array([['b', 'h', 'e'],
       ['o', 'z', 'c'],
       ['g', 'v', 'z'],
       ['r', 'n', 'k'],
       ['a', 'h', 't']], dtype=object)

In [24]: np.ndarray(arr.shape[0], dtype=[('', arr.dtype, arr.shape[1])], buffer=arr).sort()

In [25]: arr
Out[25]:
array([['o', 'z', 'c'],
       ['b', 'h', 'e'],
       ['r', 'n', 'k'],
       ['a', 'h', 't'],
       ['g', 'v', 'z']], dtype=object)

Note dtype = 'O' means numpy type of python object see here for more, which I don't think provides a comparison operator.

The two types that you've provided, normally, should still work.

The fact that sorting works for integers happens to be a coincidence this can be verified by looking at the result of floating point operations:

>>> arr = np.array([[0.5, 1.0, 10.2],
                    [0.4, 2.0, 11.0],
                    [1.0, 2.0, 4.0]])
>>> np.sort(np.ndarray(arr.shape[0], dtype=[('', arr.dtype, arr.shape[1])], buffer=arr))
array([([ 0.5,  1. , 10.2],),
       ([ 1. ,  2. ,  4. ],),
       ([ 0.4,  2. , 11. ],)], dtype=[('f0', '<f8', (3,))])
>>> np.sort(np.ndarray(arr.shape[0], dtype=[('', arr.dtype)] * arr.shape[1], buffer=arr))
array([(0.4, 2., 11. ),
       (0.5, 1., 10.2),
       (1. , 2.,  4. )],
      dtype=[('f0', '<f8'), ('f1', '<f8'), ('f2', '<f8')])

Another hint comes from looking at the bits of the numbers 0.5, 0.4 and 1.0:

0.5 = 0x3FE0000000000000
0.4 = 0x3FD999999999999A
1.0 = 0x3FF6666666666666

On a little-endian machine, we have that 0x00 < 0x66 < 0x9A (the last byte shown above comes first).

The exact answer can be verified by looking at the sorting functions in the source code. For example, in quicksort.c.src, we see that all types that are not explicitly numerical (including structure fields that are not scalars), are handled by the npy_quicksort generic function. It uses function cmp as a comparator and macros GENERIC_SWAP and GENERIC_COPY to swap and copy, respectively.

The function cmp is defined as PyArray_DESCR(arr)->f->compare. The macros are defined as element-wise operations in npysort_common.h.

So the final result is that for any non-scalar type, including packed array structure fields, the comparison is done byte-by-byte. For objects, this will of course be the numeric values of the pointers. For floats, this will be the IEEE-754 representation. The fact that positive integers appear to work correctly is caused by the fact that my platform uses little-endian encoding. Negative integers stored in twos complement form would likely not yield correct results.

This might not be a perfect answert but I hope I can help you:

1.) Why isn't it working properly: Because dtype=[('', arr.dtype)] * arr.shape[1] != dtype=[('', arr.dtype, arr.shape[1])]

2.) What's the difference between those two? Well, while the first one adds the length to the list the second one multiplies the list. This means the output of the first one is something like: [('', dtype('O'), 3)] whereas the second is [('', dtype('O')), ('', dtype('O')), ('', dtype('O'))]

3.) The sort is clearly doing something wrong - no the input was just in the wrong format

4.) Is it using pointers as the sort keys? Do you mean if it formats the data by the data-keys? Then no it sorts them according to the data itself.

EDIT: Ok to make it more clear:

First of all I think you misunderstood @Mike MacNeil's anwer. To make it more plastic here some examples:

Let's consider a class Foo:

class Foo:
    def __init__(self, id):
        self._id = id
    
    def get_id(self):
        return self._id

    def __le__(self, ob):
        return self < ob or self == ob

    def __lt__(self, ob):
        return self.get_id() < ob.get_id()

    def __ge__(self, ob):
        return not self < ob

    def __gt__(self, ob):
        return not self <= ob

    def __eq__(self, ob):
        return self.get_id() == ob.get_id()

    def __str__(self):
        return f'Foo({self.get_id()})'

    def __repr__(self):
        rep = super().__repr__()
        return f'{str(self)} {rep[rep.index("at"):rep.index(">")]}'

We see the comparisons have been implemented just like in string. I also implemented the __repr__() and __str__() methods give me a second and you will understand why:

Let's create a numpy array in the first step:

>>> arr4 = np.array([[Foo(1), Foo(2), Foo(3)],
        [Foo(4), Foo(5), Foo(6)],
        [Foo(7), Foo(8), Foo(9)],
        [Foo(10), Foo(11), Foo(12)]])

If we print it, it will look something like this:

>>> arr4
array([[Foo(1) at 0x000002411F753F08, Foo(2) at 0x000002411F73FF48, Foo(3) at 0x000002411F74EE48],
       [Foo(4) at 0x000002411F74EE88, Foo(5) at 0x000002411F74EE08, Foo(6) at 0x000002411F756148],
       [Foo(7) at 0x000002411F7561C8, Foo(8) at 0x000002411F756208, Foo(9) at 0x000002411F756248],
       [Foo(10) at 0x000002411F756288, Foo(11) at 0x000002411F7562C8,
        Foo(12) at 0x000002411F756308]], dtype=object)

If we now print the ndarray...

>>> np.ndarray(arr4.shape[0], dtype=[('', arr4.dtype, arr4.shape[1])], buffer=arr4)
array([([Foo(1) at 0x000002411F753F08, Foo(2) at 0x000002411F73FF48, Foo(3) at 0x000002411F74EE48],),
       ([Foo(4) at 0x000002411F74EE88, Foo(5) at 0x000002411F74EE08, Foo(6) at 0x000002411F756148],),
       ([Foo(7) at 0x000002411F7561C8, Foo(8) at 0x000002411F756208, Foo(9) at 0x000002411F756248],),
       ([Foo(10) at 0x000002411F756288, Foo(11) at 0x000002411F7562C8, Foo(12) at 0x000002411F756308],)], dtype=[('f0', 'O', (3,))])

...we see it basically has the same shape as

>>> np.ndarray(arr.shape[0], dtype=[('', arr.dtype, arr.shape[1])], buffer=arr)
array([['t', 'p', 'g'],
       ['n', 's', 'd'],
       ['g', 'h', 'o'],
       ['g', 'g', 'n'],
       ['f', 'j', 'x']], dtype=[('f0', 'O', (3,))])

After sorting the Foo-Array with np.ndarray(arr4.shape[0], dtype=[('', arr4.dtype, arr4.shape[1])], buffer=arr4).sort() we see that the output of arr4 looks something like:

>>> arr4
array([[Foo(1) at 0x000002411F753F08, Foo(2) at 0x000002411F73FF48, Foo(3) at 0x000002411F74EE48],
       [Foo(10) at 0x000002411F756288, Foo(11) at 0x000002411F7562C8, Foo(12) at 0x000002411F756308],
       [Foo(4) at 0x000002411F74EE88, Foo(5) at 0x000002411F74EE08, Foo(6) at 0x000002411F756148],
       [Foo(7) at 0x000002411F7561C8, Foo(8) at 0x000002411F756208, Foo(9) at 0x000002411F756248]], dtype=object)

although

>>> Foo(10) > Foo(4)
True

(Still np.ndarray(arr4.shape[0], dtype=[('', arr4.dtype)] * arr4.shape[1], buffer=arr4).sort() can print out the expected result sorted with the id-key using the defined comparison-functions.)

The comparison-rule for the dtype=object is not as you would expect just using the standard comparison functions but is comparing the objects representations (→ in this case this would mean that e.g. repr(Foo(10)) < repr(Foo(2)) would be True although we would actually expect Foo(10) to be greater than Foo(2)).

But by telling numpy the exact dimensions/shape, numpy uses the standard comparisons which will lead to the expected result because it now knows that all the elements of a row are from exactly the same type and not just some random objects clenched together into one array. This is why also your example didn't work with string however would work with str as str will be supported natively by numpy (<U1).

It appears that your first method, dtype=[('', arr.dtype, arr.shape[1])], buffer=arr).sort(), is trying to sort the dtype=object but it doesn't have enough information to sort it. When you use the second method dtype=[('', arr.dtype)] * arr.shape[1], buffer=arr).sort(), it unpacks the object, allowing the sort method to "see" what it's supposed to sort on. When you're using these methods on scalars, the sort method can see they're scalars and not an object.

This is all conjecture on my part, but it makes sense to me. If anyone can correct me, please do!