Vairoj

Create pre-allocated nested lists in Python

2011-07-03T00:00:00-07:00

Python programmers should be familiar with the following idiom:

>>> "A" * 3
"AAA"

It can be used to create pre-allocated lists, mimicking arrays.

>>> [0] * 3
[0, 0, 0]
>>> [None] * 3
[None, None, None]

Thus, to a pre-allocated nested list, i.e. a 2-dimensional array representing a matrix, the first thing that came to my mind is:

>>> [[0] * 3] * 3
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

But that is wrong, unfortunately. Though it might not be obvious at first, assigning value to an entry changes the values in every row.

>>> a[0][0] = 1
[[1, 0, 0],
 [1, 0, 0],
 [1, 0, 0]]

It actually turns out that the * operator doesn’t create copies of a specified object, but rather repeats the reference to that same object. This explains why it is no issue when the created objects are immutable. It doesn’t matter whether there are multiple references to the same immutable object; the object’s state cannot be changed so there is no harm. The only thing you can do is to change the reference to another object entirely.

>>> a = ["A"] * 3
["A", "A", "A"]
>>> a[0] = "B"
["B", "A", "A"]

On the other hand, mutable objects are modifiable. When the state of a mutable object is altered, all references to that object will reflect that changes.

The gotcha is perhaps hardly observable because most Python’s built-in types are immutable. List and other container types are mutable, however. Therefore when you create nested lists, i.e. list of lists, the issue is apparent.

To properly create pre-allocated lists, use list comprehension instead:

>>> [0 for x in range(3)]
[0, 0, 0]

And for nested lists:

>>> m = [[0 for x in range(3)] for x in range(3)]
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
>>> m[0][0] = 1
[[1, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

Google Code Jam 2011 My take on Bot Trust

2011-05-08T00:00:00-07:00

I enjoyed yesterday’s qualification round of Google Code Jam 2011. Once figured out, the problems are arguably straightforward. Code Jam website also provides informative explanation for the solutions to each problems.

Nevertheless, I want to chip in on the Bot Trust problem. Code Jam’s solution is a straightforward one, though I find that my solution is more concise yet still simple to understand. Let’s look at the code:

The idea is simple, as the problem wants the minimum time to complete the order, this algorithm does exactly that without the need for calculation at every time increment. Instead, it iterates through each command and calculates the time the corresponding bot completed the command. Last location and time of both bots are maintained. If the time a bot uses is less than the current time, it means that the bot moved in place earlier but has to wait for the other bot to push the switch, hence the time it takes is either its moving time or the latest time, whichever is larger. The +1 at the end is the time used to push the switch.

Upgrade OCZ Vertex 2 firmware on OS X

2011-05-03T00:00:00-07:00

Those who use OCZ’s Sandforce-based SSDs such as Vertex 2 with a Mac perhaps question the possibility of upgrading the drive’s firmware. From OCZ’s download page, it looks like the firmware update tool only supports Windows. In fact, OCZ also provides a firmware update tool for Linux. But for some reason, OCZ decided to conceal the link in a forum post rather than making it visible on their download page.

The OCZ-Sandforce Linux-based firmware update tool can be used together with a Linux Live CD to boot up a Mac machine and flash the SSD’s firmware. One OCZ forum member posted a very nice detailed instruction on the topic. I’ve updated my firmware from 1.27 to 1.33 following the instruction and it works perfectly. The update fixes the hibernation issue on the Mac and now I can hibernate my MacBook Pro again. There is one caveat: PCLinuxOS ISO image cannot be burned properly to DVD. You’ll need CDR/RW for that.

[9/5/11]: You might also want to check out Linux and OS X forum at OCZ website. People has been posting unofficial guides on upgrading firmware on OS X there, and you may find one that suits your scenario better than others. For instance, there is an instruction specific to MBP 2011 if you have trouble using the above method.

Correctly install pyspatialite

2011-04-15T00:00:00-07:00

You need pyspatialite to use spatialite with Python code. If you install it with easy_install, probably you will run into an error, symbol not found: _iconv, when importing the module. The tarball at pyspatialite website has the problem fixed though. Apparently, the version available at easy_install repository is not up-to-date.

Therefore, in the meantime, don’t use easy_install and download the tarball directly from the website. Note that it is not necessary to install libspatialite separately as pyspatialite includes the library and will build it as part of python setup.py install process. Also, if pyspatialite has already been installed through easy_install, you need to uninstall it first, otherwise; that version will still get picked up when importing the module.

What is Amazon Corporate Housing?

2011-03-31T00:00:00-07:00

If you get an internship offer from Amazon.com, one thing you need to decide as part of your offering package is housing option. Essentially you are given two choices: one-time stipend or Amazon-provided housing. The former is quite obvious—Amazon pays you a fixed amount of money and you are on your own. However, if you are like me, it may not be clear at first what Amazon corporate housing is like. Not only that you don’t get the stipend with this option, part of your salary will also be deducted for rental payment. Is corporate housing option really worth it?

With corporate housing option, an apartment unit is rented for you. The apartment could be one of many standard apartments in Seattle. As you may already aware of what corporate housing offers, here are the quick summary:

Choose to live alone, or with a roommate in two-bedroom apartment. Obviously you pay less on the latter option.
If you choose to live with a roommate, Graebel does roommate matching with another Amazon intern for you.
The apartment is fully furnished. There are TV, internet, couches, dining set, and kitchenwares. Just move in and fill the fridge. In addition, one parking spot is included if you will be driving.
Housekeeping service is included.

Simply put, the corporate housing option is favorable for interns. Living there for just 3 months, you might not want to go through the hassles of finding the places, buying furnitures, and so forth. Nevertheless, if you’re comfortable with those stuffs, the stipend option gives you freedom. Folks who find their own places could make extra cash e.g. by renting a place in some farther areas.

Last summer, I lived at this place with a nice roommate. The apartment was 15 minute walk to Amazon office in International District where I worked. While the unit was pretty decent, feature-wise, it was no way like the pictures on its website. If you’ve ever shopped for apartments, you probably know what I’m talking about.

A few suggestions

Whichever option you take, here are some tips to avoid surprises:

Graebel may not be your friend

If my experience is any indication, communicating with Graebel could be frustrating. In my case, I couldn’t reach my contact person until 3 days before my start date. That means flight ticket, housing, and everything had to be rushed in the last minute.

Know where you will be working at

Amazon offices used to scattered around buildings throughout downtown areas, depending on what team you will be working with. However, they had been moving to their new campus at South Lake Union and I assume that they are all at SLU now. Check with your HR person so you have an idea how your daily commute will be. Personally I find public transportation in Seattle pretty convenient. If you want to learn about bus routes check out King County Metro Transit.

Neighborhoods

Different neighborhoods in Seattle have different vibes. You may want to research on areas that you prefer or areas that you want to avoid. Although Seattle is considered a safe city, some people felt a bit uneasy in some downtown areas especially at night.

Don’t be fooled by pretty photos

When you are offered with a place, look it up online. See how the area is like. Find some reviews on Google Maps. The apartment website itself doesn’t tell you much. If you don’t like the place, you could ask for a change. After all, you will be living there for 3 months.

I hope this information helps a bit. Feel free to post questions about Seattle or Amazon internship in the comment below. You can also get in touch with me in Twitter (@ejel) too.

GitX couldn't connect to app server

2011-03-15T00:00:00-07:00

If you install GitX through MacPorts and try launching it from the the shell, you might be greeted with an error:

 
% gitx
Couldn't connect to app server!

What you need to do you is to launch GitX.app at least once. MacPorts puts it at /Applications/MacPorts/GitX.app. It seems that some initialization is required before the command-line tool can be used.

Upgraded MacBook Pro with SSD

2011-02-16T00:00:00-08:00

I finally joined the SSD upgrade train. After resisting the itch for some time, eventually posts from Coding Horror, AkitaOnRails, and Lifehacker won over my temptation. I would say the performance gain is fairly dramatic like what people say. On my MacBook Pro, the whole boot time (from power on until login finishes) went down from 105 to merely 30 seconds—almost 4 times faster. Everything is of course a lot more snappier. Applications such as Chrome, TextMate, or Twitter launch instantly. If you are interested, you can find more detail about SSD including benchmark results from the mentioned posts.

The SSD I bought is the 240GB OCZ Vertex 2. I chose OCZ over Crucial RealSSD (which also receives many positive reviews) because Crucial seems to yield optimal performance only when used with fast SATA 3.0 controllers.

Since my MacBook Pro is the early-2008 model, changing the drive is a little more involved that I expected. Fortunately, this YouTube video provides a step-by-step instruction including the required tools. Thus be sure to check out the video before trying to crack the case to avoid damaging your MBP.

One outcome from this upgrade is I no longer need to keep many apps opened anymore. Usually, there are a few apps that are needed occasionally. However, when needed, they have to show up fast enough not to divert me away from my flow–e.g. things like Dictionary, TextMate, or even Dashboard. Previously, I kept these apps opened all the time but the problem was they cluttered my Dock and Alt-Tab. I also rarely used Dashboard because of its initial startup time. Thanks to SSD’s fast access time, now I can launch the apps whenever I need and close them immediately after I am done. I also find myself using Dashboard widgets more and more.

There is one problem with the new drive though. My laptop crashes with kernel panic every time it wakes up from hibernation. The problem appears to be Vertex 2-specific problem though. Anyway, some folks recommend turning off hibernation completely when you are using SSD to prolong its life. I am still undecided on the approach though.

Powered by Jekyll

2011-02-10T00:00:00-08:00

Formatting posts on Wordpress is tedious. It is one of the reasons that had kept me from regular blogging. I would prefer to write posts in my favorite text editor using some sane format such as Markdown. Finally, after stumbled on a Stack Exchange question about blogging platforms, I finally found my solution. It is Jekyll.

Jekyll is essentially, in its own words, “a simple blog aware, static site generator”. There are already a few places discussing its virtues so I won’t repeat it here.

The thing that touches me most is its simplicity. Now I can just fire up my text editor, write the prose, save the file, and commit it to my Git repository. All posts belong with me, no longer obscured in a MySQL database hosted somewhere I don’t know.

Also, because of its simplicity, I feel excited to design own website for the first time. This thought never occurs to me when using Wordpress as theming Wordpress seems too much of a hassle.

Hopefully this move will bring me back to more frequent blogging.

Installing libxml-ruby on Windows: The painless way

2010-06-17T00:00:00-07:00

Most of the pages I googled for how to install LibXml Ruby on Windows mention building the required libraries on Windows. Not only that it is a hassle, but I could not make it works either. I finally found a straightforward way and hope it can save you some time.

UPDATE: As you guys pointed out in the comments, I updated the instruction with some more detail and steps that I didn’t mention previously.

Prerequisite: Make sure that you already have rake installed.
```
    gem install rake
```
You also probably need Ruby DevKit in order to install native libraries. Follow DevKit Installation Instructions on its wiki page.
As mentioned on LibXml RDoc, you need to download Win32 RubyGem which includes all the required binaries. This way you don’t have to go through the hassle of building all the libraries yourself. To install libxml with prebuilt binaries for Windows, executing the following command: (Thanks @Carl for the suggestion)
```
    gem install libxml-ruby --platform x86-mswin32-60
```
If there is error at this step make sure you have DevKit installed.
The DLLs must also be available in PATH environment variable. Assuming that your <ruby-path>\bin is already in your PATH (as set by RubyInstaller), copy libxml2-2.dll and libiconv2.dll from <ruby-path>\lib\gems\1.8\gems\libxml-ruby-xxx\lib to your <ruby-path>\bin directory. Your <ruby-path> should be something like C:\Ruby187.

Test if everything works by entering irb and require both rubygems and libxml.

    irb(main):001:0> require 'rubygems'
=> true
irb(main):002:0> require 'libxml'
=> true
irb(main):003:0>

And that’s it. Now you should be able to use LibXml with your Ruby code!

Replace Python range() with xrange() for speed

2010-04-29T00:00:00-07:00

A few weeks ago I stumbled on an interesting programming problem at CodeChef. The problem reminded me of dynamic programming thus I decided to try implementing a solution in Python.

Initially, the main part of the algorithm I implemented looked something like this:

for i in range(1, x):
  for j in range(i - 1, y, -1):
    # a few lines of basic comparisons,
    # calculations, and assignments
    # ......

Just a simple nested loop. When I ran the code with the test input where x is 100000 and y is 1000, however, it took 60 seconds to complete! Far from the problem’s time limit of 2 seconds. Although this is a nested loop, the running time is O(xy) which should not be that long.

To my surprise, the result from cProfile showed that most time were spent on calls to range function. After spending a few minutes googling for an explanation, it was apparent to me. When calling range function, it creates a list of all objects in the specified range all at once. In my case, the range call in the outer loop creates one million number objects right away. And that’s why it was slow.

The remedy? Use xrange instead of range. xrange is similar to range but it is a generator object which does not create any object immediately, but rather when you pull from the generator.

Changing range to xrange in the above code reduced the running time from 60 to 6 seconds right away. The moral of this story is to consider using xrange instead of range when the number is large. Note that this only applies to Python 2.x though. In Python 3 range provides an iterator over range and thus xrange was removed.

Continue further, cProfile showed that the time-consuming section now is calls to raw_input. Yes, I naively read a million line of inputs by calling raw_input in a loop. After changing the part to using sys.stdin.readlines(), the running time was decreased to 2.7 seconds. Here is the final version of my code:

(num_stations, fuel) = [int(x) for x in raw_input().split()]
# read station distances
dist = [int(x) for x in sys.stdin.readlines()]

stops = [MAX_DIST] * len(dist)
num_sols = [0] * len(dist)
stops[0] = 0
num_sols[0] = 1
for i in xrange(1, len(dist)):
  for j in xrange(i - 1, -1, -1):
    # backtrack until out of fuel range
    if dist[i] - dist[j] > fuel: break
    # assert dist[i] - dist[j] <= fuel
    cur_stop = 1 + stops[j]
    if stops[i] > cur_stop: # new min stops
      stops[i] = cur_stop
      num_sols[i] = num_sols[j] # reset number of solutions
    elif cur_stop == stops[i]: # another optimal solution
      num_sols[i] += 1
print "%d %d" % (stops - 1, num_sols) # remove final stop

I believe that there are still parts which can be further optimized, ideally to meet the 2 seconds time limit. If you have any idea or spot anything wrong, please let me know in the comment.

Hello world!

2010-01-27T00:00:00-08:00

Finally I have my own blog and website. Don’t ask me why it took so long. Anyway, I am still not sure what the content of this blog would be. While figuring that out, it would probably be random things that come up to my mind. It might not be as bad as it sounds though.