Simple Experiment Platform For Sorting Implementation

說明:

使用者要實作一個 sorting function 時,可以使用這段程式碼來驗證其演算法的正確性。

測試用的資料,來自C++ uniform distribution random library 產出隨機資料。

使用方法:

  1. 寫出你的 sorting method,其外部介面 signature 遵照 void xxx(ArrayT&);
    ArrayT 目前預設是 std::array<std::size_t, 400>;。你可以在檔案的開頭改動其要測試的 ARRAY_SIZE data set 大小、 ItemT 整數的型別、ArrayT container type(只要能支援 size 即可,最好是有支援 RnadomAccess ,這樣 std::distance 才會比較快XD)。

  2. 實作好之後,在 main.cpp 裡頭,在第一個變數 methods_to_test,多插入一個以大括號包住的結構: {你的function名稱, 你的 function readable text},來與 testing 結構做連結。

  3. 按下編譯並執行,即可觀看結果是否符合預期。

搭配服用

http://www.compileonline.com/compile_cpp11_online.php
http://pastebin.com/qZnTXeFK

Testbed Source Code

#include <iostream>
#include <random>
#include <array>
#include <vector>
#include <algorithm>
#include <iterator>
#include <iomanip>
#include <string>
#include <chrono>
#include <utility>

namespace{    
    const std::size_t ARRAY_SIZE = 400;
    const std::size_t OUTPUT_COLUMN = 20;
    const std::size_t OUTPUT_ROW = ARRAY_SIZE / OUTPUT_COLUMN;
    using ItemT = std::size_t;
    using ArrayT = std::array<ItemT, ARRAY_SIZE>;
    
    using SortingMethodT = void (ArrayT&);
    
    const ItemT VALUE_MAX = 100;
    const std::size_t DIGIT_WIDTH = 3;
    
    const std::size_t MEASURE_ROUND = 1; // run X times to measure time
}


// ###############################################
// ############  Input Data Generator ############
// ###############################################
ItemT random_number()
{
   static std::random_device rd;
   static std::uniform_int_distribution<ItemT> uid(0, VALUE_MAX);
   return uid(rd);
}

ArrayT&& random_number_array()
{
   ArrayT src;
   std::generate(src.begin(), src.end(), random_number);
   return std::move(src);
}

ArrayT&& increment_number_array()
{
   ArrayT src;
   ItemT base_item = 0;   
   std::generate(src.begin(), src.end(), [&base_item](){return base_item++;});
   return std::move(src);
}


// ###############################################
// ##############  Printing Helper  ##############
// ###############################################
bool last_element(ArrayT::difference_type index)
{
    return (index != 0) && ((1+index) % OUTPUT_COLUMN == 0);
}

char dilem( ArrayT::difference_type index)
{
    return last_element(index)?'\n':' ';
}


void print_array(const ArrayT& src)
{    
   for(auto item_iter = src.begin(); 
            item_iter != src.end(); 
            item_iter++)
   {
        std::cout << std::setfill(' ') << std::setw(DIGIT_WIDTH)
                  << *item_iter 
                  << dilem(std::distance(src.begin(), item_iter));
   }
}

void print_banner(const std::string& text)
{
    std::cout << std::endl;
    std::cout << std::string(80, '#') << std::endl;
    auto remaining_width = std::max(78 - text.size(), static_cast<std::size_t>(0));    
    std::cout << std::string(remaining_width / 2, '#') << ' ';
    std::cout << text;

    std::cout << ((remaining_width % 2)?' ':'\0');
    std::cout << ' ' << std::string(remaining_width / 2, '#') << std::endl;
    std::cout << std::string(80, '#') << std::endl << std::endl;
}



// ###############################################
// ###############  Testing Helper ###############
// ###############################################

// return Enditer, if array is sorted
//        otherwise, the first detected unsorted position
ArrayT::const_iterator assert_sorted(ArrayT::const_iterator BeginIter, ArrayT::const_iterator EndIter)
{
    ItemT max = std::numeric_limits<ItemT>::min();
    while(BeginIter != EndIter)
    {
        if(*BeginIter < max)
            return BeginIter;
        max = *BeginIter++; 
    }
    return BeginIter;
}

bool assert_sorting_method(const std::function<SortingMethodT>& f, const ArrayT& src, const std::string& test_caption)
{
    // ensure input is a unsorted array
    if(assert_sorted(src.begin(), src.end()) == src.end())
    {
        std::cout << std::setw(30) << 
            test_caption << " is failed! \n";
            "  FAIL REASON: [INVALID_INPUT]\n"
            "    Source array should be unsorted.\n"
            << std::flush;
        return false;
    }
    
    auto fixture_ary = src; // make a copy
    f(fixture_ary); // do the sorting
    
    // validate the answer
    auto iter = assert_sorted(fixture_ary.begin(), fixture_ary.end());
    if(iter != fixture_ary.end())
    {
        std::cout << std::setw(30) << 
            test_caption << " is failed! \n"
            "  FAIL REASON: [WRONG_ANSWER]\n"
            "    Result array should be sorted. Element greater than following one at index : " << 
            std::distance(fixture_ary.cbegin(), iter) << "\n";
            
        std::cout << 
            "    Result Array Dump: \n";
        print_array(fixture_ary);
        std::cout << std::endl;
        return false;
    }
    std::cout << std::setw(30) << test_caption << " is passed.";
    return true;
} 

void measure_time_of_sorting_method(const std::function<SortingMethodT>& f, const ArrayT& src)
{
    std::chrono::steady_clock::rep duration_in_ms = 0;
    for(std::size_t round = 0; round != MEASURE_ROUND; round++)
    {
        auto fixture_ary = src; // make a copy
        auto test_start = std::chrono::steady_clock::now(); // start measure
        f(fixture_ary); // do the sorting
        auto duration =  std::chrono::steady_clock::now() - test_start; // end of measure
        duration_in_ms += std::chrono::duration_cast<std::chrono::microseconds>(duration).count(); // accumalte measure time
    }
    std::cout << "|" << MEASURE_ROUND << " rounds|" << ARRAY_SIZE << " items"
                 "|" << std::setw(8) << duration_in_ms << " microseconds." << std::endl;
}

// ###############################################
// #######  Sorting functions to implement #######
// ###############################################
void std_sort(ArrayT& ary)
{
    std::sort(ary.begin(), ary.end());            
}

void wrong_sort(ArrayT& ary)
{
    std::sort(ary.begin(), ary.begin() + ary.size() / 2);  
}

void bubble_sort(ArrayT& ary)
{
    for(int i = 0 ; i < ary.size(); i++)
      for(int j = i ; j < ary.size() ; j++)
         if(ary[i] > ary[j])
           std::swap(ary[i], ary[j]);
}

int main()
{
    std::vector<std::pair<std::function<SortingMethodT>, std::string>> methods_to_test = 
    {
        {std_sort, "Correct Sort(using std::sort)"},
        //{wrong_sort, "Wrong Sort(using doing half of range)"}, // [make sure test works well to detect worng answer state.]
        {bubble_sort, "My Bubble Sort"},
    };
    
    auto fixture = random_number_array();
    
    for(const auto& method_pair: methods_to_test)
    {
        if(!assert_sorting_method(method_pair.first, fixture, method_pair.second))
            continue;
        measure_time_of_sorting_method(method_pair.first, fixture);
    }
        

    return 0;
}

comments powered by Disqus