War and Peace Insertion Showdown

warandpeace.py

import timeit

class Link:
    empty = ()

    def __init__(self, first, rest=empty):
        self.first = first
        self.rest = rest

    def insert_at_start(self, value):
        original_first = self.first
        self.first = value
        self.rest = Link(original_first, self.rest)

# From https://www.gutenberg.org/files/2600/2600-0.txt
filename = "warandpeace.txt"
big_file = open(filename, encoding="utf8")
big_str = big_file.read()
# Make a big python list
big_list = big_str.split(" ")

# Make a big linked list
big_ll = Link(big_list[0])
word_num = 1
current_link = big_ll
while word_num < len(big_list):
   current_link.rest = Link(big_list[word_num])
   current_link = current_link.rest
   word_num += 1

# Time the Python list
time_taken = timeit.timeit(lambda: big_list.insert(0, "happy"), number=100000)
print(time_taken)

# Time the linked list
time_taken = timeit.timeit(lambda: big_ll.insert_at_start("happy"), number=100000)
print(time_taken)

I feel that the claims of linked list superiority based on head-insert performance are dangerously misleading:

>>> from perf import *
>>> times = timings(10000)
link_insert_head: 0.037854647962376475
list_insert_head: 0.12644985306542367
link_insert_mid: 18.999568659928627
list_insert_mid: 0.06249492010101676
link_insert_end: 21.65465004602447
list_insert_end: 0.00235574203543365
link_search: 0.02571259206160903
list_search: 0.0014865719713270664
link_index: 0.02658910397440195
list_index: 0.001087040058337152
link_len: 0.02999969699885696
list_len: 0.001140614040195942
link_sum: 0.030164887895807624
list_sum: 0.001844951999373734

from https://gist.github.com/Iiridayn/f31e3b73983314d9d46e7cb7839aa2b1

Note that linked lists were only 4x faster when inserting at the head on my machine, and lists were superior in all other tests - overwhelmingly so with inserting at the midpoint or at the end.

Thanks for sharing your timings! This was a classroom example for CS61A to motivate why linked lists might be desirable in some situations. I use lists for most of my production Python (or dicts/sets/etc as makes sense).