Honest Illusion

Some Better-Written Custom String Methods using C#

James — Wed, 03 Feb 2010 01:07:00 GMT

In my daily web-surfing, I often stumble upon snippets of C# code posted by people. Usually, I can tweak it a bit. Sometimes, I can tweak it a lot. I usually post a quick comment to the site offering it. Today, I came upon some code that was so bad --- which the author said was from his forthcoming book! --- more drastic measures must be taken.

First we have a function to put a string into “Title Case” (which the author refers to as “Proper Case”) – Having the first letter of each word capitalized. Here’s the original:

public static String PCase(String strParam)
 {
     String strProper = strParam.Substring(0, 1).ToUpper();
     strParam = strParam.Substring(1).ToLower();
     String strPrev = "";
     for (int iIndex = 0; iIndex < strParam.Length; iIndex++)
     {         
         if (iIndex > 1)
         {
             strPrev = strParam.Substring(iIndex - 1, 1);
         }
         if (strPrev.Equals(" ") ||
         strPrev.Equals("\t") ||
         strPrev.Equals("\n") ||
         strPrev.Equals("."))
         {
             strProper += strParam.Substring(iIndex, 1).ToUpper();
         }
         else
         {
             strProper += strParam.Substring(iIndex, 1);
         }
     }
     return strProper;
 }

What wrong here? Lot’s of really bad string handling. Remember, strings are immutable, so any action on one creates a new string. So, “strParam.Substring(iIndex, 1)” creates a new string. “strParam.Substring(iIndex, 1).ToUpper()” create two new strings, and “strProper += strParam.Substring(iIndex, 1).ToUpper();” creates three new strings. And, that’s within a loop. And, since Substring is always used here to create a one-character string, it easier to just use a char --- except apparently, this book author doesn’t know how to. Nor, doesn’t he apparently know about StringBuilder. Then, we get to the algorithm itself, where he does such bizarre things as pointlessly treat the first character as a special case, in two different places.

Ok, now let’s see the revision:

    public static String PCase(String strParam)
{
         StringBuilder sb = new StringBuilder(strParam.Length);
         char cPrev = '.';  // start with something to force the next character to upper.
        foreach(char c in strParam)
         {
             if (cPrev == '.' || Char.IsWhiteSpace(cPrev))
                 sb.Append(Char.ToUpper(c));
             else
                 sb.Append(Char.ToLower(c));
             cPrev = c;
         }
         return sb.ToString();
     }

First we start with a string builder, preallocated to the size of the string we are building. The method doesn’t change the length of the string, so we know the length of the final string right from the start.

Next, since we are going to capitalize every letter after a period, and also the first letter, why not just pretend the mythical initial “last” character was a period? Suddenly, the first letter is no longer a special case, and we still get what we want.

Then, we just loop through the letters, raising or lowering letter as we need. Note that it works on characters and not strings, and uses the build-in IsWhitespace method, instead of using a hardcoded list of a subset of them. A for() loop can in certain cases (however, not the one used in the original) be faster than a foreach(), but here I figured it was safe to sacrifice a tiny bit of speed for clearer code.

Next up, Reversing a String. The Original:

    public static String Reverse(String strParam)
     {
         if (strParam.Length == 1)
         {
             return strParam;
         }
         else
         {
             return Reverse(strParam.Substring(1)) + strParam.Substring(0, 1);
         }
     }

Now, here the author might be able to earn a pass. It’s possible that somewhere in his book he talks about recursive functions, and uses this as an example. Then, if might be OK. I mean, it is the only reason I can think of that someone might want a function which reverses a string – despite ubiquity of string reversing functions in libraries like this. But, he presented it on his blog as a collection of string functions, so we’ll have to judge them on that basis.

Again we have lots of string manipulation to accomplish something simple --- where there are already method built into the framework to handle such things:

public static String Reverse(String strParam)
{
     byte[] rev = Encoding.ASCII.GetBytes(strParam);
     Array.Reverse(rev);
     return Encoding.ASCII.GetString(rev);
}

Nexy, we have a simple function to count the occurrences of a substring.

public static int CharCount(String strSource, String strToCount)
{
    int iCount = 0;
    int iPos = strSource.IndexOf(strToCount);
    while (iPos != -1)
    {
        iCount++;
        strSource = strSource.Substring(iPos + 1);
        iPos = strSource.IndexOf(strToCount);
    }
    return iCount;}

The revision isn’t much different but the subtle difference is important. Instead of creating a new, shorter string to search, we tell it to just start looking after the last match. Instead we now merely look at the string.

public static int CharCount(String strSource, String strToCount)
{
    int iCount = 0;
    int iPos = strSource.IndexOf(strToCount);
    while (iPos != -1)
    {
        iCount++;
        iPos = strSource.IndexOf(strToCount, iPos+1);
    }
    return iCount;
}

The next one has a special problem --- It doesn’t do what it claims to do!

// Trim the string to contain only a single whitepace between wordspublic static String ToSingleSpace(String strParam)
{
    int iPosition = strParam.IndexOf(" ");
    if (iPosition == -1)
    {
        return strParam;
    }
    else
    {
        return ToSingleSpace(strParam.Substring(0, iPosition) +        strParam.Substring(iPosition + 1));
    }
}

Now, it says that it should remove repeated space, so that there is only one space between words. However, what it actually does it to remove all spaces. This gives us a problem: Should my rewritten function do what it claims to do, or what it actually does? I decided to give you one of each.

Duplicating the result is quite straightforward:

public static String RemoveAllSpaces(String strParam)
{
    return strParam.Replace(" ", "");
}

Writing a function to do what it is supposed to is a little more involved, but still simple:

public static String ToSingleSpace(String strParam)
{
    var sb = new StringBuilder(strParam.Length);
    var prevWS =true;
    foreach(var c in strParam)
    {
        if (Char.IsWhiteSpace(c))
        {
            if (!prevWS)
                sb.Append(' ');
            prevWS = true;
        }
        else
        {
            sb.Append(c);
            prevWS = false;
        }
    }
    return sb.ToString();
}

We create a string builder the size of our source string, which would be the maximum size our trimmed string could be, and we set prevWS to true. This way, it will remove all leading whitespace. Then we just step through the string, character by character, appending that character to our new string if it’s not a whitespace character, and appending a space for the first whitespace character found. Note that this reduces all forms of whitespace (tabs, newlines, spaces etc) to a single space. The original just worked on spaces.

Finally, we have a function to determine is a string is a palindrome.

public static bool IsPalindrome(String strParam)
{
    int iLength, iHalfLen;
    iLength = strParam.Length - 1;
    iHalfLen = iLength / 2;
    for (int iIndex = 0; iIndex <= iHalfLen; iIndex++)
    {
        if (strParam.Substring(iIndex, 1) != strParam.Substring(iLength - iIndex, 1))
        {
            return false;
        }
    }
    return true;
}

Here the change is subtle (ignore the length calculations at the start, which are a trivial micro-optimization).

public static bool IsPalindrome(String strParam)
{
    var iLength = strParam.Length;
    var iHalfLen = iLength / 2;
    iLength --;
    for (int iIndex = 0; iIndex < iHalfLen; iIndex++)
    {
        if (strParam[iIndex] != strParam[iLength - iIndex])
        {
            return false;
        }
    }
    return true;
}

In this function, instead of comparing one-character long strings, I compare individual characters. That change, by itself, cause a 4X speed improvement.

So, there you have it. The article had more, but the other were trivial, and I couldn’t make them any better. And in case you think I’m all talk here, each of those rewrites was benchmarked to run 2 to 5 times faster than the original.

Share this post: Email it! | bookmark it! | digg it! | reddit!

A ViewComponent extension for Castle MonoRail, Part II

James — Tue, 25 Aug 2009 00:44:00 GMT

This was intended to be a two-part article. It was just after I published the original article, I noticed that I’d left out a large part of ViewComponentEx. We continue…..

        protected bool RenderOptionalSection(string section) 
        protected bool RenderOptionalSection(string section, string defaultText)

Renders the named section of a block component – if the section is present. If not, it just silently returns. The second overload lets you provide some text to be rendered, if that section isn’t given:

RenderOptionalSection("tablestart", “<table>”)

Returns true if this section was rendered; false, if the section was present. This seems like a very simple method (and it is), but if your component has a number of different sections for styling (such as the SmartGridViewComponent, which has 18!), this can do wonders to streamline your code.

        void RenderComponent<VC>(params string[] componentParams) where VC : ViewComponentEx, new();
        void RenderComponent<VC>(IDictionary componentParams) where VC : ViewComponentEx, new();
        void RenderComponent(ViewComponentEx component, params string[] componentParams); 
        void RenderComponent(ViewComponentEx component, IDictionary componentParams);

This implement, with a slightly different syntax, a technique originally devised by Joey Beninghove. The idea is to make a ViewComponent which is composite of several other VCs. The basic syntax is

 RenderComponent<LinkSubmitButtonComponent>("linkText=Search",
             string.Format("formToSubmit={0}", searchFormName));

However, the various overloads allow using an already exist component object, and/or an already built dictionary of options.

Also include in the source file is the class ViewComponentUsingSiteMap which, like ViewComponentEx, is an abstract base use for creating ViewComponents, but I’ll hold off discussing that until I ready to talk about the VCs the derive from it.

Share this post: Email it! | bookmark it! | digg it! | reddit!

A ViewComponent extension for Castle MonoRail

James — Mon, 24 Aug 2009 11:21:08 GMT

I’ve been rewriting my website, njtheater.com, (very slowly) as a Castle MonoRail application. Along the way, I’ve written a number of ViewComponent and other elements. Many of these were of general use, so I’ve added them to the CastleContib project, and documented them in the using.castleproject.org wiki.

Two problem there: First, some of the items I wrote don’t fit into an exist category in CastleContrib (There’s one for ViewComponents, which I’ve stick a filter into, but putting a Controller base class there seemed wrong). Second, CastleContrib & using.castleproject.org seem to be somewhat of a black hole. No one seems to look there for information about the Castle Project (which is kind of a shame, since that’s exactly it’s purpose).

On the other hand, blogs posts about Castle are turning up everywhere. We’ve even now got an aggregated blog feed specific to Castle. So, I figured, I start using my blog to talk about what I’ve written.

In fact, one article I discovered on that aggregator was Andy Pike’s “Integrating Gravatar with Castle MonoRail” inwhich he discusses a Helper object for Monorail which creates Gravatars for use’s email addresses. It was written last January. The only thing is, I’ve written (and added to CastleContrib) a Gravatar component three months earlier. That was going to be the topic of my first MonoRail blog post (and I will be my second), but first, I figure I should talk about the base class I once for all my ViewComponents, which I’ve given the rather imaginative name of ViewComponentEx.

ViewComponentEx derives from ViewComponent, and can be used as a “drop-in” replacement for it, as the base class for your ViewComponents. It provides a number of simple methods to help building ViewComponents.

void ConfirmSectionPresent(string section);

Throws an exception if the given section is not present.

string GetSectionText(string section);

Get the text of a section as a string.

string GetBodyText();

Get the text of the body of a block component (without section)

void RenderTextFormat(string format, params object[] args);

Renders the text, formatted. Just like String.Format()

string GetParamValue(string key, string defaultValue);

bool GetParamValue(string key, bool defaultValue);

E GetParamValue(string key, E defaultValue) where E : struct;

Gets a parameter value, with a default. Overloaded to handle string, boolean, or Enum value.

Castle.Core.Logging.ILogger Logger { get; set; }

A property for the system Logger. Automatically wired by Windsor, if active and a Logger is defined in the container. Default to NullLogger, otherwise.

string MakeUniqueId(string prefix);

Makes an unique id. The given prefix is prepended to the generated number. The ID isn't actually guaranteed to be unique (which would require using all 32 digits of the guid). But this produce ids sufficiently distinctive to generate multiple controls on a page.

Code available here: ViewComponentex.cs

Share this post: Email it! | bookmark it! | digg it! | reddit!

#songsincode : The Turtle’s “Happy Together”

James — Sat, 22 Aug 2009 15:26:29 GMT

    (Me + you) &&  (you + me)
var nomatter = dice.toss(); assert (it != null)
me.Only1(you); assert(you == me.Only1());
(Me + you).happy  = so;

(more on the meme here)

Share this post: Email it! | bookmark it! | digg it! | reddit!

Code Tune-Up: Shuffling a List

James — Sun, 16 Aug 2009 23:14:11 GMT

Over on CodeProject, I spotted an article by Mahdi Yousefi called " Creating an ASP.NET captcha using jQuery and s3capcha”.

public static List<int> shuffle(List<int> input)
{
    List<int> output = new List<int>();
    Random rnd = new Random();
 
    int FIndex;
    while (input.Count > 0)
    {
        FIndex = rnd.Next(0, input.Count);
        output.Add(input[FIndex]);
        input.RemoveAt(FIndex);
    }
 
    input.Clear();
    input = null;
    rnd = null;
 
    return output;
}

So, what’s wrong with this? Well, let’s see:

It takes a List as a parameter and returns a list. This is rather limiting. What if we have array we want to shuffle?
It takes and returns a list of integers. Again rather limiting. What if we had strings or say, PlayingCard objects we want to shuffle?
It creates a new Random object every time it’s called. Two problems there. First, when a Random object is created, a seed is produced. This is a fairly time-consuming task, which you don’t want to do repeatedly necessarily. Second, when the default constructor is called, like here, the seed is initialized using the internal clock’s TickCount --- which is the time in milliseconds. If you called shuffle() twice within a millisecond -– not unreasonable if you were writing a game – the Random objects would be using the same seed, and produce the same sequence.
It creates a new list for output. This is a problem only in that it’s a time expense we might as well avoid if possible. It also builds this list by repeated calls to Add(), but without specifying an initial size, meaning that Add() will frequently have to resize the list to keep expanding it. The fix to this would be trivial. Just create the new list as “new List<int>(input.Count);”. But as you’ll see, this won’t be necessary.
It destroys the list input. In fact, it destroys it three times over: First by removing all of it’s items. Then by calling Clear() on the empty list. Then by setting the local reference to null. That last one might cause it to be garbage-collected a couple microseconds earlier – if the calling routine didn’t hold a reference to it. I don’t want to claim this as a “Problem”, as much as a “Behavior” – It’s just something it does, so if our replacement does that as well (as it will), we haven’t lost anything. But, if you nevertheless thing that is a problem, don’t worry, we’ll address that to.
It removes that items from the list using Remove() – This is a very time-consuming method on Lists (which, contrary to popular belief are not linked-lists, but are internally implement as arrays). One call to List.Remove() is O(N) by itself. Since it’s called in a loop, that makes the complicity of this method O(N^2). Clearly that’s something we should avoid.

So, let’s tackle these. First the signature. we say we want a List, but we really only want so features of a list – that usually means we want an interface. And we want to be usable for List of all types, so it’s wants to be generic:

public static IList<T> Shuffle<T>(this IList<T> input)

IList has just the features we need, and allows us to pass different collection types (notably arrays) to the method. I’ve also implemented it as an extension method, because it seemed more useful that way. But to be an extension method, it has to be in a static class, which brings us to our next change:

static class Helper
{
       static readonly Random rnd = new Random();
    // :

I’ve moved that Random object to be a static member. That way, only one is created & initialized, and every call to Shuffle reuses the same one.

Next is that main loop:

for(var top = input.Count -1; top > 1; --top)
{
    var swap = rnd.Next(0, top);
    T tmp = input[top];
    input[top] = input[swap];
    input[swap] = tmp;
}

Here’s where we see the major change to the implementation. Both method use basically the same algorithm, but instead of building a new List, I move the elements around within the same list. Essentially, I’m doing the same thing, if you imagine the two arrays occupying that same space – as one grows small the other grows bigger.

And with that, we’re done. Since the original List is now shuffled, we could return void, but by returning the input, we can allow chaining (and it also maintains the original method signature)

So, How does it work ? Here’s a quick example, showing off some of it’s new abilities:

        string[] A = {"A", "B", "C", "D", "E", "F", "G"};
        A.Shuffle().Print();

output: D-F-A-G-B-E-C-

Print() is a simple-minded extension method which just takes a list and prints it’s elements separated by dashes. Good for demos but not much else. Also for these examples, I’ve hard-coded the seed for Random to be 1234, so the sequence is always repeated. Again, good for demos, but not for production work.

But, you said you didn’t want the original list destroyed. (yes, you did in fact say that!). No problem, we’ll just write a second method, and since the problem definition requires two lists, there’s no shame in eating the cost of creating a copy of the input list. To keep it simple, I’ll also create & return a List<> regardless of what type of IList<> you passed in.

  return new List<T>(input).Shuffle();

But that brings us to another key point. The only thing that the input is being used for is to seed the new List, and that ctor doesn’t take an IList<>, it takes the much more common IEnumerable<> (which IList just happens to be a descendant of). So, we might as well make that our input parameter.

public static IList<T> ShuffleCopy<T>(this IEnumerable<T> input)
{        return new List<T>(input).Shuffle();    }

With this, we can do some interesting things, since you input doesn’t have to be a collection at all:

        Enumerable.Range(1,10).ShuffleCopy().Print();

output:  1-5-7-9-10-2-6-3-8-4-

Here’s the full source code:

static class Helper
{
    static readonly Random rnd = new Random();
       
    public static IList<T> Shuffle<T>(this IList<T> input)
    {
        for(var top = input.Count -1; top > 1; --top)
        {
            var swap = rnd.Next(0, top);
            T tmp = input[top];
            input[top] = input[swap];
            input[swap] = tmp;
        }
    
        return input;
    }      
    
    public static IList<T> ShuffleCopy<T>(this IEnumerable<T> input)
    {        return new List<T>(input).Shuffle();    }      
    
    public static void Print<T>(this IList<T> list)
    {
        foreach(T t in list)
        {
                Console.Write("{0}-", t);
        }
        Console.WriteLine();
    }
}

Share this post: Email it! | bookmark it! | digg it! | reddit!

A (somewhat) New jQuery plug-in: Wizard

James — Tue, 28 Jul 2009 22:58:57 GMT

As I slowly rewrite NJTheater.com, one task that I was trying to move from a MSAccess application to a webpage would be made much easier if put in a wizard form, with the user being led through the steps. Since I was using jQuery throughout the site, I figured I could find a plug-in for the job, and I did – sorta.

After rejecting a couple, I found formwizard by Jan Sundman, which mostly fit my needs. I would need to make a small change – but, I never can stop at just one small change. In the end, I’ve got a plugin which has at it’s core Jan’s code, but is nevertheless quite different. The revision, with docs and examples can be found here: Wizard.

The executive summary of it’s use: You have one form. It is divided up into several <DIV>s, each marked with the class “step”. You call $(“#theForm”).Wizard(). Each <div> is displayed to the user individually, and they can click Next or Back buttons to move between the page. When the users clicks Next on the final page, the form is submitted. There are a lot of options, and you could choose to make it much more complicated.

The first thing you’ll note about it, if you are familiar with the original, is that it, to the best of my abilities, now confirms to the jQuery UI standard for interface and CSS theming. I also added a new callback, several new methods, and a couple new options. Comparing the new code to Jan’s code is a bit tricky because the jQuery UI fra mework wants methods as tag properties of an object (i.e. SomeFunc : function() {…..} rather than function SomeFunc() {….}), but the major source code difference really had nothing to to with that nor had any good code-quality reason: I made some unnamed functions into named function, and alphabetized the methods, just because it made it easier for me to navigate through the code. However, this does make doing a DIFF between the two source file difficult.

So what were the more functional changes between the two versions? Mostly they reflect a somewhat different view of the use of wizards. In Jan’s code it seems, he largely viewed the wizard as just one big form, divided up into pages with one submit at the end. There was some infrastructure to alter the flow through the wizard, but it was limited. (I’m still not quite sure of the utility of the “linkClass” in Jan’s code in real-world situations)

I see a wizard as guiding the users through a multi-step process, where what you see on step 3 depends on ajax calls based on what you entered in Step 2, and your choices there affects the options in step 4. So, you’d need more control as the user moved from step to step. Jan’s apparently saw this need as well, and added the afterBack and afterNext callbacks, but they pass no parameters – you are told that the user has click “next”, but are left to your own devices to know where he is. I figured a developer would be more concerned about where the user was in the wizard, than how he got there. So I added the “Show” callback (also wired as an event by the framework). It tells you what step the user has just moved to, by it’s index number and by a jQuery object of the div itself. It also says if the user got there by moving forward or backward.

Also, Jan added validation by means of the standard jquery.validate.js plugin. In that scenario, the user would click “Next” and then the plugin would tell him to fix things. That’s not the way Wizards normally work, where the “Next” button is disabled upon the step is complete. So, I added an option autoDisabledNext which always displays the Next button grayed initially when moving it a new step, and waits for the script to re-enable it in response to some action by the user. The “enableNext” method handles that (with “disableNext”, “enableBack” and “disableBack” also added to give the developer complete control in this area).

In Jan’s original, the formwizard() method took three parameters, each js objects, the first for the wizard itself while the other two were passed to the forms plugin and the validation plugin respectively, which are optional --- the plugins, not the parameters. So if you weren’t using those plugins, you had to pass empty objects. I moved them to named parameters in with the other wizard options, where they could be defaulted. Similarly, the boolean flags which had to be explicitly set, now derive their settings from the environment. You can still explicitly set them if you need to overrule that determination.

A few other changes just seemed to make more sense to me. formwizard expected the form to have a Submit and Reset buttons, which it converted into the Next and Back respectively. Submit for Next wasn’t too bad, but Reset for Back just seemed wrong. If you are going to have a button controlled strictly by Javascript, it should be a <button> element. So, they are indicated, by default, by the classes “wizard_next” and “wizard_back”. Another one just seems like fun and I wondered how difficult it would be: You can specify the effect used to display each page, via the “animate” option. The default is “FadeIn”.

Finally, I included a “old-school” jQuery plugin called “formwizard” which sets all the defaults I changed back to the way they were in Jan’s original, and then calls Wizard(), so we should have full backward compatibility.

Note: Despite my best effort to make the docs page look just like one of those for actual jQuery UI widgets, it is not part of the official jQuery UI package, and although submitted to them for review, probably will not be part of the official release any time soon (“not any time soon” == “a few years at least”).

Now, how can you help Wizard become part of the official jQuery UI package. Well, I guess you could mention in your blogs, tweets, forum message (particularly on the jQuery UI Google Group) that “wouldn’t it be great if jQuery UI included a Wizard widget --- just like that one James stolen from Jan”.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Posts from Comments: QuickDataBind

James — Tue, 28 Jul 2009 10:49:49 GMT

You may have noticed that I don’t write on this blog much. But the thing is I do write a lot on the inter-webs about technical matters --- I just don’t to it here. Usually, I find something interesting on someone else’s blog, and then write an improvement in the comments. So, my work goes to helping other people’s pagerank. I figure this has got to stop… To this end, I start a series where I turn comments I made on other blogs into posts on this one….

To start us off, a few days ago, Samer wrote about an extension method he created for ListView:

public static ListView QuickDataBind(this ListView myListView, object myDataSource)
    {
        myListView.DataSource = myDataSource;
        myListView.DataBind();
        return myListView;
    }

Now, this is all well and good. but why are we limiting ourselves to just ListViews? Many ASP.NET WebControl take a datasource and use that idiom. Why not make an generic extension method to handle all of them?

public static T QuickDataBind(this T myDataBoundControl, object myDataSource) 
        where T: BaseDataBoundControl
{
        myDataBoundControl.DataSource = myDataSource;
        myDataBoundControl.DataBind();
        return myDataBoundControl;
}

It's still called exactly the same well:

       myGridView.QuickDataBind(myDS);

but now it can be used on ListViews, GridView, DropDownLists DataGrids, Repeaters or anything else that uses a DataSOurce.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Washington vs. Hollywood.

James — Mon, 22 Jun 2009 16:51:05 GMT

With the pending appointment of Judge Sonia Sotomayor, someone pointed out that if she is approved, there will have been in 120 years, 111 Supreme Court Justices, of whom, only three were women and only two were African American, with all the rest being white men.

On the other hand:

In the past 80 years, The Academy of Motion Picture Art & Sciences has nominated 208 people for the Best Director Oscar™ (some more than once) of which three have been women, and only one African-American, with all the rest being white men.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Men & Women & Careers in IT.

James — Mon, 22 Dec 2008 16:28:19 GMT

(Ok, this is the third time I'm writing this. The first time it was in the comment form of a blog. For some reason, it just swallowed the message without posting it, blanking the editbox, and then giving an error saying the edit box was empty. So, I tried again. The second time, not trusting a webpage textarea, I wrote it in a text editor, so I'd have a copy if the website continued to be difficult. But I wrote it in the train into work, so I couldn't post it immediately. I just close up my laptop with the article unsaved in Crimson Editor. When I got to work and tried to upload it, my laptop refused to come out of hibernation, forcing me to power cycle it (twice). Text lost again. By the time I was half-way through the second version, I decided I should post it to my blog as well. Fortunately, Live Writer makes saving very easy (you get to skip that "Save File" Dialog), so this time it may actually see the light.)

Sara Chipps (aka "Girl Developer") just wrote an article about women in software development. I see it as a bit more complicated.

Over my 20+ (gag) years as a professional software developer, I've noticed an interesting thing about the male:female ratio amongst software developers.

For Chinese developers, it's very close to 1:1.

For Indians and Russians, it's about 2:1.

For American-born developers of Western European descent, it's around 20:1. And that's counting project leaders and other managerial roles. If we limit it to just coders, it gets close to triple digits --- and it's only that low because I worked with four fine American women programmers at one job back in the 80's -- before the big H-1B explosion.

I feel this is because programming ability, unlike being a doctor or lawyer, is not respected as a skill. Development isn't a job one aspires to; it has become just another dead-end job for those that couldn't hack med school.

Part of the problem can be traced to the fact that most Americans have absolutely no clue what a "computer person" does. They may not be able to perform surgery, but they do have a general idea what a surgeon is doing, and they can tell the doctors from the orderlies. But, very few people know the different between a computer programmer and a computer operator ("It's the different between writing a novel and running a printing press"). Most literally treat the ability to get a computer to do something as if it were a form of Black Magic (and yes, I do mean "literally" there). You just type in the memorized incantations and the computer sudden does your will -- like wizardry, a trait you are born with, not something that can be taught and developed. Most depictions in movies and TV treat the skill as something that even surprised us --- that we know how to do the spell, but not how the spell works. (unfortunately, this is becoming true...)

This, of course, shouldn't be surprising from an American populace that generally seems proud of their inability to do math, and treat anyone who can do even the simplest arithmetic in his head as a freak.

Then there is accountability --- we feel that we are able to recognize a good doctor from a bad doctor, and maybe a good lawyer from a bad lawyer, but if you have no clue what a person does, how can you rate them? They consider the teenage that can a throw together an Html page as much of a "computer genius" as a compiler author (or they would if they had any clue what a "compiler author" was).

Star doctors save lives; star athletes fill stadiums, and as such deserve huge salaries. However, star developers, in the public's mind (and unfortunately in the minds of upper management of many companies hiring developers), can be replaced by nerdy 16-year-olds. Salaries have plateaued -- According to Payscale.com, a developer with 20 years experience can be expected to make only about 30% more than one with just one year of experience. In the same survey, a similarly experienced lawyer can expect double the salary of a beginner.

We have a profession that is not respected, is not considered a learnable skill, where experience counts for little, has little job security, whose average salary becomes more mediocre with each passing year, which management believes can be out-sourced to third-world countries.

[side note: The trend to outsourcing that's been underway since the 90's has an interesting dynamic. It seems hiring has been based on the theory: "Who better to work on the Black Art of programmer than people from the mystical lands of India and the Orient?". Now, India does have one of the best Engineering schools in the world, but only a very tiny percentage of the population attends. It's much like assuming that because I'm American, I must have attended Harvard . In fact, a far greater percentage of American are Harvard grads than Indians who have graduated from the Indian Institute of Technology. On the other hand, tall tales of the Far East Mysticism go back nearly a millennium. So, it seems that hiring has gone from being based on sexism, to being based on racism.]

So, the real question is, not "Why so few Women?", but actually, "Why so many men?".

From what I've seen answering question on various programming forums, it appears that every young boy that want to start programming, does so, so that he can write, as his very first program, a First-Person Shooter game. And why not? Programming is Black Magic. Writing Grand Thief Auto is no more difficult than writing Hello World, right? Recently on StackOverflow, someone asked about writing a game. He mentioned that he wanted to write everything himself, instead of using a framework, because he "wanted it to be fast". I had to explain the game frameworks were written by teams of experts in the field with, collectively, decades of experience on micro-optimizations to squeeze every last cycle out of each video card, so if he had any hope of it being fast, he'd better use a framework.

So, where are most women and many men turning to instead of software?

Well, if the Reagan/Bush/Bush era (and to a lesser, but still real extent, the Clinton era) has taught us anything, it's that workers are scum. Only the very top of the ladder has any hope to true success. When evaluating career paths, unless someone has a "calling" into a particular job (actor, teacher, priest), based on career potential, the choices basically run : Doctor, lawyer, CEO. That where the money is. Developer has become a job you "fall into" -- just slightly above being promoted from store clerk to assistant manger.

So, what can we do about this?

Damned if I know.

I suspect that high school biology and social studies classes help us appreciate the skill of doctors and lawyer. As far as I know, HS classes on computers are largely limited to using MSWord and Excel --- teaching us to appreciate the secretaries we don't have anymore.

So, should high schoolers by required to take a semester in programming? That would be nice, but I figure if you add a required course, that means you'll have to drop an existing required course, and I'm not sure what I'd give the heave-ho to. What's more, programming isn't even my top choice for course that all should be part of the basic curriculum --- recent event have shown that that clearly needs to be a course in Personal Finance.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Sex & Computers & Rock & Roll : The Cycle of Creativity

James — Sun, 14 Dec 2008 00:55:07 GMT

Ok, there is actually no sex in this article. The title is merely a tribute to the great Ian Dury & the Blockheads. But there will be computers and Rock'n'Roll.

Recently a question of StackoverFlow.com asked about "breaking the rules" of programming. I used it to discuss my theory of the Cycle of Creativity. Since some questioned it, I figured it would make a good topic for the blog.

All human creative activity seems to follow a cycle of three phases:

A period of random experimentation and mimicry: The results are very hit & miss. We get some of the very best works, but also some of the very worst.
The establishment of "The Rules": Product is produced steadily. Quality is constant but mediocre. Corporate profits are high. Product become formulaic.
The Masters learn when to break the rules: This is the period of greatest creativity. The rules are there for support most of the time, but, once they are mastered, one knows when is the perfect time to break one, to create a work of true art.

Unfortunately, this is then always followed by people who, having seen the Masters break the rules, decided the best thing to do if just throw out the rules, plunging the whole system back into Phase One.

I believe anyone familiar with computer programming can see the three phases at work there. In phase one was the "spaghetti code" era. Phase two began with the introduction of "structured programming", then "object oriented programming" and finally "Design Patterns". We're now in phase three, where most of the data structures and algorithms we learned in school are readily available in frameworks as a black box. Now we can worry about the design of the application itself, and the skillful know the exact time to use a goto or have multiple function exit points.

The controversial part of that message was an alternate example I gave : That for Rock music, the three phases roughly correspond to the 1960s, 70s and 80s. Some balked at that, but I stand by it.

One commenter stated that R'n'R has been going downhill since Buddy Holly. That's a imprecise comparison since I was talking about an entire industry, and there will always be individual exceptions. Any observer of the music scene in the late 50s (particularly the part that was true Rock & Roll rather than Rhythm & Blues) would clearly see the random experimentation - Any song that made the Top 40 was follow immediately follows by three or more cover versions by other groups --- which also made the charts. Bobby Darrin's hit "Mack the Knife" (which you'll recall was a song about a petty thief and murderer from a ten-year old German musical ) was actually the seventh version of that song on the Top 40 that year! No one really knew what they were doing. And Buddy Holly's brief career demonstrated that he had made it through the three phases: his last recording before his death were clearly in the "master knowing when to break the rules" mode.

This continued into the 60's -- A lot of experimenting (some of it musical) going on. It produced some of the best music (The Beatles) and some of the worst ("Little Itty-Bitty Yellow Polka-dot Bikini"?).

In the 70's, the corporations finally reigned in R'n'R, and the rules were set. The instruments were fixed: (lead guitar, rhythm guitar, bass guitar, drums), bands cranked out a new album every 9 months, songs were between three and four minutes long; if a band "broke up", it were gone for good. Top 40 music became formulaic. The decade culminated with the ultimate in pre-packaged, corporate-friendly music: Disco.

And yet, at the same time, came the beginnings of the third phase, in the punk movement. The early players, notably The Clash and the Sex Pistols (especially their manager, Malcolm McLaren) were definitely in the "masters knowing when to break the rules" realm --- unfortunately, it slide into phase four quite rapidly, where everyone started breaking rules without reason, and it soon became a messy.

Which brings us to the 80s, which I have deemed the peak of the rock era, and which some dispute. Now, I spend 1980 thru 1984, in college, DJing at my college's radio station, so some might think I'm a bit biased towards that period, so I'll have to offer some proof. First of all, on the news this morning, they listed the top concert acts for the year: Bon Jovi, Bruce Springsteen, Madonna, and the Police. Now, while I think it's should be noted that the top two are both from New Jersey, the important point is when each of them hit their peak: What was that? Yes, the early 80s. (Yes, I know that "Born to Run" came out in the mid 70's, but Springsteen was just a one-hit wonder until "Hunger Heart" and "Born in the USA"). And while you might dismiss Jon, Bruce and Madge as just Top 40 fodder, Sting & the Police have proven themselves timeless artist, along with Joe Jackson, Elvis Costello, Thomas Dolby, The Talking Heads, Prince, U2 --- All major talents who established themselves by breaking rules -- under controlled conditions, and did so in the early 80s.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Predicted

James — Thu, 13 Nov 2008 04:40:57 GMT

Way back into March, my best friend Chris and I made our predictions for the presidential election. Since the election is now over (mostly), it's time to review have well we did:

	Chris's Prediction	James's Prediction	Actual results
President	McCain	The democrat	Obama
States won by Democratic nominee	14	20	27
Senate seats won by Dems	0	+4	+6 (maybe +9)
House of Representatives	-8	+10	+23
Governors won by Dems	-2	+2	+1

So, in every category, I was closer, and except for governors, even I was too pessimistic.

Share this post: Email it! | bookmark it! | digg it! | reddit!

jQuery.growl Documentation

James — Tue, 21 Oct 2008 02:47:26 GMT

Right now, I'm in the midst of a long-running project to rewrite my other website, NJTheater.com (beta at njtheater.org). In the process, I've discovered jQuery, the hot new javascript library that all the kids are using today. One of it's key selling points is it's well designed plugin system, which has led to a host of add-ons being written for it.

Recently, I stumbled upon one such plugin, jQuery Growl Plugin by David Higgins. Apparently, Growl is a MacOS application, so the Applist readers should by now figured out what it does. For the Windows/Linux folk, it displays a little popup alert box, sort-of like the Messenger "toaster" popup, except they come down from the top. They slide down, stay for a few moments, and then fade out. If another is displayed while the first is still visible, they stack. Demos here. Now, while the demos looked rather cool, library itself does suffer from the main problem that affects most open source code -- the documentation just sucks. In fact, it goes beyond mere suckage; at one point, you get the feeling the author is just mocking you.

But no sense in just complaining, or insulting a person who has contributed to the community. The best thing to do in this case is for one to contribute himself. And so, here's my documentation for the plugin

jQuery.growl

The official calling syntax is:

$.growl(title, message, image, priority);

All four parameters are strings, and all have defaults, so you only need to pass the ones you are using. However, the first two default to an empty string, so it'll be rather boring unless you specify them. The third and fourth parameters have reasonable defaults, but, well, we'll get to that in a minute.

You see, the important thing to realize here is that the HTML displayed is template driven. So, while the first parameter is called "title", that merely means that it'll be used to replace the string "%title%" in the template. Similarly, the value of the "message" parameter replaces "%message%" in the template; "image" replaces "%image%", and you guessed it, "priority" replaces "%priority%".

This is important to know, because, while there is a default template, which uses %title% as the title and %message% as the message, you can define your own template and in that template, you can use the four parameters for whatever you what. (Templates are defined at the global level, which in this context mean "for the page").

Here we start getting into the bizarre part: The replaceable keywords "%image%" and "%priority%" do not appear in the default template at all. Unless you define your own template, the values you pass for them will never be seen. Of course, if you do define your own template, there's nothing requiring that you use"%image%' as an image or "%priority%" as a priority. The only thing holding them to their preordained role is their defaults: the image parameter defaults to ''growl.jpg", and priority defaults to "normal". (So the parameters aren't used out of the box having meaningful defaults, while the two that are used, have useless defaults).

The default template is rather minimalist, but functional:

<div class="notice">
<h3 style="margin-top: 15px">%title%</h3>
<p>%message%</p>
</div>

An example of a more elaborate template would be:

<div>
  <div style="float: right; background-image: url(normalTop.png); position: relative; width: 259px; height: 16px; margin: 0pt;"></div>
  <div style="float: right; background-image: url(normalBackground.png); position: relative; display: block; color: #ffffff; font-family: Arial; font-size: 12px; line-height: 14px; width: 259px; margin: 0pt;">
    <img style="margin: 14px; margin-top: 0px; float: left;" src="%image%" />
    <h3 style="margin: 0pt; margin-left: 77px; padding-bottom: 10px; font-size: 13px;">%title%</h3>
    <p style="margin: 0pt 14px; margin-left: 77px; font-size: 12px;">%message%</p>
  </div>
  <div style="float: right; background-image: url(normalBottom.png); position: relative; width: 259px; height: 16px; margin-bottom: 10px;"></div>
</div>';

(That one came from jQuery.growl's author, and we still haven't found a use for the priority parameter!)

The template is changed by setting the $.growl.settings.noticeTemplate field.

$.growl.settings.noticeTemplate = '<div class="%priority%"><div class="%priority%-heading">%title%</div><div class="%priority%-message">%message%</div></div>'

The other setting that change be changed the same way are:

Property	Description	Default	Type
dockTemplate	Element in which the notices are created.	'<div></div>'	string
dockCss	Style elements applied on dock, generally used to specify it's position.	Fixed in the upper right corner of the browser window	object whose properties are feed to a css() method call.
noticeTemplate	Template for notice.	(see above)	string
noticeCss	Style elements applied on notice.	White on Green at 3/4 opacity.	object whose properties are fed to a css() method.
noticeFadeTimeout	How fast the notice fades out.	'slow'	String\|Number, suitable for use in an animate() method call.
displayTimeout	Total time the notice displayed.	3500 milliseconds	number
defaultImage	Value used for %image% when not specified in the call.	growl.jpg	string
defaultStylesheet	Gives the name of a stylesheet , which, if specified, is automatically loaded.	none	string.

The dock needs a bit more explanation. It's basically where the notices are drawn, and there's probably little reason to change it from it's default of a vanilla div. Note that whatever it is, it will have the attributes "id=growlDock" and "class=growl" added to it.

If you want to change the look of the dock, and want more control of it than stuffing some html into a property, you can just define an element with an id=growlDock, and $.growl will use that.

However the dock is defined, the style elements defined in the dockCss property are then added to it, and it's append to the <body> of the page.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Fun Fact: To the Moon, Alice, to the Moon!

James — Thu, 16 Oct 2008 16:15:00 GMT

I really should bring the subject matter here back around to computers.....

Lately (if you consider the last year & a half "lately"), I've been working on a project on my laptop using VisualStudio (usually on the train to work). Every now & then some action (like, say, highlighting a couple lines and pressing Ctrl-C to copy them), will cause VS to lock up for about 30 seconds, and then just pop back to life. I think it's a bad interaction between a couple of VS addins, but whatever the cause, it does leave me wondering "What the F#©& is it doing??" This lead to an idea, which after a bit of reseach, lead me to this:

In three minutes of hourglass-displaying spinning, my dual-core 1.87GHz laptop uses more CPU clock cycles then the entire six day Apollo 11 mission.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Yep, I'm a socialist....

James — Mon, 13 Oct 2008 14:12:00 GMT

I haven't posted here in a while, so I figure I'll go back to the old "generate content by taking online quizzes" trick.

You are a
Social Liberal
(66% permissive)

and an...
Economic Liberal
(20% permissive)

You are best described as a:

Socialist

Link: The Politics Test on Ok Cupid
Also : The OkCupid Dating Persona Test

Now, some people might be a bit concerned about being called a Socialist, but when you consider that the recent governement bailouts of the AIG and the mortgage industry essentailly meant that we've nationalist several large companies, making President Bush and our Congress history's biggest Marxists. It seems Socialism is all the rage.......

Share this post: Email it! | bookmark it! | digg it! | reddit!

Contribute to open source, get a shot at a free book

James — Mon, 15 Sep 2008 19:10:10 GMT

David Ward has an interesting contest. Having three copies of Advanced ASP.NET AJAX Server Controls to give away, he's created a project on CodePlex, and is offering the books to people to who contribute the most to it. One can contribute code or documentation or anything -- one book is raffled off among those who merely participate in the online discussions about it (or post a blog entry about it). Since these days I'm into Monorail and jQuery rather than asp.net, I can't contribute much in the way of code, but I am very active in the discussion group. In fact, if you discount the coordinator (Encosia aka David Ward) and JRumerman (who is one of the authors of the book being given away), I think I'm the most active guy there).

Oh, I guess I should mention the purpose of the project: it's to develop an ASP.Net AJAX web control to accept a potential username and handle automatically checking if that name is already being used by someone else.

Now, to contribute, you probably need to know a fair amount about ASP.NET AJAX control --- which means you may not need to book you could win, but it's a fun idea anyway....

Share this post: Email it! | bookmark it! | digg it! | reddit!

Billions & Billions

James — Wed, 27 Aug 2008 02:48:03 GMT

Recently I got a chain email from a friend, showing the magnitude of a billion.

A billion seconds ago it was 1959.
A billion minutes ago Jesus was alive.
A billion hours ago our ancestors were living in the Stone Age.
A billion days ago no-one walked on the earth on two feet.
A billion dollars ago was only 8 hours and 20 minutes, at the rate our government is spending it.

As I normally do with such things, I immediately went to snopes.com to find out how accurate it was. (bottom line: eh....close enough, although it was probably written in the early 1990s).

The interesting thing about it is that it apparently has gone through three phases. The first had just that bit above about billions. I guess the politics in that was too subtle for some people, so, more recently someone added a bit about Hurricane Katrina and New Orleans:

Louisiana Senator, Mary Landrieu (D) is presently asking Congress for 250 BILLION DOLLARS to rebuild New Orleans .. Interesting number... what does it mean?

A. Well... if you are one of the 484,674 residents of New Orleans (every man, woman, and child) you each get $516,528.

B. Or... if you have one of the 188,251 homes in New Orleans, your home gets $1,329,787.

Snopes dealt with this section as well, but not with their usually efficiency. They pretty much just limited themselves to checking the author's math. (again, close enough, but not perfect, which is odd considering he gave very precise wrong values). Furthermore, apparently quite recently someone added a bit more, which snopes doesn't cover at all:

Washington, D.C
< HELLO!>
Are all your calculators broken??

Accounts Receivable Tax
Building Permit Tax
CDL License Tax
Cigarette Tax
Corporate Income Tax
Dog License Tax
Federal Income Tax
Federal Unemployment Tax (FUTA)
Fishing License Tax
Food License Tax
Fuel Permit Tax
Gasoline Tax
Hunting License Tax
Inheritance Tax
Inventory Tax
IRS Interest Charges (tax on top of tax)
IRS Penalties (tax on top of tax)
Liquor Tax
Luxury Tax
Marriage License Tax
Medicare Tax
Property Tax
Real Estate Tax
Service charge taxes
Social Security Tax
Road Usage Tax (Truckers)
Sales Taxes
Recreational Vehicle Tax
School Tax
State Income Tax
State Unemployment Tax (SUTA)
Telephone Federal Excise Tax
Telephone Federal Universal Service Fee Tax
Telephone Federal, State and Local Surcharge Tax
Telephone Minimum Usage Surcharge Tax
Telephone Recurring and Non-recurring Charges Tax
Telephone State and Local Tax
Telephone Usage Charge Tax
Utility Tax
Vehicle License Registration Tax
Vehicle Sales Tax
Watercraft Registration Tax
Well Permit Tax
Workers Compensation Tax

STILL THINK THIS IS FUNNY?

Not one of these taxes existed 100 years ago...
and our nation was the most prosperous in the world.

We had absolutely no national debt...
We had the largest middle class in the world...
and Mom stayed home to raise the kids.

What happened?
Can you spell 'politicians!'

And I still have to press '1' for English.

Now, since Snopes dropped the ball on this on, I figured I'd do my part to correct the misinformation here.

First of all, as an aside, you can tell the additions were written by a right-winger, as they blame the $250 million on the state's Democratic senator, when in reality the bill was co-sponsored by her and the state's other senator, Republican David Vitter -- which points to the other sure sign it was written by a right-winger -- it's riddled with errors.

The main error is that the money is not just for New Orleans, but for all areas damaged by Katrina -- which includes large parts of Louisiana, Mississippi and bits of Texas. That pretty much invalidates his whole premise. But, even if it were just for New Orleans, his premise would still by wrong, because it's not just to rebuild people's houses, but to rebuild the entire city infrastructure: roads, schools, hospitals, levies, etc. I imagine Republicans would have might less of a problem with government if any of them actually understood how it works.

Which brings us to the third section of the email, where the writer just goes off the wall. By line count, it's half of the whole thing, so clearing this guy like hearing himself talk. Too bad he was too busy typing away to bother actually fact-checking what we wrote.

Of that long list of taxes we didn't have "a hundred years ago", many, granted, we didn't have, but mainly because for the most part, the thing being taxed didn't exist (Phones, Social Security, Motor Vehicles etc). And we really didn't have an income tax in 1908 -- That came about in 1912. But, as for the rest -- Real estate, alcohol, tobacco, marriage licenses etc --- They pretty much all were taxed.

It's also a bit questionable if we were "the most prosperous [nation] in the world" in 1908, as we really didn't start moving past England, France and German until after WWI.

His assertion that "We had absolutely no national debt... " is total fantasy. In 1908, the national debt was $2,626,806,271.54 (adjusted for inflation that would be nearly $58 billion in 2008 dollars). Granted, that's a lot less than the $9.6 trillion it is now, but we'll get to that in a minute. The last time we paid off the debt was 1834.

As for "We had the largest middle class in the world... ", again, hard to measure --- Do you count raw number of people (we probably win), or percent of population? (in which case you have to look at England, France and German again).

"Mom stayed home to raise the kids." -- Well, mom did stay at home then, but mostly to run the household, which didn't have electricity, nor, most often, running water. She had to do this because her husband was working 10 hours a day, 6 days a week at a factory -- earning about a dollar a day. She didn't spend that much time raising the kids -- because, starting at about age 9 or 10, they were with the father in the factory.

Oddly, the writer seems to be blaming the raising national debt on taxes. Maybe his a fan of Rush Limbaugh, since that's one of his wacky ideas: "The best way to increase government revenue is to cut taxes". But, in reality, it's a lot like saying "The best way to pay your bills is to quit your job". A much more reasonably plan would be "The best way to pay your bills is to quit your job, and get a better job". Similarly we could say, "The best way to increase government revenue is to cut taxes, and direct the money to growing the economy". But, like the job quitting plan, Republicans seem to leave off the last part --- the important part -- and are happy to let multi-millionaires use their tax breaks to pad out their trust funds.

Which brings us to the real causes of the national debt: Wars (historically) and Republican presidents (recently). The very first time the debt passed $1 billion dollars was during the Civil War. That was also it's fastest raise (ten-fold in just two years). It floated around $2 to $3 billion for about 50 years, when it sudden raises nine-fold in four years just in time for WWI. Then a slight rise during the Great Depression (tripling over 11 years), followed by a big jump for WWII (five-fold in four years), reaching a quarter of a trillion dollars by the end.

The debt grew rather slowly after that, taking 30 years (till 1975) to double again. Then, under the Reagan administration so-called "Economic boom," it triples, passing one trillion dollars for the first time. Overall, Reagan & Bush-41 combined brought the debt from under $1 trillion to over $4 trillion (340%) is just 12 years-- with no significant war. In contrast, during Clinton's 8 years, it raised only 31%. And we were poised to start actually paying some of it off. But with Bush-43, we're back to the old pattern, up 66% in 7 years.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Lists: Filter, Map and Reduce - and the Magic of IEnumerator.

James — Mon, 25 Aug 2008 19:16:16 GMT

I have this bad habit. I will frequently stumble upon a blog post describing some new technique, to which I will post a brilliant comment offering an improvement, which, of course, will get lost in the flotsam and jetsam of the blogosphere. I have to keep reminding myself that is what I have my own blog for.

Case in point, I recent found this article by Sarah Taraporewalla about writing tradition Filter, Map and Reduce methods for Java Lists. She wondered if they could be written in C#. I did so in the comments, and now expanded on them here.

The main difference between mine and those of Sarah's (and also those of Peter, by way of whose blog I reached Sarah's) is that they pass in a List<> object, and create a new List to return. This is limiting and unnecessary.

namespace FilterMapReduce
{
    static public class FMR
    {
        public static IEnumerable<T> Filter<T>(this IEnumerable<T> list, Func<T, bool> filter)
        {
            foreach (T item in list)
            {
                if (filter(item))
                    yield return item;
            }
        }

        public static IEnumerable<T> Map<T>(this IEnumerable<T> list, Func<T, T> map)
        {
            foreach (T item in list)
            {
                yield return map(item);
            }
        }

        public static U Reduce<T, U>(this IEnumerable<T> list, Func<T, U, U> reduce, U accum)
        {
            foreach (T item in list)
            {
                accum = reduce(item, accum);
            }
            return accum;
        }
    }
}

I used a number of .Net v3.5 features there -- notably extension methods and the Func<> delegate, but neither is vital (the non-extension version has just a little messier calling syntax, and you'd have to define your own Func delegate replacement -- so, UPGRADE!)

With those, we can now write code like this:

int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int sumOdds10 = nums.Filter(n => (n % 2) == 1)
                    .Map(n => n * 10)
                    .Reduce((n, a) => (n + a), 0);

I broke the last line to three lines for easier reading, but you could just string it out of you'd like.

Now that says, "Take the nums array, filter it so we're left with just the odd numbers, map each remaining value to itself times 10, and then sum each of those."

The important question here is: "How many times have I looped through that array?" You might think that since I call all three methods, and each has a foreach loop, that it would be only logical that we've go through the array three time. Logical, maybe, but wrong. To understand this, let's split that code up a bit:

var a = nums.Filter(n => (n % 2) == 1);
var b = a.Map(n => n * 10);
int sumOdds10 = b.Reduce((n, a) => (n + a), 0);

First we create object a, which if you recall is IEnumerator<int> object. We haven't looped through the array yet -- we just have an object that will loop throught the array.

Next, we create object b. Again, an IEnumerable<int> object, but notably, one which enumerates over, not our array, but the a object.

Finally, we call Reduce which actually does the work. It starts to iterate over the list, which is our b object, which is just an IEnumerable object. So, as we enter Reduce's foreach, it calls b's (i.e. Map's) MoveNext() method, and enters it's foreach to iterate over the a object -- for which is calls a's (Filter's) MoveNext method.

OK, so now we finally enter FIlter's foreach loop, which iterates over an array, so we get a real number (1 at first). It passes the filter so the yield return sends it back to Map, which call the mapping function on it, and yields it up Reduce, which uses it in the reduce function.

Then Reduce moves on it the next value, which means calling B's MoveNext, which calls Filter's MoveNext, which gets the next value from the array (2). This fails the filter, so it gets the next value (3), which passes and goes back to Map, and so on, to Reduce.

In the end, we've only gone through the array once.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Dev102's Challenge #13 : Brackets

James — Mon, 21 Jul 2008 17:18:03 GMT

Many people skipped last week's challenge (like I had planned to). As it turned out, I was the only blogger to responded.

For this week's challenge, they've gone back to a platform-neutral algorithm question:

Your input is a string which is composed from bracket characters. The allowed characters are:’(', ‘)’, ‘['. ']‘, ‘{’, ‘}’, ‘<’ and ‘>’. Your mission is to determine whether the brackets structure is legal or not.

The simple sentence answer is "use a stack, pushing on an open character, and popping on a close character". There are a few other things to look out for, but that's the basic concept. For the actual code, I bypassed any kind of library Stack class, since we wanted the most efficient and for the very limited need of this function, I could jury-rig a faster one out of a char array. Complexity is speed: O(N), space O(N)

static bool TestBrackets(string testcase)
{
    // create a very simple stack.  
    // Since we push on open & pop an close, stack need only be half the
    // size of the input string.  The +1 is needed because we only check
    // for too many opens after we've pushed.
    char[] stack = new char[(testcase.Length / 2) +1];
    
    int SP=0;
    foreach(char chr in testcase)
    {
        switch(chr)
        {
            // For each open character, push the close char.
            case '[':
                stack[SP++] = ']';
                break;
            case '<':
                stack[SP++] = '>';
                break;
            case '{':
                stack[SP++] = '}';
                break;
            case '(':
                stack[SP++] = ')';
                break;
                
            case ']':
            case '>':
            case '}':
            case ')':
                // check for stack underflow (too many closes)
                // or a character we weren't expecting (bad  nesting)
                if (SP==0 || stack[--SP] != chr)
                    return false;  
                break;
        }
        // Check for stack overflow (too many opens)
        if (SP==stack.Length)
            return false;
    }
    // Finally, it's good if we've closed everything we've opened.
    return SP==0;
}

Share this post: Email it! | bookmark it! | digg it! | reddit!

Dev102's Challenge #12 : Managed & unmanaged

James — Wed, 16 Jul 2008 18:52:52 GMT

My solution(s) for last week's challenge were cited, but, only as an "honorable mention" / "also run".

This week's challenge is a different sort of animal. Not that it is particularly difficult --- actually I suspect it's quite easy --- it's just that it requires a fairly specialize knowledge (Managed Extensions for C++ in this case). A couple of them in the past required some basic knowledge of .Net & the CLR, but most of the time, the challenge involve a non-platform specific algorithm.

So, knowing nothing about Managed Extension, I was just going to let this one pass. But, I happened to run into an old friend (Will Depalo) from my days as a VC++ MVP. When I went to .Net, I also switched to C#, but he stayed with C++, so I figured he would have some insight. Reducing the problem to one sentence ("we have a unmanaged class accessing an instance variable of a managed class"), and he immediately knew the answer ("you'll need to pin it"), and offered some advice ("look up '__pin' in the msdn"). However, didn't realize exactly how good that advice was, as the folk's at DEV102 apparently took the example source code from the __pin article to create the challenge. So, here's my answer (I love stuff that can be answer via copy'n'paste):

int main() 
{
   ManagedClass __pin * pMngdClass = new ManagedClass;
   UnmanagedClass* pUnmngd = new UnmanagedClass;
   pUnmngd->incr(&(pMngdClass->i));
}

The rest is unchanged.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Dev102's Challenge #11 - Summing Numbers

James — Tue, 08 Jul 2008 13:55:37 GMT

My answer was acknowledged as correct for last week's challenge. So, let's see if we can make it two in a row. This week:

Given a list of n integers and another integer called m, determine (true / false) if there exist 2 numbers in that list which sum up to m.
Example: 2,6,4,9,1,12,7 and m=14 -> 2 and 12 sum up to 14, so the answer is true.

This one is rather tricky. There is no obvious (to me) solution. I can see three viable methods, each with its own pros & cons.

Method 1: We'll call this "brute force". The obvious answer. We add the values of list[1] and list[2], then list[1] and list[3], then list[1] and list[4] and so forth, until we reach list[1] and list[ n ]. If we haven't found a match yet, we then move on to adding list[2] to list[3], then list[2] to list[4] etc. In code that would be:

for(int i= 0; i <N-1; ++i) 
    for(int j= i+1; j < N; ++j) 
       if (list[ i ] + list[ j ] == M)

The complexity for this would be Summation N which is officially O(N*N) (although it's closer to O(N*N/2) ). However, that's the worst case: we can exit early as soon as we find a valid match, making the average case O(N*N/4). It's also important to note the basic operation that's being repeated (adding two number) is very fast. Hence, this would be the winner for small values of N (and probably some very large "small values of N").

Method 2: Which we'll call the "bi-directional search". This would clearly be the winner, except for it's precondition: start with a sorted list. Add the first and last elements of the list (list[1] + list[ N ]). If they equal to goal, we're done. If they are more than the goal, add the first and second-to-last elements(list[1] + list[ N-1 ]). If they are less, then add the second element to the last element (list[2] + list[ N ]). Continue this way, moving up from the front when the sum is too low, and down from the back when it's too high until you either find a match, or meet in the middle. The complexity of this algorithm in O(N) --- for a sorted list. We're given an unsorted list, which means we'd have to sort it first. Sorting is, at best, O(N*logN), making the total complexity O(N*logN + N), which I believe is still less than method 1, but the basic task being done for the sort (comparing and swapping) is much more expensive than for method 1. Further, you must complete the sort before you can start the search, so you've taken the big hit before you get a chance for an early exit, making the average case O(NlogN+N/2), so this will win for large values of N, but they'd have to be very large values of N.

And, finally, Method 3, which we'll call the "partitioned search". Partition the list into two sublists, one with values less the M/2 and one with values greater than M/2. (The value equal to M/2 can be ignored, as we would need two of them, and we've been assured that the values in the list are unique). If a solution exists, it will require one from each list; any combination of two from the lower sublist will be two low. Any two from the upper list will be too high. So we just try every combination of one from each sublist. In the worst case, that's O((N/2) * (N/2)) or O(N*N/4), with an average case of O(N*N/8). To explain with examples: Say we are given a list of 10 numbers. Method 1 would require 55 additions to try every possibility. If we partitions the list into sublists of 5 & 5, then this method would require only 25 additions. However, if the numbers break down so that the partitions are 8 & 2, then we'd need only 16 additions. And, as before, we can exit early as soon as we find a match. Partitioning can be done in O(N): Start by pointing at the first and last elements, just as in Method 2. Seek forward looking for an element greater than N/2. When one is found, seek from the end, looking for an element less then N/2. When you have one of each, swap 'em and continue. When the pointers meet, the list is partitioned in place. That required only one pass through the list, so the step is O(N), making the total for the average case O(N*N/8 + N).

Overall, Method 1 wins for small lists, Method 3 for larger lists, and Method 2 for very large lists. Since memory read/write efficiency is the last bottleneck (how many additions is one swap worth?) the exact point where one method passes another is heavily platform dependant.

In the back of my mind, two other ideas for other methods keep flowing through. The first tells me that there should be some way to accomplish this through summing the list. This would be O(N), but I just can't think of a way to make it work. The other involves building a matrix. I'm pretty sure I could make that work, in a way that O(N) once the matrix is built, but building it would be greater the O(N) itself, so the whole task would be no faster than the means described above.

Share this post: Email it! | bookmark it! | digg it! | reddit!

Dev102's Challenge #10 - The Missing Number

James — Tue, 01 Jul 2008 18:50:34 GMT

I didn't actually skip last week's challenge for Dev102. I did write up a solution. I just forgot to post it. It was wrong anyway.

Well, no sense it looking backward... This week's:

Your input is an unsorted list of n numbers ranging from 1 to n+1, all of the numbers are unique, meaning that a number can’t appear twice in that list. ..One of the numbers is missing and you are asked to provide the most efficient method to find that missing number.

And Shahar was right, it was rather easy. We just add up the number we get, and subtract that value from the sum we should have gotten if the missing number wasn't missing.

int FindMissingNumber(IEnumerable<int> list)
{
    int actualSum = 0;
    int expectedSum = 0;
    int n = 1;
    foreach(int i in list)
    {
        actualSum += i;
        expectedSum += n++;
    }
    expectedSum += n;
    return expectedSum - actualSum;
}

Things to note:

The complexity of the algorithm in O(n).
I assured that complexity by using the least powerful collection interface (IEnumerable), and iterated through it only once.
I summed the expected total manually instead of an formula on list.Count, but for some collection types (such as a linked lists) Count is, by itself, O(n).
The method will work for an empty sequence, returning 1.

Share this post: Email it! | bookmark it! | digg it! | reddit!

DEV102's Programming Job Interview Challenge #8

James — Wed, 18 Jun 2008 19:23:13 GMT

I skipped last week's DEV102 challenge. I didn't think my answer was right. Turns out that it was. I was assuming that it had a limitation that would disqualify it. I assumed that my solution would only work if you placed the coins in a tight grid with each newly-placed coin touching an existing coin. As a practical matter, this is true. It would be virtually impossible to properly place a coin mirroring the freely-placed previous coin without resorting to a tape measure and protractor. And the placement would have to be exact for it to work. So I suppressed my solution for lack of practicality, when all they really wanted was a theoretic solution.

Anyway, onward to this week's challenge, #8 (excerpted):

You are writing a software component that receives a binary record every 20 millisecond. .... Your component goal is to alert whenever it identifies a specific expression (which is provided at the initialization process) in the stream of records - you are looking for a specific combination of binary records.

The answer is, of course, a Finite State Machine. To explain how one works, we need to come up with a example expression to search for. Let's say these records come it four formats: Type A, type B, type C and Type D, and we are looking a sequence of records in the following pattern: ABACB (if you'd like, you can assume that there are many record types, and Type D represents "any record that's not type A, B or C"). So, we start in state "0". State 0 can be called "looking for first A record". At state 0, if we find an A record, we move into state 1 ("Find first A, looking for first B"). If we find any other kind of record, we stay in state 0. This can be expressed in table form as:

	Next state	when	record	found
Current State VV	A	B	C	D
0	1	0	0	0

Next when we are in state 1, if we find a B record, we move into state 2, but the other transitions are a bit trickier. If we find a C or D, we're back to state 0 ("looking for 1st A"), but if we find another A, we have to stay in state 1. Adding that to our graph:

	Next state	when	record	found
Current State VV	A	B	C	D
0	1	0	0	0
1	1	2	0	0

Ok, now, we are in state 2 ("found AB, looking for 2nd A"), Here if we find an A, we move on to state 3 --- anything else, and we're back to state 0.

	Next state	when	record	found
Current State VV	A	B	C	D
0	1	0	0	0
1	1	2	0	0
2	3	0	0	0

State 3 ("found ABA, looking for C"), is a bit trickier again. If we find a C, naturally, we move into state 4. And if we find a D, were back into state 0. But, if we an A, we step back to state 1. And if we find a B, we step back only to state 2 (ie, we've found "ABAB" and the second "AB" may be the start of the pattern we want.

	Next state	when	record	found
Current State VV	A	B	C	D
0	1	0	0	0
1	1	2	0	0
2	3	0	0	0
3	1	2	4	0

At state 4, we enter the endgame. We're trying to find "ABACB", and so far we're found "ABAC". If the next record is a B, we have success ("Let loose the pigeons!"). If it's an A, we go to state 1 (as usually). Anything else, and we start over at state 0.

	Next state	when	record	found
Current State VV	A	B	C	D
0	1	0	0	0
1	1	2	0	0
2	3	0	0	0
3	1	2	4	0
4	1	*	0	0

Now, to put this into C# code, we merely need a simple pre-initialize int array following the structure of the chart we just built, and start with our state at 0.

const int[,] states = new int [5,4]{

{ 1,0,0,0},

{1,2,0,0}

{3,0,0,0}

{1,2,4,0}

{1,-1,0,0}

};

int state = 0;

Then as a new record comes in, we just determine it's type, and update the state:

bool MatchFound(Record newRecord)
{

// return 0,1,2 or 3 for record type A,B,C or D respectively.
// can be assumed to be present, as per the spec.
int type = GetRecordType(newRecord);

// Here's where the magic happens
// just a simple index into an array.
state = states[state, type];

return state < 0; // Report success or failure.

}

And that's it. Total state held between records: one integer. Total work needed per record to determine pattern: one array lookup and one int comparison.

And the real beauty of this approach is that if we wanted to look for other patterns at the same time, it could be done. For example, by just changing the states[] array in the above to this

const int[,] states = new int [13,4]{

{1,5,9,0},
{1,2,9,0},
{3,6,9,0},
{1,2,4,0},
{10,-1,9,0},
{1, 6, 9, 0},
{1, 6, 7, 0},
{10, 5, 8, 0},
{-2, 5, 9, 0},
{10,5, 9, 0},
{1, 11, 9, 0},
{3, 6, 12, 0},
{-3, 6, 9, 0}

};

Then we'd be able to search for ABACB (as before, found when state = -1) and BBCCA (found when state = -2), plus one more pattern (found when state = -3).

Class Homework

1) (simple) Try to figure out the third pattern that can be found using that state table. (It's a sequence of 5 records using just A B & C)

2) (hopefully not possible) Try to figure out a sequence of records that would cause the state machine to miss one of those patterns (Note: after one is found, we start over at state 0, so it's not intended to find overlapping sequences, such as "ABACBBCCA". It's find the first but not the second.)

Share this post: Email it! | bookmark it! | digg it! | reddit!

DEV102's Programming Job Interview Challenge #6

James — Mon, 02 Jun 2008 14:16:00 GMT

Another week, another C# interview question from the good folk's at Dev102.com -- Although I use the term "good folks" advisedly, as this week they did not even acknowledge the solution I posted for last weeks puzzle (which was both correct, and, I believe, the first blog post about it).

Anyway, time to move on to this week's question.

Look at the following Code segment written in C#:

   1: ArrayList a = new ArrayList();

   2: ArrayList b = new ArrayList();

3:

   4: a.Add(1);

   5: b.Add(1);

   6: a.Add(2);

   7: b.Add(2.0);

8:

   9: Console.WriteLine((a[0] == b[0]));

  10: Console.WriteLine((a[1] == b[1]));

What will be typed into the console? And WHY?

This one is fairly trivial (They seem to be alternating between difficult and easy questions). And, as requested, I formulated my answer before typing it into VS (actually, I copy'n'pasted in SnippetCompiler), but the compiler DID confirm the answer I'd already theorized.

This answer is short enough that we can use the cool "white-on-white; select to see it" trick--- However, RSS feed (and apparently the theme of this blog) seem to ignore the color style, so it's probably visible to you below..

ArrayList is deep-down, just an object[]. To store an valuetype, like an int or float, in an ArrayList, that value would first have to be boxed. Each valuetype is boxed separately, in distinct objects, even if they do happen to have the same value. When we get to the WriteLines, we are just performing (object) == (object) (actually, Object.ReferenceEquals(object1, object2); ) ReferenceEquals knows nothing about unboxing. It just asks, "Are these two references pointing to the exact same object?". For any two boxed objects, regardless of their value, the answer would be "No". Hence, both lines print "False".

(select the blank space above)

Share this post: Email it! | bookmark it! | digg it! | reddit!

DEV102's Programming Job Interview Challenge #5

James — Mon, 26 May 2008 12:57:20 GMT

DEV102 announced the correct responses to last weeks challenge today. Since I announced in my blog I got a prominent spot in their post, which is good considering I was one of about 10,000 correct answers and I gave it rather late in the process. Hopefully, I can improve on both those areas this week.

Two other things they messages showed. 1) It apparently takes a lot of hunting on this blog to figure out my name (James Curran), and 2) They like it if you hide the solution with HTML tricks. Unfortunately, while last week's answer was three simple lines of code, this week's so going to be too long to do that effectively.

Anyway, on to this week's puzzle:

You are asked to sort a collection of records. The records are stored in a file on the disk, and the size of the file is much bigger than available memory you can work with. Assume a record size is 10 bytes and file size is 1GB. you read and write data to/from disk in units of pages where each page is 1KB big. You have few (less than 10) available pages of physical memory. Assume you are given a method to compare two records.

How can you sort the records under the described conditions?

The trick here is to do lots of merge sorts, but we get to that in a minute. But first to prepare, we have to sort each page, hence, read one page, and sort it's records in memory. Exactly how it's sorted is irrelevant. A page only has 100 10-byte records so Quicksort is probably overkill -- an Insertion sort is probably best. Then that page is written back to the file in place, and we more to the next one.

When we finish sorting each page individually, then we begin the Mergesort. Read two pages and merge them by comparing the first items in each list. Once the new list fills a page, it's written to a new file. Repeat this, and eventually, you have half as many segments, each two pages long. Then, do it all over again, merging two-page segments into four page segment. The trick is, since the two-page segments are already sorted, they can be read in one page at a time, and the output can be written to disk as soon as a page is filled.

Keep repeating the process, merge four-page segment into eight-page segments, 8-pages into 16-page, etc. Eventually you will be merging two 512-page segments, and you're done.

The process own requires three pages of physical memory, and we have a bit more, so some optimizing can be done, but that's essentially it.

Share this post: Email it! | bookmark it! | digg it! | reddit!

DEV102's Programming Job Interview Challenge #4

James — Fri, 23 May 2008 13:58:31 GMT

The folks at Dev102.com are offering weekly programming challenges, where they offer questions, and let bloggers post about them. I meant to write an answer for last week, but never got around to it. Just as well -- my answer would have been wrong. SO, let's move on to this week's:

How would you implement the following method: Foo(7) == 17 and Foo(17) == 7. Any other input to that method is not defined so you can return anything you want. Just follow those rules:

Conditional statements (if, switch, …) are not allowed.

Usage of containers (hash tables, arrays, …) are not allowed.

My first thought was, since we can't use conditional statements, to use conditional expressions instead:

int foo(int n)
{
return (n==7) ? 17 : (n==17) ? 7 : n;
}

But clearly, that is just cheating. (And, besides, it turns out, it's not the best solution).

My next attempt was to use subtraction to create factors of zero.

int foo(int n)
{
return n + (10 * (n-17) * (n-6)) + (-10 * (n-16) * (n-7)) ;
}

There may be a formula in there that works, but that one doesn't, and before I found it, I stumble upon the correct solution, which was just sitting there staring me in the face:

int foo(int n)
{
return 24-n;
}

Yep, it's just that simple.

Share this post: Email it! | bookmark it! | digg it! | reddit!