Python sparse list memory / time benchmarks

Results using Python 2.7.12

Testing size 100
⏱	allocate empty list                     0.00001 seconds
	Empty list size: 888
⏱	populate list with fake results         0.00003 seconds
	“Populated” list size: 5848

⏱	allocate empty sparse list              0.00000 seconds
	Empty list size: 808
⏱	populate sparse list with fake results  0.00003 seconds
	“Populated” list size: 6776

Testing size 1000
⏱	allocate empty list                     0.00001 seconds
	Empty list size: 8088
⏱	populate list with fake results         0.00002 seconds
	“Populated” list size: 13048

⏱	allocate empty sparse list              0.00000 seconds
	Empty list size: 808
⏱	populate sparse list with fake results  0.00003 seconds
	“Populated” list size: 6776

Testing size 10000
⏱	allocate empty list                     0.00007 seconds
	Empty list size: 80088
⏱	populate list with fake results         0.00003 seconds
	“Populated” list size: 85048

⏱	allocate empty sparse list              0.00001 seconds
	Empty list size: 808
⏱	populate sparse list with fake results  0.00003 seconds
	“Populated” list size: 6776

Testing size 100000
⏱	allocate empty list                     0.00063 seconds
	Empty list size: 800088
⏱	populate list with fake results         0.00004 seconds
	“Populated” list size: 805048

⏱	allocate empty sparse list              0.00001 seconds
	Empty list size: 808
⏱	populate sparse list with fake results  0.00005 seconds
	“Populated” list size: 6776

Testing size 1000000
⏱	allocate empty list                     0.00555 seconds
	Empty list size: 8000088
⏱	populate list with fake results         0.00004 seconds
	“Populated” list size: 8005048

⏱	allocate empty sparse list              0.00001 seconds
	Empty list size: 808
⏱	populate sparse list with fake results  0.00003 seconds
	“Populated” list size: 6776

Results using Python 3.5.2

Testing size 100
⏱	allocate empty list                     0.00000 seconds
	Empty list size: 880
⏱	populate list with fake results         0.00003 seconds
	“Populated” list size: 5360

⏱	allocate empty sparse list              0.00001 seconds
	Empty list size: 664
⏱	populate sparse list with fake results  0.00004 seconds
	“Populated” list size: 5656

Testing size 1000
⏱	allocate empty list                     0.00001 seconds
	Empty list size: 8080
⏱	populate list with fake results         0.00002 seconds
	“Populated” list size: 12560

⏱	allocate empty sparse list              0.00000 seconds
	Empty list size: 664
⏱	populate sparse list with fake results  0.00003 seconds
	“Populated” list size: 5656

Testing size 10000
⏱	allocate empty list                     0.00005 seconds
	Empty list size: 80080
⏱	populate list with fake results         0.00002 seconds
	“Populated” list size: 84560

⏱	allocate empty sparse list              0.00001 seconds
	Empty list size: 664
⏱	populate sparse list with fake results  0.00003 seconds
	“Populated” list size: 5656

Testing size 100000
⏱	allocate empty list                     0.00114 seconds
	Empty list size: 800080
⏱	populate list with fake results         0.00002 seconds
	“Populated” list size: 804560

⏱	allocate empty sparse list              0.00001 seconds
	Empty list size: 664
⏱	populate sparse list with fake results  0.00004 seconds
	“Populated” list size: 5656

Testing size 1000000
⏱	allocate empty list                     0.00484 seconds
	Empty list size: 8000080
⏱	populate list with fake results         0.00003 seconds
	“Populated” list size: 8004560

⏱	allocate empty sparse list              0.00001 seconds
	Empty list size: 664
⏱	populate sparse list with fake results  0.00004 seconds
	“Populated” list size: 5656

test_heap_usage.py

#!/usr/bin/env python
# encoding: utf-8

from __future__ import print_function, unicode_literals

from contextlib import contextmanager
from timeit import default_timer
import gc
import sys

from pympler.asizeof import asizeof
from sparse_list import SparseList


@contextmanager
def time_block(message=''):
    print('⏱\t%-40s' % message, sep='\t', end='')

    start_time = default_timer()

    yield

    elapsed = default_timer() - start_time

    print('%0.000005f seconds' % elapsed)


def measure_performance(f, size):
    gc.collect()

    l = f(size)
    assert len(l) == size
    assert sum(1 for i in l if i is not None) == 10
    assert len([i for i in l if i is None]) == size - 10


def test_list(size):
    with(time_block('allocate empty list')):
        l = [None] * size

    print('\tEmpty list size:', asizeof(l))

    with(time_block(u'populate list with fake results')):
        for i in range(0, 10):
           l[50 + i] = dict((('this is a complex %d' % i, 'object like a haystack search result: %d' % i), ))

    print('\t“Populated” list size:', asizeof(l))

    return l


def test_sparse_list(size):
    with(time_block('allocate empty sparse list')):
        l = SparseList(size)

    print('\tEmpty list size:', asizeof(l))

    with(time_block('populate sparse list with fake results')):
        for i in range(0, 10):
           l[50 + i] = dict((('this is a complex %d' % i, 'object like a haystack search result: %d' % i), ))

    print('\t“Populated” list size:', asizeof(l))

    return l


gc.disable()  # We'll call gc.collect during each run to avoid confusion

for exp in range(2, 7):
    size = 10 ** exp
    print('Testing size', size)

    measure_performance(test_list, size)
    print()

    measure_performance(test_sparse_list, size)
    print()