Code: Impossible

Posts Tagged ‘code’

W.O.M.M. #6 – enumerateOver()

Sunday, March 7th, 2010

works-on-my-machine-starburst

I’ve been focusing more and more on my port of Ling-to-Objects, Jsoq the past few weeks. It’s still in really early stages and I’m not quite sure about it’s actual usefulness but I’m learning a lot about JavaScript and having a ton of fun along the way!

Jsoq deals with arrays a lot. About 95% of it’s use cases involve either looping through, altering, or creating arrays. Having a ton of for loops in my code just seems so… not right. For loops have always seemed dirty to me. They just aren’t elegant enough.

Here is your normal, average, everyday for loop in Javascript.


var array = "1,2,3,4,5,6,7,8,9,10".split(',');

for(var i = -1, l = array.length; ++i < l;) {
    alert(array[i]);
}

This works. It’s reliable and gets the message across. But what if we needed to loop over an array and get all the items that matched a condition? Using a for loop the code could look something like:


var array = [ 1, 2, 3, 4, 5, 1, 2, 3, 4 ];
var results = [];
var condition = function(i) { return i%2 == 0; };

for(var itt = -1, len = array.length; ++itt < len;) {
	if( condition(array[itt]) ) {
		results.push(array[itt]);
	}
}

This does work, I’ve written code like this many times before, and while technically there isn’t anything wrong with it I think there is still room for improvement.

Jsoq is going to be handling arrays all over the place so the solution to this problem needs to be simple.

Here’s what I need:

  • to loop over an entire collection and perform an action on each item.
  • If that action produces a result, the item is to be pushed into an array and returned to after the loop is done
  • .

  • Also: it needs to be readable, someone else coming along should be able to determine what this thing is doing without too much difficulty. So I had my work cut out for me.

A few hours later I had a decent function that I could use to replace a lot of the for loops I had. After some more refactoring I was able to wipe them all out and replace them with calls to enumerateOver(). Here is the latest version from source control:


function enumerateOver(collection, work) {
	var result = [], val = [];

	if (isArray(collection)) {
		try {
			for (var i = -1, l = collection.length; ++i < l;) {
				result = work(collection[i], i);
				if (typeof result !== "undefined" && result != null) {
					val.push(result);
				}
			}
		}catch (e) {
			if (e != jsoq.$break) throw(e);
		}

		if (val.length > 0) {
			return val;
		}
	}else {
		try {
			val = work(collection, 0);
		}
		catch (e) {
			if (e != jsoq.$break) throw(e);
		}
		if (typeof val !== 'undefined') {
			return val;
		}
	}
	return result == null ? [] : result;
}

And here is the code to replace the for loops above, re-written to use enumerateOver()


var results2 = enumerateOver(array, function(i, c) {
     return i%2 == 0;
});

So by implmenting this function I was able to come up with a more readable, testable and streamlined codebase. Is this suitable for everyone? Definitely not, but I did it for a few reasons:

  1. Like I mentioned before. I’ve never been at ease with for loops and being able to replace them all with calls to a single function was a huge win for me
  2. The normal use-case didn’t fit right. I needed to not only iterate over arrays but also return the results of work performed on those items. Doing this the “regular” way just wouldn’t work (see previous reason)
  3. I thought this was a fun problem to solve

If you have any feedback, good, bad, or indifferent add a comment!

JavaScript Performance Re-match

Wednesday, December 2nd, 2009

Back in 2007 Jeff Atwood ran the top 4 web browsers through the SunSpider JavaScript Benchmark and posted his findings. It’s been close to 2 years since then and I was curious to see how FireFox 3.5, IE8, IE7 (in Compatibility Mode) and Google Chrome 4.0.249.11 would fair.

So I did pretty much the same thing Jeff did and here is what I found:

JavaScript Performance Graph

* System specs: Windows 7 64-bit on a Dual-Core 2.53ghz CPU with 4gb of RAM with no browser extensions

  1. Chrome kicks some serious butt over everyone else with the entire test suite running to completion in under 1 second!!
  2. FireFox 3.5 has some serious improvements coming in at just over 1.5 seconds total, which is about 1/10 the time it took FireFox 2.0
  3. Internet Explorer 8 and Internet Explorer 7 (compat mode) are still bringing up the rear but they had a better showing than the 20+ seconds IE7 took when Jeff ran the test

Surprises?
The only thing I found surprising about the results was that if you removed the string test from both IE runs then IE8 in compatibility mode beats IE8 running normally. That doesn’t seem right to me and I seriously hope JavaScript performance is something that gets addressed in IE9. And by “addressed” I mean “fixed by replacing Trident with WebKit”.

So, what do these results actually mean? Well I guess it depends. If you use your browser to read blogs and check your gmail then you shouldn’t really care about these numbers. However, if you’re a web developer you should be paying strong attention to these numbers and how far they’ve come in just 2 years.

W.O.M.M. Project Euler #3

Wednesday, November 25th, 2009

works-on-my-machine-starburst

Here we are with another excellent installment in the “Works On My Machine” series where I post some code, some thoughts and hopefully show you something interesting/cool/new.

Today I’m going to talk briefly about Project Euler problem #3. Problem 3 asks you to find the largest prime factor of the number 600,851,475,143.

My solution is pretty simple but it works:


var getLargestPrimeFactor = function(num)
{
    var factors = [];
    for ( var f = 2; f < num; f++ )
    {
        if( num%f == 0 )
        {
            factors.push(f);
            num = num /f;
        }
    }
    factors.push(num);
    return factors[factors.length-1];
};

alert( getLargestPrimeFactor(600851475143));

Try this code!

You may have noticed that there isn't a check for a factors optimus primeness anywhere in there.

Thats because the getLargestPrimeFactor() function is dividing the number by it's smallest factor, and the smallest factor for any number is always prime so when we run out of factors we've got the largest prime factor. Yeah, that's pretth cool IMO.

I read the discussion threads for problem 3 after I solved it and I was surprised that hardly anyone removed the prime checks from their code.

So, problem 3 is in the bag and I feel pretty good about coming up with the prime check optimization (or lack thereof). A small bit of proof that I know what I'm doing. Sometimes :D

W.O.M.M. #5 Project Euler – Problem 2

Friday, September 11th, 2009

works-on-my-machine-starburst

Project Euler is an awesome website that I found out about a while back via this question on StackOverflow. Basically, it’s a website that poses a ton of programmer related challenges and it keeps track of the problems that you solve.

The problems start out relatively easy (Add all the natural numbers below one thousand that are multiples of 3 or 5.) and progress all the way to insane (Caradano Triplets and Covex Holes).

I’m on the easy side, I just started working through them tonight and thought it would be cool to post how I build the solution to each problem as I complete them.

Problem 2 is pretty easy:

“Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.”

So first things first, I’ll need to pick a language to use to solve this. I chose javascript simply because it was something I knew I could get running pretty quickly.

Next I’ll need some variables. (note: if you’re not familiar with Fibonacci numbers Wikipedia has an awesome article on them.)


var start = 1, end = 4000000, current = 1, previous = 1, sum = 0, temp = 0;

That should do. I’ve got my start variable (dropping the 0 in favor of more readable code), my end counter, and my “where-am-i” variables: current, previous, temp and my sum variable.

Obviously we’ll need some kind of loop. How about a while loop?


while( current <= end )
{

}

Cool. Now when the loop is running I'll need a way to keep track of the current value, the previous value and I need to add the current value to the sum. So....


while( current <= end )
{
    temp = current;
    current = current + previous;
    sum += current;
    previous = temp;
}

And there we hav... Oh Wait!

I overlooked a pretty important part of the problem description: "sum of all the even-valued terms"!!!

So given this new(ish) piece of info my solution end sup being:


var start = 1, end = 4000000, current = 1, previous = 1, sum = 0, temp = 0;

while( current <= end )
{
	temp = current;
	current = current + previous;

	if( current%2 == 0 )
		sum += current;

	previous = temp;
}

alert(sum);

W.O.M.M. #4 – Asp MVC Route Attributes

Monday, June 22nd, 2009

Download the source code mentioned in this blog post.

works-on-my-machine-starburst

A few weeks ago on the StackOverflow podcast, something Jeff said got me thinking. Jeff was discussing how the stackoverflow team implemented their route mappings:


Those routes are… the way we implemented them are actually like decorators. Attributes on the methods. - Jeff Atwood (stackoverflow episode #54)

This instantly piqued my interest and I completely zoned out for the rest of the podcast: caught up in working out the details of how I could do this for my own Asp.net MVC projects.

Coming up with the actual attribute code was easy; writing the code to set up all the Routes using only data defined in by the attribute was tricky.

Being new to attributes, and reflection in general, it took me a few hours until I had a very basic demo working. However, I was really starting to like where it was going.

As a side note: There are lot of “helper” classes and objects in the route attribute project (it feels cluttered to me) and the reason I did this was to make the code in AssemblyExtensions.GetRoutes() easier to read.

After a few nights of Mtn Dew and convenience-store cherry-pie I finished the rough code, tests and demo project (included in this blog post) and I was starting to realize that:

  1. Using the attributes is more declaritive and it feels cleaner
  2. Having your route information right above your actions is incredibly useful
  3. I had no more need to switch back and forth between your controller and the Global.asax.cs

How does it work?

All of the real work for the RouteAttribute is done in the AssemblyExtensions class. This class uses extension methods to augment the System.Reflection.Assembly class with two methods: GetControllers() and GetRoutes().

GetRoutes is the only method that is used by other classes, I made GetControllers public for unit testing.

GetRoutes()

GetRoutes’ first order of business is to make a list of data that it will need to build out all the routes for the assembly it was passed. After thats done GetRoutes will loop through the collected route data, build up each route and add it to the dictionary that will eventually be returned.


namespace CodeImpossible.Mvc.Routing
{
    public static class AssemblyExtensions
    {

        public static BindingFlags ActionFlags =
            BindingFlags.Instance |
            BindingFlags.Public |
            BindingFlags.DeclaredOnly;

        public static IList<ControllerMetaData> GetControllers(this Assembly assembly)
        {
            var controllers = assembly.GetTypes().ToList().FindAll(type =>
            {
                var isValidController = type.IsClass &&
                    type.IsPublic &&
                    type.IsSubclassOf<Controller>();

                var hasValidActions = type.GetMethods(ActionFlags).ToList().Any(m =>
                {
                    var valid = false;
                    if (m.ReturnParameter != null && m.ReturnParameter.ParameterType == typeof(ActionResult))
                    {
                        valid = m.GetAttributesOfType<RouteAttribute>().Count > 0;
                    }

                    return valid;
                });

                return isValidController && hasValidActions;
            }).Select<Type, ControllerMetaData>((t) => new ControllerMetaData(t)).ToList();

            return controllers;
        }

        public static IDictionary<string, Route> GetRoutes(this Assembly assembly)
        {
            var Routes      = new Dictionary<string, Route>();

            var data = (from c in assembly.GetControllers()
                        from a in c.GetActions()
                        from r in a.Data
                        select new
                        {
                            ControllerName = c.Name,
                            ActionName = a.Name,
                            RouteData = r,
                            RouteParams = a.Params
                        }).ToList();

            foreach (var r in data)
            {
                var route               = new Route(r.RouteData.RoutePath, new MvcRouteHandler());
                route.Constraints       = new RouteValueDictionary();
                route.Defaults          = new RouteValueDictionary(new {
                    controller = r.ControllerName,
                    action = r.ActionName
                });

                if (r.RouteData.RequireRouteParams && r.RouteParams.Count() == 0)
                {
                    throw new MissingRouteParameterException("Unknown", r.RouteData.RoutePath);
                }

                var missingParams = new List<ParameterMetaData>();

                if (r.RouteData.RequireRouteParams)
                {
                    missingParams = (from p in r.RouteParams
                                     where r.RouteData.RoutePath.IndexOf("{" + p.Name + "}") == -1
                                     select p).ToList();
                }

                if (missingParams.Count > 0)
                {
                    var param = missingParams.First();
                    throw new MissingRouteParameterException(param.Name, r.RouteData.RoutePath);
                }

                foreach (var param in r.RouteParams)
                {
                    if (param.Data != null)
                    {
                        if (param.Data.DefaultValue != null)
                        {
                            route.Defaults.Add(param.Name, param.Data.DefaultValue);
                        }

                        if (param.Data.Constraint != null)
                        {
                            route.Constraints.Add(param.Name, param.Data.Constraint);
                        }
                    }
                }

                Routes.Add(r.RouteData.Name ?? r.RouteData.RoutePath, route);
            }

            return Routes;
        }
    }
}

Getting the Routes into the RouteTable

Slapping route attributes onto your classes and methods is all well and good but it doesn’t mean anything unless we can get those routes into the RouteTable object easliy. Originally I had the code to add the routes looking something like


var routes = Assembly.GetCurrentExecutingAssembly().GetRoutes();

routes.ForEach(r => RouteTable.Add(r));

This, although pretty easy, wasn’t as readible as I wanted. So I added some extension methods to the RouteTable class:


RouteTable.Routes.IncludeRoutesFromAssembly();

I think both of these are much clearer than doing:


RouteTable.Routes.MapRoute("Root",
    "",
    new { controller = "Test", action = "GetItem", id = 1 });

RouteTable.Routes.MapRoute("Search",
    "Search/{id}",
    new { controller = "Test", action = "Search", id = 1 });
//.. SNIP ...

Using the RouteAttribute and RouteParamAttribute

In the controller “TestController” below there are three actions: Index, FindByText, and GetItem. Using the RouteAttribute and RouteParamAttribute makes it pretty clear that the routes for FindByText and GetItem are the same but use different RouteContraints.

So a request for /Test/Search/Hello will go to FindByText while /Test/Search/1 will go to GetItem. Also notice how GetItem has a default value of 2 for the id argument.


public class TestController : Controller
{

    [Route(RoutePath = "Test")]
    public ActionResult Index()
    {

        return View();
    }

    [Route(RoutePath = "Test/Search/{query}")]
    public ActionResult FindByText(
        [RouteParam(Constraint="[a-zA-Z]{1,}")]
        string query)
    {

        return View();
    }

    [Route(RoutePath = "Test/Search/{id}")]
    public virtual ActionResult GetItem(
        [RouteParam(Constraint=@"\d{1,}", DefaultValue=2)]
        int id)
    {

        return View();
    }
}

There is support for binding multiple routes to the same action; just add another Route attribute:


[Route("Products/Search/{id}")]
[Route("Products/{id}")]
public ActionResult GetProductById(int id)
{
    return View();
}

Downsides or things I haven’t gotten to yet

Just some gotchas that I think people might raise issue with.

All of your controllers must inherit from the System.Web.Mvc.Controller class
This isn’t really a big deal because if you are using Asp.net MVC then you really should inherit from the Controller class, but for those of you using FubuMVC or another MVC framework this should be easy to change.

Attributes can be ugly
I know a few people out there are against attributes but I think that this is a more than acceptable use because it made the code much easier to understand.

Reflection can be slow
Honestly, when I first started working on this demo I was sort of turned off by the use of Reflection myself. After weighing the possible performance loss against the gains in both readability and maintenance I decided this was definitely worth it. I haven’t performance tested this code so, as always YMMV.

As always, if I screwed up or there is a better way to do this, please let me know in the comments.

Download the source code mentioned in this blog post.


Page optimized by WP Minify WordPress Plugin