Showing posts with label C#. Show all posts
Showing posts with label C#. Show all posts

Saturday, March 07, 2009

Scaling images while keeping aspect ratio and max size

In an application I am writing, I recently came across the need to accept uploaded pictures and scale them to a set size for inclusion in a table. Simple stuff, just a “let’s make all pictures the same size for easier layout” kind of deal. Say the “target” size was 800x600, and given a size originalSize, the function needs to figure out a new size for the image that meets the following demands:

1. The entire image must fit inside the target size.

2. The image must keep its’ aspect ratio.

3. The size of the new image must never be larger in either direction than the original (no upscaling)

4. The image must be as large as possible without breaking the three other rules.

After a few days of wrapping my head around this (and doing other stuff), I realized it was all the aspect ratio – which way we used to calculate the width/height that should be returned, depends entirely on which of the aspect ratios are larger; That of the original image, or that of the target size.

I of course started with the unit tests – a MbUnit RowTest with 20 rows of different combinations of picture sizes, new sizes, and expected result sizes. I had done all the calculations on paper in advance and was pretty sure they were correct.

After a little bit of experimentation, I ended up with this method:

  1: public static Size GetRenderSize(Size originalSize, Size targetSize)
  2: {
  3:     float targetRatio = targetSize.Width / (float)targetSize.Height;
  4:     float imageRatio = originalSize.Width / (float)originalSize.Height;
  5: 
  6:     if (imageRatio < targetRatio) // Target ratio is wider than the source ratio, scale by height
  7:     {
  8:         var smallerY = Math.Min(originalSize.Height, targetSize.Height);
  9:         return new Size((int)Math.Round(smallerY * imageRatio,0), smallerY);
 10:     }
 11:     // Target ratio taller than source ratio or the same - scale by width
 12:     var smallerX = Math.Min(originalSize.Width, targetSize.Width);
 13:     return new Size(smallerX, (int)Math.Round(smallerX / imageRatio,0));
 14: }


A lot simpler than I thought, and seems to give correct results on each and every calculation. :)

Sunday, August 31, 2008

Collection sorting – when the built-in stuff doesn’t work

C# and the the .Net framework has a lot of excellent support for collections – no more mucking about creating your own linked list structures, hash tables etc. This means you get easy to use lists of your stuff almost for free, saving you a lot of testing/debugging whenever you make a brain fart during tedious boilerplate coding.

The network also has a lot in place for sorting these collections – the Sort() function allows you to plug in your own comparer and will then perform a relatively performant sort for you (QuickSort? I dunno). Isn’t it nice that we can skip this stuff and concentrate on getting the logic unique to our application right?

Well, yes. However, there are cases where the default sort does not work. I recently encountered one of those in one of my applications.

This application keeps a bunch of tags. You know, the del.icio.us kind, that you can use to label your data in different ways. We can mark certain products with a tag, and then, when we search for the tag, we’ll find all producst tagged by it. Simple stuff.

One particular feature here is that each tag keeps a list of “implied tags” – i.e. if you add this tag, you also implicitly have these tags as well. An example will hopefully clarify;

If you have the products ham, bacon and sirloin, you might want a tag for the first two named pork, and a tag for the last named beef. In addition, you would typically have a tag named meat that is implied both by pork and beef. That way, if you search for products that contain meat, you will find any products that contain ham, bacon or sirloin.

This is a simple, contrived example, but it should illustrate how implied tags work. It also leads to some limitations on the implementation of this system. Data in this case is to be stored in an XML file, and will be fetched in such a way that when a tag references (implies) another tag, the implied tag will already have to be defined; I.e. an implied tag has to come before the tag doing the implying in the XML file.

In my case, recursive tag implication is not allowed. Tag A can not imply tag B which in turn implies tag A, or any deeper variation of that. Therefore, the solution is simple; In the XML file, we need to make sure that tags that don’t imply anything else come first (there will always be at least one of these, because of the limitation on recursion). Then come the tags that only imply one or more of these first tags, and then in turn the tags that imply the tags we already have. Basically, a tag can only be added to the file once all tags it implies are already in the file.

My first attempt to take care of this was a relatively boneheaded one in retrospect; I implemented a comparer, implementing IComparer<Tag> to figure out the sort order, based on wether or not tag X implies tag Y, or Y implies X (and if they both implied each other, I threw – that’s tag implication recursion right there). Now, in theory this would work, but unfortunately the List.Sort() method was a little to clever for me. The result of one single comparison in my case only says something about the relation between these two elements. However, for the Sort() method, if A comes before B, and B comes before C, then we don’t even bother comparing A and C – we’ve already worked that part out implicitly. It doesn’t take a lot of imagination to come up with a situation where a tag list wouldn’t be sorted in the right order with this kind of sorting. And a quick unit test or two easily demonstrated that this would not handle all cases:

[Test]
public void TestImplicationSortingCreatesCorrectOrder()
{
var t1 = new Tag("Level 1");
var t2 = new Tag("Level 2");
var t3 = new Tag("Level 3");

t2.ImpliedTags.Add(t1);
t3.ImpliedTags.Add(t2);

var list = new List<Tag>() { t3, t2, t1 };
var newlist = Tag.SortTagListByImplication(list);

Assert.AreEqual(t1, newlist[0]);
Assert.AreEqual(t2, newlist[1]);
Assert.AreEqual(t3, newlist[2]);
}


This test would easily fail using the built-in sorting. Tag.SortTagListByImplication( IEnumerable<Tag>) was just a static wrapper that created the correct comparer and performed the sort.

To get this to work properly, however, I had to implement the sorting myself, so I chose to do it in the same method:


public static List<Tag> SortTagListByImplication(IEnumerable<Tag> tags)
{
if (tags == null)
throw new ArgumentNullException();

if (tags.Count() == 0)
return new List<Tag>(tags);

var newlist = new List<Tag>();
var sourceitemlist = new List<Tag>(tags);

do
{
var newbatch = new List<Tag>();
foreach (var t in sourceitemlist)
{
var hasAnyUnresolvedImplications = false;

foreach (var it in t.ImpliserteTags)
{
if (!newlist.Contains(it))
hasAnyUnresolvedImplications = true;
}
if (!hasAnyUnresolvedImplications)
newbatch.Add(t);
}
if (newbatch.Count == 0)
throw new InvalidOperationException("No new Tag items added to list - recursion nightmare!");
newlist.AddRange(newbatch);
foreach (Tag t in newbatch)
sourceitemlist.Remove(t);

}
while (sourceitemlist.Count > 0);

return newlist;
}
This code is very much a “first pass” – i.e. I stopped working on it once the unit test started working. Yes, I am quite sure it can be improved. However, right now, it does what I need it to do, so I will leave it alone.

The point of this post? I just wanted to mention that there are situations where the built in sorting logic is not proper. If it helps someone in the future, great. :)

Saturday, August 30, 2008

Book impression – C# in Depth

I’m calling this an impression, since I have no idea what kind of stuff I have to put in here to justify calling it a review. Smile

The other day I finished reading C# in Depth by Jon Skeet, one of those people with such a deep understanding of how stuff works that you just have to admire them. Small disclaimer; Jon replied to a newsgroup post of mine a few years back and turned out to be a very helpful and friendly guy. So I might be a bit biased.

The title of the book is no lie; We’re really going in depth here. Not through the whole language, mind you, “just” the improvements in version 2 and 3 of the C# language itself (which is versioned separately from the .Net framework). That means we get a lot of information on delegates/lambdas, expression trees, and other would-be headache-inducing low-level (at least from my viewpoint) programming constructs.

Then again, I guess you could point out what a nerd I am when I admit that I read part of this book on the beach in Alicante (Spain) during my summer vacation. Big Grin

I have read quite a few programming books, from basic C introductions to relatively complex stuff on a diverse range of topics. However, I must say that no book has ever triggered the “coding itch” quite as bad as this one, and while I am by no means any less of an amateur programmer now than I was before, I feel that I have a deeper understanding of a lot of what the book explains, and I have also been inspired to take my understanding of the language further; If only every online tutorial and article were written as clearly as Jon’s book.

While I am right now plowing through Programming WPF and jQuery in Action for specific projects, next on my list is LINQ in Action – I suspect I will have an easier time grokking that one thanks to C# in Depth.

If you want to have a deeper understanding of the C# language and learn useful stuff like how to use many of the technologies that make up LINQ separately for other things, this is definately a great book. I recommend it highly!

Wednesday, August 27, 2008

Automatically implemented properties and WPF

This blog hasn’t lived much recently – I’ll try to post a little more, but no promises (since noone reads it anyway).

I’ve been looking into Windows Presentation Foundation lately, and it is very fascinating; It opens up a lot of doors for new UI possibilities, but also quite a few new challenges. If you want to display your object model in the “WPF way”, one of the things you have to do is implement INotifyPropertyChanged. This allows WPF to pick up on object changes and update the user interface accordingly.

One of the very helpful new features in C# 3 (i.e. the language, which confusingly was released with .Net 3.5) is automatically implemented properties. Basically these guys allow you to implement trivial properties on objects without a lot of code, backing fields etc. A one-line property makes code more readable, and you have less possibility of failure in a no-code property than one that contains some code.

These two things put together, however, are currently not compatible by default. If you have an automatically implemented property, it will not notify WPF of changes to its’ value. There are of course ways of doing this using reflection and attributes and such, but wouldn’t it be really cool if the C# compiler knew of INotifyPropertyChanged and actually triggered the PropertyChanged event for you automatically on these autoprops?

I certainly think so, but I can see why some people would disagree.

No matter what, I think it would be really useful.

Monday, September 24, 2007

Fun with optimalization

Sloth, being written in/towards the .Net Framework (currently 2.0), is an object oriented application. I try to follow a few general principles on how to do stuff. One of the things I try to avoid is premature optimalization - the idea being that you first get it to work, with unit tests as a backing confidence booster, and THEN you optimize.

Just for fun, I thought I would optimize something that has survived since the early days of Sloth v0.0.0.1 - it is well proven code, and it would be very easy to verify if my optimizations break anything, as Sloth would cease to function at all.

The area I chose for this experiment is the Channel object, more specifically the OnNow and OnNext properties. These basically tell the caller which show is on the channel right now, and which one is on next.

A run with a profiler shows me that while this does not affect overall application performance much, it is definately ready for some improvements. These properties have largely gone unchanged after being more or less among the first 20 or so things written in Sloth. Optimizing them should be very easy, but I was eager to see just how much I could squeeze out of it. The routines are used by the main window to determine which shows to list, as well as by the "early warning system" that scores OnNow/OnNext before anything else to get alerts launched ASAP after Sloth starts.

The original OnNow would loop through the collection of shows until it found one whose StartTime was less than/equal to DateTime.Now, and whose StopTime was larger than/equal to DateTime.Now. If a match was found, it was returned. Since Sloth never adds shows that end before the current day to the list, at most this would mean having to traverse a whole day of shows before finding the right one. Didn't take long, but it took long enough - there was a definitive room for improvement here!

The implementation of OnNext was way worse. Keep in mind that this was written in the days where Sloth made no warranty that the list of shows was sorted in chronological order. So basically, OnNext would loop through the collection, and if it found any show with a StartTime larger than DateTime.Now, check if it was lower than what it already had (if anything), and if so, grab it. This meant looping through the whole collection. Large room for improvement.

While these numbers are taking from a single profiling session, and in no way represent any real benchmarks, they give you a good indication of the "savings" possible. What I did was basically profile these two properties from Sloth startup until the UpdateScores routine was finished and all alerts fired.

Original OnNow 67 ms
Original OnNext 82 ms

Wow - together they consume a whopping 0.15 seconds on my PC! Way to pick an important target for optimization! ;)

Well, I'm in it for the lesson, not the ... eh ... something.

So time to try to be clever.

Optimization 1 - Cached objects

So how about we cache the show found to be OnNow, the show to be OnNext, and that way, we don't have to look through the list all the time? Excellent idea! How do we know when we actually have to go looking again? Easy - OnNow.StopTime should tell us when the show currently on is over and the next one is ready. So I added two local variables for onNow and onNext, and a DateTime called cachedOnNowSwitch (yeah, clever name) which would be set to the time it was necessary to run the list again.

OnNow simple optimization 19 ms
OnNext simple optimization 42 ms

That's nice - reducing OnNow by a third and halving OnNext shows that caching the objects was a good plan. If only we could tighten the list traversal a little..

Optimization 2 - Cached DateTime.Now

In the profiler, DateTime.Now suddenly stuck out as a sore thumb. It seems like fetching this from the OS takes a relatively long time. So how about instead of calling DateTime.Now all the time I do date comparison in the list, I create a local DateTime called now that I set at the beginning, and then compare to it instead?

OnNow medium optimization 6,8 ms
OnNext medium optimization 28 ms

Okey, now we're talking! But it should be possible to optimize even further...

Optimization 3 - No more OnNext list walking

Since the original code was written, Sloth has started ensuring that the show lists are sorted at all times. It's just more efficient that way. So is it really necessary for OnNext to run through the whole list of shows to find its' target? Of course not.

Since OnNow is cached and these two are always called near each other, lets have OnNext just call showlist.IndexOf(OnNow) and add 1 - that should be our show!

OnNow cool optimization 6,1 ms
OnNext cool optimization 3,2 ms

No special reward for OnNow this time around, just an insignificant brain fart probably. But OnNext is starting to look real good!

Optimization 4 - Cache the IndexOf result

Since we already know via the cached DateTime when our OnNow will be outdated, why don't we just cache the result of the IndexOf call as well? Also, let's add some checking for empty show lists and not doing anything when hitting out-of-bounds conditions.

OnNow super optimization 2,9 ms
OnNext super optimization 0,2 ms

Nice numbers!

So there we have it - I'm not going to try to go further, as there is probably nowhere left to optimize for a developer of my skill level. Most of the fat now is in the looping and date comparison stuff, which I can do very little about. So I am plenty happy with the outcome.

I'm looking forward to seeing what can be done in other time-intensive Sloth loops!

Until next time...

Monday, June 11, 2007

Simplicity is overrated

So I have this new thingy in Sloth v0.1 that downloads some images off the net. It's not very advanced at all, it pretty much just fires off a Google Images search and gets the results (i.e. the first 20 or so pictures), puts them in an owner drawn ListBox, and whenever one is clicked (or when the first one is added), the real size image will be put in a PictureBox.

Nothing to it, right?

Well, I wanted this to be quick without slowing the UI to a crawl, so getting the images from the web would have to happen through the magic of threads. And that is always when things get interesting.

Now, the first thing I did was to start one thread, and have it fetch all 20 images sequentially. Worked fine, but slowly - if the first image was loaded slowly and the next ones quick, well, you didn't get to *see* the next ones before that first slow one was done. So I thought that something as easy and light (cpu wise) as this, why not start one thread per image?

Sure thing, now everything was quick and nice. Images appeared, some quicker than others, but you always got SOME images quickly, at least creating an illusion of speed.

However, as one alpha-tester quickly discovered, there was a problem here - if you closed the window before all the threads had either downloaded their stuff or given up, the program would crash fatally. Not every time, you had to time it just right.

It turned out this happened because the object I was adding the images to (the ListBox, in this case), was disposed. Not only that, it was disposed so that I got bitten by a textbook race condition;

if( control != null && !control.IsDisposed && !control.Disposing )

control.Add( pictureEntity );

Now I would get an exception because the object was disposed in the control.Add() line - a real classical case.

Turns out what I had to do to get it working was to implement a queue, and a timer, and then have the threads insert stuff into the queue instead. Then when the timer fired, the form itself would add any queued items - with the added detail that of course, if the form is closed, the timer is stopped and nothing more happens.

Considering how trivial this really is - is it any wonder why multithreaded programming quickly becomes such a pain?