Template Numerical Library version\ main:eacc201d
Loading...
Searching...
No Matches
Sorting tutorial

Introduction

TNL offers several different parallel algorithms for sorting of arrays (or vectors) and also sorting based on user defined swapping. The later is more general but also less efficient.

Sorting of arrays and Vectors

The sorting of arrays and vectors is accessible via the following functions:

The following example demonstrates the use of ascending and descending sort. See

1#include <iostream>
2#include <TNL/Containers/Array.h>
3#include <TNL/Algorithms/sort.h>
4
5using namespace TNL;
6using namespace TNL::Containers;
7using namespace TNL::Algorithms;
8
9template< typename ArrayT >
10void sort( ArrayT& array )
11{
12 const int size = 10;
13
14 /****
15 * Fill the array with random integers.
16 */
17 Array< int > aux_array( size );
18 srand( size + 2021 );
19 aux_array.forAllElements( [=] __cuda_callable__ ( int i, int& value ) { value = std::rand() % (2*size); } );
20 array = aux_array;
21
22 std::cout << "Random array: " << array << std::endl;
23
24 /****
25 * Sort the array in ascending order.
26 */
27 ascendingSort( array );
28 std::cout << "Array sorted in ascending order:" << array << std::endl;
29
30 /***
31 * Sort the array in descending order.
32 */
33 descendingSort( array );
34 std::cout << "Array sorted in descending order:" << array << std::endl;
35}
36
37int main( int argc, char* argv[] )
38{
39 /***
40 * Firstly, test the sorting on CPU.
41 */
42 std::cout << "Sorting on CPU ... " << std::endl;
44 sort( host_array );
45
46#ifdef HAVE_CUDA
47 /***
48 * And then also on GPU.
49 */
50 std::cout << "Sorting on GPU ... " << std::endl;
52 sort( cuda_array );
53#endif
54 return EXIT_SUCCESS;
55}
#define __cuda_callable__
Definition: CudaCallable.h:22
Array is responsible for memory management, access to array elements, and general array operations.
Definition: Array.h:67
T endl(T... args)
Namespace for fundamental TNL algorithms.
Definition: AtomicOperations.h:14
Namespace for TNL containers.
Definition: Array.h:21
The main TNL namespace.
Definition: AtomicOperations.h:13
T rand(T... args)
T sort(T... args)

Here we create array with random sequence of integers (lines 17-20) and then we sort the array in ascending order (line 27) and descending order (line 33). The result looks as follows:

Sorting on CPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Array sorted in ascending order:[ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Array sorted in descending order:[ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Sorting on GPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Array sorted in ascending order:[ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Array sorted in descending order:[ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]

How to achieve the same result with user defined ordering is demonstrated by the following example:

1#include <iostream>
2#include <TNL/Containers/Array.h>
3#include <TNL/Algorithms/sort.h>
4
5using namespace TNL;
6using namespace TNL::Containers;
7using namespace TNL::Algorithms;
8
9template< typename ArrayT >
10void sort( ArrayT& array )
11{
12 const int size = 10;
13
14 /****
15 * Fill the array with random integers.
16 */
17 Array< int > aux_array( size );
18 srand( size + 2021 );
19 aux_array.forAllElements( [=] __cuda_callable__ ( int i, int& value ) { value = std::rand() % (2*size); } );
20 array = aux_array;
21
22 std::cout << "Random array: " << array << std::endl;
23
24 /****
25 * Sort the array in ascending order.
26 */
27 sort( array, [] __cuda_callable__ ( int a, int b ) { return a < b; } );
28 std::cout << "Array sorted in ascending order:" << array << std::endl;
29
30 /***
31 * Sort the array in descending order.
32 */
33 sort( array, [] __cuda_callable__ ( int a, int b ) { return a > b; } );
34 std::cout << "Array sorted in descending order:" << array << std::endl;
35}
36
37int main( int argc, char* argv[] )
38{
39 /***
40 * Firstly, test the sorting on CPU.
41 */
42 std::cout << "Sorting on CPU ... " << std::endl;
44 sort( host_array );
45
46#ifdef HAVE_CUDA
47 /***
48 * And then also on GPU.
49 */
50 std::cout << "Sorting on GPU ... " << std::endl;
52 sort( cuda_array );
53#endif
54 return EXIT_SUCCESS;
55}

The result looks as follows:

Sorting on CPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Array sorted in ascending order:[ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Array sorted in descending order:[ 15, 14, 14, 11, 8, 5, 5, 2, 1, 0 ]
Sorting on GPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Array sorted in ascending order:[ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Array sorted in descending order:[ 15, 14, 14, 11, 8, 5, 5, 2, 1, 0 ]

The same way, one can sort also TNL::Containers::ArrayView, TNL::Containers::Vector and TNL::Containers::VectorView.

Sorting with user define swapping

1#include <iostream>
2#include <TNL/Containers/Array.h>
3#include <TNL/Algorithms/sort.h>
4
5using namespace TNL;
6using namespace TNL::Containers;
7using namespace TNL::Algorithms;
8
9template< typename ArrayT >
10void sort( ArrayT& array )
11{
12 const int size = 10;
13
14 /****
15 * Fill the array with random integers.
16 */
17 Array< int > aux_array( size );
18 srand( size + 2021 );
19 aux_array.forAllElements( [=] __cuda_callable__ ( int i, int& value ) { value = std::rand() % (2*size); } );
20 array = aux_array;
21
22 /***
23 * Prepare second array holding elements positions.
24 */
25 ArrayT index( size );
26 index.forAllElements( [] __cuda_callable__ ( int idx, int& value ) { value = idx; } );
27 std::cout << "Random array: " << array << std::endl;
28 std::cout << "Index array: " << index << std::endl;
29
30 /***
31 * Sort the array `array` and apply the same permutation on the array `identity`.
32 */
33 auto array_view = array.getView();
34 auto index_view = index.getView();
35 sort< typename ArrayT::DeviceType, // device on which the sorting will be performed
36 typename ArrayT::IndexType >( // type used for indexing
37 0, size, // range of indexes
38 [=] __cuda_callable__ ( int i, int j ) -> bool { // comparison lambda function
39 return array_view[ i ] < array_view[ j ]; },
40 [=] __cuda_callable__ ( int i, int j ) mutable { // lambda function for swapping of elements
41 TNL::swap( array_view[ i ], array_view[ j ] );
42 TNL::swap( index_view[ i ], index_view[ j ] ); } );
43 std::cout << "Sorted array: " << array << std::endl;
44 std::cout << "Index: " << index << std::endl;
45}
46
47int main( int argc, char* argv[] )
48{
49 /***
50 * Firstly, test the sorting on CPU.
51 */
52 std::cout << "Sorting on CPU ... " << std::endl;
54 sort( host_array );
55
56#ifdef HAVE_CUDA
57 /***
58 * And then also on GPU.
59 */
60 std::cout << "Sorting on GPU ... " << std::endl;
62 sort( cuda_array );
63#endif
64 return EXIT_SUCCESS;
65}
__cuda_callable__ constexpr void swap(Type &a, Type &b)
This function swaps values of two parameters.
Definition: Math.h:480

In this example, we fill array array with random numbers and array index with numbers equal to position of an element in the array. We want to sort the array array and permute the index array the same way. See the lines 34-38. Here we call function sort which does not accept any array-like data structure but only range of indexes and two lambda functions. The first one defines ordering of the elements (line 35) by comparing elements of array array. The second lambda function is responsible for elements swapping (lines 36-38 ). Note that we do not swap only elements of array array but also index array. The result looks as follows:

Sorting on CPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Index array: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
Sorted array: [ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Index: [ 4, 1, 6, 3, 0, 9, 5, 8, 7, 2 ]
Sorting on GPU ...
Random array: [ 5, 1, 15, 5, 0, 11, 2, 14, 14, 8 ]
Index array: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
Sorted array: [ 0, 1, 2, 5, 5, 8, 11, 14, 14, 15 ]
Index: [ 4, 1, 6, 0, 3, 9, 5, 7, 8, 2 ]