21 April 2013
I’ve been interested for a while in developing a Ruby implementation of the Dual-Pivot Quicksort algorithm Vladimir Yaroslavskiy developed, that was later improved by Yaroslavskiy, Jon Bentley, and Joshua Bloch, and was implemented as the default sort algorithm for primatives in Java 7.
A little more about the algorithm:
“This algorithm offers O(n log(n)) performance on many data sets that cause
other quicksorts to degrade to quadratic performance, and is typically
faster than traditional (one-pivot) Quicksort implementations.”
– OpenJDK 7
The algorithm’s performance characteristics are still being studied. In particular, Martin Aumüller and Martin Dietzfelbinge from the Ilmenau University of Technology have a an interesting new paper.
I’ve also wanted to contribute for a while to an interesting project Kanwei Li has on GitHub that’s intended to provide useful algorithms and data structures for Ruby, with optional C extensions. So I’ve combined both interests and added my take on a Ruby version of the algorithm to my GitHub fork of Li’s project.
Update: Kanwei Li has accepted my pull request, so you can now find the algorithm in the main project repository on GitHub.
21 April 2013
When it comes to hosting web applications these days, web developers live in a time of plenty. We have many options available to us, including using our own in-house hardware, using a virtual private server (VPS) like those available from Linode, or using a cloud platform as a service (PaaS) provider like Heroku.
At one point or another in setting up your application on a remote server, you may need to set up a brand new remote Git repository. Different developers use different methods of course, but I thought it might be helpful if I shared mine. I remember the first time I tried to do this, and it wasn’t clear at all. There’s a little “magic” in the post-receive hook, but we’ll go through this step-by-step, and we should be fine.
For this example we’re going to assume:
- That we’re pushing to a typical Linode VPS.
- That we’re using the default SSH port to communicate with the remote server.
- That the local repository we want to push to the remote server is named “jenkins”.
- That the directory structure we want on the remote server is something like this:
The actual repository will be stored in the “jenkins” directory, and the Git repository will reside in the “jenkins.git” directory.
Of course this technique is easily adapted to other circumstances— I’m just using the assumptions to establish a common starting point for the example.
Let’s get started!
On the REMOTE server, go to the directory where you want to create our two directories: In our example, this would be “/var/www”:
On the REMOTE server, we now create our bare Git repository:
git init --bare
On the REMOTE server, now we add our post-receive hook in the new, empty repository.
We’ll put a file in the “jenkins.git/hooks” directory called “post-receive” that will tell Git to actually publish the repository to the “jenkins” directory whenever it receives changes:
"GIT_WORK_TREE=/var/www/jenkins git checkout -f" \
Be sure that there is a space between “jenkins” and “git” in that ECHO command. This is where we tell Git that we actually want to publish the repository to the “jenkins” directory, not “jenkins.git”.
On the REMOTE server, we make the post-receive hook executable:
chmod a+x hooks/post-receive
On the REMOTE server, we create the directory that will actually hold our application:
On the LOCAL machine, we add the new remote to our .git/config file. You can either do this with the Git command:
git remote add linode moc.elpmaxenull@resu/var/www/jenkins.git
or do it by appending this to the .git/config file:
url = ssh://moc.elpmaxenull@resu/var/www/jenkins.git
fetch = +refs/heads/*:refs/remotes/linode/*
Finally, on the LOCAL machine, we can push the LOCAL repository to the REMOTE server:
git push linode master
And we’re done!
From now on, whenever you want to push your changes to the remote server, just do
git push linode master
28 March 2013