Adam Horvath's blog

One of the most common usages of hash tables is to count/group occurrences of different elements in it, something like this: dict[“key”]++ . The direct access hash table outperforms any generic implementations, even though hash tables are supposed to be excellent at this task. Although this operation is considered to be constant time ( O(1) ), the generic implementations of dictionaries do an unnecessary step: double hashing of the key. If we look at the disassembled code of the example above, this is what happens in the background (.NET ILDASM simplified code snippet): get_Item(!0) // retrieve the item using the key (hashing happens) ldc.i4.1 // store the result integer add // increment the integer set_Item(!0,!1) // store the new value with the original key (hashing happens) Generally hashing is fairly quick, however, if the key is a string for instance, the hash function has to check every character of the string to create the hash value, which is an integer. The CPU is reall...

Quick select algorithm (Hoare's selection algorithm) – select the Kth element or  the first K element  from a list in linear time Working with large datasets is always painful, especially when it needs to be displayed in a ‘human readable’ format. It is a very frequent task to display only the largest, newest, most expensive etc. items. While sorting the whole dataset definitely gives a correct result, it is much slower than it needs to be – it needs at least O(n*log(n)) time and an it often uses recursion for the sorting, so in practice it can be quite slow. The quick select algorithm can get the top K element from a list of N items in linear time, O(n), with a very reasonable multiplication factor. The quick select does not use recursion so the performance is great for even large datasets. Algorithm The idea of the quick select is quite simple: just like with quicksort, select a random element from the list, and place every item that is smaller to the first half o...

Displaying optional content for high resolution or mobile users on your web page The W3C Media Queries provide a great opportunity to display a webpage content differently based on the capabilities of the user’s browser or machine. This can be especially useful for mobile browsers or variable screen width/resolution. Many webpages do not care at all if you have a high resolution screen, the content will stay static and will just waste the extra space on your monitor –as two wide white columns on the left and right. However, without any special programming we can provide extra, non essential but useful content to the users with a decent resolution (or remove these for mobile devices). If we want to target a specific resolution, we can address them using the following CSS media query: @media only screen and ( max-width : 600px) { /* CSS styles here*/ } These styles will only apply on the users screen if the browser window size is maximum 600 pixels – meaning probably on s...

If you ever envied Safari on Mac - or to be precise envied how smooth it's scrolling was compared to Google Chrome, it's time for a simple fix! Open up advanced/experimental settings of Google Chrome by visiting chrome://flags/ Find a setting called   GPU compositing on all pages and Enable it. This settings requires a restart, so go ahead, restart Chrome. When it comes back, the scrolling should be as smooth as with Safari!

The power of two - fast division and modulo operations There are some - admittedly rare - cases, when the division and modulo operations are responsible for a great percent of the total runtime. Such case might be when a high performance circular array positioning is calculated and the pointers use the modulo (ptr = curr % ArraySize) operation to calculate the real position in the current array. The good news is, that if all the variables are known at compile time, the compiler will help to optimise the division/modulo. The bad news is, that with a dynamic sized array, the compiler won't help anything. Even worse news is that both the DIV and MOD operations are pretty slow on every CPU (or at least  slower than other atomic operations). Speeding it all up If the pointer calculation in the previous example is a concern, there is a way to speed it up: use the powers of two! If the divider is a power of two, both the division and modulo operations become extremely simple:...

First of all, let me try to highlight that if I’m downloading YouTube videos to watch offline I don’t feel I am stealing their content. The content was already there, published, free to watch but in some cases it’s just not convenient to sit in front of the computer to watch an hour-long presentation. I study a lot with my iPad – watching presentations and lectures on it while I cannot really do anything else (on the bus). However, trying to watch a video on a 3G internet connection just does not cut it. I had to find a way to download YouTube videos and save them to my iPad. Catch network traffic The simplest way is to start watching the video, open Chrome’s developer toolbar (CTRL+SHIFT+J or COMMAND+OPTION+J on Mac), switch to the network tab, and check which URL takes so long to download. Copy-paste this URL into a new window and ready to download the MP4 formatted video. Most of the cases it works, but for some large videos YouTube uses around 10mb chunks for the d...