On Algorithms
So, generally speaking, I’ve typically adhered to the rule that those who develop software should be aware of various classes of algorithms and data structures, but should avoid implementing them if at all possible. The reasoning here is pretty simple, and I think pretty common:
- You’re reinventing the wheel. Stop that, we have enough wheels.
- You’re probably reinventing it badly.
So just go find yourself the appropriate wheel to solve your problem and move on.
Ah, but there’s a gotcha, here: Speaking for myself, I never truly understand an algorithm or data structure, both theoretically (ie, how it works in the abstract, complexity, etc) and practically (ie, how you’d actually implement the thing) until I try to implement it. After all, these things in the abstract can be tricky to grok, and when actually implemented you discover there’s all kinds of details and edge cases that you need to deal with.
Now, I’ve spent a lot of my free time learning about programming languages (the tools of our trade that we use to express our ideas), and about software architecture and design, the “blueprints”, if you will. But if languages are the tools and the architecture and design are the blueprints, algorithms and data structures are akin to the templates carpenters use for building doors, windows, etc. That is, they provide a general framework for solving various classes of problems that we as developers encounter day-to-day.
And, like a framer, day-to-day we may very well make use of various prefabbed components to get our jobs done more quickly and efficiently. But without understanding how and why those components are built the way they are, it can be very easy to misuse or abuse them. Plus, it can’t hurt if, when someone comes along and asks you to show off your mad skillz, you can demonstrate your ability to build one of those components from scratch.
Consequently, I plan to kick off a round of posts wherein I explore various interesting algorithms and data structures that happen to catch my attention. So far I have a couple on the list that look interesting, either because I don’t know them, or because it’s been so long that I’ve forgotten them…
Data Structures
- Skip list
- Fibonacci heap
- Red-Black tree
- Tries
- Radix/PATRICIA Tries
- Suffix Tries
- Bloom filter
Algorithms
- Various streaming algorithms (computations over read-once streams of data):
- Heavy hitters (finding elements that appear more often than a proscribed freqency)
- Counting distinct elements
- Computing entropy
- Topological sort
And I guarantee there’s more that belong on this list, but this is just an initial roadmap… assuming I follow through, anyway.
Hosting Git on Windows
Using Git to push changes upstream to servers is incredibly handy. In essence, you set up a bare repository on the target server, configure git to use the production application path as the git working directory, and then set up hooks to automatically update the working directory when changes are pushed into the repository. The result is dead easy code deployment, as you can simply push from your repository to the remote on the server.
But making this work when the Git repository is being hosted on Windows is a bit tricky. Normally ssh is the default transport for git, but making that work on Windows is an enormous pain. As such, this little writeup assumes the use of HTTP as the transport protocol.
Installation
So, first up we need to install a couple components:
- msysgit
- Apache
Note: When installing msysgit, make sure to select the option that installs git in your path! After installation the system path should include the following1:
C:\Program Files\Git\cmd;C:\Program Files\Git\bin;C:\Program Files\Git\libexec\git-core
Now, in addition, we’ll be using git-http-backend to serve up our repository, and it turns out the msysgit installation of this tool is broken such that one of its required DLLs is not in the directory where it’s installed. As such, you need to copy:
C:\Program Files\Git\bin\libiconv-2.dll
to
C:\Program Files\Git\libexec\git-core\
Repository Initialization
Once you have the software installed, create your bare repository by firing up Git Bash and running something like:
$ mkdir -p /c/git/project.git $ cd /c/git/project.git $ git init --bare $ git config core.worktree c:/path/to/webroot $ git config http.receivepack true $ touch git-daemon-export-ok
Those last three commands are vital and will ensure that we can push to the repository, and that the repository uses our web root as the working tree.
Configuring Apache
Next up, add the following lines to your httpd.conf:
SetEnv GIT_PROJECT_ROOT c:*git* ScriptAlias *git* "C:/Program Files/Git/libexec/git-core/git-http-backend.exe/" <Directory "C:/Program Files/Git/libexec/git-core/"> Options +ExecCGI FollowSymLinks Allow From All </Directory>
Note, I’ve omitted any security, here. You’ll probably want to enable some form of HTTP authentication.
In addition, in order to make hooks work, you need to reconfigure the Apache daemon to run as a normal user. Obviously this user should have permissions to read from/write to the git repository folder and web root.
Oh, and last but not least, don’t forget to restart Apache at this point.
Pushing the Base Repository
So, we now have our repository exposed, let’s try to push to it. Assuming you have an already established repository ready to go and it’s our master branch we want to publish, we just need to do a:
git remote add server http://myserver/git/project.git git push server master
In theory, anyway.
Note: After the initial push, in at least one instance I’ve found that “logs/refs” wasn’t present in the server bare repository. This breaks, among other things, git stash. To remedy this I simply created that folder manually.
Lastly, you can pop over to your server, fire up Git Bash, and:
$ cd /c/git/project.git $ git checkout master
Our Hooks
So, about those hooks. I use two, one that triggers before a new update comes to stash any local changes, and then another after a pack is applied to update the working tree and then unstash those local changes. The first is a pre-receive hook:
#!/bin/sh export GIT_DIR=`pwd` cd `git config --get core.worktree` git stash save --include-untracked
The second is a post-update hook:
#!/bin/sh export GIT_DIR=`pwd` cd `git config --get core.worktree` git checkout -f git reset --hard HEAD git stash pop
Obviously you can do whatever you want, here. This is just something I slapped together for a test server I was working with.
-
Obviously any paths, here, would need to be tweaked on a 64-bit server with a 32-bit Git. ↩
Review: Leviathan Wakes
Review of Leviathan Wakes (The Expanse #1.0) by James S. A. Corey (9780316129084)★★★★(https://b-ark.ca/u2ACAS)Humanity has colonized the solar system - Mars, the Moon, the Asteroid Belt and beyond - but the stars are still out of our reach.
Jim Holden is XO of an ice miner making runs from the rings of Saturn to the mining stations of the Belt. When he and his crew stumble upon a derelict ship, the Scopuli, they find themselves in possession of a secret they never wanted. A secret that someone is willing to kill for - and kill on a scale unfathomable to Jim and his crew. War is brewing in the system unless he can find out who left the ship and why.
Detective Miller is looking for a girl. One girl in a system of billions, but her parents have money and money talks. When the trail leads him to the Scopuli and rebel sympathizer Holden, he realizes that this girl may be the key to everything.
Holden and Miller must thread the needle between the Earth government, the Outer Planet revolutionaries, and secretive corporations - and the odds are against them. But out in the Belt, the rules are different, and one small ship can change the fate of the universe.
I wanna give half stars! This book didn’t totally blow my mind (like, say, The Road), but it was a really solid space opera. 4.5.
Review: Spin
Review of Spin (Spin #1.0) by Robert Charles Wilson (9780765348258)★★★★(https://b-ark.ca/K6wWOa)Spin is Robert Charles Wilson's Hugo Award-winning masterpiece―a stunning combination of a galactic "what if" and a small-scale, very human story.
One night in October when he was ten years old, Tyler Dupree stood in his back yard and watched the stars go out. They all flared into brilliance at once, then disappeared, replaced by a flat, empty black barrier. He and his best friends, Jason and Diane Lawton, had seen what became known as the Big Blackout. It would shape their lives.
The effect is worldwide. The sun is now a featureless disk―a heat source, rather than an astronomical object. The moon is gone, but tides remain. Not only have the world's artificial satellites fallen out of orbit, their recovered remains are pitted and aged, as though they'd been in space far longer than their known lifespans. As Tyler, Jason, and Diane grow up, a space probe reveals a bizarre truth: The barrier is artificial, generated by huge alien artifacts. Time is passing faster outside the barrier than inside―more than a hundred million years per year on Earth. At this rate, the death throes of the sun are only about forty years in our future.
Jason, now a promising young scientist, devotes his life to working against this slow-moving apocalypse. Diane throws herself into hedonism, marrying a sinister cult leader who's forged a new religion out of the fears of the masses.
Earth sends terraforming machines to Mars to let the onrush of time do its work, turning the planet green. Next they send humans…and immediately get back an emissary with thousands of years of stories to tell about the settling of Mars. Then Earth's probes reveal that an identical barrier has appeared around Mars. Jason, desperate, seeds near space with self-replicating machines that will scatter copies of themselves outward from the sun―and report back on what they find.
Life on Earth is about to get much, much stranger.
I think of Greg Bear as the kind of writer who’s willing to take a big idea with big consequences, and then actually explore those consequences. Mr. Wilson does the same, here, in Spin, and I think executes it quite well. The mystery is well delivered, the narrative well paced, the characters interesting and fairly realistic, and the examination of the consequences of his idea, both on the individual characters as well as the earth (and universe) at large, is fascinating and compelling. Definitely worth a read.