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

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)