DEV Community

Cover image for How I Built My Own List Type in Python With a String
Simon Egersand 🎈
Simon Egersand 🎈

Posted on • Edited on • Originally published at prplcode.dev

How I Built My Own List Type in Python With a String

#python #programming #fun

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)