blist¶

class blist.blist(iterable)¶

The blist is a drop-in replacement for the Python list that provides better performance when modifying large lists. For small lists, the blist and the built-in list have virtually identical performance.

To use the blist, you simply change code like this:
>>> items = [5, 6, 2]
>>> more_items = function_that_returns_a_list()
to:
>>> from blist import blist
>>> items = blist([5, 6, 2])
>>> more_items = blist(function_that_returns_a_list())
Python’s built-in list is a dynamically-sized array; to insert or remove an item from the beginning or middle of the list, it has to move most of the list in memory, i.e., $\Theta\left(n\right)$ operations. The blist uses a flexible, hybrid array/tree structure and only needs to move a small portion of items in memory, specifically using $\Theta\left(\log n\right)$ operations.

Creating a blist from another blist requires $\Theta\left(1\right)$ operations. Creating a blist from any other iterable requires $\Theta\left(n\right)$ operations.

L + L2, L2 + L

Returns a new blist by concatenating two lists.

If the other list is also a blist, requires $\Theta\left(\log m + \log n\right)$ operations. If it’s a built-in list, requires $\Theta\left(m + \log n\right)$ operations, where m is the size of the other list and n is the size of L.

Return type:	`blist`

x in L

Returns True if and only if x is an element in the list.

Requires $\Theta\left(n\right)$ operations in the worst case.

Return type:	`bool`

del L[i]

Removes the element located at index i from the list.

Requires $\Theta\left(\log n\right)$ operations.

del L[i:j]

Removes the elements from i to j from the list.

Requires $\Theta\left(\log n\right)$ operations.

L == L2, L != L2, L < L2, L <= L2, L > L2, L >= L2

Compares two lists. For full details see Comparisons in the Python language reference.

Requires $\Theta\left(n\right)$ operations in the worst case.

Return type:	`bool`

L[i]

Returns the element at position i.

Requires $\Theta\left(\log n\right)$ operations in the worst case but only $\Theta\left(1\right)$ operations if the list’s size has not been changed recently.

Return type:	item

L[i:j]

Returns a new blist containing the elements from i to j.

Requires $\Theta\left(\log n\right)$ operations.

Return type:	`blist`

L += iterable: The same as L.extend(iterable).

L *= k

Increase the length of the list by a factor of k, by appending k-1 shallow copies of the list.

Requires $\Theta\left(\log k\right)$ operations.

iter(L)¶

Creates an iterator over the list.

Requires $\Theta\left(\log n\right)$ operations to create the iterator. Each element from the iterator requires $\Theta\left(1\right)$ operations to retrieve, or $\Theta\left(n\right)$ operations to iterate over the entire list.

Return type:	iterator

L.append(object)¶

Append object to the end of the list.

Requires amortized $\Theta\left(1\right)$ operations.

L.count(value)¶

Returns the number of occurrences of value in the list.

Requires $\Theta\left(n\right)$ operations in the worst case.

Return type:	`int`

L.extend(iterable)¶

Extend the list by appending all elements from the iterable.

If iterable is a blist, requires $\Theta\left(\log m + \log n\right)$ operations. Otherwise, requires $\Theta\left(m + \log n\right)$ operations, where m is the size of the iterable and n is the size of the list initially.

L.index(value[, start[, stop]])¶

Returns the smallest k such that $s[k] == x$ and $i <= k < j$ . Raises ValueError if value is not present. stop defaults to the end of the list. start defaults to the beginning. Negative indexes are supported, as for slice indices.

Requires $\Theta\left(\textrm{start}-\textrm{stop}\right)$ operations in the worst case.

Return type:	`int`

L.insert(index, object)¶

Inserts object before index. The same as s[i:i] = [x]. Negative indexes are supported, as for slice indices.

Requires $\Theta\left(\log n\right)$ operations.

L.pop([index])¶

Removes and return item at index (default last). Raises IndexError if list is empty or index is out of range. Negative indexes are supported, as for slice indices.

Requires $\Theta\left(\log n\right)$ operations.

Return type:	item

L.remove(value)¶

Removes the first occurrence of value. Raises ValueError if value is not present.

Requires $\Theta\left(n\right)$ operations in the worst case.

L.reverse()¶

Reverse the list in place.

Requires $\Theta\left(n\right)$ operations.

L.sort(cmp=None, key=None, reverse=False)¶

Stable sort in place.

cmp is suppoted in Python 2 for compatibility with Python 2’s list.sort. All users are encouraged to migrate to using the key parameter, which is more efficient.

key specifies a function of one argument that is used to extract a comparison key from each list element: key=str.lower. The default value is None (compare the elements directly).

reverse is a boolean value. If set to True, then the list elements are sorted as if each comparison were reversed.

Requires $\Theta\left(n \log n\right)$ operations in the worst and average case and $\Theta\left(n\right)$ operation in the best case.

blist¶

Table of contents

blist

heapdict

winreg_unicode

ion-sampler

Navigation

blist¶

Table of contents

blist

heapdict

winreg_unicode

ion-sampler

Quick search

Navigation