When no one is looking...

Caching Calculations in Javascript

2011-09-09T15:49:00.000-04:00

I've been asked to demonstrate a solution to a small problem using JavaScript. The problem is basically one of scope and calculation caching, and is defined thusly:

I have two functions that perform calculations. Function A is always called before function B, and function B always calls function A. How can I make this more efficient?

Of course there's probably a way to solve this problem through refactoring the code, but let's pretend there isn't in our scenario. Javascript is a prototypal language, not a class based one. Fortunately for us, this means we can create a function and then attach properties to it that make it behave somewhere between a true function and an object. On to the code...

Internally Managed Data Caching
If a function performs heavy calculations, you really don't want it to perform the calculations over and over again, especially not while the parameters are the same. The following function employs caching to make its execution more efficient:

function A()

{

if (A.cache === false)

{
// Our super complex calculation

A.cache = 1 + 2 + 3 + 4;

}

return A.cache;

}

// Define a static variable that is local to the A function that
// will store the result of the super complex calculations.

A.cache = false;

In the above example, we've made a function and a property attached to that function that is used to store the result of a calculation. The first time the function is executed, the cache container "A.cache" property is set to 'false' which triggers the calculation to be performed. But notice that instead of simply returning the value of the calculation, we cache it. Since the function is always returning the cached calculation, it can be called as many times as you want, but it will only perform the calculation once. So with the problem stated above, you could call function A, then function B knowing full well that function A will get called a total of two times, but will only do any actual work once.

Externally Managed Data Caching

How can you force the function to refresh its cache if there's no way to tell it that the environment changed in such a way that the result of the calculation could be different? What you really need is a mechanism for informing the function that its cache is dirty and needs to be refreshed. This could technically be done by setting A.cache = false, but here's a slightly more robust example.

function A()
{

if (A.cache === false || A.cacheIsDirty !== false)

{

// Our super complex calculation

A.cache = 1 + 2 + 3 + 4;

A.cacheIsDirty = false;

}

return A.cache;

}

// Define a static variable that is local to the A function that

// will store the result of the super complex calculations.

A.cache = false;

// Define a static variable that is local to the A function that

// will be used to inform function A that its cache is not to be

// trusted.

A.cacheIsDirty = true;

And done! We've now got a way for outside code to warn a function that its internal cache may no longer be safe to use. A simple use case for this might be a form wherein a user can input multiple parameters and then view the calculations. Well, if the user doesn't modify any of the parameters that function A might need to look at, then it should be allowed to return the cached result. But if the user does change a parameter that function A cares about, then the piece of code that was listening for that change can call A.cacheIsDirty = true; to make sure that function A will discard its cache and run its calculations again.

Getting Back To Nature, On Our Computers

2011-09-08T22:27:00.001-04:00

It's my humble opinion that Apple has been the clear victor in the battle to create an easy to use computer interface, however there are still elements that just don't make sense to everyone. Is it even possible to make a user interface that everyone can easily understand? Given that "It is impossible to make anything foolproof, because fools are so ingenious.", I doubt it. But I believe you're only saying it's impossible because no one has ever done it before. (major geek points to anyone who gets both references)

Let me start by admitting that I watched Discovery's "Curiosity: Did God Create The Universe" with Stephen Hawking last night. One of the things that Stephen drives home is that the laws of nature, or physics, are immutable and cannot be broken. They are also universally understood and obeyed. Keep that in your back pocket. I'm coming back to it.

Earlier today I logged into an OS X computer to assist a customer of mine and noticed something brief, but odd. The global menu bar at the top of the screen wasn't visible, yet its shadow was. Clearly this breaks a few fundamental laws of nature and would never happen in the physical world. So about 0.75 seconds later, I found that I had resolved that issue by tying Professor Hawking's cautionary notes about the laws of nature into a desktop environment. It was a desktop environment that embraced the laws of nature instead of poorly mimicking them or outright ignoring them.

The easiest way to define the desktop environment that I envisioned is to remind my imaginary development team that two objects having mass cannot occupy the same space at the same time. That and to force them into believing that computer graphics have mass. This is a law that even my fish understands; he knows that he can't go through the rocks at the bottom of his tank nor the glass that surrounds him. He might not understand exactly why, but it makes sense to him that he cannot pass through those things. He also understands how to move water around him, not through him, so that he can swim. Try to apply this rule to any part of the current desktop/windowing systems out there and I think you'll find that they break that law in almost every instance. Icons overlap each other on the desktop and neither one is clearly on top of another; two inactive windows are positioned behind a third window in such a way that it is unclear which one is in the middle and which one is behind the other two. Why have we complacantly put up with this for so long, realizing that our interactions with computers have no analog in the physical world.

The Missing Z Axis
Every windowing system attempts a half-hearted implementation of the z axis, as do some applications such as the browser your using right now (think z-index). The problem with the current system is that it doesn't provide a truly 3 dimensional experience for the user. Instead, it allows objects to be stacked in a particular order in 2 dimensions. But what if we introduced three extra attributes to those objects?

Space: Everything we interact with is surrounded by space. We reach for things through space, we pry things apart by inserting a tool into a space too small for our fingers, we expect and understand space.
Perspective Scaling: When things get further away from us, they appear to shrink. When they are getting closer, they appear to grow. Virtual objects should therefore also shrink and grow as is appropriate for their distance from us.
Visual Clarity: This is one area where modern windowing systems are getting close, but still don't quite have it down. The blur effect is somewhat annoying in its current state, but that's because most implementations are boolean; blur on vs. blur off. But if we have 20/20 vision and something is 21 feet away from us, it starts to appear a little fuzzy. Objects that are 50 feet away are increasingly fuzzy. So let's take the blur effect and make it a little more intelligent. For a spiffier desktop environment, we could even introduce a lightweight particle system to simulate the particles that make things appear lighter (assuming a sunny day) the more distant they are.

But 3D Desktops Suck

Yep, they do and yes I realize that I'm describing one. I strongly believe the reason that they suck is the same reason 2D desktops suck: They are attempting to look interesting but don't actually remind us of anything in the physical world. Developers and engineers aren't to blame here. We simply don't have a holodeck yet, and until we do 3D is going to be a pretty tough sell for our senses.

Okay, so why am I proposing a 3D desktop if I think they suck? The answer is simply that I don't want a 3D desktop. What I want is an experience akin to a surgeon using a camera inside a patient to see where to cut. In other words, I want a 2 dimensional interface to a place that my mind can believe is 3 dimensional. No, it's not ideal, but it's a better use of current technology than what we're doing with it right now.

Interacting With a 3D World with a 2D Interface
We already know how to get from point A to point B on a cartesian plane; you just move your mouse and your cursor moves to that point. But how can we easily move along the z axis without special hardware? I'm sure there are plenty of ideas out there, but one of them might finally be a good use for "hot corners", or maybe even hot 'edges'. Say you want to zoom out to a window behind you, maybe you move the mouse to the bottom of the screen or to one of the bottom corners. Zooming in could be done by either moving your mouse to the top of the screen, or by simply clicking on a window that is in the distance. To make zooming a little more friendly, we can take a page from Apple's menu scrolling engine wherein scrolling starts slowly and immediately when the mouse enters the appropriate area of the menu, then increases in speed as the mouse is held in place.

Back to the Shadows
Remember way back at the beginning of this post how the whole idea started because I saw a shadow with no object? Let's wrap this up by getting back to that. Current window shadowing techniques generally only have 3 possible states: A bold shadow for the active window, a not-so-bold shadow for all of the inactive windows, and no shadow at all for those utility windows. You may have noticed as you peel your eyes away from the computer screen that this is yet another area where there is no real world analog. But hey, we've just described a 3D space for those windows which means we should be able to fix this problem as well.

The existence of a shadow implies three things; a light source, an object with mass in the foreground, and an object with mass in the background. Current shadowing techniques have, or at least imply, all three of these things. But where is that light source exactly? It's almost directly behind our heads. Every real-world scenario that I can come up with where any light source would be behind my head involves a face-plant, which I'm not terribly fond of.

We've got a 3D space for windows and their shadows now, so let's move that light source to someplace a little more natural, someplace a little higher above us and maybe off to one side a bit. Heck, it could even move around a bit to correspond with the time of day. We can then project the shadows on the floor of our 3D space. In this instance, the window that is in focus wouldn't have a shadow at all while windows in the background would. Think of a scenario where you're reading a newspaper while waiting for the bus. The newspaper has no shadow that you care to acknowledge because its shadow is being cast outside of your field of vision. However, if you peer around your newspaper for just a moment and notice another person standing just like you, reading the same paper that you're reading, you can see the shadow that their paper casts on the ground or perhaps on the other person's legs because both the paper and its shadow fit within your field of vision.

So let's move the shadows down to the ground where they belong, and lets let the things we're looking at feel like they are really right in front of us while everything else is far away. For a little per-widow depth, we could add subtle widget shadows. For example, I can see a shadow being cast in Safari right now that is meant to make the tabs appear to be beneath the address bar and slightly embedded. Let's keep that going, but make it adhere to the position of the light source so it makes sense.

Fin
So there we have it. A poorly described, but fairly thorough thought experiment into a 3D desktop with a 2D interface. You know what would really make this idea cool? Using it on a tablet that supports multitouch. I'd imagine you could zip around quite nicely within 3 dimensions on one of those things. If anyone decides to implement such a concept, I'd love to know about it and help test it. I'd also gladly accept royalties or shares in your wildly successful company. ;-)

Big-O Example

2007-01-20T13:55:00.000-05:00

If you're like me you've seen the term "Big-O" but didn't quite grasp it the first time. You've also probably looked all over the Internet trying to make heads or tails of this seemingly complex term. If you weren't confused by the first definition that you found, try checking out the Wikipedia entry - that should get you nice and confused.

The purpose of Big-O notation is to provide a language that describes how efficient an algorithm is (or is not) without taking into consideration the exact speed of a particular computer that it might be running on. But how to calculate it?

Eventually I found a short mention of this topic in "Objects, Abstraction, Data Structures and Design using Java Version 5.0" by Elliot B. Koffman and Paul A.T. Wolfgang that seemed to make sense to me, and hopefully will click for you as well. The following was taken from pg113 Example 2.19:

Given T(n) = n² + 5n + 25, we want to show that this is indeed O(n²). Thus we want to show that there are constants n₀ and c such that for all n > n₀, cn² > n² + 5n + 25. To solve this we need to find a point where
cn² = n² + 5n + 25
If we let n be n₀ and solve for c, we get
c = 1 + 5/n₀ + 25/n₀²
For an n₀ of 5, this gives us a c of 3. So 3n² > n² + 5n + 25 for all n greater than 5