Groups > comp.lang.python.announce > #1765

[ANN] pyskiplist-1.0.0

Return-Path	<geertj@gmail.com>
X-Original-To	python-announce-list@python.org
Delivered-To	python-announce-list@mail.python.org
X-Spam-Status	OK 0.001
X-Spam-Evidence	'H': 1.00; 'S': 0.00; 'memory.': 0.05; 'implements': 0.07; 'key.': 0.07; 'pypi': 0.07; 'subject:ANN': 0.07; 'width': 0.07; 'corresponds': 0.09; 'integers': 0.09; 'iterate': 0.09; 'url:github': 0.09; 'python': 0.11; '(key,': 0.16; 'node,': 0.16; 'node.': 0.16; 'nodes': 0.16; 'pairs': 0.16; 'skipped': 0.16; 'memory': 0.17; 'bytes': 0.18; 'subject:] ': 0.19; 'insert': 0.23; "i've": 0.24; 'second': 0.24; 'order.': 0.27; 'message-id:@mail.gmail.com': 0.28; 'node': 0.29; 'novel': 0.29; 'searches': 0.29; 'value)': 0.29; 'saves': 0.31; 'certain': 0.31; 'link.': 0.32; 'structure': 0.32; 'maintaining': 0.34; 'received:google.com': 0.34; 'stores': 0.35; 'list,': 0.36; 'position.': 0.36; 'at:': 0.37; 'should': 0.37; 'delete': 0.37; 'level': 0.37; 'supports': 0.38; 'subject:[': 0.39; 'does': 0.39; 'performance': 0.39; 'to:addr:python.org': 0.39; 'subject:-': 0.39; 'data': 0.40; 'where': 0.40; 'per': 0.61; 'skip:n 10': 0.63; 'incoming': 0.70; 'fast,': 0.84; 'technique': 0.93
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=qdWmOFNKWjF8bY364OVnUc/trPXKUIPRYZ9WI1cT7t0=; b=O4jHEyiyi5jTBhfn/9mCQjXyzwYmMiTPmDuA+hpwmCx1bpBjrcudpbpKXHaUoS659F cOMAiXjs/k9nuMve/EYrtgOGPLRUDdsTdile32cpt4L4f0MwNCuF/GdPsrRew21QmyYR bhjMkCu3ix2ua0gQoP6WtMOvHJDoivo+XZ5/dNwBqQ9VvGnuEH/rQBFxkxg/Oc7yzFgl 2+1a6cvnNkR6bsfSnsOwMcvBTqJbi429s6wzY1iDJDMfdcXWOUj0ItzDY5Fr7v7ZQ0IN MaRnHf4+cQsxBAD2LQB5eqN717XulIPA1Vkgz7DPDL3ci4mLsRc70VfOeJmUSp2P0UZP o4Ag==
MIME-Version	1.0
X-Received	by 10.50.164.199 with SMTP id ys7mr6913737igb.6.1436051101557; Sat, 04 Jul 2015 16:05:01 -0700 (PDT)
Date	Sat, 4 Jul 2015 19:05:01 -0400
Subject	[ANN] pyskiplist-1.0.0
From	Geert Jansen <geertj@gmail.com>
To	python-announce-list@python.org
Content-Type	text/plain; charset=UTF-8
X-Mailman-Approved-At	Sun, 05 Jul 2015 08:08:53 +0200
X-BeenThere	python-announce-list@python.org
X-Mailman-Version	2.1.20+
Precedence	list
List-Id	Announcement-only list for the Python programming language <python-announce-list.python.org>
List-Unsubscribe	<https://mail.python.org/mailman/options/python-announce-list>, <mailto:python-announce-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-announce-list/>
List-Post	<mailto:python-announce-list@python.org>
List-Help	<mailto:python-announce-list-request@python.org?subject=help>
List-Subscribe	<https://mail.python.org/mailman/listinfo/python-announce-list>, <mailto:python-announce-list-request@python.org?subject=subscribe>
Approved	python-announce-list@python.org
Newsgroups	comp.lang.python.announce
Message-ID	<mailman.297.1436076534.3674.python-announce-list@python.org> (permalink)
Lines	30
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1436076534 news.xs4all.nl 2956 [2001:888:2000:d::a6]:57655
X-Complaints-To	abuse@xs4all.nl
Path	csiph.com!usenet.pasdenom.info!news.stben.net!border1.nntp.ams1.giganews.com!nntp.giganews.com!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Xref	csiph.com comp.lang.python.announce:1765

Show key headers only | View raw

PySkipList is a fast, pure Python implementation of an indexable skiplist. It
implements a SkipList data structure that provides an always sorted,
list-like data structure for (key, value) pairs. It efficiently supports the
following operations:

* Insert a pair in the list, maintaining sorted order.
* Find the value of a given key.
* Remove a given pair based on a key.
* Iterate over all pairs in sorted order.
* Find the position of a given key.
* Access a pair at a certain position.
* Delete a pair at a certain position.

This implementation uses a novel (as far as I know) technique where it stores
just a single link width per node, and only in nodes with level > 0. The link
corresponds to the number of nodes skipped by the highest incoming link. Other
implementations that I've seen all store a width for every link. This approach
saves a lot of memory. The overhead should just be 1/e (0.37) integers per
node. It makes an indexable skiplist almost as memory efficient as its
non-indexable cousin.

Performance wise, it does around 77K searches per second on 100K nodes,
and has an overhead at this node count of about 106 bytes per node.

Available on PyPI as "pyskiplist" and Github at:

https://github.com/geertj/pyskiplist

Regards,
Geert

Back to comp.lang.python.announce | Previous | Next | Find similar | Unroll thread

Thread

[ANN] pyskiplist-1.0.0 Geert Jansen <geertj@gmail.com> - 2015-07-04 19:05 -0400

csiph-web