behind the a-pillar: July 2011

31 July, 2011

Tax the Cyclists!

Seriously, I mean it!

Today, reading an opinion piece called The Dutch Way: Bicycles and Fresh Bread, I was jealous of how, "the coexistence of different modes of travel is hard-wired into the culture." In the US, as a cyclist, it doesn't feel as if we're just seen as yet some other Americans who've chosen a different mode of transportation, we're, "them." We're a counter culture. I wish we could be seen as humans first (all of us, in cars on bikes, whatever...) but even if we were to take a nationalistic look at it, I wish people in cars could look at those on bikes as contributing to the overall good of our nation by a) increasing our general health, b) improving our environment by cutting down on pollution, or c) increasing the security of our nation by reducing consumer pressures on our strategic oil reserves. But, alas, those vectors of thought are a bit too abstract.

So, how do you legitimize anything in the eyes of US citizens (or permanent resident aliens)? You tax it! Well, you create a user fee of some sort. (No matter how you put it, paying money to your government is tax whether it's a user fee or a general contribution to VAT or payroll tax. At least that's my interpretation and I'm just going to use the word tax intertwined with user fee for the sake of this diatribe.)

Seriously, though, us and them mentalities come from someone thinking the other group is "getting away with something." We cyclists should save the money we don't spend on fuel and auto expenses, but maybe mandatory licensing or bicycle tire taxes would eliminate the feeling that cyclists were somehow avoiding something by choosing not to get around by car. The reality is that we contribute to the tax base in other ways with our income, homeowners, and all sorts of value-added taxes, but the drivers have those too, so cyclists are seen as someone consuming space on roads we somehow didn't pay for.

In Minnesota, however, bicycle licensing was eliminated in 2005. (Point of interest, I did not know that until I set out to write this. I was looking up fees and was intending to step up and license all of my bikes as a way of putting my money where my mouth was.) Sheesh, law-abiding and anarchist cyclists alike should bristle at the lack of registration requirements. The anarchists who ride unregistered bikes are no longer stickin it to the man, they're just passively following the law, and in the same vein the law-abiding doo-gooders have no badge to prove they're following the law.

Anyway, I digress. The point is, that cyclists who use their bikes for legitimate transportation (not just sport or recreation) might be seen as "one of us" on the road by people driving cars if they also contributed to the transportation budget. I know, nanny-state, big-government haters will poo poo this as expansion of government and somehow twist this into a loss of liberty, but, seriously, when was the last time any of you substituted a car trip with a bicycle?

Oh, by the way, I'd sure love to be wrong on this stereotype. So, let me know if you don't share my views on government but share my passion for bicycle transport. I am all for casting aside clichès and having real conversations.

(Yes, this is over simplified. It's meant to be a conversation starter.)

16 July, 2011

effin around with ibonacci

First off, thanks to Alex Gorbatchev for his awesome SyntaxHighlighter. I've used it here with his great instructions for embedding. I took his instructions here using the "pre" method and just embedded the scripts within the script tags of this post instead of referencing them. If I use this again, I'll figure out how to upload the scripts I need to blogger, so I can just reference them. Anyway... this is really high quality stuff, nice work Alex.

So, I was playing around with, or did I say effin around with ibonacci? (Yes, putting the "f" in fibonacci.) I wanted to try out a few variations of Fibonacci algos to do some speed comparisons. I was knew that recursion would take a bit of a hit, but I was really surprised that it would be this bad.

recurFib(45) took 6813 milliseconds to calculate 1134903170
iterFib(45) took 0 milliseconds to calculate 1134903170
iterNoArrFib(45) took 0 milliseconds to calculate 1134903170

I love the elegance of recursive code.

 public static int recurFib(int n) {
  if (n == 0) {
   return n;
  }
  if (n <= 2) {
   return 1;
  }
  return recurFib(n - 1) + recurFib(n - 2);
 }

As opposed to the faster-performing iterative code.

public static int iterNoArrFib(int n) {
  int f = 0;
  //special case #1
  if (n == 0) {
   return f;
  }
  
  int x = 1;
  int y = 1;
  //special case #2
  if (n <=2) {
   return x;
  }
  
  for (int i = 3; i <= n; i++ ) {
   f = x + y;
   //set up x and y for next loop
   y = x;
   x = f;
   
  }
  return f;
 }

So, I tried a couple of things. First, I tried to neaten up the iterative version with an array instead of shuffling through the variables:

public static int iterFib(int n) {
  int[] f = new int[n+1];
  f[0] = 0;
  f[1] = 1;
  if (n >= 2) {
   f[2] = 1;
  }
  for (int i = 3; i <= n; i++ ) {
   f[i] = f[i - 1] + f[i - 2];
   
  }
  return f[n];
 }

It was no faster or slower (by my crude benchmark), but a little cleaner. Then, I tried to speed up our recursive version with a little caching. I was pretty sure that the recursive version recalculates all of the children for each node of the tree, so, I added an array to cache values, checking to see if it was already calculated before doing a recursive call:

private static int[] recurCache ;
 
 public static int recurCacheFib(int n, boolean first) {
  
  recurCache = (recurCache == null || first)? new int[n+1] : recurCache ;
  
  if (n == 0) {
   recurCache[n] = 0;
   return n;
  }
  if (n <= 2) {
   recurCache[n] = 1;
   return 1;
  }
  
  int f = recurCache[n];
  if (f == 0) {
   f = recurCacheFib(n - 1,false) + recurCacheFib(n - 2,false);
   recurCache[n] = f;
  }
  
  return f;
 }

Well, low and behold, it was just as fast as the iterative version:

recurFib(45) took 6813 milliseconds to calculate 1134903170
recurCacheFib(45) took 0 milliseconds to calculate 1134903170
recurCacheFib(45) took 0 milliseconds to calculate 1134903170 a second time
iterFib(45) took 0 milliseconds to calculate 1134903170
iterNoArrFib(45) took 0 milliseconds to calculate 1134903170

I ran it twice just to see if I would take much of a hit recreating the array for the cache. Apparently not.

However, when I compare the cached recursion code to the array-based version of iterative code, I think the array-based version is slightly more elegant. This is mostly due to the addition of the external array and not just lines of code. What do you think? The entire code is below.

package org.bikeonastick.examples;

import java.util.ArrayList;
import java.util.List;

public class Fibonacci {
 
 public static void main(String[] args) {
  int toFib = Integer.parseInt(args[0]);
  long start = System.currentTimeMillis();
  int fib = Fibonacci.recurFib(toFib);
  long finish = System.currentTimeMillis();
  System.out.println("recurFib(" + toFib +") took " + (finish - start) + " milliseconds to calculate " + fib);
  
  start = System.currentTimeMillis();
  fib = Fibonacci.recurCacheFib(toFib,true);
  finish = System.currentTimeMillis();
  System.out.println("recurCacheFib(" + toFib +") took " + (finish - start) + " milliseconds to calculate " + fib);

  start = System.currentTimeMillis();
  fib = Fibonacci.recurCacheFib(toFib,true);
  finish = System.currentTimeMillis();
  System.out.println("recurCacheFib(" + toFib +") took " + (finish - start) + " milliseconds to calculate " + fib + " a second time");

  
  start = System.currentTimeMillis();
  fib = Fibonacci.iterFib(toFib);
  finish = System.currentTimeMillis();
  System.out.println("iterFib(" + toFib +") took " + (finish - start) + " milliseconds to calculate " + fib);
  
  start = System.currentTimeMillis();
  fib = Fibonacci.iterNoArrFib(toFib);
  finish = System.currentTimeMillis();
  System.out.println("iterNoArrFib(" + toFib +") took " + (finish - start) + " milliseconds to calculate " + fib);
  
 }
 
 public static int recurFib(int n) {
  if (n == 0) {
   return n;
  }
  if (n <= 2) {
   return 1;
  }
  return recurFib(n - 1) + recurFib(n - 2);
 }
 
 private static int[] recurCache ;
 
 public static int recurCacheFib(int n, boolean first) {
  
  recurCache = (recurCache == null || first)? new int[n+1] : recurCache ;
  
  if (n == 0) {
   recurCache[n] = 0;
   return n;
  }
  if (n <= 2) {
   recurCache[n] = 1;
   return 1;
  }
  
  int f = recurCache[n];
  if (f == 0) {
   f = recurCacheFib(n - 1,false) + recurCacheFib(n - 2,false);
   recurCache[n] = f;
  }
  
  return f;
 }

 
 public static int iterFib(int n) {
  int[] f = new int[n+1];
  f[0] = 0;
  f[1] = 1;
  if (n >= 2) {
   f[2] = 1;
  }
  for (int i = 3; i <= n; i++ ) {
   f[i] = f[i - 1] + f[i - 2];
   
  }
  return f[n];
 }
 
 public static int iterNoArrFib(int n) {
  int f = 0;
  //special case #1
  if (n == 0) {
   return f;
  }
  
  int x = 1;
  int y = 1;
  //special case #2
  if (n <=2) {
   return x;
  }
  
  for (int i = 3; i <= n; i++ ) {
   f = x + y;
   //set up x and y for next loop
   y = x;
   x = f;
   
  }
  return f;
 }

}

14 July, 2011

a different side of south dakota

graffiti alley in rapid city is a bit different than president heads and baaaaadlands.

sodak

sooo, south dakota! we took a trip to south dakota to see rushmore, the black hills, and the badlands. we had a pretty good time. after seeing the presidents peeking at you from that mountain, they seem to be everywhere.