Sort 5 objects with 7 comparisons

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Jun 16, 2007 at 13:39

Hi!

Do you think it’s possible to sort 5 objects with 7 comparisons? I’m doing a small research project where I use 5 parallel clipping planes, which need to be sorted. I define an order by taking the distance to the user. I know it’s possible with 8, but each operation is important, since we’re extremely low-level.

Thank you!

9 Replies

Please log in or register to post a reply.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jun 16, 2007 at 15:22

Is there any way to take advantage of temporal coherence? For instance, is it possible to start with the order from last frame and just update it to get the order for the current frame?

2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Jun 16, 2007 at 15:48

Unfortunately no, we thought about that strategy though.

A9102969e779768e6f0b8cb87e864c94
0
dave_ 101 Jun 16, 2007 at 18:18

… I’m not sure about the implementation but I quickly knocked this up:

#include <iostream>
#include <vector>
#include <algorithm>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <Windows.h>

unsigned compares=0;

struct SomeSortable {
    SomeSortable() : v(rand()) {}

    bool operator <(const SomeSortable& rhs) const { ++compares; return v < rhs.v; }
    bool operator >(const SomeSortable& rhs) const { return v > rhs.v; }

    unsigned v;
}; 

template<typename T>
bool is_sorted(T start, T end)
{
    for(T itt = start; itt != end; ++itt)
    {
        if (itt > itt+1)
            return false;
    }
    return true;
}



int main(int argc, char *argv[])
{
    time_t t;
    time(&t);
    srand((unsigned int)t);

    std::vector<SomeSortable> sort1;
    
    const unsigned num_iterations = 100000;

    DWORD start;
    start = GetTickCount();
    for (unsigned j = 0; j < num_iterations; ++j)
    {
        for (unsigned i = 0; i < 5; ++i)
        {
            sort1.push_back(SomeSortable());
        }
        std::sort(sort1.begin(), sort1.end());

        bool sorted = is_sorted(sort1.begin(), sort1.end());
        assert(sorted);
        sort1.clear();
    }
    DWORD end;
    end = GetTickCount();

    std::cout << "std::sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

    compares = 0;
    start = GetTickCount();
    for (unsigned j = 0; j < num_iterations; ++j)
    {
        for (unsigned i = 0; i < 5; ++i)
        {
            sort1.push_back(SomeSortable());
        }
        std::stable_sort(sort1.begin(), sort1.end());

        bool sorted = is_sorted(sort1.begin(), sort1.end());
        assert(sorted);
        sort1.clear();
    }

    end = GetTickCount();
    std::cout << "std::stable_sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

    compares = 0;
    start = GetTickCount();
    for (unsigned j = 0; j < num_iterations; ++j)
    {
        for (unsigned i = 0; i < 5; ++i)
        {
            sort1.push_back(SomeSortable());
        }
        std::sort_heap(sort1.begin(), sort1.end()); 

        bool sorted = is_sorted(sort1.begin(), sort1.end());
        assert(sorted);
        sort1.clear();
    }

    end = GetTickCount();
    std::cout << "std::sort_heap number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

    return 0;
}

std::sort number of comparisons 9 duration 4047
std::stable_sort number of comparisons 8 duration 4344
std::sort_heap number of comparisons 5 duration 4016
2b97deded6213469bcd87b65cce5d014
0
Mihail121 102 Jun 16, 2007 at 18:31

Ehm Dave, there is most probably an error in your code. There is no sorting algorithm, that can sort 5 comparable objects with 5 comparisons, since the lower bound of the amount of comparisons for the worst case (n objects) should be greater equal log2 (n!) . In our case that’s 7.

A9102969e779768e6f0b8cb87e864c94
0
dave_ 101 Jun 16, 2007 at 19:25

Heapsort has a worst case complexity of O(n log n) that should be 11.61 so I’ve no idea where the error is.

Edit figured it out. I wasn’t dereferencing the iterators and I also forgot a make heap. That doubles the comparisons. :(
Corrected results, with more iterations

std::sort number of comparisons 9 duration 20875
std::stable_sort number of comparisons 8 duration 21266
std::sort_heap number of comparisons 10 duration 22688
A9102969e779768e6f0b8cb87e864c94
0
dave_ 101 Jun 16, 2007 at 23:07

Since they’re parallel planes is it possible to sort them by ‘d’ first to gain some advantage?
What about caching normal . eye?
Edit: Though about it a bit more.
comparison is normal1 . eye + d1 < normal2 . eye + d2
since plane1 & plane2 are parallel normal1 == normal2
can you simplify this to just d1 < d2?
Have you already done this optimization? Is it even valid?

#include <iostream>
#include <vector>
#include <algorithm>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <Windows.h>

unsigned compares=0;


float eyex = 1.0f, eyey = 12.433f, eyez = -100.f;
struct SomeSortable {
    SomeSortable() : x_(0.58f), y_(0.58f), z_(0.58f), d_((rand() % 1000)*1.f) {}

    float distanceToEye() const
    {
        float dot = x_ * eyex
            + y_ * eyey
            + z_ * eyez;
        return dot + d_;

    }
    bool operator<(SomeSortable const& rhs) const
    {
        ++compares;
        return distanceToEye() < rhs.distanceToEye();
    }
    bool operator>(SomeSortable const& rhs) const
    {
        return distanceToEye() > rhs.distanceToEye();
    }

    float x_, y_, z_, d_;
}; 

template<typename T>
bool is_sorted(T start, T end)
{
    for(T itt = start; itt != end-1; ++itt)
    {
        if (*itt > *(itt+1))
            return false;
    }
    return true;
}

struct Sorter
{
    Sorter() {}
    bool operator()(SomeSortable const& lhs, SomeSortable const& rhs) const
    {
        ++compares;
        return lhs.d_ < rhs.d_;
    }

};


int main(int argc, char *argv[])
{
    time_t t;
    time(&t);
    srand((unsigned int)t);

    std::vector<SomeSortable> sort1;

    const unsigned num_iterations = 100000;

    DWORD start;
    start = GetTickCount();
    for (unsigned j = 0; j < num_iterations; ++j)
    {
        for (unsigned i = 0; i < 5; ++i)
        {
            sort1.push_back(SomeSortable());
        }
        std::sort(sort1.begin(), sort1.end());

        bool sorted = is_sorted(sort1.begin(), sort1.end());
        assert(sorted);
        sort1.clear();
    }
    DWORD end;
    end = GetTickCount();

    std::cout << "std::sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

    compares = 0;
    start = GetTickCount();
    for (unsigned j = 0; j < num_iterations; ++j)
    {
        for (unsigned i = 0; i < 5; ++i)
        {
            sort1.push_back(SomeSortable());
        }
        std::stable_sort(sort1.begin(), sort1.end());

        bool sorted = is_sorted(sort1.begin(), sort1.end());
        assert(sorted);
        sort1.clear();
    }

    end = GetTickCount();
    std::cout << "std::stable_sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;

    compares = 0;
    start = GetTickCount();
    for (unsigned j = 0; j < num_iterations; ++j)
    {
        for (unsigned i = 0; i < 5; ++i)
        {
            sort1.push_back(SomeSortable());
        }
        std::make_heap(sort1.begin(), sort1.end()); 
        std::sort_heap(sort1.begin(), sort1.end()); 

        bool sorted = is_sorted(sort1.begin(), sort1.end());
        assert(sorted);
        sort1.clear();
    }

    end = GetTickCount();
    std::cout << "std::sort_heap number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;



    compares = 0;
    start = GetTickCount();
    for (unsigned j = 0; j < num_iterations; ++j)
    {
        for (unsigned i = 0; i < 5; ++i)
        {
            sort1.push_back(SomeSortable());
        }

        std::sort(sort1.begin(), sort1.end(), Sorter());


        bool sorted = is_sorted(sort1.begin(), sort1.end());
        assert(sorted);
        sort1.clear();
    }

    end = GetTickCount();
    std::cout << "dot sort number of comparisons " << compares/num_iterations << " duration " << end - start << std::endl;


    return 0;
}
99f6aeec9715bb034bba93ba2a7eb360
0
Nick 102 Jun 17, 2007 at 08:57

@Mihail121

I’m doing a small research project where I use 5 parallel clipping planes, which need to be sorted.

Could you give us a little hint at what you’re trying to do? It sounds interesting, but I can’t imagine anything where sorting 5 numbers is a performance bottleneck. And it’s even weirder that there’s no temporal/spacial coherence…

A3dd48e1deb889dd2b4d5e129550e9fd
0
Hyde 101 Jul 12, 2007 at 22:21

I bet you can’t avoid having to do 8 compares, given that you assume nothing.

B7dcbc0c0f07253f25ff5c25fe38c081
0
SamuraiCrow 101 Jul 13, 2007 at 01:06

The only way you can beat O(n log n) time with a sorting algorithm is if you can use the values themselves as an index and avoid the whole comparison-type sorting algorithms altogether. Eg. the radix sort.