May 2008 - Posts

Cloning objects in .NET

In an interesting project where I'm giving a hand, we need to clone objects of a number of different types, perhaps surprisingly the CLR doesn't offer a general cloning method, of course you could use MemberwiseClone() but this is a protected method, so it can be invoked only from inside the class of the object being cloned, which makes it difficult to use it in a general method, besides, MemberWiseClone() does just a shallow copy and what we really need is a deep copy.

There is a good reason for not having such a general method: object cloning is one of those problems which have a simple solution for simple scenarios but that resist a satisfactory solution for all the scenarios, for example the objects may have references to other objects and even to themselves be it directly or after a long chain, for example a customer has invoices that have payments that refer to the customer, a general cloning algorithm for a web several times more complex than that is anything but trivial. But the need of moving objects (and their web) is inescapable in distributed environments, because you have to move the invoices and the customers from the business layer to the presentation layer, so there are indeed mechanisms, albeit with some limitations, for serializing and deserializing object graphs, with the help of these mechanisms we can try and build a general object cloner:

    1 

    2     public static T BinaryClone<T>(this T originalObject)

    3     {

    4         using (var stream = new System.IO.MemoryStream())

    5         {

    6             var binaryFormatter = new System.Runtime.Serialization.Formatters.Binary.BinaryFormatter();

    7             binaryFormatter.Serialize(stream, originalObject);

    8             stream.Position = 0;

    9             return (T)binaryFormatter.Deserialize(stream);

   10         }

   11     }

   12 

We just convert, using as intermediary a memory stream, our object to a bit string and then we synthesize a *new object* from that bit string. The use of BinaryClone() flows nicely:

    1 

    2     var clone = person.BinaryClone();

    3 

Easy to write, but we have to be careful of the performance and the corner cases. I run a few *very informal* performance tests with this object:

    1 

    2     var person = new Person

    3     {

    4         Id = 101,

    5         Name = "Sánchez, Sebastián",

    6         Salary = 590.20m,

    7         BirthDate = new DateTime(2000, 6, 15),

    8         Address = new Address { Number = "N24-78", Street = "Pasaje Córdova" }

    9     };

   10 

And I found that doing a hundred thousand clones takes some nine thousand milliseconds, that is each cloning takes less than one ten-thousandth of a second, which is adequate to our needs. BinaryFormatter has been with us since .NET Framework 1.0 so I'm not like saying anything even remotely new or unknown, but tomorrow (or the day after, or the day after...) I'll talk about a small refinement to BinaryClone().

Posted by Edgar Sánchez with 3 comment(s)
Filed under: ,

A cool way to find out whether a number is palindromic

In this blog entry I proposed a solution to Problem 4 at Project Euler, a crucial element of the problem is to find out whether a number is a palindrome (909 is, 809 isn't), a bit out of laziness and a bit in order to reuse existing methods, I decided to verify the palindrome by converting the number into a char array and then comparing this array with its mirror version, it works but it's not really that mathematical... Dustin Campbell proposed a solution kind of similar to mine (alas, more elegant and, above that, in F#) and using the same trick of converting the number to chars, as he didn't like this part of the solution, in this new blog entry he proposes the detection of a palindrome by mirroring the number one digit at a time. A translation of his F# code to C# 3.0 could be:

    1     Func<int, int, int> TailReverseNumber = null;

    2     TailReverseNumber = (n, res) => n == 0 ? res : TailReverseNumber(n / 10, 10 * res + n % 10);

    3 

    4     Func<int, bool> IsPalindrome = n => n == TailReverseNumber(n, 0);

TailReverseNumber takes a number n and "mirrors" it, one digit at a time, for example: TailReverseNumber(237, 0) -> TailReverseNumber(23, 7) -> TailReverseNumber(2, 73) -> TailReverseNumber(0, 732), the big trick is that res works as an accumulator that is multiplied by 10, therefore moving its value to the left, and putting in the "hole" that appears at the right the least significant digit of n. As it names implies, TailReverseNumber() uses tail recursion, so that no extra call stack space is used to save any intermediate results, which makes the process pretty efficient. Actually, in my PC it's four times faster than the initial solution. More efficient and more elegant, a smart guy Dustin.

New version of F# just released

In its way from research language to commercial language, Don Syme just announced that, silently, on May the 1st version 1.9.4.15 of F# was released.

 F# 1.9.4.15

This new version incorporates a number of specific enhancements (F# is now basically in stabilization mode, so we really shouldn't expect significative changes to the language). By the way, the example in the picture shows my idea for solving Problema 2 of Project  Euler: find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million. For an explanation of how it works, I suggest you this Dustin Campbell blog, which proposes a solution similar to mine with a couple of elegant touches and, above all, with a detailed and engaging explanation.

Which is the ten thousand first prime?

Prime numbers have a good deal of practical applications (for example in cryptography) but let's face it, even if they would have none, they would still be the favorite toy of mathematicians. In Problem 7 of Project Euler, we are asked to find the 10001st element of the famous list, my approach was this:

  1. Define the *infinite* sequence of the prime numbers
  2. From this sequence, throw away the first 10000 items and then take the first of the remaining

Creating an infinite sequence in C# is easy (since version 2) thanks to IEnumerables and, above all, the yield statement:

    1 IEnumerable<int> Primes()

    2 {

    3     yield return 2;

    4 

    5     var primesSoFar = new List<int>();

    6     primesSoFar.Add(2);

    7 

    8     Func<int, bool> IsPrime = n => primesSoFar.TakeWhile(p => p <= (int)Math.Sqrt(n)).FirstOrDefault(p => n % p == 0) == 0;

    9 

   10     for (int i = 3; true; i += 2)

   11     {

   12         if (IsPrime(i))

   13         {

   14             yield return i;

   15             primesSoFar.Add(i);

   16         }

   17     }

   18 }

The yield at line 3 returns the first item of the sequence: the always excepcional 2 (the only even prime). Then at line 5 we create a list where we will be saving the generated primes as we progress in the sequence (this way we will gain speed at the cost of memory). The IsPrime(n) function defined at line 9, proposes a method -pretty crude actually- of verifying whether a number is prime: we take all primes generated so far which are lower or equal than the square root of n, and we look for the first among them that divides n evenly, if such a divisor exists then n is not a prime, that is: if none of the primes already generated is an exact divisor of n then FirstOrDefault() returns a 0, signaling the fact that n is indeed a prime. Finally at line 10 starts the loop that, every time the Prime() invoker asks for an item, it progresses thru 3, 5, 7, 9, 11, 13, ... stopping and returning, thru yield, when it finds a new prime.

With this sequence in our hands, step 2 of my plan is utterly simple:

return Primes().Skip(nth - 1).First();

We take the Primes() sequence, ignore the first nth - 1 (in our case nth = 100001) and then take the first of the remaining. This little code returns the answer in far less than a second.

More Posts