Monday, July 28, 2008

Cedric's Coding Challenge

I came across a programming challenge on Cedric Beust's blog and thought I'd have a go at it. The goal is to write a counter function that counts from 1 to max but only returns numbers whose digits don't repeat. It has been solved by many users in a number of different ways using languages such as Java, C, Perl, Erlang, Javascript, C#, Groovy, Haskell, AS3, C, Fan, LUA, J, OCaml, Factor, Forth, Lisp, Ursala and Prolog. I am going to write a Unix Shell program to solve it (simply because this hasn't been tried by anyone else yet).

My Shell Solution:

#!/usr/bin/sh
#
# Counts from 1 to max and prints numbers whose digits
# don't repeat. Displays the biggest jump and the total
# count of numbers.
# Author: sharfah

max=$1
counter=1
prev=$counter
maxdiff=0
total=0

while ( [ $counter -le $max ] )
do
    echo $counter | grep '\(.\).*\1' > /dev/null
    if [ $? -ne 0 ]
    then
        echo "$counter"
        total=`expr $total + 1`
        diff=`expr $counter - $prev`
        if [ $diff -gt $maxdiff ]
        then
            maxdiff=$diff
            from=$prev
            to=$counter
        fi
        prev=$counter
    fi
    counter=`expr $counter + 1`
done
echo "Biggest jump is $maxdiff:$from->$to"
echo "Total count of numbers is $total"
Output
Run on an Intel(R) Xeon(R) CPU 2.33GHz 8 CPU, SUSE LINUX Enterprise Server 9, it produced:
sharfah@starship:~> time ./beust.sh 10000 > beust.log
   38.68s real    12.71s user    25.80s system

sharfah@starship:~> tail beust.log
9867
9870
9871
9872
9873
9874
9875
9876
Biggest jump is 105:1098->1203
Total count of numbers is 5274
When run on Solaris 10, it took 1m26.219s.

If you think you can make this go faster, let me know how in the comments section!

Friday, July 25, 2008

SSH Without a Password

I often have to login to many different servers and hate having to type my password in everytime. What's even worse, is that I can't even cron up any nice scripts which use the SSH or SCP commands, because they would just hang asking for a password!

SSH works by the exchange and verification of information, using public and private keys, to identify hosts and users. It then provides encryption of subsequent communication, also by the use of public/private key cryptography. This post will show you how you can generate a public/private key pair, install them in the correct location and SSH without being prompted for a password.

Here are the steps involved:

1. Generate the public/private keys on the Client
First you have to generate a public/private key pair on the client, which is the machine you will be ssh'ing from. To do this, use the ssh-keygen command:

sharfah@starmobile:~> ssh-keygen -t dsa
Generating public/private dsa key pair.
Enter file in which to save the key (/home/sharfah/.ssh/id_dsa):
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /home/sharfah/.ssh/id_dsa.
Your public key has been saved in /home/sharfah/.ssh/id_dsa.pub.
The key fingerprint is:
d1:98:9d:8b:7d:f6:c1:ba:1d:cc:05:ee:0b:9d:2d:17 sharfah@starmobile
Now, if you look in your ~/.ssh directory, you will see two files:
  • id_dsa (the private key)
    -----BEGIN DSA PRIVATE KEY-----
    MIIBugIBAAKBgQDBDQ/+YpRikQfo/1x1mXRy83wbLJ67hUm357Vy24ab17V1FThm
    3S14D0UoqcTN0uflDLjj3CtfGeMU85t7Kbf1DBaiQ55syPilVqzQTjpuN44A3j5K
    e1eRX6LK46lspGR/ylrVHCRxJGXZ4K1OsxPgN7RhRHlRSOs5QAGeSAsHBQIVAJU1
    lempGnCjsaPop1BiYPvRoh4NAoGAI6qObsda+DnV3qQVHmV//iThpY3Z+z81uyUF
    1qq6XRnOTIwqJuF4lm0VBb4G+8pWIn3y5Kc+051sZ+gKlHcmtLMpxh+6QVD5KoRg
    XWHW11KEQldK9TKr18Taw8AhWFvp++kOd4I2Eq287Lecr95ty8YfdXD78kS+skpa
    z7/OdhkCgYAIXN2ljv5J1XAeZDnCfOPKkxWRoJ7M4/aKqdMIHAlxp6btpCuCl2cz
    F2/e0QQHUvABWjJpFG6IUNxRxDmvOinorfXR42thOFs4pNGMUWxVS4rRTYDpRGBz
    YbuY8awyzp2rAS6uhoHbpbDjsXhAA+fOJ0Xy6mJhDsj9Hnte5OD6DAIUBD2sJqrp
    ya/kd8vZSFrepLioucY=
    -----END DSA PRIVATE KEY-----
    
  • id_dsa.pub (the public key)
    ssh-dss AAAAB3NzaC1kc3MAAACBAMEND/5ilGKRB+j/XHWZdHLzfBssnruFSbfntXLbhpvXtXUVOGbdLXgPRSipxM3S5+UMuOPcK18Z4xTzm3spt/UMFqJDnmzI+KVWrNBOOm43jgDePkp7V5FfosrjqWykZH/KWtUcJHEkZdngrU6zE+A3tGFEeVFI6zlAAZ5ICwcFAAAAFQCVNZXpqRpwo7Gj6KdQYmD70aIeDQAAAIAjqo5ux1r4OdXepBUeZX/+JOGljdn7PzW7JQXWqrpdGc5MjCom4XiWbRUFvgb7ylYiffLkpz7TnWxn6AqUdya0synGH7pBUPkqhGBdYdbXUoRCV0r1MqvXxNrDwCFYW+n76Q53gjYSrbzst5yv3m3Lxh91cPvyRL6ySlrPv852GQAAAIAIXN2ljv5J1XAeZDnCfOPKkxWRoJ7M4/aKqdMIHAlxp6btpCuCl2czF2/e0QQHUvABWjJpFG6IUNxRxDmvOinorfXR42thOFs4pNGMUWxVS4rRTYDpRGBzYbuY8awyzp2rAS6uhoHbpbDjsXhAA+fOJ0Xy6mJhDsj9Hnte5OD6DA== sharfah@starmobile
    

2. Copy the public key to the Server(s)
Next, copy your public key, id_dsa.pub, to the server's authorized_keys2 file. The server is the machine you will be ssh'ing to. You can do this by editing the authorized_keys2 file on the server directly (not recommended) or with the one line command below, which appends the public key to the end of the authorized_keys2 file:

sharfah@starmobile:~/.ssh> cat id_dsa.pub | \
 ssh sharfah@starserver "cat >> ~/.ssh/authorized_keys2"
That's it! You can now SSH onto the server without being prompted for a password!

Thursday, July 24, 2008

Caching Remote Stubs to Improve RMI

In a typical RMI-based distributed system, the client makes two remote calls to the server:
  1. To fetch a stub from the remote RMI registry, and
  2. To make a method call to the server using the stub

This is horribly inefficient. Remote method calls are slow - most tests indicate that a simple remote method call is at least 1,000 times slower than an ordinary, in-process method call (and this will only get worse as processor speed is increasing at a faster rate than network speed).

Another problem you may see, especially in a very large distributed environment, is the "too many open files" error. This occurs if your client is making lots of quick RMI calls to lots of different remote servers and there isn't enough time for the opened RMI sockets to close. (I think sockets are closed if they have been idle for at least 15 seconds). As a result, you run out of "file descriptors" and aren't able to make any more remote calls, until some have freed up. This can be a pain and you have to get your Unix SA to increase the ulimit on the client host, in order make more remote connections.

In this post, I will describe how you can use a cache to halve the number of remote calls you make. So instead of fetching a new stub each time, simply fetch the stub the first time and store it in a local stub cache (e.g. in a hash table in memory). The second time you need to make a remote call, the stub is already available locally and, hence, only one remote method invocation is necessary. BUT the stub may not be valid (e.g. if the server has been restarted). If the stub isn't valid, an instance of RemoteException will be thrown when client attempts to use it to make a remote method call. In this case, the stub should be removed from the cache and a remote lookup performed to get a fresh one.

RemoteCache.java

import java.net.MalformedURLException;
import java.rmi.NotBoundException;
import java.rmi.Remote;
import java.rmi.RemoteException;
import java.util.Hashtable;
import java.util.Map;

/**
 * A local Remote stub cache
 * Instead of fetching stubs each time over the network,
 * simply fetch them the first time and store them in a
 * local cache.
 *
 * @author Fahd Shariff
 */
public class RemoteCache
{
  private static Map<String,Remote> cache
   = new Hashtable<String, Remote>();

  /**
   * Returns a stub to the remote object.
   * This method first checks the cache
   * and if not found, looks up in the registry
   *
   * @param serverDescription the url to the server
   * @return a stub to the remote object
   * @throws MalformedURLException
   * @throws RemoteException
   * @throws NotBoundException
   */
  public static Remote get(String serverDescription)
    throws MalformedURLException,
           RemoteException,
           NotBoundException {
    Remote toReturn=cache.get(serverDescription);
    if (toReturn==null) {
      toReturn=(Remote)RMIRegistry.lookup(serverDescription);
      if (toReturn!=null) {
        cache.put(serverDescription,toReturn);
      }
    }
    return toReturn;
  }

  /**
   * Removes the specified Remote Object from the cache.
   *
   * @param serverDescription
   */
  public static void remove(String serverDescription) {
    cache.remove(serverDescription);
  }

}
Using the RemoteCache
The following code snippet shows how you use the RemoteCache to obtain a stub. There is a simple retry loop - if a RemoteException occurs, the invalid stub is removed from the cache and a fresh one is obtained.
String url = "rmi://remotehostname:2138";
while(retries<MAX_RETRIES){
  try{
    MyRemoteObject remoteObj = (MyRemoteObject)
                           RemoteCache.get(url);
    remoteObj.callMyMethod();
    break;
  }
  catch(RemoteException e){
    //stub is invalid, so remove and retry
    RemoteCache.remove(url);
    retries++;
  }
}
References:
Seamlessly Caching Stubs for Improved Performance
Expiring Data with Hashbelts

Monday, July 21, 2008

Syntax Highlighting Code in Webpages

This post is deprecated. Please read my new entry on: "Upgrading to SyntaxHighlighter 3.0"

If you're a code blogger or someone who frequently posts code snippets online, then you'll know how difficult it can be to get your code highlighted and displayed nicely on your webpage. I have tried a number of different ways, such as saving code to HTML in SciTe or using Java2HTML to produce HTML files from Java and then copying the HTML output into my webpage. These processes are time-consuming and the HTML produced is ugly so I have always been on the lookout for something that will make code posting easier.

A few months ago, I stumbled across SyntaxHighlighter and it's just what I've been looking for! All you have to do is link your webpage to some CSS and JavaScript and surround your code with a tag saying which language the code is in. It's really that simple!

This is how you can use SyntaxHighlighter to highlight your code:

1. Download SyntaxHighlighter
This is an optional step. You don't necessarily have to download it because you can just link to the free hosted version. But if you have your own server you can download the latest version of SyntaxHighlighter here and upload it.

2. Link to CSS and Javascript
Open your webpage's HTML file and add links to the SyntaxHighlighter's CSS and JavaScript files. For optimal results, place these lines at the very end of your page, just before the closing body tag.

<link type="text/css" rel="stylesheet" href="http://alexgorbatchev.com/pub/sh/current/styles/shCore.css"></link>
<link type="text/css" rel="stylesheet" href="http://alexgorbatchev.com/pub/sh/current/styles/shThemeDefault.css"></link>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shCore.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shLegacy.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushBash.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushJava.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushXml.js"></script>
<script type="text/javascript" src="http://alexgorbatchev.com/pub/sh/current/scripts/shBrushSql.js"></script>
<script type="text/javascript">
    SyntaxHighlighter.config.bloggerMode = true;
    SyntaxHighlighter.all();
</script>
It is not necessary to add the js files for all the languages - just for the ones you will be using.

3. Add Code
Now add the code you wish to highlight in your webpage, surrounded by the <pre> tag. Set the class attribute to one of the language aliases you wish to use, such as java, xml, sql, ruby etc.For example: brush:java

<pre title="Test SyntaxHighlighter" class="brush: java;">
public void printHello(){
    System.out.println("Hello World");
}
</pre>
4. View Page
View the webpage in your browser and you should see your syntax highlighted code snippet as:
public void printHello(){
    System.out.println("Hello World");
}

Configuration Options
Here are a couple of handy options. (Full list of here):

  • If you don't want to display the line numbers column, use the gutter option e.g. gutter:false.
  • If you don't want to display the top toolbar, use the toolbar:false option.
If you use an alternative to SyntaxHighlighter, share it with us in the Comments section!

Links:
SyntaxHighlighter Homepage

Thursday, July 17, 2008

Get Google's new icon in Firefox's Search Box

This is how you can update your search box in Firefox to display Google's new favicon

1. Go to the searchplugins directory, where you installed Firefox. In Windows XP, this will normally be: C:\program files\Mozilla Firefox\searchplugins

2. Open google.xml in your favourite text editor.

3. Change the Image tag to the following and save:

<Image width="16" height="16">data:image/x-icon;base64,AAABAAEAEBAAAAEAIABoBAAAFgAAACgAAAAQAAAAIAAAAAEAIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC1tbUFHBwcFQAAABoAAAAaAAAAFgAAAA8AAAAWBAAAGwIAABoAAAAXAAAAGQAAABkAAAAaAAAAGg0NDRiOjo4JJiYmDwAAABQAAAATAAAADQwCAR1YFRB4nCsqua0yLMSbLCyxYxoYfBgFAiwDAQAUAAAAEgAAABMAAAAUBwcHEhQUFA0AAAAOAAAACxMEARayLy%2FF7T9C%2F640K7FuJR1pZiMgYpczMZqeLSzBIAcFPQEBABAAAAANAAAADgAAAA4XFxcJAAAACgAAAABbKSNY%2F1ZO%2F3MdHY8AAAAAAAAAAAAAAAAAAAAAjzc2lHwdG7oDAAAVAAAACAAAAAoAAAAKFxcXBgAAAAcAAAAAVj43Tfx6df87BQFmAQIAAgAAAAQAAAAEAAAAAI0vJomvLCftCwEAHQAAAAQAAAAHAAAABxEREQQAAAAEAAAAAwYEAAi4bVm0uT8%2F4UwOC1wnBgMlFAQAEF4YGmnwQ0X8niQfxQEAAAgAAAADAAAABAAAAAQzMzMCHh4eAh8fHwMAAAAAKSglBJVbWGfQX16qxktJsLItKNTqP0X%2F5DxE8VklJTsAAAAAHx8fAh8fHwIfHx8C7%2B%2FvBO3t7QTt7e0E7e3tBOrr6wIAAAAAAAAAALWHgkH%2BVFD%2FxjI226J1dDYAAAAA7e7uBO3t7QTt7e0E7e3tBP%2F%2F%2Fwn%2F%2F%2F8K%2F%2F%2F%2FCv%2F%2F%2Fwv%2F%2F%2F8Eybi3HHw1LHeySkjC%2Fnd2%2F34iIZ1rbGkJ8fHxCv%2F%2F%2Fwr%2F%2F%2F8K%2F%2F%2F%2FCv%2F%2F%2Fwr%2F%2F%2F8R%2F%2F%2F%2FE%2F%2F%2F%2FxP%2F%2F%2F8P9OTiHtFGSNHPKS%2F%2F15KSeP7k4Evgb3DOXh4cjouJiCD9%2Ff4R%2F%2F%2F%2FE%2F%2F%2F%2FxP%2F%2F%2F8T%2F%2F%2F%2FGf%2F%2F%2Fxv%2F%2F%2F8b%2F%2F%2F%2FDvu3rnbrNCn%2Fo1NTk9%2Fr6wn%2F%2F%2F8C%2F9fXaqskJf9kTUxX7e%2FvGP%2F%2F%2Fxr%2F%2F%2F8b%2F%2F%2F%2FG%2F%2F%2F%2FyH%2F%2F%2F8k%2F%2F%2F%2FJP%2F%2F%2Fxb%2F0MyT00JA%2F5Byblv7%2F%2F8d%2F%2F%2F%2FFv7Ix3XUNjH%2FhFhVee%2Fz8x3%2F%2F%2F8j%2F%2F%2F%2FJP%2F%2F%2FyT%2F%2F%2F8o%2F%2F%2F%2FLf%2F%2F%2Fyz%2F%2F%2F8j%2F%2FDmZNphWv%2BOa2ll4urpJPHy8iLwcWDF0zEn%2B7edm1f%2F%2F%2F8m%2F%2F%2F%2FLP%2F%2F%2Fyz%2F%2F%2F8s%2F%2F%2F%2FMP%2F%2F%2FzX%2F%2F%2F80%2F%2F%2F%2FM%2F%2F%2F%2Fy77u7KoxlhZyrV%2Ff3XSc3Oy7z83%2F7w5NtymioZg5OHgOf%2F%2F%2FzP%2F%2F%2F80%2F%2F%2F%2FNf%2F%2F%2Fyv%2F%2F%2F89%2F%2F%2F%2FOv%2F%2F%2Fzr%2F%2F%2F84%2F%2F%2F%2FM%2F%2FT0m%2F3oaGk%2FbS0uv24ubPujouw2oqIoO3j40r%2F%2F%2F83%2F%2F%2F%2FPP%2F%2F%2FzP%2F%2F%2F8K%2F%2F%2F%2FMf%2F%2F%2Fz7%2F%2F%2F89%2F%2F%2F%2FPf%2F%2F%2Fz3%2F%2F%2F80%2F%2F%2F%2FMf%2F%2F%2FzH%2F%2F%2F8x%2F%2F%2F%2FMf%2F%2F%2FzX%2F%2F%2F88%2F%2F%2F%2FPv%2F%2F%2Fzf%2F%2F%2F8SAAAAAAAAAAAAAAAAI8AAACBAAAAAAAAAEAgAAAYQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA%3D%3D</Image>
4. Restart Firefox to see the curly-g icon in your search box!

Related Posts:
Google's New Favicon
How-to write your own Search Plugin for Firefox