Jump to content
  • Advertisement
Sign in to follow this  
  • entries
  • comments
  • views

Todays Lesson

Sign in to follow this  


Todays Lesson:

Don't assume that the third-party software package you are using has any sort of logical consistency within its functions. And be very careful to read every part of their documentation, no matter how much of it seems to be copy&pasted.


I'm using a container class that has optional sorting abilities. When you call "AddRange", the items are added to the container at the end, and you are required to manually call "Sort" at the end to sort it.

I made the shortsighted assumption that the "Add" function (which adds a single item to the container) would work in the same way.

Since the contents of the container are generated on the fly, I don't have a pre-existing container of these items to call "AddRange" with.

So rather than introducing an intermediary container, I simply "Add"ed each item as it was generated, and "Sort" was called after all items were added.

Weeks went by, and everything seemed to work great. More and more data was added to the program. The program became slower and slower and slower, until finally, it was noticable to the point of annoyance. Loading 5,000 transactions shouldn't be taking over 6 seconds!! It should be almost instantaneous!

A few breakpoints later, I noticed that the routine to add items to the container was the culprit. "That's odd," I remarked. I was certain that it would be the drawing code; graphics operations are typically the worst cpu-eaters of most programs.

So I dug deeper and deeper into the documentation, until I found a quaintly hidden gem: "Add causes items to be added to the container at the end if the Sorter object is null, or into its properly sorted position if it isn't."

Well gosh; why would Add auto-sort a single item (using a quicksort, no less, which is insanely bad when you're inserting a single item into to an already sorted container!!), yet AddRange not?

Who knows.

But it turns out that I was doing N+1 quicksorts, giving my generation method a nice complexity factor of O(N^2logN), which, is even worse than a bubble sort.

To get around this, I ended up creating a one-time-use array (The AddRange function doesn't have any overloads that allow you to specify how many items in that array to add, it just assumes you're adding the whole thing) to store the generated items, before passing that array into the container.

Seems like a waste. Eesh.
Sign in to follow this  

1 Comment

Recommended Comments

Which is why when using 3rd party software... you make NO assumptions... and in most cases you avoid 3rd party software


Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!