C++

Forum

 
Tell me how crazy this idea sounds...

Pages: 1234
helios (17506)
You didn't answer my question. How is it a dick move for me to explain why your algorithm isn't working and to show you how it can be made to work?

so how is it constructive for you to repeat what I already said and know.
So it doesn't matter what any new information I added, the fact that I repeated anything at all ("your code doesn't work") makes my comment unconstructive in your mind. Is that it? Somehow I doubt it.
If I had to guess, I'd say you just take it personally when someone criticizes your code. That's common, but it's something you need to grow out of.

I wasn't asking for help so when I need it I'll let you know.
So what do you want, then? What's the point of this thread?
markyrocks (346)
How is it a dick move... bc in my mind it serves no legitimate purpose except for mockery. It's like me taking you're picture and drawing a mustache on it.

Your information would be useful if like you said it was new. You saying things to me that I already know that I didn't ask for your input on again leads me to believe that you think I'm some kinda idiot. No I don't take it personally when someone critiques my work in a respectful way, usually preceeded by a request for said input. I don't need to grow out of anything, again disrespectful.
helios (17506)
You don't take it personally, yet you think criticizing your code is a form of mockery. Sure.

usually preceeded by a request for said input.
This is a forum, man. If you don't want people's opinions just don't post. If you post anything you're inviting commentary. If you can't deal with that, start a blog and disable comments.

Not to mention you explicitly invited commentary in the title of this thread:
Tell me how crazy this idea sounds...
You got feedback and you didn't like it. I certainly haven't seen that a million times before here. *Eyeroll*
markyrocks (346)
Not all criticism is mockery. That's just how you're trying to paint my response bc of lack of self awareness. I can deal with it just fine, thanks for your concern. Obviously there's been plenty of comments in this thread and yet you're the only person being a dick about it. Normally someone who wasn't trying to be a troll would have just left it alone and went about their business but yet here you are. Do you not agree that posting someone's entire code , commenting out all but 2 or 3 lines and adding swap(a,b) is not trolling? See above about lack of self awareness. Yes I got feedback from a troll I didn't like *eyeroll* yes you've seen it a million times bc of your condescending attitude and trollish nature I would not be surprised if you get this reaction quite commonly.
helios (17506)
Okay. You've already agreed that everything I said previously was correct. How would you have rephrased this post http://www.cplusplus.com/forum/beginner/278466/2/#msg1202411 to "remove the trolling" while communicating the same objective information? I think this could be a useful exercise for at least one of us.
Ganado (6784)
The conversation in this thread started going south by the end of the first page, well before the "std::swap" post that we seem to be dwelling on now. I read this thread, but still don't understand what the initial purpose of it was. Helios gets shit on because he's the one that bothers to initially respond, and doesn't qualify his posts with meaningless feel-good fluff. When I first read your post, I also didn't understand much of it, but the difference is I didn't even bother trying to help decipher what was being said.

How would you have rephrased this post ... to "remove the trolling"
I'm not saying it was trolling, but for me the main purpose of the commented out code was to show how the previous structure of the code still existed in some way, but was simplified, right? Perhaps this "hand-made diff" isn't useful when most of the code becomes comments. You could still explain what you changed (like you said in your "EDIT:" section), but just don't bother putting in the previous comments when the comments take up the majority of the code.

One thing from this thread that I love is the series of famous quotes that all complement each other,
Quote from David Wheeler "All problems in computer science can be solved by another level of indirection"
Here's another frequently cited quote:
"Most performance problems in computer science can be solved by removing a layer of indirection" [unknown]
"All problems in computer science can be solved by another level of indirection"
Except the problem of too many levels of indirection.
TheIdeasMan (6781)
Well here you go: I came up with an algorithm of my own. Some uses cases probably don't really make it practical.

All it does is make a new vector where the subscript is the value.

It is about half the speed of std::sort, but it is only single threaded. There are 1 million items. Output after the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>

int f();
class Timer
{
public:
  Timer(const std::string& name)
    : name_ (name),
      
      start (std::chrono::steady_clock::now() )
    {
    }
  ~Timer()
    {
    auto end = std::chrono::steady_clock::now(); 
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count(); 
    std::cerr << name_ << ": " << elapsed << " ns\n";
      
    }
private:
  std::string name_;
  std::chrono::steady_clock::time_point  start;
};                     

int main() {

    constexpr std::size_t SIZE {1'000'000};
    std::vector<std::size_t> unsorted(SIZE);
    std::generate(unsorted.begin(), unsorted.end(), f );

    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(unsorted.begin(), unsorted.end(), g);

    std::vector<std::size_t> sorted(SIZE);
    {
        Timer("Subscript Sort");
        for(const auto& item : unsorted) {
            sorted[item] = item;
        }
    } // Timer goes out of scope
    std::vector<std::size_t> sorted2 = unsorted;
    {
        Timer("std::sort ");
        std::sort(sorted2.begin(), sorted2.end());
    }
}

[[nodiscard]]
int f() 
{ 
    static int i;
    return ++i;
}


Subscript Sort: 135 ns
std::sort : 66 ns
Ganado (6784)
My results for your code are a decisive "maybe".
cplusplus278466>main
Subscript Sort: 0 ns
std::sort : 0 ns

cplusplus278466>main
Subscript Sort: 302 ns
std::sort : 0 ns

cplusplus278466>main
Subscript Sort: 0 ns
std::sort : 302 ns


Edit: Either my compiler is re-ordering the instructions, or there is something wrong the the timing. I am getting the same numbers even when I increase N. I suspect you will too.

Edit 2: If I add a system call before the end time call, I get more realistic numbers 
1
2
 
     system("");
     auto end = std::chrono::steady_clock::now();


For N = {1'000'000}; I get
Subscript Sort: 70942856 ns
std::sort     : 67622541 ns


But if I re-order it, I get around the same
std::sort     : 70594795 ns
Subscript Sort: 67158259 ns


So this test is invalid, imo. I would suggest making completely independent programs (with #if maybe) to make proper timing tests.

Increasing N to perhaps drown out the effect of the system call:
Subscript Sort: 71517926 ns
std::sort     : 72971753 ns


std::sort     : 72233066 ns
Subscript Sort: 71535435 ns


From this trial of 1, it seems std::sort is 1-2% faster.
Last edited on
TheIdeasMan (6781)
@Ganado

Edit: Didn't see your edits.

Yeah I had some different results on consecutive runs, but that is probably due to the call to std::shuffle. But I never had any 0 timings.
It's 04:00AM at this end, I wonder if I screwed something up? The timings are way less than what againtry had, I didn't expect mine to be that quick for 1 million items, I was expecting something around 12 milliseconds. Hopefully we are all using Release mode ;+)

Any way, the idea of this post was to demonstrate to the OP a simple algorithm.
Last edited on
TheIdeasMan (6781)
Ok, so I wonder what is wrong with the Timer class?

I might have a misconception with duration's.

It's really late for me now, need to stack ZZZZZZZZzzzzzzzzz's
helios (17506)
doesn't qualify his posts with meaningless feel-good fluff.
Thanks. I like it when people get what I'm about.

I'm not saying it was trolling, but for me the main purpose of the commented out code was to show how the previous structure of the code still existed in some way, but was simplified, right? Perhaps this "hand-made diff" isn't useful when most of the code becomes comments. You could still explain what you changed (like you said in your "EDIT:" section), but just don't bother putting in the previous comments when the comments take up the majority of the code.
That was my intention, yes. Perhaps I was a bit hasty when I posted it; I literally just copied what I had on my IDE while I was trying to get it to work. Basically I was saying "look, I didn't just write an unrelated sort. It's your code with a bunch of stuff that doesn't work removed, and now it works".

TheIdeasMan: That's very nearly counting sort, just without allowing repeats. It's one of the few non-comparison sorts, thus not subject to the O(n log n) lower bound.
againtry (2313)
I like it when people get what I'm about.

Me too.
Ganado (6784)
To beat the commented-code dead horse further: I don't agree that it's reasonable to see the code as trolling; I was just trying to play devil's advocate for why one might interpret it as such.
seeplus (6457)
Either my compiler is re-ordering the instructions,


It's called optimisation! No. The issue is that the scope of the temporary Timer is only for the duration of the statement. It doesn't extend until the end of the block. Using a named Timer causes the duration to extend to the end of the block as expected.

Try this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <numeric>
#include <cstdlib>

class Timer
{
public:
	Timer(const char* name) : name_(name), start(std::chrono::high_resolution_clock::now()) {}

	~Timer() {
		const auto diff {std::chrono::high_resolution_clock::now() - start};

		std::cout << name_ << " took " << std::chrono::duration<double, std::milli>(diff).count() << " ms\n";
	}

private:
	std::string name_;
	decltype(std::chrono::high_resolution_clock::now()) start {};
};

int main(int argc, char* argv[])
{
	constexpr std::size_t SIZE_ {1'000'000};
	const size_t sze {argc == 2 ? std::atoi(argv[1]) : SIZE_};

	std::vector<std::size_t> unsorted(sze);

	std::iota(unsorted.begin(), unsorted.end(), 0);
	std::shuffle(unsorted.begin(), unsorted.end(), std::mt19937(std::random_device {}()));

	std::cout << "Size " << sze << '\n';

	{
		std::vector<std::size_t> sorted(sze);
		Timer t1 ("Subscript Sort");

		for (const auto& item : unsorted)
			sorted[item] = item;
	}

	{
		std::vector<std::size_t> sorted {unsorted};
		Timer t1("std::sort");

		std::sort(sorted.begin(), sorted.end());
	}
}


Which on my computer gives:


Size 100000
Subscript Sort took 0.278954 ms
std::sort took 6.95211 ms

Size 1000000
Subscript Sort took 6.80986 ms
std::sort took 85.1946 ms

Size 10000000
Subscript Sort took 119.491 ms
std::sort took 990.512 ms

Size 100000000
Subscript Sort took 1666.02 ms
std::sort took 11347.1 ms

Last edited on
seeplus (6457)
For comparison purposes, timings for a bubble sort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
template<typename T>
void bubbleSort(std::vector<T>& a)
{
	auto n {a.size()};

	do {
		size_t newn {1};

		for (size_t i = 1; i < n; ++i)
			if (a[i - 1] > a[i])
				std::swap(a[i - 1], a[newn = i]);

		n = newn;
	} while (n > 1);
}



Size 1000
Subscript Sort took 0.001185 ms
std::sort took 0.044253 ms
My bubble sort took 0.735315 ms

Size 10000
Subscript Sort took 0.019756 ms
std::sort took 0.558697 ms
My bubble sort took 126.553 ms

Size 100000
Subscript Sort took 0.25011 ms
std::sort took 7.11094 ms
My bubble sort took 15068.9 ms


I won't go any larger. You get the picture....
seeplus (6457)
I love is the series of famous quotes


My favourite is by Thomas Waton of IBM fame "I think there is a world market for maybe five computers". Admittedly, this was said in 1943. Perhaps he meant five billion?

My second is by Ken Olsen, founder of DEC in 1977 "There is no reason anyone would want a computer in their home".

Coming in at a strong no. 3 by no less than Bill Gates in 2004 "Two years from now, spam will be solved."

What are other's famous quotes?
Last edited on
TheIdeasMan (6781)
@helios

It's not very often that I expect to have done something original, thanks for providing the name, I hadn't heard of that before :+)

@seeplus

Thanks for all of your effort, not just for fixing my code, but your effort in general on this forum - I always look forward to reading your code :+D. I guess not naming the Timer is a really dumb thing that I did at 04:18AM !!
helios (17506)
To beat the commented-code dead horse further: I don't agree that it's reasonable to see the code as trolling; I was just trying to play devil's advocate for why one might interpret it as such.
No worries, I perfectly understood what you were going for. Obviously I agree, and I maintain that OP is just sensitive about having his code criticized.

TheIdeasMan: You might find this an interesting read: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
The non-comparison algorithms are particularly interesting because of the unusual tricks they take advantage of, which allows them to have
doug4 (1534)
don't leave me hanging.

which allows them to have ... what?
dutch (2548)
... better than n log n performance.
Pages: 1234