| View previous topic - View next topic |
| Author |
Message |
white_door
Icemonkey
Joined: 30 May 2002
Posts: 243
Location: New Zealand
|
 Posted: Mon Jun 28, 2004 9:22 pm Post subject: |
[quote] |
|
It's quite funny how things aren't always as fast as you think or as slow. In the case of sorting something like a sprite list, each frame there might be only a few changes to an otherwise sorted list, so actually a bubblesort would be my choice. You would lose out at the start, but in the long run...
Which is also why I quite liked the second article, it shows quite a clever way of gain quite a bit of speed given certain limitations. And while I doubt I will ever use Director, I still found the article very interesting.
|
|
| Back to top |
|
 |
DrunkenCoder
Demon Hunter
Joined: 29 May 2002
Posts: 559
|
| Posted: Mon Jun 28, 2004 9:38 pm Post subject: |
[quote] |
|
The usuall way to implement std::sort is via intro sort, basicly it's a quicksort that gets monitored and when performance degrades it switches to heapsort that is O(n log n).
Always profile your code...
_________________
If there's life after death there is no death, if there's no death we never live. | ENTP
|
|
| Back to top |
|
|
Joakim
Tenshi's Bitch (Peach says "Suck it!")
Joined: 05 Apr 2004
Posts: 64
|
| Posted: Mon Jun 28, 2004 9:45 pm Post subject: |
[quote] |
|
|
So you're telling me that I'm using an algorithm that is a lot worse than bubble sort when the list is almost or fully sorted? Because that list will be 99% sorted all the time!
|
|
| Back to top |
|
|
DrunkenCoder
Demon Hunter
Joined: 29 May 2002
Posts: 559
|
| Posted: Mon Jun 28, 2004 9:55 pm Post subject: |
[quote] |
|
| Joakim wrote: | | So you're telling me that I'm using an algorithm that is a lot worse than bubble sort when the list is almost or fully sorted? Because that list will be 99% sorted all the time! |
No he's telling you that under a certain implementation performance of quicksort will degrade to O(N^2), depending on how you choose your pivot that could be nearly sorted, nearly backwards sorted or as was proved sometime in the 70ties won't happen at all (although the pivot choosing algoritm used then altough theoreticly nice proves to be ineffecient in practice)
Also note that std::sort most of the time is *not* implemented via quicksort as I said.
Still, always profile before rolling your own solutions to something in the standardlibrary or making a more complicated solution than needed.
_________________
If there's life after death there is no death, if there's no death we never live. | ENTP
|
|
| Back to top |
|
|
mandrake_lazy
Guest
|
| Posted: Tue Jun 29, 2004 5:30 am Post subject: |
[quote] |
|
well, hey look over there-> there's the original topic! oh we have strayed from it's path!
Either way, he's using director, so std::sort is completely out of the question. And, also, there is no reason to question why he chose canopy instead of z-sorting. Both implementations work, and both ahve constraints and problems that arise. In a clinch (ie: a limited peice of time he had to finish the game) he chose one way. Why is his way better/worse than any other way?
|
|
| Back to top |
|
|
DrunkenCoder
Demon Hunter
Joined: 29 May 2002
Posts: 559
|
| Posted: Tue Jun 29, 2004 9:14 am Post subject: |
[quote] |
|
| mandrake_lazy wrote: | well, hey look over there-> there's the original topic! oh we have strayed from it's path!
Either way, he's using director, so std::sort is completely out of the question. And, also, there is no reason to question why he chose canopy instead of z-sorting. Both implementations work, and both have constraints and problems that arise. In a clinch (ie: a limited peice of time he had to finish the game) he chose one way. Why is his way better/worse than any other way? |
I think we're all quite awere that he's using director esp the few of us that strayed a bit off-topic and I actually consider it better to address that issue as quickly as possible instead of leaving someone wondering and getting the impression that std::sort would be a bad alternative without even running a profiler.
About the use of canopy instead of z-sorting the article explains the design quite well yes it's a tradeoff but so is everything else it works wonderfully in the game (wich I've played through loved it).
I think Nephelim explains his design desicions in good detail and they work for his game, he's not telling you that it's the only way or the "best" but he explains very well why he made those choices and they make sense.
_________________
If there's life after death there is no death, if there's no death we never live. | ENTP
|
|
| Back to top |
|
|
mandrake_lazy
Guest
|
| Posted: Fri Jul 02, 2004 12:28 pm Post subject: |
[quote] |
|
|
I wasn’t saying that Nephlim was claiming his was the only way, but instead questioning those attacking his methods in favor of their own. Maybe, some implementations are not quite possible all of the time.
|
|
| Back to top |
|
|
DrunkenCoder
Demon Hunter
Joined: 29 May 2002
Posts: 559
|
| Posted: Fri Jul 02, 2004 1:20 pm Post subject: |
[quote] |
|
My reply wasn't aimed at you mandrake it was aimed at the people selling their methods.
_________________
If there's life after death there is no death, if there's no death we never live. | ENTP
|
|
| Back to top |
|
|
mandrake_meep
Guest
|
| Posted: Fri Jul 02, 2004 1:40 pm Post subject: |
[quote] |
|
|
oh. never mind then, it seems we are on the same page.
|
|
| Back to top |
|
|
Nephilim
Mage
Joined: 20 Jun 2002
Posts: 414
|
|
| Back to top |
|
|
Rainer Deyke
Demon Hunter
Joined: 05 Jun 2002
Posts: 672
|
| Posted: Wed Jul 07, 2004 3:53 am Post subject: |
[quote] |
|
|
A fascinating series of articles, especially the part about the cutscene engine. Thanks for posting them.
|
|
| Back to top |
|
|
