Matthew Hutchinson

What is ‘Computational Complexity’ ?

Basically a theory describing the scalability of algorithms. “As the size of the input to an algorithm increases, how do the running time and memory requirements of the algorithm change?” Wikipedia has a more complete description. Complexity can be considered in terms of;

• Time Complexity – the number of steps that it takes to solve an instance of the problem as a function of the size of the input, using the most efficient algorithm.
• Space Complexity – the amount of space, or memory required by the algorithm.

If you consider an array with n elements, and in solving a problem on this array, it takes n times n (or n²) steps. You could say the algorithm used had a complexity of n². Now with different programming languages there may be additional steps in the algorithm necessary to solve the problem. To describe a general level of complexity across any language, the Big Oh Notation is used. So the time-complexity for this algorithm would be Θ(n²)

‘Θ’ basically indicates that we are ignoring any language dependent factors, allowing complexity to be expressed purely in terms of the size of the input.

An Example

if you take a simple problem like, finding the ‘mode’ average on an array. I.e. the most frequently occurring element in a sequence (lets say of numbers) – You could do this an number of ways. Here is a brute force attempt (in Ruby).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def calculate_mode(nums)
  hi_count = 0
  mode = nums[0]
  nums.each do | search_for |
    count = 0
    nums.each do |num|
      if search_for == num
        count += 1
      end
    end
    if count > hi_count
      hi_count = count
      mode = search_for
    end
  end
end

It should be obvious that this algorithm has a complexity of Θ(n²) – since every element of the array must be searched by each element to find the highest count value (and hence the mode).

Could it be done any faster? If the array of elements was sorted (ordered numerically) – the mode could be found by finding the longest continuing sequence in the array, that should only take n iterations. Employing a quick sort algorithm first; which can sort (on average) with Θ(n log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def quicksort(a)
  return a if a.size <= 1
  pivot = a[0]
  quicksort(a.select {|i| i < pivot }) +
      a.select {|i| i == pivot } + 
      quicksort(a.select {|i| i > pivot })  
end

def calculate_mode_fast(nums, time_start)
  # sort array first
  sorted_nums = quicksort(nums)

  hi_count = 0
  mode = nums[0]  
  count = 1
  idx = 1

  sorted_nums.each do | search_for |
   if search_for == sorted_nums[idx]
     count += 1
     if count > hi_count
       hi_count = count
       mode = search_for
     end
   else
     count = 1
   end
   idx += 1 if idx < sorted_nums.length
  end
end

So we could say that this approach has (on average) a complexity of Θ(n+(n log n)) which is significantly less that Θ(n²)

I’ve posted this code listing which implements both algorithms running to compute the modal average on identical arrays of random integers. You can vary n (the number of elements) to see how each method performs. From the results (below) its clear that the 2nd algorithm is more time-efficient in this case.

calculate_mode
====================
mode => 3 (it occurs 44 times)
array length was 1000
num loops was 1000000
completed in 0.71737

calculate_mode_fast
=========================
mode => 3 (it occurs 44 times)
array length was 1000
num loops was 1040
completed in 0.011247

I have managed to turn my work at gravatar caching into a little plugin for Mephisto. Its available to install via subversion like so:

ruby script/plugin install http://svn.hiddenloop.com/public/plugins/mephisto_gravatar_cache

You can browse the source code and the README file, which describes how to install and configure it. Although the plugin will work out of the box with it’s default settings.

Given the nature (and newness) of the Gravatar service, its (highly) likely that they may change their usage instructions again. I originally came across some gravatar caching code from a Daniel Haran – it worked with the old gravatar API, which is no longer available.

This new plugin works in a similar way (wget’ing the images) – however – to check an email has a gravatar at all, a request is made to gravatar.com (with a default no-gravatar image). If a 301 (redirect) is found on this request – it is assumed that the user has no image to fetch. The plugin also includes a rake task (for use in a cron job), image expiry time and other configurable class settings for caching options.

While this plugin is a Mephisto Gravatar Cache plugin – with a little modification it could work for any Rails application. The rake task ‘cache_gravatars’ would need to be modified, and a call to cache_gravatar made on any email addresses.

I have tried to comment my code as best as possible, to encourage further development. Please report all bugs and/or submit patches to me at this post. Your comments, criticisms and thoughts are welcome.

• What is Gravatar? – find out here
• More Mephisto Plugins
• Original Gravatar Caching work by Daniel Haran – the older gravatar API

—Update – Curtis at millarian.com has recently played around with this plugin and fixed some bugs. I’ll be sure to update the repository soon and add some more tests. This was my first plugin release and something I coded rather hastily.

Maybe I am a bit late to the party, but OpenID seems to have made a surging comeback in the last month or so, not least in the Rails community. Its something I am looking to implement on a few projects of my own, and luckily (with Rails) I won’t have to re-invent the wheel. Here are some useful links on the matter:

• OpenID Rails Plugin – using the Ruby-OpenID gem
• Mephisto and OpenID support
• Collection of links at Ruby Inside
• PeepCode – will have a screencast on the matter soon.

Last year during @media2006, Mr. DHH questioned whether login/signup (and managing multiple usernames/passwords across the web) was such a big problem after all. With modern browsers capable of remembering passwords and client side tools to take care of the matter. He does seem to have changed his tune on the matter now. You can see how 37 Signal’s new HighRise application handles it (with a small unobtrusive link in the login box corner).

For some more discussion on the good/bad aspects of OpenID, we have:

• Simon Willison, explains OpenID – Video Interview at Vitamin
• Positive thoughts at ‘We Break Stuff’
• How to best merge OpenID with regular username/password authentication
• Matt Pelletier – OpenID, Rails, and Identity 2.0 – summary of RailsConf talk

One awkward part of OpenID at the moment, is the use of a URL to login with; to the average user this has to be a bit confusing. With that, and few major sites offering OpenID support, it may be a while before it takes off across the web.

I think IRC is a vastly under-rated tool. It is somthing I used a lot in the mid/late 90’s and in my first few years at University on the old DEC Workstations. Back before Skype and before the web was getting ready for its next version number, IRC was the best way to chat online.

For a long time I forgot about IRC, until it became obvious that (with a channel bot) it can be useful for all sorts of things, beyond just regular chat. With a bot parsing and watching RSS feeds, your channel can include notifications for just about anything you want, SVN commits, Trac tickets, even exceptions thrown from your code (you’ll have to build a feed for that yourself).

So I looked into setting up a channel bot myself (something I haven’t done before). Looking around I played with infobot (Perl) and eggdrop (C/TCL) – before (rather predicatably) going with RBot (Ruby) I had a little hassle getting the bot to work on Debian. It requires the Berkley Database (and Ruby’s binding to it).

Of course the BDB that comes with GNU/Debian Linux (apt-get) is out of date, and you will need to compile the most recent version instead. If you already installed Berkeley DB on your Debian Box, uninstall it to prevent conflicts. Then get it from here (./configure, make, make install). Choose BDB 4.4 or lower since the Ruby BDB bindings are not compatible with the new 4.5) – I couldn’t find all of those caveats documented together in the one place, so that may be of use to someone.

Next grab Ruby’s BDB bindings – and finally make sure you can call the bdb library in irb. If you can do,

1
2
3

:~$ irb
>> require 'bdb'
=> true

- without throwing an error, then download and install RBot. Its fairly simple to setup and there are a large number of plugins to play around with. Rbot will install a some of these by default (including rss.rb) and you can extend them, or write your own in the bot’s local plugin directory.

To persist the bot, use a simple ‘keep alive’ script;

#!/bin/bash

proc=`ps -fu $LOGNAME | grep name_of_your_bot | grep -v grep | wc -l`
if test $proc -eq 0
then
 nohup rbot /home/username/.name_of_your_bot > /dev/null &
fi

And put it in a cron job to check its running (e.g. every 55 minutes);

# make sure rbot is running all the time
*/55 * * * * /home/username/rbotchk.sh

My work in progress Rbot (kafka) is sitting in #komura on irc.perl.org – expect it to be broken most of time as I add a few plugins and try stuff out.

While there are hundreds of IRC clients available, I have stuck to using IRSSI (a terminal client) its old-fashioned (I know), but simple and I can access it from anywhere (keeping it running on a screen). I’d also recommend Colloquy a decent graphical client for OSX.

Some years ago I made use of a Windows based (and free) packet analsyer tool Packetyzer, from Network Chemistry) It did the job and proved to be invaluable for testing and building different packet headers – for projects just like this – but as a fan of Ruby, I had to see if this could be done in the language of my choice.

Just a few months ago I began doing a little research into GPRS packets for a potential ‘location-based’ mobile web service. To do this I was hoping to use Ruby and through pCap I was able to.

To start monitoring packets, you’ll first have to install libpcap – a low level packet capture library (authored in C) – from LBNL’s Network Research Group You can follow this short tutorial to do this. The libpcap library grabs packets from any network adaptor on your system, giving you the raw data to work with. Doing this is immensely powerful, you could write listeners to monitor anything from email traffic to instant message conversations (provided the traffic isn’t encrypted of course).

Next, to allow us to write Ruby code to interface with this library, you’ll need to install pcaplet – This Ruby binding library makes writing capture programs easy. Its as simple as using require ‘pcaplet’ at the head of your Ruby code and your off.

I was able to use these libraries to examine TCP/IP packets from my mobile device (sent via GPRS over TCP/IP) to my server. The following Ruby script extracted the information I was interested in (data addressed to HTTP) using a regular expression;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#!/usr/bin/env ruby

require 'pcaplet'

# create a sniffer that grabs the first 1500 bytes of each packet
$network = Pcaplet.new('-s 1500')

# create a filter that uses our query string and the sniffer we just made
$filter = Pcap::Filter.new('tcp and dst port 80', $network.capture)
$network.add_filter($filter)

# the packet sniffer loop
for p in $network
  # if the packet matches the filter and the regexp...
  if $filter =~ p and p.tcp_data =~ /GET(.*)HTTP.*/
    # print all packet data for each packet that matches
     puts p.tcp_data
  end
end

Then save this and run the script with something like;

ruby packet_filter_regex.rb 
# you may need to run this as root if you have permission problems

The add_filter function, with ‘tcp and dst port 80’ – means all tcp traffic directed at port 80 on the adapter, this resource details all the tcpdump syntax for different filter designs. This code will be a useful tool for me in another project -looking at streaming video and audio.

Another article at Linux.Ars roughly describes what is behind this and shows some more example Ruby scripts for packet monitoring (including an aim chat sniffer). There are also a few more example filters on the pcaplet site.

Apr-07 UPDATE – Sylvain Sarmejeanne has just released Scruby a Ruby application that works on UNIX providing a shell where you can perform packet creation, sending and sniffing functions in a Ruby-esque fashion. It requires libpcap and uses PCapRub (a mininal PCAP wrapper) rather than using PCAP directly. The package is well documented and has an irb-like interface, accepting command line input for debugging.