Algorithmic ownage

I felt good when I simplified one of my algorithms and sped it up 10 times. I felt so good that I even wrote an entire blog post about it patting myself on the back. Then last week I got an email from Kevin of Keming Labs suggesting a few alternatives.

First of all, his solutions looked much cleaner than mine. Then over the weekend I was able to incorporate his 3 algorithms into my program. I ran a few benchmarks and here are the average of 2 tests using a dataset of 28,760 items.

My algorithm. Elapsed time: 68372.026532 msecs.
Kevin’s solution #1. Elapsed time: 156.940976 msecs.
Kevin’s solution #2. Elapsed time: 60.165483 msecs.
Kevin’s solution #3. Elapsed time: 296.162042 msecs.

Total ownage.

That’s what I like about sharing my work; once in a blue moon, a random person drops by and generously show me how I can improve a solution 1,000 times! Now the ball is in my hands to understand what he has done and improve myself.

Collaborating and learning, that’s why I open source.

Update: I’ve done some more digging and it seems that one of the reasons for the drastic improvement in performance is due to the use of transients in the built-in functions. Lesson of the day, leverage the language’s inherent optimization by staying with core data structures and functions as much as possible.

Eureka moment on design patterns for functional programming

Understanding design patterns for object-oriented programming made my life easier as a Java programmer. So I have been looking for a comparable book for functional programming ever since my sojourn into this age-old paradigm. It looks as though I’m not the only one looking too. But the thing is, I think I’ve just had a revelation of sort.

There is one and only one guideline to designing functional architectures — Keep it simple.

Simple as in keeping your functions having one purpose only. Simple as in work with the data directly and don’t conjure unnecessary intermediaries. Simple, as elaborated by Rich Hickey in his talk, Simple Made Easy.

Much of this is conveyed in Bloch’s Effective Java — item #5: Avoid creating unnecessary objects, item #13: minimize accessibility of classes and members, for examples. As Majewski said in a stackoverflow reply, “the patterns movement started because object-oriented programming was often turning into ‘spaghetti objects’”. So keeping it simple are what design patterns ultimately strive for.

“Functional programming is a restricted style of programming, so it didn’t need to grow a set of restricted conventions to limit the chaos.” As such, there is no design pattern book for functional programming. I didn’t get that earlier this year. But something clicked recently.

During the past few months, I’ve been doing some consulting and open source projects solving algorithmic problems with Clojure. One problem in a project that I was faced with this week is calculating the occurrence of each distinctive element within a list of elements.

Say we have a list, coll = (“orange”, “bottle”, “coke”, “bottle”). The output would be something like [("orange", "bottle", "coke") (1 2 1)]

This is my first solution.

The specs are not exactly as I described but the concept remains. What I did is to use tail calls (it’s supposed to be fast, isn’t it?) to aggregate each counter to produce a vector of counts. Then I map each pair of fragment with its corresponding count to generate a final output collection. Sounds overly complicated, doesn’t it? This is the first warning of a bad functional design.

For a collection of 30,000 items, this function took 11 minutes to compute on my notebook. This looks like a good place to exploit the parallel nature of this problem. Specifically, the counting of each fragment is independent of other fragments. Thus, there’s no need for the program to wait for one fragment to finish to process the next. I simplified the program to remove this inherent assumption of procedural processing.

Here is the gist of the refactored code where each function only does one job. Since the processing are modularised, I can parallelize the algorithm easily with the use of pmap instead of map on the last line.

I’ve split the first function into 3 functions (2 shown here). As Hickey said in his talk, simplifying can often produce more, not less, functions. Yet, the program is not only easier to read and runs in less than a minute. An order of magnitude faster!

There are still lots for me to learn. I want to find more challenging projects to push my own limits. But rather than solving arbitrary problems, I prefer to tackle real-world challenges. So if you know of anyone that can benefit from collaborating with a functional developer to build robust and scalable software, please pass along my contact. I offer a 15% referral reward for successful paid jobs too.

Vector algorithm using tree composition

Sniffed this trick from the Incanter source. Here’s a demo of using tree composition to calculate a 2-d Euclidean distance between two points.

(def x [1 2])
(def y [4 5])

(defn- tree-comp-each [root branch & leaves]
 (apply
  root (map branch leaves)))

(defn euclidean-distance
	[a b]
	{:pre [(= (count a) (count b))]}
	(sqrt
  	(apply
   		tree-comp-each
   		+
  		(fn [[x y]]
    		(pow (- x y) 2))
  		(map vector a b))))

I’ve only had exposures to tree traversal in the use of implementing searching and sorting algorithms. This trick here definitely widened my eyes to the wonders of functional programming. It’s more than just being able to pass and manipulate functions.

I need to think like a tree.

Social media: The fourth dimension in market data

It looks as though the first hedge fund utilizing social media data is about to launch in April. This “Twitter hedge fund” is based on the work of Bollen et al., “Twitter mood predicts the stock market,” Journal of Computational Science, 2011. In more general terms, this is an example use of Natural Language Processing (NLP) to assess the semantic of tweets relating to the stock market.

NLP, or more specifically semantic search, has been the holy grail of search engine companies since people realized that you can make a boatload of money by providing good search results. Semantic search improve search accuracy by understanding the seacher’s intent and the contextual meaning rather than going on the vocabulary alone (see Nature: Quiz-playing computer system could revolutionize research). What Bollen et al. are proposing is a subset of the grander NLP problem, in that they are only concerned with the “mood states” rather than the whole meaning of the tweets. In other words, sentiment analysis.

NLP is not new. R, for example, has a Natural Language Processing task view. Python has a Natural Language Toolkit. Wikipedia has a good list of NLP toolkits for other languages.

Traders understand that the market is driven by people, and people are ultimately driven by emotions. So far, there hasn’t been a method to directly evaluate the emotions of market participants. Would social media provide a glimpse to the emotions of the masses? According to Bollen et al., yes.

At any rate, data is king in quantitative trading. I have no idea would their particular implementation of data mining social media work or not. What’s true is that as more and more people publish their lives on the internet, all these non-quantitative information are just waiting to be exploited. Ethics and privacy issues aside, look at what Facebook is doing with their ads as an example.

In addition to time, volume, and price, data mining social media may provide us with a fourth dimension to market data.

Network latency on Amazon EC2 t1.micro to Dukascopy

While the processing power of a EC2 t1.micro server sucks (benchmarks have shown it is slower than a Nokia N900 phone), network performance is well-known to be exceptional for EC2 servers throughout the spectrum of their offerings.

Here’s a ping test from my home computer with a ADSL connection in Ottawa, Canada to 194.8.15.1, one of the Dukascopy web servers.

PING 194.8.15.1 (194.8.15.1) 56(84) bytes of data.
64 bytes from 194.8.15.1: icmp_req=1 ttl=242 time=149 ms
64 bytes from 194.8.15.1: icmp_req=2 ttl=242 time=134 ms
64 bytes from 194.8.15.1: icmp_req=3 ttl=242 time=135 ms
64 bytes from 194.8.15.1: icmp_req=4 ttl=242 time=148 ms
64 bytes from 194.8.15.1: icmp_req=5 ttl=242 time=135 ms

--- 194.8.15.1 ping statistics ---
5 packets transmitted, 5 received, 0% packet loss, time 4003ms
rtt min/avg/max/mdev = 134.364/140.579/149.726/7.053 ms


Then the same test from a EC2 t1.micro instance located in Dublin, Ireland (closest Amazon EC2 server location to Geneva).

PING 194.8.15.1 (194.8.15.1) 56(84) bytes of data.
64 bytes from 194.8.15.1: icmp_req=1 ttl=243 time=40.9 ms
64 bytes from 194.8.15.1: icmp_req=2 ttl=243 time=41.2 ms
64 bytes from 194.8.15.1: icmp_req=3 ttl=243 time=49.0 ms
64 bytes from 194.8.15.1: icmp_req=4 ttl=243 time=41.2 ms
64 bytes from 194.8.15.1: icmp_req=5 ttl=243 time=41.2 ms

--- 194.8.15.1 ping statistics ---
5 packets transmitted, 5 received, 0% packet loss, time 4005ms
rtt min/avg/max/mdev = 40.961/42.728/49.013/3.154 ms


Exceptional, indeed.

With the monthly pricing of a t1.micro going for around $12/month, there are few reasons not to get a remote server to run your trading system rather than pray for your home internet connection to remain reliable 24/7.

Update with ping test from Berlin courtesy of commenter Holger:

Ping wird ausgeführt für 194.8.15.1 mit 32 Bytes Daten:

Ping-Statistik für 194.8.15.1:
Pakete: Gesendet = 4, Empfangen = 4, Verloren = 0 (0% Verlust),
Ca. Zeitangaben in Millisek.:
Minimum = 43ms, Maximum = 43ms, Mittelwert = 43ms


Update April 12, 2011: I’ve been using Rackspace Cloud (#2 cloud server provider, after Amazon). Here’s the ping result from their London, UK server.


PING 194.8.15.1 (194.8.15.1) 56(84) bytes of data.
64 bytes from 194.8.15.1: icmp_seq=1 ttl=246 time=69.2 ms
64 bytes from 194.8.15.1: icmp_seq=2 ttl=246 time=69.6 ms
64 bytes from 194.8.15.1: icmp_seq=3 ttl=246 time=68.8 ms
64 bytes from 194.8.15.1: icmp_seq=4 ttl=246 time=66.6 ms
64 bytes from 194.8.15.1: icmp_seq=5 ttl=246 time=68.5 ms
64 bytes from 194.8.15.1: icmp_seq=6 ttl=246 time=64.6 ms
64 bytes from 194.8.15.1: icmp_seq=7 ttl=246 time=68.5 ms
64 bytes from 194.8.15.1: icmp_seq=8 ttl=246 time=69.1 ms
64 bytes from 194.8.15.1: icmp_seq=9 ttl=246 time=66.6 ms
^C
--- 194.8.15.1 ping statistics ---
9 packets transmitted, 9 received, 0% packet loss, time 8012ms
rtt min/avg/max/mdev = 64.677/67.986/69.617/1.573 ms


Update April 26, 2011: I’m testing Quickweb Germany’s VPS.

PING 194.8.15.1 (194.8.15.1) 56(84) bytes of data.
64 bytes from 194.8.15.1: icmp_seq=1 ttl=247 time=15.4 ms
64 bytes from 194.8.15.1: icmp_seq=2 ttl=247 time=15.3 ms
64 bytes from 194.8.15.1: icmp_seq=3 ttl=247 time=15.2 ms
64 bytes from 194.8.15.1: icmp_seq=4 ttl=247 time=15.3 ms
64 bytes from 194.8.15.1: icmp_seq=5 ttl=247 time=15.1 ms
64 bytes from 194.8.15.1: icmp_seq=6 ttl=247 time=15.2 ms
64 bytes from 194.8.15.1: icmp_seq=7 ttl=247 time=15.4 ms

--- 194.8.15.1 ping statistics ---
7 packets transmitted, 7 received, 0% packet loss, time 6000ms
rtt min/avg/max/mdev = 15.152/15.306/15.463/0.116 ms