Small screen big window trick

Ever happened to you that you opened some application on your netbook with screen resolution small x even smaller and the application contains big unresizable window? And do you know the frustration when the thing you need to click (save/ok/whatever) is in the bottom part of the window which is invisible to you? Then you know what I am talking about. Especially because you cannot move window above top of the screen. Well, at least, not with only mouse. Today, I am proud to introduce you a linux (gnome) solution for this problem. It is called ALT+F7 and it is "move window" shortcut. Except, for some strange reason, there is no limitation on where you move the window with this shortcut, i.e. you can move it over top edge of the screen!

PHP and consistency? No way

Today I was debugging my PHP code and trying to figure out why my references (quite nasty feature of PHP but sometimes required) do not work only to learn that my bug was in array_key_exists function call.

So, try to guess what are the arguments for array_key_exists. If you think it is

array_key_exists($array, $key)

you are quite wrong, just read the documentation:

array_key_exists ( mixed $key , array $search )

You may say, ok, this is just a convention. Well, not exactly, looking at the manual, one can summarize the functions as following:

array array_change_key_case ( array $input [, int $case = CASE_LOWER ] )
array array_chunk ( array $input , int $size [, bool $preserve_keys = false ] )

vs

array array_combine ( array $keys , array $values )
array array_fill_keys ( array $keys , mixed $value )
mixed array_search ( mixed $needle , array $haystack [, bool $strict = false ] )
bool in_array ( mixed $needle , array $haystack [, bool $strict = FALSE ] )

But the best part is this (can you spot the black sheep?):

array array_filter ( array $input [, callable $callback = "" ] )
array array_map ( callable $callback , array $arr1 [, array $... ] )
mixed array_reduce (array $input, callable $function [, mixed $initial = NULL ] )

In summary, PHP requires a manual, unless you are good at guessing/coin flipping.

Bonus from the manual:

string implode ( string $glue , array $pieces )
string implode ( array $pieces )

Join array elements with a glue string. Note: implode() can, for historical reasons, accept its parameters in either order. For consistency with explode(), however, it may be less confusing to use the documented order of arguments.

Round and round around the floats

Isn't rounding numbers easy? Well, not always. And not always consistent:

Python (the same for C/C++,):

>>> "%.1f" % 0.05
'0.1'
>>> "%.1f" % 0.15
'0.1'
>>> "%.1f" % 0.25
'0.2'
>>> "%.1f" % 0.35
'0.3'
>>> "%.1f" % 0.45
'0.5'
>>> "%.1f" % 0.55
'0.6'
>>> "%.1f" % 0.65
'0.7'
>>> "%.1f" % 0.75
'0.8'
>>> "%.1f" % 0.85
'0.8'
>>> "%.1f" % 0.95
'0.9'

But that is nothing compared to results obtained from MySQL today:



+--------------+----------------+
| sum(penalty) | count(penalty) |
+--------------+----------------+
|         5091 |             24 |
+--------------+----------------+

+------------------------+--------------+
| ROUND(avg(penalty), 2) | avg(penalty) |
+------------------------+--------------+
|                 212.12 |      212.125 |
+------------------------+--------------+

+-------------------+-------------------+

| ROUND(212.125, 2) | ROUND(5091/24, 2) |

+-------------------+-------------------+

|            212.13 |            212.13 |

+-------------------+-------------------+

To hash, to map?

As the question in the title says, in this post I will be comparing the two C++ std library algorithms, unordered_map (formerly known as hash_map) and map. The focal point of the comparison is the memory -- which algorithm is more effective? For this purpose, I created a simple program which inserts N random keys into the data structure. Then I needed to obtain a memory information. At the first glance, it seemed that

mallinfo().uordblks

will be sufficient. However, after going through a painful excercise with the std::vector, it seems that vector (and therefore probably also unordered_map) use some other weird technique -- instead of malloc()-ing the data, the vector mmap()-s some memory blocks! Thus, the real memory usage is more like

int mem = mallinfo().hblkhd + mallinfo().uordblks;

Anyway, here is the program:

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
using namespace std;

#define HASH 0

#if HASH
  #include <unordered_map>
  typedef unordered_map<int, int> mymap;
  const char* text = "hash";
#else
  #include <map>
  typedef map<int, int> mymap;
  const char* text = "map";
#endif

const int Ki = 1000;
const int Mi = 1000 * Ki;

const int TESTS = 5;
int test_sizes[TESTS] = {Ki, 10 * Ki, 100 * Ki, Mi, 10 * Mi};

int main() {
  mymap mapa;
  for (int t = 0; t < TESTS; t++) {
    while (mapa.size() < test_sizes[t]) {
      int k = rand();
      mapa[k]++;
    }
    // total memory (malloc + mmap)
    int mem = mallinfo().hblkhd + mallinfo().uordblks;
    printf("%s: Items: %d, Mem: %d, per-entry: %.1f\n", text, 
          test_sizes[t], mem, mem * 1.0 / test_sizes[t]);

  }
}

And the results:
(Note that  2 integers (key&value) consume 8 bytes).

map: Items: 1000, Mem: 48000, per-entry: 48.0
map: Items: 10000, Mem: 480000, per-entry: 48.0
map: Items: 100000, Mem: 4800000, per-entry: 48.0
map: Items: 1000000, Mem: 48000000, per-entry: 48.0
map: Items: 10000000, Mem: 480000000, per-entry: 48.0

hash: Items: 1000, Mem: 46016, per-entry: 46.0
hash: Items: 10000, Mem: 441504, per-entry: 44.2
hash: Items: 100000, Mem: 4211808, per-entry: 42.1
hash: Items: 1000000, Mem: 40454240, per-entry: 40.5
hash: Items: 10000000, Mem: 463691872, per-entry: 46.4

The conclusion? Both hashing and binary trees use roughly the same amount of memory (hashing a bit less but it is fluctuating as the hash-table is resized). And the overhead is quite big -- 5 to 6 times for the integer key-value pair.

Howto: install dctcp (or new kernel) in debian

As I was fighting with DCTCP (datacenter TCP) installation last week, here is the recipe on how to win this battle. Some of the steps are trivial but some of them like reading the old tactics and ensuring that you really won are not an obvious steps for new generals.


Prepare for the battle:
[ ~ ]>sudo apt-get install kernel-package libncurses5-dev fakeroot


Get instructions for operation "dctcp":
[ ~ ]>mkdir dctcp
[ ~ ]>cd dctcp
[ ~/dctcp ]>wget  http://www.stanford.edu/~alizade/Site/DCTCP_files/dctcp-2.6.38.3-rev1.1.0.tgz
[ ~/dctcp ]>tar -xvvf dctcp-2.6.38.3-rev1.1.0.tgz


Get the battle plan:
[ ~/dctcp ]>wget http://www.kernel.org/pub/linux/kernel/v2.6/linux-2.6.38.3.tar.bz2
[ ~/dctcp ]>tar jxvf linux-2.6.38.3.tar.bz2


Prepare supplies:
[ ~/dctcp ]>cp dctcp-2.6.38.3-rev1.1.0/dctcp-2.6.38.3-rev1.1.0.patch linux-2.6.38.3
[ ~/dctcp ]>cd  linux-2.6.38.3
[ ~/dctcp/linux-2.6.38.3] patch -p1 < dctcp-2.6.38.3-rev1.0.0.patch


Read old battle tactic:
[ ~/dctcp/linux-2.6.38.3 ]>cp /boot/config-x.y.z-amd64 .config
[ ~/dctcp/linux-2.6.38.3 ]>make oldconfig


Begin the battle:
[ ~/dctcp/linux-2.6.38.3 ]>fakeroot make-kpkg clean
[ ~/dctcp/linux-2.6.38.3 ]>fakeroot make-kpkg kernel_image

Battlefield after the battle:
[ ~/dctcp/linux-2.6.38.3 ]>cd ..
[ ~/dctcp ]>sudo dpkg -i linux-image-2.6.38.3_2.6.38.3-10.00.Custom_amd64.deb


Ensure the victory by signing boot contracts:
[ ~/dctcp ]>cd /boot
[ /boot ]>sudo mkinitramfs -o initrd.img-2.6.38.3 2.6.38.3
[ /boot ]>sudo update-grub
[ /boot ]>sudo reboot

Google geocoder API without hitting the rate-limit?

While developing my new application which uses reverse geocoding from Google Maps API v3, I came across the problem of rate-limiting the queries. Google happily returns "OVER_QUERY_LIMIT" instead of the result if you fire the requests rapidly. Sadly, the API does not solve this (which is quite stupid as the people must come up with workarounds). Anyway, here is a simple rate-limiter which should work in most cases, just replace

var geocoderService = new google.maps.Geocoder();

with

var geocoderService = {
    geocoder : new google.maps.Geocoder(),
    queue : [],
    delay: 2000, // in milliseconds
    timer: null,
    geocode: function(request, callback) {
        this.queue.push([request, callback]);
        if (this.timer == null) {
            this.timer = setInterval(this.processQueue.bind(this), this.delay);
        }
    },
    processQueue: function() {
        if (this.queue.length > 0) {
            var data = this.queue.splice(0, 1)[0];
            var request = data[0];                                                                                                              
            var callback = data[1];
            this.geocoder.geocode(request, callback);
        } else {
            clearInterval(this.timer);
            this.timer = null;
        }
    },
};

Javascript is an exception...

Javascript is an exception ... from any reasonable exception handling. The general construct is

try {
  code_throwing_exceptions();
} catch (e) {
  do_something_with_exception(e);
}

Which seems reasonable. But ... how to catch different exceptions? Well ... it seems that there is only one way and that is manual if-s:


try {
  code_throwing_exceptions();
} catch (e) {
  if (e instanceof RangeError) {
    alert('out of bounds');
  } else if (e instanceof TypeError) {
    alert('type problem!');
  } else {
    raise e;
  }
}

Coder classification part II (right coder)

leftcoder sticks to the left of his editor window word-wraps on 40 characters believes that the true power is in simplicity uses variables and functions that are short: int i,j,x,y,a,b; void fn_a2(int n); the optimal program have average of zero characters per line

rightcoder loves to make veeery loooong statements does not have an editor with word wrapping uses variables and functions according to the following scheme for (int myVariableToIterateSimpleCycle=0; myVariableToIterateSimpleCycle < myNumberOfCycleIterations; MyVariableToIterateSimpleCycle++) int calculateAverageOfSuppliedListOfNumbers(vector<int> suppliedListOfNumbers) the example of an optimal program is one-line database server in C++ hates Python for not being able to put conditionals,cycles and loops on a single line others fear if he says "that is one-liner"

Coder classification part I (topcoder)

topcoder is lazy to scroll writes his own functions near the beginning of the file hopes that this way he may show everyone how cool his code is makes his functions long so other developers need to scroll a lot

bottomcoder writes his own functions near the end of the file hopes that nobody (especially his boss) will ever look so far into the code have a macro to jump to the end of the file the usual edit to his code by other developers starts with //WTF? or //FIXME

Helvetica coding contest II

Thanks Mino for this great idea ;-)

#include <stdio.h>

int main() {

  print(“Helvetica coding contest\n”);

  return 0;

}

#include <stdio.h>

int main() {

  print(“Courier coding contest\n”);

  return 0;

}

#include <stdio.h>

int main() {

  print(“Times coding contest\n”);

  return 0;

}

Helvetica coding contest 2012

Finally, after so long time, I decided to take a test of my coding skills. The Switzerland's hc2 contest is one of the major contests for Swiss high school and university contest. The contest itself is a team contest however. And there is a particular lack of Slovakian ACM team membest here in Lausanne. So I decided to take a wild shot and join Dimitri + one more person from random team-matching. But you know ... plans are usually changing. For such stupid reasons like "washing clothes" (Dimitri somehow failed to reserve washing timeslots in advance and the only ones left were during the competition). 

Therefore, the team (with the random name "The rainbow unicorns") turned out to be formed just by a physicist and me. But I must say it was a splendid combination. During the training session we decided to split responsibilities -- Andrey was being responsible for reading the problem statements and figuring out solutions and I was responsible for transferring them by beating the hell out of the keyboard. And it worked out quite well. In fact, during the first hour, I think we were leading the scoreboard for a while. Anyway, it was a tough competition. 

The moments before the scoreboard freeze (1 hour before the end of the contest) we were on the 4th place with 9 problems solved -- the same number as the second team only higher penalty. The last hour was hectic. We tried to solve different problems but we did not came up with any good solution. Then, after ingenious idea of using apple (taken from free-food area outside of the room) as a model of sphere on which one can draw with a pen (yeah, I was trying a long time to figure out where should I visualize the damn sphere from the problem statement) the idea hit me and we submitted our 10th task. But then nothing. I tried to push one rather-bruteforce solution to the last geometrical task without success (unless you take 9 wrong/time limit exceeded submissions as a success). 

During the final hour and especially before the results announcement (organizers take their time to prepare it) I was getting anxious. What will be the final ranking? How many teams managed to submit the last task during that hour? I was pretty sure that we end up on the fourth place. I was so wrong. At the ceremony, we learnt (from the absence of our name during the backward listing of the teams up to third place) that we actually ended up in top 3. And the surprise after announcing third team was ... hard to describe. It turned out that none of the other teams with 9 tasks before the freeze actually managed to solve something in the last hour. Anyway, thanks organizers for the extremely interesting event and for the tasks -- they were well balanced, not very traditional and very enjoyable. Thanks again!

Silver medal

And the certificate