Archive

Archive for August, 2010

Use a Hash Map instead

August 10, 2010 Leave a comment

I learned a valuable lesson just before coming to Sentry that I’ve shared with my co-workers and thought I’d share here at well.

If you find yourself searching through an array try to turn it into a hash/map instead.

Instead of an O(N) operation (looking at every element in an array), you can often turn it into a direct access hash map O(1).  Remember Big-O notation? Make sure you keep that in your hip pocket.  You never know who may ask about it (Amazon and Google will).

You rarely write your own search function since most languages provide one for you.  The PHP function in_array($needle, $haystack)) is your O(N) search and will only get worse as the size of the array gets bigger.  It’s tempting to throw that in whenever needed.

Here’s a quick PHP snippet that I recently worked through with another developer.

// $worksheet_names is still an array, but we
// use the index/key of the array instead of the value.
$worksheet_names = array();

foreach ($results as $row) {
     ...
     // instead of in_array, we look directly at the index.
     // previously in_array($name, $worksheet_names)
     while (isset($worksheet_names[$name])) {
         $name = substr($name,0,24) . "($duplicate_sheet_counter)";
         $duplicate_sheet_counter += 1;
     }
     $row['worksheet_name'] = $name;
     // previously $worksheet_names[] = $name;
     $worksheet_names[$name] = true;
}
Other Uses
Another helpful trick is to keep track of duplicate values in an array.  What’s the easiest way to get the number of occurrences for all these values?
<?php

$a = array (1, 2, 3, 3, 1, 4, 5, 3, 4);

$map = array();
foreach  ($a as $entry) {
     if (!isset($map[$entry])) {
          $map[$entry] = 1;
     } else {
          $map[$entry]++;
     }
}

print_r($map);
Array
(
    [1] => 2
    [2] => 1
    [3] => 3
    [4] => 2
    [5] => 1
)
Categories: Uncategorized Tags: