New Things

I am trying to be more organized on my Mac. As part of this I have added some new apps: Cyber Duck (a pretty good FTP client) and Syrinx for twitter. They work, they don't get in the way and they look they are part of the system.

Regex Exploration

The Question

I was asked a question on the way out of the office at the end of the week: what is the difference between a regex match and a regex search?

It didn't seem like a difficult question but it stumped me for a little while. Both a search and a match should use a regular expression and evaluate it against a text. Perhaps a regex search traverses the input string and returns one result at a time and a regex match does.. hm.. or maybe a regex match is used for validation and a regex search is more exploratory?

The individuals asking the question were looking at the Python regex documentation (or rather AMK's very excellent regex howto ) which says "match() function only checks if the RE matches at the beginning of the string while search() will scan forward through the string for a match" which is interesting because it means that the Python regex match effectively inserts a leading anchor before attempting evaluation. Both functions return a MatchObject.

Wait a minute, you may say, you have the documentation to answer the original question! Not exactly because this question was not inspired by an abstract search for knowledge but a performance problem. The other interesting part was that Python documentation was being studied but the code is in C++ with no Python involved.

If you need a regex library for C++ then a good place to look is at the Boost home page which is “...one of the most highly regarded and expertly designed C++ library projects in the world” and has libraries for all sorts of things like graph theory, linear algebra or interprocess communication. So what does the Boost Regex library say about match and search? How about this: "the result is true only if the expression matches the whole of the input sequence. If you want to search for an expression somewhere within the sequence then use regex_search". Of note is the fact that the return type of match is boolean.

Did you get that? The Python regex match/search answer is a matter of the start position of the match and the Boost C++ answer is whether the input sequence is consumed.

Performance Evaluation

Another alternative for a regex library for the C++ developer is the Perl Compatible Regular Expression library (see the website) which offers a single execute function instead of a search or match function, with a flag parameter modifying behaviour. One suggestion I heard was that the PCRE library performs faster than the Boost library because "maybe the Boost library sucks?" but as Carl Sagan said "Extraordinary claims require extraordinary evidence" or, in other words, how do you figure?

I wrote a small app that generates multiple random strings by appending together words randomly picked from a small dictionary and then evaluates a number of regular expressions. Here's the results (slightly re-arranged):

Boost regex search, pattern: yellowgreensapphireruby.*bluered
12.50 s

Boost regex search with continuous flag, pattern: yellowgreensapphireruby.*bluered
0.07 s

Boost regex search with any flag, pattern: yellowgreensapphireruby.*bluered
12.51 s

Boost regex match, pattern: yellowgreensapphireruby.*bluered
0.05 s

PCRE regex, pattern: yellowgreensapphireruby.*bluered
1.47 s

Boost regex search, pattern: ^yellowgreensapphireruby.*bluered
6.59 s

Boost regex search with continuous flag, pattern: ^yellowgreensapphireruby.*bluered
0.07 s

Boost regex search with any flag, pattern: ^yellowgreensapphireruby.*bluered
6.57 s

Boost regex match, pattern: ^yellowgreensapphireruby.*bluered
0.05 s

PCRE regex, pattern: ^yellowgreensapphireruby.*bluered
0.02 s

Boost regex search, pattern: yellowgreensapphireruby.*bluered$
14.16 s

Boost regex search with continuous flag, pattern: yellowgreensapphireruby.*bluered$
0.07 s

Boost regex search with any flag, pattern: yellowgreensapphireruby.*bluered$
14.15 s

Boost regex match, pattern: yellowgreensapphireruby.*bluered$
0.05 s

PCRE regex, pattern: yellowgreensapphireruby.*bluered$
2.01 s

Boost regex search, pattern: ^yellowgreensapphireruby.*bluered$
6.59 s

Boost regex search with continuous flag, pattern: ^yellowgreensapphireruby.*bluered$
0.07 s

Boost regex search with any flag, pattern: ^yellowgreensapphireruby.*bluered$
6.59 s

Boost regex match, pattern: ^yellowgreensapphireruby.*bluered$
0.05 s

PCRE regex, pattern: ^yellowgreensapphireruby.*bluered$
0.02 s


Eric's Law

If you think the compiler is wrong, you are 99.999% certain to be the problem.

*This number may vary according to the platform and the compiler.

Web2py rocks more than the alternatives?

I need to find some spare time, perhaps just some of that discretionary sleeping time, to take a look at web2py. I have a small project in mind - updating my friends website to have a simple calendar and appointment system - but I have been getting slammed at the office porting an application to AIX (yes, it's still in use) and busy at home with the twins.

Linus comes to his senses

According to a link on Slashdot, Linus Torvalds has finally come to his senses and now agrees with me that Gnome is a better choice for a desktop than KDE.

Best Mac Downloads of 2008

Brad added this link for the best Mac downloads of 2008 to his del.icio.us account and it has several interesting entries including Timemachine backups over the network, Dropbox (file synchronization over the net) and XBMC (a very nice looking cross platform media center).

Writable NTFS on Mac

I use an external HD to to carry large files between home and office but the Mac (or at least Leopard) doesn't support NTFS as a writable filesystem so the arrangement is only useful when all the new data is at the office and nothing needs to be changed at home. Obviously this is not ideal.

MacFUSE allows the addition of new fileystems to the Mac including NTFS-3g which originated on Linux (I believe). Installation is quick and simple (install MacFUSE, install NTFS-3g) and after a reboot, NTFS partitions are writable without any configuration required.

A quick search turns up a number of other filesystems that could also be used through MacFUSE incuding two that will encrypt a partition and one that will allow the se of a Gmail account as storage.

Illegal Use of Linux in the Classroom

A teacher in Austin, TX did not like what she saw when she found a student in her class experimenting with a liveCD from HeliOS.. so she confiscated the CD, reprimanded the student and then wrote a letter to his after explaining he was potentially liable to a civil suit and that the kids should be using Microsoft products which they (MS) would be happy to supply for free..

Wow.

Breathlessly awaiting the followup after the teacher and the parent meet in the superintendent's office.

More Uses For An OLPC

Video player for toddler.

Meghan likes watching DVDs in the minivan and she likes banging on the keys of the OLPC so I combined the two. I used Handbrake to rip one of her favorite DVDs then loaded mplayer onto the OLPC and played back the movie from a a thumb-drive.

VLC and mplayer had similar problems with freezing before announcing the file was longer available. I tried turning off power management with no improvement. It wasn't until I disabled the radio that playback was successful .. then I found the defect mentioned earlier.

Perl is Dead! Long Live Perl!

This somewhat risible survey reveals that Perl has almost fallen out of the top 10 programming langauges in use. Given the many different ways that statistics can be mashed together and the loose method of collecting the numbers, I think it is unlikely that they can claim 3 decimal places of accuracy for any of this.

On the other hand, using activity as a barometer of interest in a langugae and perhaps what to brush up on to stay/get employed, take a look at stats on Ohloh. You can pick a basket of languages and compare check-ins and TLOC and decide that actionscript is not about to overtake C++ any time soon.

This page lets you look at a ramge of stats for a language off their long list while this will let you compare a wide range of languages with a pretty chart: take a look at this comparison showing that the volume of Python checkins is growing faster than Perl and Ruby together. Or maybe it is showing the rate of Python projects being added to Ohloh? Who can say?