Tell me how crazy this idea sounds...

[markyrocks]

Ok so I've been playing around with pointers and sorting ALOT almost too much. An idea that keeps reoccurring in my mind is if it's possible to find a way to slide pointers down an array without doing all the swapping... hence efficiency.

So here's the concept. Say I have a pp** array and I'm sending low numbers to an end but I want those numbers to walk and change order without swapping. I'd probably actually need a ppp*** to change the order of the pp** without screwing this next part up.

The idea is Say I have an unassociated pointer that it's like a ppppp*****. And an unassociated p*** array of Say 5 elements. With casting could I then set each level of my ppppp***** to a different element in said ppp*** array and to effectively shift the order set the last level to the level below, hopefully drawing all the levels up with it and the set the bottom layer to the new incoming pp**. In my mind it's like a single element 3d array. I haven't had time to do anything with this but idk why I feel like it should work
I realize this is very unorthodox but I'd like to hear your thoughts.

[helios]

What? Honestly, I couldn't understand a word you said.

Suppose you have objects A through E of some arbitrary type, such that A < B < C < D < E, and an array s = [D, A, C, B, E]. Instead of trying to sort s itself, you could construct an array t consisting of pointers to said objects. t = [&D, &A, &C, &B, &E]. You can sort t by the value of the objects, rather than the value of the pointers themselves. Then t would act as a sort of sorted view into s. The advantage of doing this would be not having to move around the objects (which might be big enough that swapping would be expensive) and not having pointers to those objects become invalidated.

template <typename T>
void sort_objects(std::vector<T> &data){
    std::sort(data.begin(), data.end());
}

template <typename T>
void sort_pointers(std::vector<T *> &pointers){
    std::sort(pointers.begin(), pointers.end(), [](T *a, T *b){ return *a < *b; });
}

template <typename T>
void sort_indices(std::vector<T> &data, std::vector<size_t> &indices){
    std::sort(indices.begin(), indices.end(), [&data](size_t a, size_t b){ return data[a] < data[b]; });
}

[markyrocks]

That's basically what I'm talking about when I'm talking about a pp** which is an array of pointers.

This is just a quick example of what I'm describing

int* a=new int[]{1,2,3,4,5};
int** pp=new int*[]{a,a+1,a+2,a+3,a+4};

int*** ppp=new int**[5];

int***** bs;

****bs=(int*)bs;
***bs=(int**)bs+1;
**bs=(int***)bs+2; 
// and so on

//
//to set a number 
******((int***)bs)=pp;  

It's not pretty but I hope that kinda describes what I'm thinking

[jonnin]

swapping pointers is very efficient. I have no idea what you said, but if you need to rearrange things, doing so by pointers or references or similar lightweight swaps is the way to go.

[helios]

I don't get what lines 5-16 are supposed to be doing. It's complete nonsense, as far as I can tell. In fact line 16 is actually invalid; you can't sextuple-derefence a triple pointer.

This is valid:

int data[] = {42, 1, 36, 13, 1024, };
std::vector<int *> pointers(data, data + 5);
sort_pointers(pointers);
print(pointers); //prints 1 13 36 42 1024
*pointers[0] = 65536; //change the smallest value
print(pointers); //prints 65536 13 36 42 1024 

[lastchance]

https://www.geeksforgeeks.org/tag-sort/

[markyrocks]

it was just an idea. I wrote this an it seems to essentially be doing what i was trying to do but in a different way. As you can see how ridiculous it starts to get with pointers. The sad part is I'm actually understanding why 3 4 5 layers of pointers is sometimes necessary....

If you check out the relationship between the arrays in the following code especially between lo and lo_order. This is the type of functionality i was trying to achieve and if you peek the output the idea is to grab numbers less than the low number as the low number is being overwritten with a new low the older lows get pushed down and put them into a shifting array in a way that it wraps around the world and automatically puts them in an order... Sort!

int main() {


	int a[10] { 7,5,8,9,5,4,3,2,3,1 };

	int* b[10];
	int* cc_a = a;
	int** cc_b = b;
	
	while (cc_b < b + 10) { //copy a pointers to b
		*cc_b = cc_a;
		cc_b++; cc_a++;
	}

	int** lo[5]; //lo number list

	int*** lo_order[]{ lo, lo + 1 ,lo + 2,lo + 3, lo + 4 };

	int** low = b;
	int l_count = 0;
	int**** cc_lo_order = lo_order;
	cc_b = b;

	while (cc_b < b + 10) {

		if (**cc_b < (**low) + 1) {
			*low = *cc_b;
			//cout << **cc_b << " ";
			**cc_lo_order = cc_b;

			if (cc_lo_order + 1 == lo_order + 5) {
				cc_lo_order = lo_order;
			}
			else { cc_lo_order++; }
		}

		cc_b++;
	}

	for (auto i = lo_order; i < lo_order + 5; i++) {
		cout << ****i;
	}

21543

[helios]

So what you're saying is... bubble sort, except each bubbling pass returns a new level of indirection that's slightly more sorted than the previous level/pass. I mean, it works, except that you to sort a sequence of n elements you need n arrays of pointers, and the last array is an n-star pointer. It's a pain to even implement it:

#include <vector>
#include <iostream>

//Regular bubble sort:

template <typename T>
void bubbling_pass(std::vector<T> &data){
    for (size_t i = 0; i < data.size() - 1; i++)
        if (data[i + 1] < data[i])
            std::swap(data[i], data[i + 1]);
}

template <typename T>
void bubble_sort(std::vector<T> &data){
    for (size_t i = 0; i < data.size(); i++)
        bubbling_pass(data);
}

//Pure insanity:

template <typename T>
class ArbitraryDepthPointer{
    void *p = nullptr;
    int depth = 0;
    ArbitraryDepthPointer(void *p, int depth): p(p), depth(depth){}
public:
    ArbitraryDepthPointer() = default;
    ArbitraryDepthPointer(T &data): p(&data), depth(1){}
    ArbitraryDepthPointer(const T &data): p((void *)&data), depth(1){}
    ArbitraryDepthPointer(const ArbitraryDepthPointer &) = default;
    ArbitraryDepthPointer &operator=(const ArbitraryDepthPointer &) = default;
    ArbitraryDepthPointer one_more_level() const{
        return {(void *)&this->p, this->depth + 1};
    }
    T &get() const{
        auto ret = this->p;
        for (auto d = this->depth - 1; d--;)
            ret = *(void **)ret;
        return *(T *)ret;
    }
};

template <typename T>
std::vector<ArbitraryDepthPointer<T>> stupid_bubbling_pass(std::vector<ArbitraryDepthPointer<T>> &previous){
    std::vector<ArbitraryDepthPointer<T>> next;
    next.reserve(previous.size());
    for (auto &p : previous)
        next.push_back(p.one_more_level());
    for (size_t i = 0; i < next.size() - 1; i++)
        if (next[i + 1].get() < next[i].get())
            std::swap(next[i], next[i + 1]);
    return next;
}

template <typename T>
std::vector<std::vector<ArbitraryDepthPointer<T>>> stupid_bubble_sort(const std::vector<T> &data){
    std::vector<std::vector<ArbitraryDepthPointer<T>>> levels(data.size());
    for (auto &d : data)
        levels.front().emplace_back(d);
    for (size_t i = 1; i < levels.size(); i++)
        levels[i] = stupid_bubbling_pass(levels[i - 1]);
    return levels;
}

void example(int n){
    std::vector<int> data;
    for (int i = n; i--;)
        data.push_back(i);
        
    auto stupid = stupid_bubble_sort(data);
    std::cout << stupid.back().front().get() << " ... " << stupid.back().back().get()
        << "\nAdditional memory required: " << stupid.size() * (stupid.size() * sizeof(ArbitraryDepthPointer<int>) + sizeof(void *)) << " bytes.\n";
}

int main(){
    example(5);
    example(10);
    example(1024);
    example(10240);
    return 0;
}

0 ... 4
Additional memory required: 220 bytes.
0 ... 9
Additional memory required: 840 bytes.
0 ... 1023
Additional memory required: 8392704 bytes.
0 ... 10239
Additional memory required: 838901760 bytes.

As you can see, sorting 10 times more data requires 100 times more memory.

[TheIdeasMan]

jonnin wrote:

swapping pointers is very efficient. I have no idea what you said, but if you need to rearrange things, doing so by pointers or references or similar lightweight swaps is the way to go.

I agree.

std::swap probably* uses move semantics with rvalues, and is probably as about as good as it is going to get, certainly much better than dealing with 4 levels of indirection with pointers. More than 2 levels of indirection is probably worse than swapping / moving 2 pointers.

* the implementation is not defined in the standard, I am referring to code I have seen here:

http://thbecker.net/articles/rvalue_references/section_04.html

Consider sticking to the STL or some other respected library unless you have a very good reason to do so.

[seeplus]

When considering various algorithms for the same problem, as well as theoretical considerations, you should also time performance for say 1,000, 10,000, 1,000,000, 10,000,000 items for same sets of data (on the same system). Then you get the empirical timing data to determine in which circumstances one method (or coding) is better (or worse!) than another.

@markyrocks. You're presented some ideas re efficiency. OK. Now obtain the performance data. Not just for 10 or so items - but as a start for 1,000 and compare the timings for your method with say std::sort() etc. Then ramp up the data size.

If you want some timing software for a function. have a look at https://github.com/fenbf/articles/blob/master/filterElements/all_combined/all_combined.cpp

which contains code to run, measure and display timings for various functions.

[jonnin]

What really costs you and takes up the time in a sort? How can you do less of it? What can you do inexpensively, does doing more of it help avoid the more costly part? What are your limited resources? Start there.
the same answers apply to most of what a computer can do; its a good exercise generally.

[TheIdeasMan]

@markyrocks

Some ideas for you :+)

IIRC, this is how std::sort works, for numerical data at least :

https://en.wikipedia.org/wiki/Introsort

I have heard of another method, but I don't remember where I saw it:

First, a number of buckets are created, each of equal size. So for example if one had 1 million items, there may be 100'000 buckets which can hold up to 10 items. Second, the items are placed in the appropriate bucket, with insertion sort within the bucket.

Insertion sort, is very efficient up to size of 16, so this is the limit for the bucket size. The data type of the bucket is a list, because this is easiest to insert into for insertion sort.

[jonnin]

several variants do a 'quicksort'(the parent of intro) recursion part and then break off; you can break off to do shell (which is an improved variant of insertion!) with very large buckets (on today's machines, even a million to shell per bucket is reasonable but there is probably an optimal size you can find for a given implementation). With multi core processors, breaking off to do chunks in threads is very powerful but the chunks need to be significant in size, else the thread creation costs more than the gains.. each chunk needs to be several ms worth of work or more.

I did a study ~ when quad cores came out, and was at that time able to beat c++ library sort on g++ & msvs for billions of items using a multi threaded attack. But it was not a blowout or anything, it was better but in terms of real wall clock time saved it was not impressive. Now that I have 10 cores maybe I should try that again ...

[markyrocks]

Yes helios I was planning on doing this every pass until I get like thousands of depth in pointers so dereferenceing looks like this ******************************************************************I.

The idea is that after this pass was done the containing pointers would be swapped into the pp** array and the container reused. After size / size of lo_,list passes you'd have an array of ordered runs that could then be manipulated.

Trust me this isn't the final solution or the principle sort type. It's just one aspect that given this 10 element array that it essentially sorted half of it in one pass in my mind is pretty impressive.

Trust me I am trying this stuff out on bigger sample sizes using a timer. It is obvious that after like an array of a few thousand that std sort changes bc im able to do better than it b4 the change.

I am definitely thinking about what takes the time and resources. I've considered multithreaded approaches. Just haven't gotten there yet.

I'm just on my own little code journey. I'm sure when Bill Gates was starting off there was a guy on an internet forum somewhere that was ready to tar and feather his ass. <-joke.


I appreciate all the input guys.

[jonnin]

what you are doing is pretty neat. I wonder how much of the indirection the compiler is smart enough to avoid ...

[markyrocks]

@jonin what led me to this idea was that a simple sort method I was using simply compared the current number to the end and beginning of the array. If it was smaller than the beginning it got swapped with the current same with the end if it was greater than. Once the loop ended it could be shrunk in both directions bc those numbers would never need looked at or touched.

Then I started thinking about the number that was in those positions b4 the swaps took place and how the resulting list would create a run of numbers that were more ordered than they would have been previously (at least you would hope). The method I described about comparing the first and last is surprisingly fast.

Anyways last night I did write a true heap sort and that kinda has me thinking that big arrays like 1000 elements or more should probably be made into a 3d grid and comparing left and right with up or down. But I'm thinking about it the rows should be sorted b4 the columns. Or collums first maybe a combination? Idk. I have all day to think about it.

[TheIdeasMan]

markyrocks wrote:

The method I described about comparing the first and last is surprisingly fast.

Can I ask what it is being compared with to make you suggest that it is fast? Did you compare it to std::sort ? I would love to see the results if you have. Note that one would have compare using at least 10'000 or even 100'000 items to make a decent comparison. In tests that I have done in the past, I usually have 1'000'000 items or more. More about that below.

So your algorithm is basically a bubble sort, which is one of the worst performing sorts. I am not sure why you think you can improve on this very bad algorithm compared to what is routinely used.

markyrocks wrote:

..... that big arrays like 1000 elements or more .....

Are you aware that an array with 1'000 elements is actually quite small ? One million ints is about 4MB - which is still small, if one is using an average machine with 8 or 16 GB of ram. One billion ints is about 4 GB, is still not a stretch for the average machine. Even if one doubled that because of using 64 bit values like std::size_t, then doubled it again if it required as much ram to do the sorting as it does to store the data, we still only get to 16GB ram. That is too much for the average machine, but 1 billion is 6 orders of magnitude more then 1'000 .

I still think that the premise of your question is wrong: swapping / moving with pointers is not a slow operation. Swapping large objects by value is expensive, but C++ coders are always trying to avoid that.

In the past, I was comparing the performance of sorting std::vector versus std::map. With some advice from JLBorges and helios, I discovered that std::vector could initialise and sort 1 million ints faster than std::map could initialise 1 million ints. I had to go up to 8 million before I could get std::map to be faster. But std::map uses hashing, so if one inserts more data, then the hash function has to be recomputed for all the data again. So std::vector was the overall winner.

The other things to consider: move semantics ; concurrency (aka threading) ; and cache effects. These can greatly improve running times. But the easiest thing to do is testing: get some hard data. Make sure you have a control like using std::sort for example to compare against.

I am sorry if I sound a bit harsh, but none of what you are saying makes any sense to me. I hope that i have pointed out some things that you may not have been aware of. Good Luck, and I look forward to your reply :+)

[markyrocks]

I should have been more specific. It's surprisingly fast for arrays of 1000 elements or less. I am doing these comparisons against std sort and testing with arrays of 10, 20, 100, 1000, 10000 etc. Not sure what you want me to say, congrats you've done testing b4 too. Thanks for the math lesson and you're right I guess I'll just do nothing, accept that it's impossible to do better. Why even try.... why are any of us coding anything bc you aint going to do better than what's out there already. Just go play solitaire or something...

[seeplus]

But std::map uses hashing, so if one inserts more data, then the hash function has to be recomputed for all the data again.

??? I thought std::unordered_map (and std::unordered_set) used hashing (why recomputed?) and that std::map (like std::set) often used a tree (red-black) ?

[helios]

It actually is impossible to do better. It's been proven mathematically that it's impossible to sort a sequence in fewer than O(n log n) comparisons. It's theoretically possible to optimize the constant part of the algorithm to get non-asymptotic improvements, but that's about it.

That said, I have no reason to believe OP has discovered anything out of the ordinary. One typically doesn't optimize an algorithm by adding arbitrary levels of indirection. Let's put it that way.
Without seeing code, I can't even say whether the run time is being measured correctly, or whether the comparison is fair. Did the compiler reorder timing calls? Is the cache equally cold or hot for both operations being compared? Does OP even know what I'm talking about?