CUDPP: Sorting a Structure Array

Problem

The cudppSort function from the CUDPP library can be used to sort an array of keys and an array of values along with it. However, the value types that are supported are only 32-bit. Thus, an array of structures cannot directly be sorted by using cudppSort.

Solution

One way to sort such a structure array is as follows:

1. Create an index array. Fill it with indices of the array using a simple kernel.
2. Use this index array as the value array and sort the key and value arrays using cudppSort.
3. Pass the sorted index array to a simple kernel and use it write the structures of the array to their sorted destinations.

This solution assumes that the structure array has an additional array of keys. More details and code on this method can be seen in my post on Compacting a Structure Array.

Tried with: CUDPP 1.1.1 and CUDA 3.2

C++: Sorting 2, 3 or 4 Values

The STL sort algorithm is very useful because it works both on STL containers and on normal arrays. It is hard to beat on performance too.

#include <algorithm>
int v[4] = { 99, 10, 5, 56 };
std::sort( v, v + 4 );

However, if your application needs to only sort 2, 3 or 4 length arrays whose values are simple types, you are better off using your own special sorting function written for these cases. Such scenarios occur in geometry, where you might be using a line segment (2 points), triangle (3 points) or a tetrahedron (4 points).

If you are processing millions of these objects, your application is significantly faster using a custom sort than the STL sort or a handwritten bubble sort. On a test with 20 million 4-length arrays, STL sort was 1.0s, bubble sort was 0.7s and custom sort was 0.5s.

void sort2( int* v )
{
    if ( v[0] > v[1] )
        swap( v[0], v[1] );

    return;
}

void sort3( int* v )
{
    if ( v[0] > v[1] )  swap( v[0], v[1] );
    if ( v[0] > v[2] )  swap( v[0], v[2] );
    if ( v[1] > v[2] )  swap( v[1], v[2] );

    return;
}

void sort4( int* v )
{
    if ( v[0] > v[1] )  swap( v[0], v[1] );
    if ( v[0] > v[2] )  swap( v[0], v[2] );
    if ( v[0] > v[3] )  swap( v[0], v[3] );

    sort3( &v[1] );

    return;
}

Python: __lt__()

If you try to sort a list of objects of your own class …

class Foobar:
    def __init__(self, idx):
        self.idx = idx
        return

fooList = [Foobar(10), Foobar(2)]
fooList.sort()

… you get a TypeError error:

TypeError: unorderable types: Foobar() < Foobar()

Python is reporting that it does not know how to compare Foobar objects.

Define a __lt__() method in the Foobar class. This rich comparison method is preferred over the generic __cmp__() method.

class Foobar:
    def __lt__(self, other):
    """Less-than comparison."""
    return self.idx < other.idx

Python: Sorting a List

alist = [10, 2, 8]

# Returns sorted list of input list
blist = sorted(alist)

# In-place sort of list
alist.sort()

Python: Sort a dictionary by value

# Also see: http://stackoverflow.com/questions/613183
adict = {"nine": 9, "one":1, "eight":8, "three":3}
import operator
sorted(adict.items(), key=operator.itemgetter(1)) # [('one', 1), ('three', 3), ('eight', 8), ('nine', 9)]