Find values with the smallest absolute delta
A few days ago a fellow niner, with whom I chat from time to time over messenger, asked me how to get all the values from a list that are the nearest (speaking of an absolute difference) to a value in question. Like, for example, you have a list {1, 2, 4, 5, 7} and the value is 6 then you want as result {5, 7} because they both have an absolute delta of 1.
I asked the dude if he wanted to do it with LINQ and he said that it would be nice to use that. First I thought like in SQL world and created an inner query and an outer query. The inner query calculates the absolute minimum delta from the list. The outer query would then use that minimum delta and return all the values that fit that delta:
var list =
int valueInQuestion = 6;
// query that returns the values with minimum
// absolute delta.
var query = from c in list
where Math.Abs(c - valueInQuestion) ==
(
// the inner query that calcuates the
// deltas and returns the minimum.
from l in list
select Math.Abs(l - valueInQuestion)
).Min()
select c;
// print the results to the console.
foreach (var item in query)
{
Console.WriteLine(item);
}
This approach is not very fast because for each item in the outer query you need to run the inner query (which runs on the whole list) and the result is then compared with the current value of the outer query (which loops also over the whole list). This makes it n^2 speaking of speed.
Since we are not in SQL world we can store stuff and that’s what I did second. I run the inner query once and stored the result. After that I used that value while running over the list again and doing the compare:
var list =
int valueInQuestion = 6;
// this query calcuates the
// deltas and returns the minimum.
int minDelta =
(
from l in list
select Math.Abs(l - valueInQuestion)
).Min();
// query that returns the values with minimum
// absolute delta.
var query = from c in list
where Math.Abs(c - valueInQuestion) == minDelta
select c;
// print the results to the console.
foreach (var item in query)
{
Console.WriteLine(item);
}
The runtime behaviour of this modification is n*2 because the list is only iterated twice. The first run is to calculate the minimum delta and then (in the second run) to get all values that fit the minimum delta.
But, to make the algorithm very fast we need to leave the world of LINQ and write the whole algorithm on our own. The idea is to initialize the minimum delta with a very high value and if the delta of current value is below the global delta erase the list and store the value. If the value’s delta is equal to the current global delta the current value is only added to the list (the list is not erased as we found more values with the same delta). Otherwise nothing is done.
{
// initialize the list and the delta.
var result =
int delta = int.MaxValue;
// loop over the value in the list.
for (int i = 0; i < values.Count; i++)
{
int value = values[i];
// create the absolute difference.
int absDiff = Math.Abs(value - valueInQuestion);
// clear the list if the current diff is below the delta.
if (absDiff < delta)
result.Clear();
// if below or equal add the item to the list.
if (absDiff <= delta)
{
result.Add(value);
// set the current diff as delta.
delta = absDiff;
}
}
return result;
}
Usage looks like this:
var list =
// invoke the method to return the result.
var result = GetNearestValues(list, 6);
// loop over the results and print them to the console.
foreach (var item in query)
{
Console.WriteLine(item);
}
Speaking of speed this algorithm needs only one run over the list which makes it n.
You might argue that n*2 and n are similar when we deal with complexity but when you have to iterate over a few tousand (or even more) items one time or twice, and that very often, you might see the difference. You can then even argue that another form of list should be used to store the values in such a scenario but that’s another story. 
Published on Dec 31st, 2007 —
Tags: algorithm, C#, delta, nearest values 
Comments (2) 
digg it!
kick it
How to use reflection in .NET
I have done another screencast. This time on reflection in .NET.
In this screencast I explain how to use .NET Reflection to create highly dynamic frameworks. I’m also going to show you how to use it to create a simple serializer that serializes any kind of objects. The screencast might be interesting if you have never done anything with .NET Reflection and want to get a general overview on what is possible.
A dive into the Parallel Framework for .NET
The Parallel Framework for .NET (PFX) is available since November (I have posted about it) and you can download it from here. The framework allows you to easily parallelize a piece of code by using the classes that come with the framework. But what is exactly coming with the framework?
The first class that you might encounter when checking out the samples is named Parallel. Parallel comes with a few methods that are very easy to use: Do, For and ForEach (with different overloads). They represent the different keywords that are also available in C#: do, for and foreach. An example of the usage is:
var list =
// create the array holding the results.
double[] results =
// loop over the list, create the square root and
// store it in the result array.
Parallel.For(0, list.Count, index =>
{
results[index] = Math.Sqrt(list[index]);
});
The method takes the lower and upper bound (as the first two arguments) and the third argument is the method that is called during all iterations. This looks very similar to the C#’s for statement. 
What does this give us? The For method is going to understand how many cores and CPUs are in the current machine and parallelizes the loop as much as possible. The engine underneath is even smart enough to make sure that all cores are always busy. That means when a core has no work left it is going to steal the work from other cores to make sure the workload is balanced between the different cores.
But the PFX functionality doesn’t stop here. Let’s dive a little bit deeper and look what we find. The next interesting class is called Task. It allows us to create tasks and make them run on the different cores. The framework is looking what core could be used for each task and runs it on that. If, for example, you create a list of tasks they are going to be run on all the different cores in your system and the engine will properly distribute them on the different cores.
Task t = Task.Create(delegate { Console.WriteLine(“foo”); });
// check if the task has been completed.
while (!t.IsCompleted)
{
// do something else here…
}
// this would also make us wait until the task has finished.
t.Wait();
Random rnd =
for (int i = 0; i < 20; i++)
{
// create a new task and make it print something to the console.
Task t = Task.Create(delegate
{
// sleep for a while and print the results.
Thread.Sleep(rnd.Next(0, 1000));
Console.WriteLine(“do something…”);
});
}
Another interesting class that is also coming with the framework is the so called Future<T>. This class - compared to the Task class - returns a value after having completed. You can use it like that:
// this could be an arbitrary operation.
int i = 0;
Future<int> f = Future.Create<int>(() => i + 1);
while (!f.IsCompleted)
{
// do something here…
}
// we can also wait by requesting the value.
// or request it after the job has been finished.
// requesting the value will block until the value has been
// calculated.
var result = f.Value;
// The Wait method call will also wait until the job is done.
f.Wait();
Another interesting thing about the Future and Task classes is that they have an event that is fired when the work is done. The only problem with that event is that it creates a possible race-condition. If the work that the Task/Future do is done in a blink of an eye the event might not be registered and you might miss it. I have created a short example where I delay the execution to make sure the event doesn’t get missed:
// create a future that does some work.
var f = Future.Create<int>(() =>
{
// sleep some time.
Thread.Sleep(1000);
return i + 1;
});
// register the event that is fired when the work is done.
f.Completed += delegate { Console.WriteLine(“Finished”); };
// get the value.
int value = f.Value;
I hope they somehow re-do this for the final version to make sure that you can register an event while the Task/Future gets created - or find another way to eliminate the race-condition! In the mean time you could create your own class that bridges the gap by allowing you to register a second method that get’s invoked when the future has finished its work. Something like this would do it:
{
/// <summary>
/// Creates a new Future{T} and allows to specify a method
/// that is invoked when the future has finished with the work.
/// </summary>
/// <param name="valueSelector">The value selector for the
/// future.</param>
/// <param name="continueWith">The method that is processed when
/// the future has finished it work.</param>
/// <returns></returns>
public static Future<T> Create<T>(Func<T> valueSelector,
Action<T> continueWith)
{
// create the future.
return Future.Create<T>(() =>
{
// get the value from the value selector.
T result = valueSelector();
// feed it into the next delegate and
// return the result of that.
continueWith(result);
// return the result.
return result;
});
}
}
This class allows you to specify a second method that is used to continue with after the value selector has finished its work. The second method gets the result of the value selector as input. Usage looks like this
// the second method prints the result to the console.
int i = 0;
var f = FutureFactory.Create<int>(() => i + 1,
arg => Console.WriteLine(arg));
// get the result from the future.
var value = f.Value;
The Future and Task classes hold other interesting properties and methods that you should inspect when working with the framework.
Another important thing here (and in .NET general) is exception handling. An exception always only happens in the thread where it is thrown. An exception walks the thread’s stack and when not handled it just aboards the thread and that’s it. Since the Parallel Framework creates threads for the different tasks this is an important issue when you use the framework.
The Future and Task class have both a property that holds the exceptions that have been thrown in the classes. The default behavior is not to break and just hold the exception but you can alter that by calling the Wait method and wait until the task is done. In that case the exception will be thrown again in the main thread and walk the main thread’s stack. Otherwise you can inspect the properties holding the exceptions and throw an exception if that is appropriate.
Another interesting class that comes with the framework is the TaskManager. It allows you to customize how the framework works internally. You can, for example, specify the maximum amount of cores that should be used:
TaskManager manager =
// create a new future that simply increments the value given.
// this could be an arbitrary operation.
int i = 0;
Future<int> f = Future.Create<int>(() =>
{
// do the heavy work here and return the results.
return 0;
}, manager, TaskCreationOptions.SelfReplicating);
f.Wait();
Attention: if you specify to many cores (more than your system has) the Future or Task will throw an exception. You could query the amount of maximum cores by using the Environment class that comes with the .NET Framework.
In the previous code snippet I have given an instance of the TaskManager to the Future but I have also specified a flag from the TaskCreationOptions flags enumeration. This flag allows the task to self-replicate itself, if other cores become available.
Another interesting feature that comes with the PFX is the Parallel LINQ extension. That extension allows you to create in-memory LINQ queries and parallelize them with one method call. The method that you need to call on the data source is called AsParallel. That method returns an enumerable that is parallelizable and allows the PFX to move the different method calls such as where, orderby etc. to the different cores:
List<int> list =
// call the AsParallel method to parallize the query.
var query = from c in list.AsParallel<int>()
where c > 1
orderby c ascending
select c;
// loop over the results and print them.
foreach (var item in query)
{
Console.WriteLine(item);
}
I hope this dive into the Parallel Framework for .NET was interesting for you and gave you some insides that you might find useful in your future or ongoing projects.
Published on Dec 29th, 2007 —
Tags: .NET, multi core, multi threading, Parallel computing, Parallel FX, PFX Comments (2) digg it!
kick it
Japanese IQ Test
This is one hell of an interesting IQ test. It has nothing to do with the normal piece of paper that you get (at least in Europe) as IQ test because they don’t ask you to solve some math puzzles, rotate some picture, group stuff together or similar. The goal is only to bring a group of people from one side of the river to the other side and it looks like this:
This IQ test is used by companies in Japan to see if possible candidates fit for a job.
The rules are:
- Only 2 persons on the raft at a time.
- The father cannot stay with any of the daughters, without their mother’s presence.
- The mother cannot stay with any of the sons, without their father’s presence.
- The thief (striped shirt) cannot stay with any family member, if the Policeman is not there.
- Only the Father, the Mother and the Policeman know how to operate the raft.
To start it click here and then on the round button. Can you master it?
Extension Methods in C# 3.0
I have created a short screencast that introduces you with extension methods in C# 3.0.
In this webcast I explain why extension methods have been added to .NET 3.5. What are the benefits of using them? Then I’m going to show you how to create your own extension methods in C#. I also explain how the extension method calls are translated by the compiler. In the end I also show the problems that might come up when extension methods are used heavily in applications.
Click here to watch the screencast
Published on Dec 29th, 2007 —
Tags: .NET, C# 3.0, extension methods, screencast Comments (1) digg it!
kick it
A fast way to grayscale an image in .NET (C#)
Have you ever needed a way to edit images directly in .NET? The framework comes with the Bitmap and Image class that allows you to edit different images. But the problem is that by default you probably will end up with the GetPixel and the SetPixel methods (of these classes) to edit the image.
It won’t be long until you realize that the GetPixel and SetPixel couple is damn slow. But there’s another way. This way is a lot faster but requires you to use a little bit pointer arithmetics and embed that pieces of code into an unsafe block. That means that you need to compile the project with the /unsafe switch (found in the project properties). If you don’t want to do that you could extract this class into an own assembly - that you compiled with the unsafe switch - and use it from the other assembly.
The Bitmap class has a method that is called LockBits. With that you can lock the bits in the image and from then on use the data in the image directly. The following piece of code shows you how to walk through the pixels of the bitmap and convert all of them into a grayscale representation. For that I used the Y value that is calculated while converting an image from RGB space into the YCbCr color space. The Y component contains the brightness of the pixel, which is exactly what we need:
/// Grayscales a given image.
/// </summary>
/// <param name="image">The image that is transformed to a grayscale image.</param>
public static void GrayScaleImage(Bitmap image)
{
if (image == null)
throw
// lock the bitmap.
var data = image.LockBits(
try
{
unsafe
{
// get a pointer to the data.
byte* ptr = (byte*)data.Scan0;
// loop over all the data.
for (int i = 0; i < data.Height; i++)
{
for (int j = 0; j < data.Width; j++)
{
// calculate the gray value.
byte y = (byte)((0.299 * ptr[2]) + (0.587 * ptr[1]) + (0.114 * ptr[0]));
// set the gray value.
ptr[0] = ptr[1] = ptr[2] = y;
// increment the pointer.
ptr += 3;
}
// move on to the next line.
ptr += data.Stride - data.Width * 3;
}
}
}
finally
{
// unlock the bits when done or when
// an exception has been thrown.
image.UnlockBits(data);
}
}
Published on Dec 28th, 2007 —
Tags: .NET, Image processing, pointers, unsafe code Comments (2) digg it!
kick it
Family history
I have a very uncommon last name: Liensberger. This name means something like “the people coming from the liens mountain”. The “liens mountain” is a small mountain near Kiens in South Tyrol.
There aren’t that much people with my last name, which makes it easier to contact people from the family (it’s very, very likely that somebody with the same last name is part of the family if you go back a few generations).
Today Armin Liensberger from Austria contacted me (over Skype) and I sent him a picture of our family emblem. On the bottom of the emblem is a text that says “Zu Lehen empfangen Fürstbistum Brixen dem Ansitz Thun Freiherrn Liensberg“, which means something like “the bishop of Brixen gives the baron Liensberg a piece of land“.
It means that we got some piece of land (sometimes in the middle ages) from the bishop of Brixen, which was the bishop of Tyrol and had a lot of power during that time. I don’t know why we got it and which piece of land that was, but it is most likely to be the one near Kiens that holds the mountain.
Published on Dec 28th, 2007 —
Tags: emblem, family name, last name, Liensberger Comments (5) digg it!
kick it
Crazy VB.NET Christmas song
This is freaking crazy… must be Don Box and Chris Anderson to come up with something like that! This year they invited Amanda Silver from the VB.NET team! Enjoy
The lyrics:
Module VB : Dim myvar As _
Integer?() = {3 * 3}
Sub Main() : For Each i In myvar
Console.Write(“Hello VB”)
With i : Console.Write(.Value)
End With REM a language so true
If i IsNot Nothing Then
Console.WriteLine() : End If REM
Console.Write(<some>xml</some>)
Next : End Sub : End Module
Published on Dec 25th, 2007 —
Tags: christmas, Song, VB.NET, Visual Basic .NET Comments (0) digg it!
kick it