Thread: Distinct doubles

Originally Posted by laserlight

I did, by stating that "it appears to be using the very property of strings being strings of characters to organise the strings into a tree structure". A trie is "a tree for storing strings in which there is one node for every common prefix". I even suggested what you now conclude as "one way to use the algorithm for doubles would be to consider a double to be an 8 character string and use the algorithm directly".


As I noted earlier, the correct standard container for your purposes would be std::map, not std::set.


If you use std::vector, then you should only use std::sort() and not std::unique(). I gave you the std::unique() suggestion because you only mentioned counting the number of distinct elements. I do not think that there is a standard algorithm to perform the count of the distinct groups, but it does only take a single pass after the range is sorted. Ultimately, the time complexity will be the same as for std::map, so if you need something asymptotically faster, neither will suffice.

You are right. Going back and reading your comments now makes sense, which tells me you did have a clue as to what the algorithm was doing. I didn't know what the algorithm was, and you failed to give me a name for the algorithm, so I had no idea what you were saying. Up until then the only thing that I was familiar with was an ordinary binary tree.

I actually haven't tried to solve my problem using std::map, but I will run a test to see what I get. I'll try to post my final code and compare it with the std version. Judging how std::set compares with the digital search trie, I figured it would be slow too.

Originally Posted by laserlight

I feel that ArlexBee-871RBO should have:

• Stated clearly the goal of the algorithm instead of stating it partially.
• Linked to the source of the implementation instead of vaguely stating that "found this block of code on the web".
• Posted the equivalent example using the standard library.
• Posted the relevant performance comparisons from the start.

The first point would have avoided getting incorrect suggestions and a correction to use std::map instead of std::set from the start. The second point could have more directly led to a explanation of the algorithm. The third point would have avoided grumpy's assumption that perhaps ArlexBee-871RBO did not really know how to use the standard library correctly in this case. The fourth point would make it more convincing that there was an attempt to actually measure to see if the performance was good enough.

The reason I didn't post my actual problem that I was trying to solve and my goal was because I knew I would get flamed by some for asking help with something that I had almost no clue as to how to solve without showing some lines of code first.

I had a rough idea of what was needed, and that was to find the distinct number of doubles. That was a starting point for me. Because I needed the best performence, I Googled to find something that defeats the std::set. I had a rough idea of what the original algorithm that I post was doing, and I managed to modify it to work with doubles. But I had a sense that it might be doing something wrong because I didn't know what it was, so I thought I post here.

I figured the code I posted would make sense to some because it's a complete program. It's not just some random block of code that doesn't run. Anyway...

I'll post some comparison code onceI finish up with the digital trie and figure out which is the fastest.

Originally Posted by anon

There surely has been some misunderstanding.

OP, it might be indeed hard to determine how good you really are from the initial posts, so there's no reason to be offended. But I think we've established now that you have a clue

Yes, I can agree with that. There was some misunderstandings. And I wasn't offended, really. I just can't stand to see people treat others so harshly when there is no real reason for it, and I'm not afraid to bite back when someone treats me like that.