Entries Tagged 'tech' ↓

At 1.4 seconds, the ITA puzzle solution I dreamed up while on codeine was already fast enough. Since the pain has subsided and I stopped taking the damned pain-killers, I thought I should go back, optimize and clean up. The code is now shorter, and runs about 10 times faster.

The new version is also on refactormycode, where you can critique and suggest changes.

If you want to see different approaches, there are other solutions and discussions of this puzzle in various places.

The optimizations I made were guided by ruby’s own profiler (invoking ruby with the -r profile flag ). The first time it ran, I felt a tinge of embarrassment, seeing that format_units was called 248,440 times, accounting for over 43% of the computation time.

$ruby -r profile ita.rb

  %   cumulative   self              self     total

 time   seconds   seconds    calls  ms/call  ms/call  name

 43.87    84.78     84.78   248440     0.34     0.50  NumberWriter#format_units

 17.99   119.55     34.77   134583     0.26     1.29  NumberWriter#write

...

Caching the 1,000 potential return values for that function in an array immediately brought the execution time down under a second. Optimization can really be that easy sometimes.

Most optimizations were done iteratively, taking whatever operation was taking the most time and trying to find ways to reduce its footprint. When code started getting messy and verbose, I re-factored and got another speed boost. Overall, the exercise was amazingly easy, taking less than 2 hours of total time without involving any complex code.

What astonishes me is that there is still low-hanging fruit for anyone that would want to make this even faster. Half the time is now spent sorting. A better profiler would definitely help, as the one available out of the box only breaks things down by function. However it’s clear that the profiler’s top 5 results could be mostly avoided if string representations of numbers and ranges didn’t have to be created to sort them alphabetically:

$ time ruby -r profile ita.rb

  %   cumulative   self              self     total

 time   seconds   seconds    calls  ms/call  ms/call  name

 31.13     4.84      4.84    64521     0.08     0.15  ITA::Number#<=>

  8.49     6.16      1.32        3   440.00  3676.67  Array#sort

  8.10     7.42      1.26    68831     0.02     0.03  ITA::Number#to_s

  6.43     8.42      1.00    61704     0.02     0.03  ITA::Range#to_s

  6.30     9.40      0.98     6178     0.16     0.33  ITA::NumberWriter#write

  5.14    10.20      0.80        4   200.00  2850.00  Array#each

  4.63    10.92      0.72    64521     0.01     0.01  String#<=>

I don’t feel the need to push this puzzle any further. If you do, go for it, and please share on refactormycode.

I spent most of my week-end solving the ITA puzzle, while high on codeine. As I write this, I am literally shaking from withrawal. Those pills just take too long to get in your blood stream.

A root canal Friday forced me to make an exception to my usual drug-free lifestyle; the infection had reached the bone, so I’m also taking anti-biotics. Since I couldn’t dance, puzzle solving was the best thing to keep me distracted. I found a solution I’ll post later; it runs over 1,000 times faster than others I’ve seen or heard about.

There’s no way I can maintain a codeine habit, so I may have to try doping my writing abilities with alcohol.

Edit: Comments disabled because of spam

Being familiar with many of the most common cognitive biases is not only useful to lead happier lives; it’s also becoming essential for survival.

Smart People Make Big Money Mistakes. We pursue things that won’t make us happy and perceive the world as more violent than it really is, even as wars have decreased by orders of magnitude. The availability heuristic affects how we (mis-)spend money on security, including in information security.

Jamais Cascio nails it when he says we have trouble envisioning a future that isn’t catastrophic. He appropriately concludes:

Sometimes, being a futurist isn’t about making forecasts or spotting trends.

Sometimes, being a futurist means acting as a civilizational therapist.

All the essays, books and videos linked above can help us do our individual part for this civilizational therapy project. Have fun

Like most geeks, I love puzzles. I solved Google’s infamous puzzle that started with {first 10-digit prime found in consecutive digits of e}.com. I also solved one of Facebook’s puzzles, just for fun.

Today, Jonathan sent me a link to ITA Software’s hiring puzzles. It’s sexy stuff, and Standout Jobs would have some hiring puzzles too if I could come up with something particularly demented. Jonathan suggested an intriguing roman numeral puzzle. Sadly, we both realize that many people can’t even write a simple Fizzbuzz.

Ah well, back to the ITA Software puzzle. Looking at the average length of a few numbers, I estimate there’s a good chance the 51 billionth letter either doesn’t exist, or is very close to the end. Gauss would be amused.

Even if I’m wrong, brute force is obviously out of the question. It would however be nice to start from the end and have the algo run in a fraction of the time. So here’s how I start.

units = %w{ one two three four five six seven eight nine }
tens = %w{ ten twenty thirty fourty fifty sixty seventy eighty ninety }
teens = %w{ ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen }

def sum_string_sizes(units)
units.inject(0) {|memo, unit| memo + unit.size }
end

sum_string_sizes(units)
=> 36
sum_string_sizes(teens)
=> 70

([''] + units).inject(0) {|memo,i| memo + "twenty#{i}".size }
=> 96
'twenty'.size * 10 + sum_string_sizes(units)
=> 96
# sanity check doesn't bounce, wOOt!

sum_string_sizes(tens[1..-1]) * 10 + 8 * sum_string_sizes(units)
=> 758

So for numbers 1 to 99, I get strings of total length 864. I’m certain of my solution up to 999, but I’m not awake enough to be sure I have the rest really nailed. Either way, if there’s more than 51 billion letters, there’s still a fair chunk of work to do.

Have you solved this? If so, do you want to work for Standout Jobs? If not, how would you go about it?

It’s on the company blog, and Marc-André blogged about a typical day here at the office. We need another Ruby developer - either a “Guru” or a “Devotee”. I wasn’t going to blog about it, having sent email / IMs to people to encourage them to apply for work here.

The answers I got were surprising. The main question was around compensation.

Here’s the scoop: pay is above average for Montreal. Plus benefits. Plus stock options. Plus working with an awesome language, a beautiful framework, under good working conditions (read Marc-André’s blog post!)

Now, here’s scoop #2. Marc-André and I will also be interviewing candidates. We have high standards: we are looking for other passionate people. We want people that enjoy coding and are continually learning.

If you don’t have passion, you shouldn’t bother applying. If you do, we expect you’ll have code to show us - although it might be Python, Erlang, Javascript or another cool language.

I finished reading The End of Medicine: How Silicon Valley (and Naked Mice) Will Reboot Your Doctor last week-end. Andy Kessler is a Silicon Valley geek that struck it rich, and wants to find the next big thing in medicine. I give the book 3 out of 5 stars.

Looking for areas where silicon meets biology, he documents one year of dialogs with various researchers including Nobel prize winners. No doubt being wealthy opens many doors. Silicon gets better, faster and cheaper - surely if we can bring these qualities to medicine in a way that can scale we can cure many diseases?

I’m not convinced Kessler is quite on the right track. While the technologies he describe are very promising, modern medicine has had plenty of spectacular failures and the future rarely unfolds as expected. We have bottled water and oxygen bars, but we still don’t have flying cars or X-Ray machines in every living room.

More to the point, his emphasis on early detection misses the most obvious point: prevention. Several times when dining with eminent researchers Kessler judges whether they are true believers by the fat content of their meals. Apparently someone convinced that their research will bear fruit wouldn’t subject themselves to bland and healthy food.

We are already doing much better at curing some cancers like childhood leukemia. Even while more children fall ill, fewer die. In other words, more and more children go through the ordeal of cancer treatment and we still aren’t sure what’s causing the disease.

Perhaps Kessler thinks his bacon and eggs are worth the risk of needing treatment. And in his mind, treatment will be quick zaps at the very earliest onset of the disease. I hope so, but doubt it.

My hope for the future is radically different. As more sensors let us capture more and better data, and as early diagnostics help us better associate environmental conditions and diseases, we will be able to more clearly identify causes. We may finally answer whether and which pesticides cause childhood leukemia.

Prevention won’t make anyone billions the way cheap silicon wafers cancer diagnostic kits and advanced imaging will. Because Kessler is chasing money, he misses the obvious - that prevention always saves many more lives than treatment.

Campfire / office chat:

Daniel H. : This is annoying:
The name ‘employer’ is reserved by Ruby on Rails.
Please choose an alternative and run this generator again.

Fred N.: emplyer

Daniel H.: what? come on

Fred N.: wait
employr

Daniel H. : Aah yes, spelling 2.0

Efficiency Measures Could Cut Data Center, Server Energy Use by Half, or how to get suckered by the anti-Kyoto crazies.

A few years back a story circulated meant to stir FUD against Kyoto. The gist went something like this: computers are using a huge percentage of our electricity consumption! If the US signs on to Kyoto, we will cripple our high-tech economy! oh noes!

The story keeps getting reused, recycled and repurposed. In that way at least, it’s green.

It makes for great marketing material if you’re selling SUN servers (see my comment: That VP is pulling numbers out from where the sun don’t shine). “Data centers alone, Sun calculates, account for 2-3 percent of total world energy use.” That of course is completely outrageous.

Now it’s the EPA’s turn to release numbers. They’re not quite as crazy as SUN’s: now US data centers only consume 1.5% of US electricity (as opposed to energy!). Even the usually sane Worldwatch Institute is being used as a megaphone for this ideologically-driven hack-job (it also got reprinted through Worldchanging).

First off, the EPA report clearly says they’re estimating these numbers:

These energy consumption estimates were derived using a bottom-up estimation method based on the best publicly available data for servers and data centers. The estimation was performed as follows:

• estimated the U.S. installed base of servers, external disk drives, and network ports in data centers each year (based on industry estimates of shipments and stock turnover);
• multiplied by an estimated annual energy consumption per server, disk drive, or network port; and
• multiplied the sum of energy use for servers, storage, and networking equipment by an overhead factor to account for the energy use of power and cooling infrastructure in data centers. (EPA report: executive summary)

Estimates multiplied by estimates, multiplied by an overhead factor. Makes you feel confident public policy is based on sound advice, doesn’t it?

If the numbers were true, it might matter. However many vendors are already trying to sell more energy-efficient servers, and data centers are also looking for cost-effective ways to save money. It’s unclear what the US government could do that the market isn’t already doing.

It’s also doesn’t matter in the sense that energy use in data centers shouldn’t be considered in isolation. Servers are also displacing other energy-intensive applications. If people file their income tax through a server, that’s energy that wasn’t used to transport paper - let alone pulp wood and printing costs.

The EPA report had two objectives. One was to create FUD, the other to delay action. It’s worked admirably well.

Because I work on web software, other geeks ask me for help with really odd side-projects…

I want to repeatedly do a superpoke action on facebook.
like every 5 minutes
ok
what’s the easiest way to set that up?
I tried wget and it needs both to set the browser type and also a cookie for logged in which I don’t know how to do via wget
curl may be better for that - more options
alternative is Mechanize

…

so my facebook poking problem has been solved.
oh?
I just used a small amount of javascript and an iframe
hahahaha
I had it poke her once every other minute, however you’re limited to 100 pokes per day per person apparently before it starts deleting the old ones.
so I’ll set it to once every 864 seconds for now

For those of you puzzled by 864: 24 hours * 60 minutes * 60 seconds = 86,400 seconds.

Doing some research for url_pipe for DemoCampMontreal4, I went around looking for the state-of-the-art in feed technology. Some of this stuff was too cool not to turn into a bookmarklet.

Create a bookmark (e.g. “Map this!”), with the following for location:
javascript:links = document.getElementsByTagName('link');for(var i=0; i < links.length; i++) {if (links[i].rel == 'alternate') {this.location = 'http://maps.google.com/maps?f=q&hl=en&q=' + 'http://ws.geonames.org/rssToGeoRSS?feedUrl=' + encodeURIComponent(links[i].href);}}

Now try clicking it on while visiting the Standoutjobs blog or Crunchboard for an instant mapping mashup.

How it works: this will grab the first alternate link on a page (RSS/Atom - it could break if it’s print!), and send you to Google Maps. The magic bit is provided by Geonames’ rss-to-georss converter, which adds geographic location to a feed before GMap gets its hands on it.

Again, this could break very easily. If you go to the 37signals job board, there is no alternate link - the RSS is in the main body. Nothing really bad happens, it’s just not very elegant.

Any suggestions as to how to make this better, or improvements are appreciated. Wordpress doesn’t like code in comments, so please post any code on your favourite pasting site. (It also wouldn’t let me create an easy to drag bookmarklet. Any hints on how to make it do that would be appreciated).