test/radix_sort_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 15 Mar 2011 19:32:21 +0100
changeset 936 ddd3c0d3d9bf
parent 443 de16f1f2d228
child 1043 1bafdbd2fc46
permissions -rw-r--r--
Implement the scaling Price Refinement heuristic in CostScaling (#417)
instead of Early Termination.

These two heuristics are similar, but the newer one is faster
and not only makes it possible to skip some epsilon phases, but
it can improve the performance of the other phases, as well.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <lemon/time_measure.h>
    20 #include <lemon/smart_graph.h>
    21 #include <lemon/maps.h>
    22 #include <lemon/radix_sort.h>
    23 #include <lemon/math.h>
    24 
    25 #include "test_tools.h"
    26 
    27 #include <vector>
    28 #include <algorithm>
    29 
    30 using namespace lemon;
    31 
    32 static const int n = 10000;
    33 
    34 struct Negate {
    35   typedef int argument_type;
    36   typedef int result_type;
    37   int operator()(int a) { return - a; }
    38 };
    39 
    40 int negate(int a) { return - a; }
    41 
    42 
    43 void generateIntSequence(int n, std::vector<int>& data) {
    44   int prime = 9973;
    45   int root = 136, value = 1;
    46   for (int i = 0; i < n; ++i) {
    47     data.push_back(value - prime / 2);
    48     value = (value * root) % prime;
    49   }
    50 }
    51 
    52 void generateCharSequence(int n, std::vector<unsigned char>& data) {
    53   int prime = 251;
    54   int root = 3, value = root;
    55   for (int i = 0; i < n; ++i) {
    56     data.push_back(static_cast<unsigned char>(value));
    57     value = (value * root) % prime;
    58   }
    59 }
    60 
    61 void checkRadixSort() {
    62   {
    63     std::vector<int> data1;
    64     generateIntSequence(n, data1);
    65 
    66     std::vector<int> data2(data1);
    67     std::sort(data1.begin(), data1.end());
    68 
    69     radixSort(data2.begin(), data2.end());
    70     for (int i = 0; i < n; ++i) {
    71       check(data1[i] == data2[i], "Test failed");
    72     }
    73 
    74     radixSort(data2.begin(), data2.end(), Negate());
    75     for (int i = 0; i < n; ++i) {
    76       check(data1[i] == data2[n - 1 - i], "Test failed");
    77     }
    78 
    79     radixSort(data2.begin(), data2.end(), negate);
    80     for (int i = 0; i < n; ++i) {
    81       check(data1[i] == data2[n - 1 - i], "Test failed");
    82     }
    83 
    84   }
    85 
    86   {
    87     std::vector<unsigned char> data1(n);
    88     generateCharSequence(n, data1);
    89 
    90     std::vector<unsigned char> data2(data1);
    91     std::sort(data1.begin(), data1.end());
    92 
    93     radixSort(data2.begin(), data2.end());
    94     for (int i = 0; i < n; ++i) {
    95       check(data1[i] == data2[i], "Test failed");
    96     }
    97 
    98   }
    99 }
   100 
   101 
   102 void checkStableRadixSort() {
   103   {
   104     std::vector<int> data1;
   105     generateIntSequence(n, data1);
   106 
   107     std::vector<int> data2(data1);
   108     std::sort(data1.begin(), data1.end());
   109 
   110     stableRadixSort(data2.begin(), data2.end());
   111     for (int i = 0; i < n; ++i) {
   112       check(data1[i] == data2[i], "Test failed");
   113     }
   114 
   115     stableRadixSort(data2.begin(), data2.end(), Negate());
   116     for (int i = 0; i < n; ++i) {
   117       check(data1[i] == data2[n - 1 - i], "Test failed");
   118     }
   119 
   120     stableRadixSort(data2.begin(), data2.end(), negate);
   121     for (int i = 0; i < n; ++i) {
   122       check(data1[i] == data2[n - 1 - i], "Test failed");
   123     }
   124   }
   125 
   126   {
   127     std::vector<unsigned char> data1(n);
   128     generateCharSequence(n, data1);
   129 
   130     std::vector<unsigned char> data2(data1);
   131     std::sort(data1.begin(), data1.end());
   132 
   133     radixSort(data2.begin(), data2.end());
   134     for (int i = 0; i < n; ++i) {
   135       check(data1[i] == data2[i], "Test failed");
   136     }
   137 
   138   }
   139 }
   140 
   141 int main() {
   142 
   143   checkRadixSort();
   144   checkStableRadixSort();
   145 
   146   return 0;
   147 }