473,320 Members | 2,000 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

collections.chain

Several languages like Java, C# etc have a List type in the std lib.
Python has a built-in list(), it's implemented as array dynamic on the
right.

Not too much time ago Hettinger has added a collections.deque (its C
code is really nice), that compared to list() allows a faster append
on the right and a much faster prepend on the left. It's implemented
as a double linked list of fixed-sized blocks. All blocks but the
first and last are fully filled, so such blocks don't need to store
their length, and the data structure just needs to store the length of
the first and last block.

In the C++ STL I think the deque can be implemented as a dynamic array
of pointers, that point to the start of each fixed-size block. This
allows a faster access of items, because you need two lookups and you
don't need to follow the linked list (plus maybe a module operation).
I don't know why the collections.deque uses a double linked list,
maybe because it allows a simpler design (in the dynamic arrays of
pointers you have to manage them as a circular array, so you need the
module or an if).

A double-ended queue covers lot of usages of a linked list, but not
all of them. So if enough Python programmers feel the need of a
(light) data structure that allows O(1) removal and add of items in
any point, then such data structure can be created. The name can be
"chain", because it's easy, short, it means the right thing, and
"list" is already taken.

Its implementation can be a normal double linked list. But on modern
CPUs they can be not much efficient, so there are few strategies to
improve that:
http://en.wikipedia.org/wiki/CDR_coding
http://en.wikipedia.org/wiki/Unrolled_linked_list
I think an unrolled double linked list is a fit implementation for
this purpose. This data structure is quite similar to the
collections.deque, but each block has to keep the number of items it
contains (note: if experiments show that such overhead in memory and
speed is little enough, then most of the C code of the deque may even
be thrown away, using the chain to implement it).

Are enough Python programmers interested in such chain data structure?
Can the typical Python programs enjoy the use of it? I presume it's
not very important, but sometimes I have found a use for it.

If enough people are interested in this data structure, then I think
there's a problem to be solved. How to manage references into the
chain itself. You need references, otherwise many operations become
O(n), and this makes the chain quite less useful.

A simple solution is to create another independent object like
chainptr, that's essentially a pointer to an item of the chain, it can
also become nil/Nil/Null/null, I presume... If you have two chainptr
that point the n-th item, and you remove the n-th item, then the
second chainptr now doesn't point to the n+1-th item (this is true for
python list, where pointers are integer numbers), it's a broken
pointer. Etc. Such low-level problems are probably out of place in
Python.

A way to avoid those problems is to make the pointers part of the
chain object itself, so they are kept consistent. I presume there must
be some way to add/remove such indexes dynamically, but I presume in
Python this is not too much a problem, but such kind of management
slows down the data structure a little. Every operation has to control
the state of all defined indexes, but I presume their number is usally
low (one, two) so it may not be a problem.

I don't have ideas for a good API yet, but if the pointers are part of
the chain, the syntax may becomes something like:

from collections import chain
d = chain("ABCD")
d.addindex() # creates p0 that points A
d.p0.next()
d.p0.next() # now p0 point C
d.addindex(d.p0) # now p1 point C
d.p0.delete() # now p0 and p1 point D (or nothing?)

Well, that's ugly. But first of all it's important to see if a chain i
useful, if the answer is positive, then I can look for a decent API.

Bye,
bearophile
Oct 25 '08 #1
0 1055

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: njp | last post by:
BlankHi, How do I create a tightly coupled Object 1 such that when I update it in one collection, it is simultaneously and automatically updated in other collections? The collections are defined...
10
by: David Murmann | last post by:
Hi all! I could not find out whether this has been proposed before (there are too many discussion on join as a sequence method with different semantics). So, i propose a generalized .join method...
5
by: Simon | last post by:
Hi all, I am writing a windows application using vb.net on the 1.1 framework. We have in the application, some strongly typed collections that have been written as classes that do not inherit...
4
by: Adam Clauss | last post by:
I ran into a problem a while back when attempting to convert existing .NET 1.1 based code to .NET 2.0 using Generic collections rather than Hashtable, ArrayList, etc. I ran into an issue because...
4
by: Sid Price | last post by:
Hello, I have a class of objects (Device) that are managed by another object (Devices) with a collection class (DeviceCollection) inherited from Collections.Hashtable. Each of the Device objects...
2
by: Cramer | last post by:
More of a theoretical question here: It just occurred to me that the ASP.NET request pipeline delivers much of the GoF Chain of Responsibility pattern. What do you think? If it does not, then, why...
15
by: jzakiya | last post by:
I'm translating a program in Python that has this IF Then chain IF x1 < limit: --- do a --- IF x2 < limit: --- do b --- IF x3 < limit: --- do c --- .----- ------ IF x10 < limt: ---...
6
by: vwkng1987 | last post by:
Hi everyone Please look at the code below: (I am picking up JS from Crockfold and a few other online sources too) *************************************************************** function...
11
by: ManWithNoName | last post by:
Dear sir, say, do you know if it is possible to "break" a method chain in php? e.g. class a{
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.