Tell me how crazy this idea sounds...
LOL. Oops. I guess I got distracted. Yes, better than linearithmic performance. Some are even linear.
Last edited on
@helios
Thanks for the link to all the sorting algorithms :+)
I am thinking about creating a new container: a bit like std::deque, but allows insertions with
One thing I am not sure about is an aspect of concurrency: if I have a single std::vector is it possible to have multiple threads mutate it? I mean in this situation there is a guarantee that a particular subscript won't be accessed by multiple threads, so I won't need any mutexes or locking of any kind? Maybe I can just use std::async with a suitable insert function?
This is all just thoughts at the moment, after some red wine ;+) I probably should start a new topic about this.
Thanks for the link to all the sorting algorithms :+)
I am thinking about creating a new container: a bit like std::deque, but allows insertions with
operator[] , will see how that goes. Hopefully it will deal with the issue of avoiding memory hog when there is sparsity, might even try to deal with negative values and non uniqueness as well.One thing I am not sure about is an aspect of concurrency: if I have a single std::vector is it possible to have multiple threads mutate it? I mean in this situation there is a guarantee that a particular subscript won't be accessed by multiple threads, so I won't need any mutexes or locking of any kind? Maybe I can just use std::async with a suitable insert function?
This is all just thoughts at the moment, after some red wine ;+) I probably should start a new topic about this.
that page is neat but shell is misleading. Modern sequences have cut the time down (the best ones currently the run time isn't proven out), you can sort of generalize it by saying 'a good sequence gives n^ (x+1/x) eg 4/3 or 7/6. The bigger x gets, the faster it runs...
sadly they cut up the wiki page, it used to have like 30 sequences, they have reduced it to some older ones and the top couple new ones.
yes, multiple threads can fool with the same vector.
consider passing 2 sort threads [0]-[n/2] and [n/2+1][last] and sorting those in parallel then merge back (not merge sort, just merge). This works great for large data on multi core machines. Speaking of shell, I keep thinking there may be a way to exploit the presorted nature (the closer the array is to sorted, the faster it runs) to make a sequence that exploits a threaded sort result to do the merge cheaply.
sadly they cut up the wiki page, it used to have like 30 sequences, they have reduced it to some older ones and the top couple new ones.
yes, multiple threads can fool with the same vector.
consider passing 2 sort threads [0]-[n/2] and [n/2+1][last] and sorting those in parallel then merge back (not merge sort, just merge). This works great for large data on multi core machines. Speaking of shell, I keep thinking there may be a way to exploit the presorted nature (the closer the array is to sorted, the faster it runs) to make a sequence that exploits a threaded sort result to do the merge cheaply.
Last edited on
Topic archived. No new replies allowed.