Why I like dictionaries so much?

Complexity in data structures is defined for each of its actions (access, insert, delete, search) and dictionaries shine on three of these operations. Because of this, they become useful in reducing the complexity of many algorithms when you apply a clever use of them. For dictionaries, accessing, deleting and inserting operations could be achieved quickly despite the number of elements they have. So let’s pick up our headset and get to coding while we listen to smooth jazz (hint hint, Kenny G).

Let’s consider the following problem: Write a function that prints a count of how many times all letters appear in a given string.  To simplify the use of dictionaries I will decide to use PHP, but this approach could be seen in almost any language.

One approach without dictionaries could be the following: 

<?php
$string = "Hello World!";
$split = str_split($string);

getCount($split);

function getCount($split) {
while(!empty($split)) {
$count = 1;
$newArray = array();
$firstChar = $split[0];
for($i = 1; $i < count($split); $i++) {
$element = $split[$i];
if($element != $firstChar) {
$newArray[] = $element;
} else {
$count++;
}
}
$split = $newArray;
echo $firstChar . " = " . $count . "\n";
}
}

As you can see this getCount(…) function will need to traverse the data in the array almost as many times as there are elements in it. This accomplishes the task, but the cost is exponentially proportional to the size of the array.   Let’s simplify this with dictionaries, shall we? 

<?php
$string = "Hello World!";
$split = str_split($string);

getCountDictionary($split);

function getCountDictionary($split) {
$dict = [];
foreach($split as $char) {
if (!isset($dict[$char])) {
$dict[$char] = 1;
} else {
$dict[$char]++;
}
}

print_r($dict);
}

Excellent, now the code is cleaner and more effective. With this new approach, we traverse the array only once during processing and since the access and insert operations in a dictionary are of complexity O(1), we can be sure we do not unnecessarily go through the array many times for the same solution, turning an exponential algorithm into a linear one. Dictionaries are remarkably useful when you can think in terms of categories. Whenever I see myself writing a nested loop, like in the first example, I put some effort into thinking about how to use dictionaries to accomplish the same task. 

You should always consider dictionaries when you are accessing, inserting, and deleting elements from a data structure and their order is not relevant.

Leave a Reply

Your email address will not be published. Required fields are marked *