⚠ The Built-in Standard Libraries Can Trick You!

Sadly, The built-in standard libraries can trick you! So, pay a closer attention.

OMAR ELGABRY
Feb 17, 2017 · 3 min read

This is just a quick warning note about those folks who use the built-in libraries available at their programming language blindly; without having a clear idea about the complexity and how it’s being implemented.

What seems to you at the mirror is not always true, just get a closer look — huffingtonpost.com

Why It’s too slow?

You may get a logarithmic running time for an associative array, while you’re expecting a constant time in average. This is because it’s being implemented using self-balancing binary search tree instead of using hash tables.

Even though, if you used hash tables, your program might be slow if your objects have a trivial the hash function.

If you’re trying to sort an already sorted array or numbers, and the built-in sort function uses quicksort, you may get a quadratic time if the sort function doesn’t shuffle the array.

A data structure that uses a linked list instead of an array may take a linear time to access an element.

A sorting algorithm that makes poor use of cache memory like heapsort (since it points to nodes far away from each other) is not the same as using a sorting algorithm that checks nearby elements like quicksort, which in turn makes it slower in a lot of situations where caching is important.

A hash table implemented using “linear probing” as a collision resolution technique has a better cache performance over “separate chaining” technique as traversing a linked list has poor cache performance, making the processor cache ineffective.

Why I am running out of memory?

A data structure that uses a linked list instead of an array consume extra memory for the links and node creation and management.

A sorting algorithm that uses extra space for the auxiliary array of size N like in mergesort is not the same as sorting in-place like in quicksort.

A hash table with a load factor tends to zero has more wasted space unless the hash table uses a resizing array to make sure the table is always at a suitable size; less wasteful and saves memory.

Why It gives me unexpected output?

Getting one level deeper worth it.

Iterating over the keys in an associative array might print the items in no particular order, while you’re expecting to be printed in order.

You may accidentally delete key-value pairs from your associative array because the insert operation deletes the key-value pair if the value is null.

A method that returns a null whenever there is no suitable value to be returned is not the same as throwing an exception.

Sorting a table of students according to their names, then sorting according to their sections, mightn’t guarantee stability (students are no longer sorted by name) if the sort function uses a sorting algorithm like quicksort instead of mergesort (or insertion sort).

Can I grow and shrink?

A data structure that’s able to grow and shrink at any size using a resizing array is much suitable in most of the application than using a fixed size array.

However, the overhead of resizing operation can add an additional cost if all what you need is a fixed size array with an initial capacity.

Why It doesn’t change?

A data type that can’t be modified once it’s created is not the same as a dynamic one.

If you’re doing a lot of manipulation on a string for example, which is immutable by the built-in library, you’re actually creating a new string every time you make an update on the existing one unless you use mutable data type.


It’s worth to mention that the code in your programming language libraries has more operations, and therefore, you can’t assume much about the performance.

So, when to use the built-in implementation?

Use your own implementation as long as you it’s available and well-tested.

Maybe later on after being an experienced programmer who understand how to use your programming language libraries code efficiently.

To do that, you have to refer back to the language documentation, and ask & test your code whenever you’re not sure.

OmarElGabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

OMAR ELGABRY

Written by

Software Engineer. Going to the moon 🌑. When I die, turn my blog into a story.

OmarElGabry's Blog

This is my freedom area. Don't underestimate it. The devil is in the detail.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade