I had this idea of building a list type in Python just using the string type. Sounds stupid, right? “Crazy idea; bad pitch” as one of my old colleagues used to say. I knew it was stupid, and that was the point! The idea came to me a few years ago when I was implementing a linked list. “In what other ways can I represent a list?” I thought. “Let me build a list type using a string!”
Choosing Python 🐍
Python is fun! It’s quick to get started with, there’s a big community and there are mature tools to help you. I could have chosen JavaScript but I’m less experienced with Python and I wanted to learn more about it.
List Type Design
This is the part where most brain power is used — usually. For me it was quick. I decided to design my list type in a string list this:
element1,element2,element3
I chose "," as the delimiter between elements, mostly for readability.
Just like in (untyped) Python, my list was gonna be heterogeneous, which means I can store elements of different types in the same list. I took this decision to align with the native list type and to simplify the implementation.
List API Design 📄
Next step was to decide the API for my new list type. I looked at the API for Python’s list and decided to implement most of them. Some of them, like copy() and reverse() I chose to exclude.
Implementation 😌
This was the fun part! Initialising a new list was easy, just create an empty string. Same for add(), just append it to the end with the delimiter in between.
__list: str = ""
__delimiter: str = ","
def add(self, element: object) -> None:
if self.is_empty():
self.__list = element
else:
self.__list += "{}{}".format(self.__delimiter, element)
I also added support for remove() which was slightly more complicated.
def remove(self, element: object) -> bool:
for i in range(self.size()):
if self.get(i) == element:
self.remove_at(i)
return True
return False
I ended up implementing 12 methods but I don’t want to clutter this post with any more code. See below for a link to the repo.
Performance 🚀
Once I had implemented my list type I was super curious how it performed in comparison to the native list type. I decided to benchmark all my new methods, and here are the results:
List Function Description N Result
----------------------------------------------------------------------------------------------------------
Native constructor new instance with 100 strings 10000 7.07ms
SlowList constructor new instance with 100 strings 10000 1926.76ms
----------------------------------------------------------------------------------------------------------
Native constructor new instance with 100 ints 10000 5.95ms
SlowList constructor new instance with 100 ints 10000 1499.77ms
----------------------------------------------------------------------------------------------------------
Native constructor new instance using of() with 100 strings 10000 6.40ms
SlowList constructor new instance using of() with 100 strings 10000 1868.80ms
----------------------------------------------------------------------------------------------------------
Native constructor new instance using of() with 100 ints 10000 5.77ms
SlowList constructor new instance using of() with 100 ints 10000 1447.82ms
----------------------------------------------------------------------------------------------------------
Native add add strings to list 10000 1.00ms
SlowList add add strings to list 10000 28.26ms
----------------------------------------------------------------------------------------------------------
Native add add ints to list 10000 3.25ms
SlowList add add ints to list 10000 41.65ms
----------------------------------------------------------------------------------------------------------
Native add_at add_at fixed position with string 10000 21.93ms
SlowList add_at add_at fixed position with string 10000 684.87ms
----------------------------------------------------------------------------------------------------------
Native add_at add_at fixed position with int 10000 21.45ms
SlowList add_at add_at fixed position with int 10000 183.11ms
----------------------------------------------------------------------------------------------------------
Native contains contains with string 10000 1.19ms
SlowList contains contains with string 10000 106.24ms
----------------------------------------------------------------------------------------------------------
Native contains contains with int 10000 0.96ms
SlowList contains contains with int 10000 94.71ms
----------------------------------------------------------------------------------------------------------
Native get get last element of list of size 100 10000 0.46ms
SlowList get get last element of list of size 100 10000 104.16ms
----------------------------------------------------------------------------------------------------------
Native index_of index_of last string in list of size 100 10000 15.42ms
SlowList index_of index_of last string in list of size 100 10000 10365.40ms
----------------------------------------------------------------------------------------------------------
Native index_of index_of last int in list of size 100 10000 16.63ms
SlowList index_of index_of last int in list of size 100 10000 7364.60ms
----------------------------------------------------------------------------------------------------------
Native last_index_of last_index_of las string in list of size 100 10000 9.85ms
SlowList last_index_of last_index_of las string in list of size 100 10000 295.06ms
----------------------------------------------------------------------------------------------------------
Native last_index_of last_index_of last int in list of size 100 10000 9.08ms
SlowList last_index_of last_index_of last int in list of size 100 10000 225.17ms
----------------------------------------------------------------------------------------------------------
Native remove remove last string in list of size 100 10000 21.70ms
SlowList remove remove last string in list of size 100 10000 12636.32ms
----------------------------------------------------------------------------------------------------------
Native remove remove last string in list of size 100 10000 21.24ms
SlowList remove remove last string in list of size 100 10000 9124.89ms
----------------------------------------------------------------------------------------------------------
Native remove_at remove_at last int in list of size 100 10000 6.34ms
SlowList remove_at remove_at last int in list of size 100 10000 2270.03ms
----------------------------------------------------------------------------------------------------------
Native size size with string list of size 100 10000 0.80ms
SlowList size size with string list of size 100 10000 9.06ms
----------------------------------------------------------------------------------------------------------
Native size size with int list of size 100 10000 0.94ms
SlowList size size with int list of size 100 10000 7.40ms
----------------------------------------------------------------------------------------------------------
Native set set last string in list of size 100 10000 0.48ms
SlowList set set last string in list of size 100 10000 427.26ms
----------------------------------------------------------------------------------------------------------
Native set set last int in list of size 100 10000 0.55ms
SlowList set set last int in list of size 100 10000 430.91ms
----------------------------------------------------------------------------------------------------------
Native to_string to_string string list of size 100 10000 9.19ms
SlowList to_string to_string string list of size 100 10000 43.74ms
----------------------------------------------------------------------------------------------------------
Native to_string to_string int list of size 100 10000 269.77ms
SlowList to_string to_string int list of size 100 10000 38.11ms
No surprises really. The native list is faster in all the methods except for to_string() where my list is. faster. This is not entirely accurate though because Python’s list doesn’t have a to_string() so I created one by using ''.join(list).
Conclusion
After seeing the results of the benchmarks, the name of the list type became obvious -- SlowList. I’m sure it could be faster and more optimised by someone more knowledgeable on Python than me, but of course it will never be as fast as the native list.
I really enjoyed this project. I knew from the beginning no one would ever use it, or even star it on Github, and that was the root of the enjoyment. I’m so used to thinking I need to deliver value that it was a relief to build something completely useless.
You can find the project on Github.
What’s Next? 🌌
If you think this project is interesting and want to contribute to it there’s a few issues on Github you can look at. I always welcome help 😊
Learn More 👩🏫
For more serious topics on how to grow yourself as a software engineer, check out these posts:
Follow me on Twitter @prplcode
Originally published at https://prplcode.dev
Top comments (0)