diff options
author | SVN-Git Migration <python-modules-team@lists.alioth.debian.org> | 2015-10-08 08:33:59 -0700 |
---|---|---|
committer | SVN-Git Migration <python-modules-team@lists.alioth.debian.org> | 2015-10-08 08:33:59 -0700 |
commit | 0b68c6d00a2c84a5db13ba5fa304a6eadc4279f2 (patch) | |
tree | 1af54f1d5bdd9e7eb77d75e875c25bb7b6fbb7b4 /PKG-INFO |
Imported Upstream version 1.3.4
Diffstat (limited to 'PKG-INFO')
-rw-r--r-- | PKG-INFO | 202 |
1 files changed, 202 insertions, 0 deletions
diff --git a/PKG-INFO b/PKG-INFO new file mode 100644 index 0000000..a43d00d --- /dev/null +++ b/PKG-INFO @@ -0,0 +1,202 @@ +Metadata-Version: 1.1 +Name: blist +Version: 1.3.4 +Summary: a list-like type with better asymptotic performance and similar performance on small lists +Home-page: http://stutzbachenterprises.com/blist/ +Author: Stutzbach Enterprises, LLC +Author-email: daniel@stutzbachenterprises.com +License: BSD +Description: blist: a list-like type with better performance + =============================================== + + The ``blist`` is a drop-in replacement for the Python list the provides + better performance when modifying large lists. The blist package also + provides ``sortedlist``, ``sortedset``, ``weaksortedlist``, + ``weaksortedset``, ``sorteddict``, and ``btuple`` types. + + Full documentation is at the link below: + + http://stutzbachenterprises.com/blist-doc/ + + Python's built-in list is a dynamically-sized array; to insert or + removal an item from the beginning or middle of the list, it has to + move most of the list in memory, i.e., O(n) operations. The blist + uses a flexible, hybrid array/tree structure and only needs to move a + small portion of items in memory, specifically using O(log n) + operations. + + 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()) + + Here are some of the use cases where the blist 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 + + Other data structures + --------------------- + + The blist package provides other data structures based on the blist: + + - sortedlist + - sortedset + - weaksortedlist + - weaksorteset + - sorteddict + - btuple + + These additional data structures are only available in Python 2.6 or + higher, as they make use of Abstract Base Classes. + + The sortedlist is a list that's always sorted. It's iterable and + indexable like a Python list, but to modify a sortedlist the same + methods you would use on a Python set (add, discard, or remove). + + >>> from blist import sortedlist + >>> my_list = sortedlist([3,7,2,1]) + >>> my_list + sortedlist([1, 2, 3, 7]) + >>> my_list.add(5) + >>> my_list[3] + 5 + >>> + + The sortedlist constructor takes an optional "key" argument, which may + be used to change the sort order just like the sorted() function. + + >>> from blist import sortedlist + >>> my_list = sortedlist([3,7,2,1], key=lambda i: -i) + sortedlist([7, 3, 2, 1] + >>> + + The sortedset is a set that's always sorted. It's iterable and + indexable like a Python list, but modified like a set. Essentially, + it's just like a sortedlist except that duplicates are ignored. + + >>> from blist import sortedset + >>> my_set = sortedset([3,7,2,2]) + sortedset([2, 3, 7] + >>> + + The weaksortedlist and weaksortedset are weakref variations of the + sortedlist and sortedset. + + The sorteddict works just like a regular dict, except the keys are + always sorted. The sorteddict should not be confused with Python + 2.7's OrderedDict type, which remembers the insertion order of the + keys. + + >>> from blist import sorteddict + >>> my_dict = sorteddict({1: 5, 6: 8, -5: 9}) + >>> my_dict.keys() + [-5, 1, 6] + >>> + + The btuple is a drop-in replacement for the built-in tuple. Compared + to the built-in tuple, the btuple offers the following advantages: + + - Constructing a btuple from a blist takes O(1) time. + - Taking a slice of a btuple takes O(n) time, where n is the size of + the original tuple. The size of the slice does not matter. + + >>> from blist import blist, btuple + >>> x = blist([0]) # x is a blist with one element + >>> x *= 2**29 # x is a blist with > 500 million elements + >>> y = btuple(x) # y is a btuple with > 500 million elements + + 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 + + If you're running Linux and see a bunch of compilation errors from + GCC, you probably do not have the Python header files installed. + They're usually located in a package called something like + "python2.6-dev". + + The blist package 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 require Python 2.6 or higher. + + Feedback + -------- + + We're eager to hear about your experiences with the blist. You can + email me at daniel@stutzbachenterprises.com. Alternately, 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 add extra 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. + +Keywords: blist list b+tree btree fast copy-on-write sparse array sortedlist sorted sortedset weak weaksortedlist weaksortedset sorteddict btuple +Platform: UNKNOWN +Classifier: Development Status :: 5 - Production/Stable +Classifier: Intended Audience :: Developers +Classifier: Intended Audience :: Science/Research +Classifier: License :: OSI Approved :: BSD License +Classifier: Programming Language :: C +Classifier: Programming Language :: Python :: 2.5 +Classifier: Programming Language :: Python :: 2.6 +Classifier: Programming Language :: Python :: 2.7 +Classifier: Programming Language :: Python :: 3 +Classifier: Programming Language :: Python :: 3.1 +Classifier: Programming Language :: Python :: 3.2 +Provides: blist |