Sights and sounds, in and around Vasai

This is what population growth, and the resulting competition, can do.

~

English is a foreign language to most Indians, and yet it seems to be preferred for dispensing information. It's not uncommon to see a gaffe every now and then.

Do you see me?

Updating my profile picture isn't an easy task anymore. There are many sites where I own a profile, and I have to look just right on each one of them.

As of now, these are the places you can see my shiny new profile picture:

• http://sandesh247.com


• http://www.google.com/profiles/sandesh247


• http://www.linkedin.com/in/sandesh247


• http://identi.ca/sandesh247/


• http://www.facebook.com/profile.php?id=543752933


• http://www.goodreads.com/sandesh247


• http://www.last.fm/user/sandesh247


• http://friendfeed.com/sandesh247


• http://www.orkut.co.in/Main#FullProfile.aspx?uid=6964782234814101571


• http://www.gravatar.com/avatar/f37a7393ce728b072aca55535f759e9f (all gravatar enabled websites)


• http://twitter.com/sandesh247

 
Phew. I hope that covers them all.

P.S. Last.fm and Twitter aren't playing nice right now. I guess I have to keep trying.

Tuning LINQ performance with Mr. P and Mr. S

I thought I'd take a second look at the Mr. P and Mr. S problem, which I'd posted more than a couple of years ago. The last time I tried it, I wasn't successful. I had a strategy to solve it, but somehow I just couldn't translate it into code.

I've been programming a lot with C# lately, and decided to use LINQ to solve the puzzle. Although not very concise, compared to the Python and Haskell solutions out there, it does print out the right answer. After you've tried to solve it yourself, you can have a look at my solution here.

There's something special about LINQ queries. All LINQ queries are deferred, which means that they aren't executed until they are accessed. Also, they are re-executed when the execution context changes. Say we have a list of numbers, and a query on it like so :

var numbers = new List<int>();
var query =
  from i in numbers
  select i;

The query hasn't been executed yet. We add a few numbers to the list, and compare the counts of the list and the query.

numbers.Add(0);
numbers.Add(1);
numbers.Add(2);

// 3 elements in list, 3 in the query
Assert.AreEqual(numbers.Count, localDeferredQuery.Count());

The test passes. LINQ queries are "live", very much like functions. Usually, this is a good thing, as no operation is performed until it is actually needed. However, there are exceptions. For example, I used these three ranges -

public static IEnumerable OddRange(int stop) // returns odd numbers upto "stop"
{
  for (int i = 1; i < stop; i+=2) yield return i;
}
 
public static IEnumerable EvenRange(int stop) // returns even numbers upto "stop"
{
  for (int i = 2; i < stop; i+=2) yield return i;
}
 
public static IEnumerable Range(int stop) // returns all numbers upto "stop"
{
  for (int i = 0; i < stop; ++i) yield return i;
}

To define the Deferred() and Immediate() functions below:

public void Deferred()
{
  var all = Range(limit);
  var even = from e in EvenRange(limit) where all.Contains(e) select e;
  var odd = from o in OddRange(limit) where !even.Contains(o) select o;
  
  var query = from q in odd select q;
 
  foreach(var i in query) { var j = i+1; }
}
 
public void Immediate()
{
  var all = Range(limit);
  var even = (from e in EvenRange(limit) where all.Contains(e) select e) .ToArray();
  var odd = (from o in OddRange(limit) where !even.Contains(o) select o) .ToArray();
  
  var query = (from q in odd select q).ToArray();
 
  foreach(var i in query) { var j = i+1; }
}

all, even and odd are three sub queries, each using the previous one. The Immediate() function only differs from Differed() due it's forced execution of the subqueries with ToArray(). However, Immediate() performs much better than Deferred(). I knew LINQ operators are actually euphemism for functions, and that iterator blocks are actually exploded by the compiler into a lot of code. But Deferred() was waaaayy slower than Immediate(), and the time taken would increase exponentially with the value of limit. This couldn't be just some extra code.

I posted a query on stackoverflow, and it did not disappoint. It is quite obvious in hindsight. This statement -

var odd = (from o in OddRange(limit) where !even.Contains(o) select o).ToArray();

in deferred mode, turns out to be pretty expensive indeed. It contains a call to even.Contains(o). While in the immediate mode this is an O(n) operation, in deferred mode, the sequence of calls looks like this -

odd --> even -+-> EvenRange()
              |
              +-> all --> Range()

A simple O(n) operation is now O(n³). We can do better than O(n), however, by using a Hashset.

var evenSet = new HashSet(even);
var odd = from o in OddRange(limit) 
          where !evenSet.Contains(o) select o; // Contains() is now O(1)

It doesn't get much better than this.

Microblogging on identi.ca

If my journal template hasn't changed since this post, you should see a µBlog roll on the sidebar. If you've clicked on any of the links, you'd now that those notices (or 'dents') come from identi.ca.

identi.ca is a website very similar to twitter, only better. It's built with the open source laconi.ca project, and has tags and groups too. The killer feature for me is IM support, along with a decent command list. All you have to do is add their bot on google talk, and you can send/receive messages in real -time.

the commands currently supported by the IM bot are:

on - turn on notifications
off - turn off notifications
help - show this help
follow <nickname> - subscribe to user
leave <nickname> - unsubscribe from user
d <nickname> <text> - direct message to user
get <nickname> - get last notice from user
whois <nickname> - get profile info on user
fav <nickname> - add user's last notice as a 'fave'
stats - get your stats
stop - same as 'off'
quit - same as 'off'
sub <nickname> - same as 'follow'
unsub <nickname> - same as 'leave'
last <nickname> - same as 'get'

identi.ca also supports forwarding dents to twitter, so you wont completely alienate your fans on twitter. However, identi.ca doesn't pull tweets, so you wont see any @replies from twitter on identi.ca. At least until you can convince your friends to move from twitter.

identi.ca belongs to a larger ecosystem of OpenMicroBlogging software, which have adapted a common standard so that messages between them may be shared. If you use a software that supports OMB, you wont alienate someone just because they happen to like something different (in contrast, the twitter community belongs only on twitter).

Another popular µBlogging site is jaiku, which will support OMB, and go open source soon. If identi.ca is not your cup of tea, or if you happen to like everything Google, jaiku may be for you.

Good intentions

There's a video about Intentional Software over at MSDN, and it's definitely one of the more brilliant things to have come out in a while. Most of the times, people who best know how a software should function, are not the ones writing it. That is how people who write software for money, make money - they pitch their ability to convert business requirements into "executables". With intentional software, everyone does what they do best.

All the places I've worked at had tools that made it easy for domain experts to give their inputs, since turnaround time is extremely important for business. Even for personal projects, I've toyed with modeling tools and OR mapping frameworks to make my model somewhat independent of the implementation. Never have I seen a tool so comprehensive, though - watching an electrical circuit being modeled as a diagram, along with the impedance and voltages was amazing. This wasn't just the model being abstracted - it was the whole program, editable as text, diagrams or XML, and easily converted into executable code.

Martin Fowler has quite a lot to say about it too, there isn't much I can add to it. Open source junkies like me will look for an open source alternative for this, and will find JetBrains' Meta Programming System. The next few days will be exciting, as I try to evaluate this beast and see whether it fits into any of my current work.