Friday, July 18, 2008

Generating random sequences with LINQ

A concise random number generator

Inspired by The LINQ Enumerable Class article from the lastest MSDN Magazine issue, I started to play a little bit with the random sequence generator:

/* generate the sequence */
Random rnd = new Random();
var sequence = Enumerable.Range( 1, 10 ).OrderBy( n => rnd.Next() );
 
/* write down the sequence */
sequence.ToList().ForEach( n => Console.WriteLine( n ) );

As you can see, the sequence is generated with two statements, the first one initializes a random number generator and the second one sorts the list using the results from the generator.


My immediate thought was: "Is there a way to genearte such random sequence using a single statement?"


The obvious approach



var sequence = Enumerable.Range( 1, 10 ).OrderBy( n => (new Random()).Next() );

does not work because a new random number generator is created for each value from the list and the same random value is returned from all these newly created generators.




Random number generator testing

Let's write a test of the random number generator - we treat consecutive values from the array as coordinates and draw an image of the generator:



static void RandomSequenceGeneratorTest( IEnumerable<int> Sequence )
{
    int Max = Sequence.Max();
 
    /* create image */
    using ( Bitmap bitmap = new Bitmap( Max, Max ) )
    using ( Graphics graphics = Graphics.FromImage( bitmap ) )
    {
        graphics.Clear( Color.Black );
 
        int prev = Sequence.First();
        foreach ( var current in Sequence.Skip(1) )
        {
            graphics.DrawRectangle( 
                Pens.White, 
                new Rectangle( 
                    /* draw a point 
                       using current and previous values
                       as coordinates
                    */
                    new Point( prev, current ), 
                    new Size( 1, 1 ) ) );
 
            prev = current;
        }
 
        bitmap.Save( "test.png", ImageFormat.Png );
    }
}

Testing the generator (version 1)

Let's also test our generator:



var sequence = Enumerable.Range( 1, 500 ).OrderBy( n => ( new Random() ).Next() );
RandomSequenceGeneratorTest( sequence );


An improved generator (version 2)

However, I can modify the generator slightly to get much better results!



var sequence = Enumerable.Range( 1, 500 ).OrderBy( n => n * ( new Random() ).Next() );
RandomSequenceGeneratorTest( sequence );


Hey! It seems that the multiplication makes the generator much less predictive, however as the clear pattern reveals, the resulting sequence is still not random!


What exacly happens is the arithmetic overflow caused by



n * (new Random()).Next()

which "distrubutes" multiplied values in a more "random" way.


Do we really need (new Random())?

After I've realized that the "randomness" of the improved generator is caused by arithmetic overflows, I immediately thought of getting rid of the (new Random()). Maybe the overflow itself is enough to get random sequence?



var sequence = Enumerable.Range( 1, 500 ).OrderBy( n => n * 1234567890 );
RandomSequenceGeneratorTest( sequence );


Well, it is not. Altough the sequence printed on the console looks quite random at first sight, the image reveals that it's not random at all. It seems that the value produced by the (new Random()).Next() is then important, even though the first test (version 1) revealed that the value itself is not enough!


Even more improved generator (version 3)

Let's go back to our improved generator and try to improve it even more:



var sequence = Enumerable.Range( 1, 500 ).OrderBy( n => n * n * ( new Random() ).Next() );
RandomSequenceGeneratorTest( sequence );


I guess, I am satisfied. However, I do not think I am curious enough to dig for a exhaustive explanation. Does really the arithmetic overflow causes this generator to produce random sequence? What's the exact role of (new Random()).Next() here? It seems that it's not important itself (version 1), however removing it completely also does not work.


I belive that the deferred nature of LINQ enumeration is the one of keys to explain these obervations. I would also like to see some deeper and more throughout tests of my "yet-improved" generator.


On the other hand, could it be possible that incidentally, by making a square function (n*n), I've built a chaotic function with random distribution over its domain?

Friday, July 11, 2008

C# Puzzle No. 11 (intermediate)

Generic list type needs an item type to be initialized:

List<int>    listInt;
List<string> listString;
...

On the other hand, C# 3.0 allows anonymous types to be used in the code. An anonymous type is never explicitely named:



var item = new { Field1 = "The value", Field2 = 5 };
Console.WriteLine( item.Field1 );

How it is then possible to declare a generic list of anonymous type?



var item = new { Field1 = "The value", Field2 = 5; };
 
List<?> theList = 
    /* how do I make a generic list with item in it 
       so that I can add other items of the same anonymous type?
     */

Sunday, July 6, 2008

Brief FAQ of AJAX Programming Concepts

Q: What is the AJAX?

A: Well, it is the Asynchronous Javascript And Xml. The technology exists since 1995-98, however the term AJAX is used since 2005.

Q: How does the AJAX work?

A: The AJAX works as follows:

  • the javascript in a browser reacts to a client-side event. An instance of XMLHttpRequest class is created inside a web browser. It acts like a "browser" inside the browser - it can handle GET/POST request from within the javascript,
  • the XmlHttpRequest connects to the server and a server-side component handles the request,
  • the request returns to the original page and a XML response is handled by another javascript routine which updates the state of the page according to the response content,

Most of todays frameworks actually do not rely on XML as the response protocol but instead the JSON is used. It also means that today we rather use AJAJ than AJAX (Asynchronous Javascript And JSON). Client-server roundtrips are usually called callbacks instead of postbacks which occur in standard form-posting scenario. The most reduced infrastructure, where the response takes form of an HTML fragment which is used to replace part of a page in user's browser, is often referred to as AHAH (Asynchronous HTTP and HTML).

Q: So, why do we need AJAX?

A: To minimize the ugly effect of page reloading? No. It can be achieved much easier.

There are in fact two important reasons for AJAX:

  • to minimize the amount of data sent to and from the application server (we do not POST the entire HTML form and do not respond with the entire HTML page)
  • to improve the user performance (for example: to provide a dynamic context-sensitive content when the user types into a textbox)

Q: Why do we need AJAX frameworks?

A: It is easy and possible to write an AJAX-style application without any support from a high-level framework. You just learn how to use the XMLHttpRequest and are on your own.

This, however, could be very inefficient. For any action which needs to be "AJAXified" you need three core components:

  • (I) a client-side javascript code raised by a browser event, responsible for creating a request to the server
  • (S) any server-side component which handles the GET/POST of the request from previous step
  • (R) a client-side javascript which handles the response of the server

I call these three components I, S and R (Init, Server and Response) and I call the whole AJAX mayhem "the I-S-R problem".

The nice aspect of calling all these three components is to realize that they are, in fact, quite independent. You can expect frameworks which attack all three issues in one coherent way, however nothing stops you from using completely different components for each of the three.

Q: I am lost in the plethora of AJAX frameworks. Can they be somehow classified?

A: I did some research and I've found the I-S-R perspective quite handy. When I see a new framework, I immediately focus on its I-S-R components and thus I am able to compare the framework to other which focus on similar issues. I think that five different approaches to AJAX can be identified:

I Incomplete I-S-R frameworks

Examples:

Profile:

  • you manually program the client-side user interface ...
  • ... or manually program the server-side components ...
  • ... or manually consume server responses on the client-side
  • sometimes semi-automatic creation of callbacks (for example: server-side interface is "mirrored" on the client side by a set of proxy interfaces and a convenient way of calling server-side API with these proxies is provided)

None of these "incomplete" frameworks provide the complete way to handle the I-S-R problem. The interesting thing is that this is where you can mix different frameworks which operate on different levels of the problem so for example you can use Bindows as the GUI provider and the JayRock as the server-side gateway.

II Custom AJAX components

Examples:

Profile:

  • someone builds a set of ASP.NET components which, instead of providing values for standard form POSTs, handle their events in an AJAX-style. Usually these components "mimic" the ASP.NET components and you "switch" from ASP.NET library components to such AJAX-enabled components by just changing <asp:Button> to <XYZ:Button> etc.
  • it's great to see that someone knows how AJAX works, however I belive that "component switching" is just a wrong direction

III Ajax Managers

Examples:

Profile:

  • you get an AJAX Manager, an ASP.NET component which, when put on a page, automatically converts all postbacks to callbacks. Sometimes it takes 15 seconds to AJAX-enable your application,
  • more advanced frameworks are in the II and III group in the same time - you have AJAX Managers which convert existing applications into AJAX-enabled applications plus a bunch of optimized components is available for more advanced UI stuff

IV "Client-side logic with server-side tools" frameworks

Examples:

Profile:

  • client-side logic is built with server-side technology (C#/Java) and then magically converted to a bunch of javascripts
  • you develop "javascripts" using strongly-typed languages, you test "javascript" with your favourite testing frameworks
  • it sounds great until you try write a code which opens a file ...
  • ... and then you realize that, in fact, you are using a really small subset of server-side technology and "opening files" does not belong to this subset ...
  • ... so whenever you are to perform a server-side action, you are on your own (which means: use a framework which makes RPC possible, perhaps something from group I?)

V Server-side AJAX

Examples:

Profile:

  • "dumb client, almighty-server", there's no "logic" on the client-side but rather messages passed to and from the server
  • it is the server which holds the complete state of the application and the user interface and the client-side only renders it
  • all client-side events are processed on the server
  • this approach is the most resource demanding of all
  • in the same time, it's most safe, since many typical internet attacks just don't work here (for example, Cross-site Request Forgery or ViewState Tamplering attacks are impossible).
  • it's impossible to easily AJAX-enable existing ASP.NET applications with this approach

For an up-to-date list of .NET Ajax Frameworks, visit the AjaxProjects page.

Q: Any concise AJAX references?

A: If you need something really concise, "Teach Yourself Ajax in 10 Minutes" should be great. I can also recommend "Ajax Design Patterns".

Tuesday, July 1, 2008

How to detect which application server runs the ASP.NET code

Apart from issues with querying Google, I belive that the most reliable way to detect which application server runs an ASP.NET application is to check the SERVER_SOFTWARE variable available in Request.ServerVariables:

string server_software = this.Request.ServerVariables["SERVER_SOFTWARE"];
The integrated web server (aka Cassini) returns an empty string while the IIS seem to return a meaning value (Microsoft-IIS/5.1 on my XP machine). If there's more convenient way (I doubt) I would be glad if anyone would drop a note about it.

Google considers its own query as spyware

Since I am stuck in an ASP.NET issue, as always I try to use Google. Specifically, I would like to somehow detect in server code whether the application is deployed on IIS or on the integrated development web server.

So I type:

asp.net detect development server

in the Google search text field:

However, only first 11 pages can actually be examined. When you click on the link to page number 12 (or any greater number) you'll learn that the link comes from a virus or a spyware software (screenshot taken on another machine since the description is localized on my development machine):

I guess it's one of the simplest viruses/spyware ever written. If you are a numerologist you'll probably know what's so specific in number 12.