Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I'm using XNA (Monogame) in C#. My implementation contains a SpriteComponent class which has a Z property; I use this to determine the order in which to draw my entities (higher Z = drawn on top). It's a simple integer.

What I'm worrying about (premature optimization, I suspect) is the runtime complexity of the function which gets the list of all the SpriteComponents to draw, in order of their Z attribute:

List<IEntity> entitiesToDraw = currentScreen.Entities
    .Where(e => e.HasComponent<SpriteComponent>())
    .OrderBy(e => e.GetComponent<SpriteComponent>().Z)
    .ToList();

From what I've read, OrderBy uses QuickSort, which is O(n log n). Not sure about Where.

I can reasonably assume:

  • 1000+ entities can concurrently exist
  • 90% or more of entities have a SpriteComponent in them
  • Changing the Z of a sprite happens fairly infrequently for most sprites

My questions are:

  • Should I be worrying about this call at all?
  • If so, how can I reduce the runtime complexity, and/or cache the results reliably?
share|improve this question
    
You can retag your own question at any rep by editing it. I've added the tag for you, though. –  Bobson Nov 29 '12 at 14:36
add comment

1 Answer

up vote 5 down vote accepted

Not sure about Where

Where method (if applied to IEnumerable<T>) is O(N) operation, and it's a lazy operation so it will do the filtering while consumer reads the result.

Should I be worrying about this call at all?

The best way to answer this question is to measure the performance and see if it satisfies you. If not - then start thinking about caching results and refreshing them instead of calculating from scratch.

If so, how can I reduce the runtime complexity, and/or cache the results reliably?

It's hard to suggest good solution based on the information you've provided... Will the number of entities change over time? Can they "loose" SpriteComponent?

Assuming that the number of entities is the same and only Z will slightly change you can cache the sorted list from previous run, and apply TimSort or Insertion sort (you would need to implement it yourselves or grab from Wikipedia) to nearly-sorted list.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.