Skip to main content

a list-like type with better asymptotic performance and similar performance on small lists

Project description

The BList is a type that looks, acts, and quacks like a Python list, but has better performance for for modifying large lists. For small lists (fewer than 128 elements), BLists and the built-in list have very similar performance.

Here are some of the use cases where the BLists asymptotically outperforms the built-in list:

Use Case BList list
Insertion into or removal from a list O(log n) O(n)
Taking slices of lists O(log n) O(n)
Making shallow copies of lists O(1) O(n)
Changing slices of lists O(log n + log k) O(n+k)
Multiplying a list to make a sparse list O(log k) O(kn)
Maintain a sorted lists with bisect.insort O(log**2 n) O(n)

So you can see the performance of the BList in more detail, several performance graphs available at the following link: http://stutzbachenterprises.com/blist/

Example usage:

>>> from blist import *
>>> x = blist([0])             # x is a BList with one element
>>> x *= 2**29                 # x is a BList with > 500 million elements
>>> x.append(5)                # append to x
>>> y = x[4:-234234]           # Take a 500 million element slice from x
>>> del x[3:1024]              # Delete a few thousand elements from x

For comparison, on most systems the built-in list just raises MemoryError and calls it a day.

Installation instructions

Python 2.5 or higher is required. If building from the source distribution, the Python header files are also required. In either case, just run:

python setup.py install

The BList module will be installed in the ‘site-packages’ directory of your Python installation. (Unless directed elsewhere; see the “Installing Python Modules” section of the Python manuals for details on customizing installation locations, etc.).

If you downloaded the source distribution and wish to run the associated test suite, you can also run:

python setup.py test

which will verify the correct installation and functioning of the package. The tests regrettably do not work on Python 3.

Feedback

We’re eager to hear about your experiences with the BList. Please send all feedback and bug reports to daniel@stutzbachenterprises.com. Bug reports and feature requests may be reported on our bug tracker at: http://github.com/DanielStutzbach/blist/issues

How we test

In addition to the tests include in the source distribution, we perform the following to additional rigor to our testing process:

  1. We use a “fuzzer”: a program that randomly generates list operations, performs them using both the BList and the built-in list, and compares the results.
  2. We use a modified Python interpreter where we have replaced the array-based built-in list with the BList. Then, we run all of the regular Python unit tests.

Project details


Release history Release notifications

History Node

1.3.6

History Node

1.3.5

History Node

1.3.4

History Node

1.3.3

History Node

1.3.2

History Node

1.3.1

History Node

1.3.0

History Node

1.2.1

History Node

1.2.0

History Node

1.1.1

History Node

1.1.0

This version
History Node

1.0.2

History Node

1.0.1

History Node

1.0.0

History Node

0.9.17

History Node

0.9.16

History Node

0.9.15

History Node

0.9.14

History Node

0.9.13

History Node

0.9.12

History Node

0.9.11

History Node

0.9.10

History Node

0.9.9

History Node

0.9.8

History Node

0.9.7

History Node

0.9.6

History Node

0.9.5

History Node

0.9.4

History Node

0.9.3

History Node

0.9.2

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size & hash SHA256 hash help File type Python version Upload date
blist-1.0.2.tar.gz (97.3 kB) Copy SHA256 hash SHA256 Source None Oct 15, 2009
blist-1.0.2.win32-py2.6.exe (252.1 kB) Copy SHA256 hash SHA256 Windows Installer 2.6 Oct 21, 2009
blist-1.0.2.win32-py3.1.exe (249.0 kB) Copy SHA256 hash SHA256 Windows Installer 3.1 Oct 21, 2009

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging CloudAMQP CloudAMQP RabbitMQ AWS AWS Cloud computing Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page