Get your books more cheaply – possibly

I often link from this site to Amazon – the hope is that you might buy some of the things I talk about and then I get a (small) return which I can use to buy things I like at Amazon. It doesn’t work too well for me – I think I have made 26 pence in the last six months or so. Back when I ran a blog about politics it was a bit more successful – people obviously thought I had something worthwhile to say on politics, but less so on science and computing. For shame. (Actually, another factor is that the vast majority of this blog’s readership is from outside the UK.)

Image representing Amazon as depicted in Crunc...
Image by None via CrunchBase

So, I guess I am not exactly cutting my own throat when I tell you that recent legal changes in the UK may mean that while Amazon is a great place to see what is available and even to look who to buy from, it might not make financial sense to buy from them directly.

Until recently Amazon exercised some pretty heavy controls over the prices third-party sellers could charge customers who bought directly from their (the third party’s) website. In essence they forbid them from charging less than they offered through Amazon, at pain of being delisted from Amazon.

But that approach has now been ruled anti-competitive and so it might just make sense to use Amazon to window shop and to buy directly from the third party seller.

Here’s a real example I have just spotted.

The Pragmatic Programmer is a very well regarded book on programming (often compared to the brilliant Programming Pearls, a book absolutely every programmer should read) – one I was thinking of buying for myself. Amazon sell it for £22.39 – including the price of delivery.

The two cheapest third party sellers offer it for £17.86 and £17.87 respectively, but also charge an additional £2.80 for delivery – bumping up the price to £20.66 and £20.67, still cheaper than buying directly from Amazon though. But if you go to the second of these two suppliers – UK Paperback Shop – they are selling it direct for £18.76.

Other sellers may even be cheaper – I haven’t checked.

Of course, there might be other reasons why you want to shop through Amazon, but it is worth remembering that it might pay to look around. I am guessing that the savings will be most easily realised if you are buying low volume or specialist or technical books.

Of course if you want to buy a Kindle Tablet I’d love it if you did it through that link 🙂

Better algorithm found

An animation of the quicksort algorithm sortin...
Image via Wikipedia

Late last night, in a state of some despair, I pleaded for computing power help with my MSc project. Today, having thought about it long and hard I found a better algorithm and speeded the whole thing up by a factor of 50.

Like, I am sure, many people previously in my position, my inspiration was the classic Programming Pearls.

This is a Birkbeck set text but it’s also one that I did not read when I should have last year – or rather I just read a small part of it. Luckily I am systematically going through it now and was yesterday reading about how much of a difference a better algorithm can make – not that I did not know this, but it helped provide the determination to find one.

So what did I do. Firstly I realised that there was a specialist implementation of the Java Map interface that, as the Javadoc file explicitly says, is good for LRU caches (essentially what I am seeking to model): LinkedHashMap.

This sets up a last-accessed order and so means that it is no longer necessary to search through the whole Map to find the out-of-date pages. Using an Iterator and an EntrySet I only need to get to the first page that is not out-of-date and stop.

When I was checking that worked I noticed that temporal locality meant that in many cases the LRU page was still inside the time frame I was seeking to check – in other words literally billions of checks for outdated pages were taking place needlessly. As pages in the cache cannot get “older” (ie there reference time cannot go backwards), at time \tau + \delta the oldest page cannot be any older than it was at \tau – hence if we do not check until we have reached the point here we need to expire pages with time \tau we will not miss any needed evictions.

The result of these two changes is a massive speed up in the code – by a factor of 40 – 50.