Mailing List Archive

Roy,

You don't have to maintain a separate keylist. Try:

>>> d = {1:11,2:22,3:33}
>>> keylist = d.keys()
>>> keylist.sort()

then do for key in keylist:

--

Emile van Sebille
emile@fenx.com
-------------------


Roy Smith <roy@popmail.med.nyu.edu> wrote in message
news:roy-2507991300370001@mc-as01-p61.med.nyu.edu...
> I've got a dictionary of items which I will sometimes want random
access
> to, but sometimes I'll want to be able to step through the items in a
> fixed order as well. Any good way to do that?
>
> The best I've come up with so far is to keep a parallel list of the
> dictionary keys in sorted order and use that to step through when I
need
> to:
>
> for key in keylist:
> do_stuff (dict[key])
>
> which will work, but seems kind of clumsy. Anything smoother I can
do?

Roy> I've got a dictionary of items which I will sometimes want random access
Roy> to, but sometimes I'll want to be able to step through the items in a
Roy> fixed order as well. Any good way to do that?

You demonstrated the best way. There is no need to save the key list unless
the dictionary is very large though. Just grab 'em and sort 'em when you
need:

keylist = dict.keys()
keylist.sort()
for key in keylist: do_stuff(dict[key])

Skip Montanaro | http://www.mojam.com/
skip@mojam.com | http://www.musi-cal.com/~skip/
847-475-3758

Skip Montanaro <skip@mojam.com> wrote:

: Roy> I've got a dictionary of items which I will sometimes want random access
: Roy> to, but sometimes I'll want to be able to step through the items in a
: Roy> fixed order as well. Any good way to do that?

: You demonstrated the best way. There is no need to save the key list unless
: the dictionary is very large though. Just grab 'em and sort 'em when you
: need:

: keylist = dict.keys()
: keylist.sort()
: for key in keylist: do_stuff(dict[key])

There are times when the entries cannot be sorted and the order must
still be preserved.

A good way to handle this is a modified UserDict subclass.

from UserDict import UserDict
class OrderedDict(UserDict):
def __init__(self, dict=None):
UserDict.__init__(self, dict)
if dict and isinstance(dict, OrderedDict)
self.ordered = dict.ordered[:]
elif dict:
self.ordered = dict.values() # must be taken unordered
else:
self.ordered = []
def __getitem__(self, index):
if isinstance(index, type(0)):
return self.ordered[index]
else:
return UserDict.__getitem__(self, index)
def __setitem__(self, index):
UserDict.__setitem__(self, index, value)
self.ordered.append(value)

One problem to this mechanism is that numbers are not indices instead
of keys. But you can do this in other ways to fill the application's
needs.

Remember that you aren't creating copies of the objects, just references
to the same object, so you should be creating only twice the memory
space as the dictionary itself (relatively speaking).

-Arcege

On Sun, 25 Jul 1999 12:22:03 -0500 (CDT), Skip Montanaro wrote:
> You demonstrated the best way. There is no need to save the key list unless
> the dictionary is very large though. Just grab 'em and sort 'em when you
> need:
>
> keylist = dict.keys()
> keylist.sort()
> for key in keylist: do_stuff(dict[key])
>

But how much time requires the keylist generation?

That is, the keylist is made traversing all the dictionary nodes or is
cached inside it?

--
Diego Dainese
--
To reply remove the numbers and the `x' from my address
--
Sorry for my bad English!

Hi Diego,


Diego Dainese <ddainese97x@x18dsi.unive.it> wrote in message
news:slrn7po8t3.6k.diego@blanka2.blankanet.it...
> On Sun, 25 Jul 1999 12:22:03 -0500 (CDT), Skip Montanaro wrote:
> > You demonstrated the best way. There is no need to save the key
list unless
> > the dictionary is very large though. Just grab 'em and sort 'em
when you
> > need:
> >
> > keylist = dict.keys()
> > keylist.sort()
> > for key in keylist: do_stuff(dict[key])
> >
>
> But how much time requires the keylist generation?

I tried this test and found that the results varied on the number of
items. For example, at 100000 entries, the .keys() was generally
faster, but at 50000 entries, it was not faster. I'm on a PII-266
w/64Mb but I've got lots running so YMMV (your mileage may vary). Test
on your platform. Ultimately, you'd need to wrap up a separate keylist
in a class structure to ensure consistency, and that may also impact
speed.

########
import time
d = {}
r = ('spam','eggs','eggs','bacon','eggs','and','spam')
test1start = time.clock()
for i in xrange(100000):
d[i] = i, 2*i, r
k = d.keys()
test1end = test2start = time.clock()
d = {}
k = []
for i in xrange(50000):
d[i] = i, 2*i, r
k.append(i)
test2end = time.clock()
print 'test1: ',test1end - test1start
print 'test2: ',test2end - test2start
########
>
> That is, the keylist is made traversing all the dictionary nodes or is
> cached inside it?

I can't help you with this one...

>
> --
> Diego Dainese
> --
> To reply remove the numbers and the `x' from my address
> --
> Sorry for my bad English!

Not bad at all.

--

Emile van Sebille
emile@fenx.com
-------------------

( oops ;-( )

Of-course,-had-I-allowed-both-tests-to-do-the-same-number-of-iterations,
-the-results-may-have-been-different-ly yr's

--

Emile van Sebille
emile@fenx.com
-------------------

Diego> But how much time requires the keylist generation?

On my 233MHz P-II it takes about 0.07s to generate the list of keys for a
dictionary with 100,000 int keys.

Skip Montanaro | http://www.mojam.com/
skip@mojam.com | http://www.musi-cal.com/~skip/
847-475-3758

This is a multi-part message in MIME format.
--------------76166A5423E2C203D9B306C9
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Roy Smith wrote:
>
> I've got a dictionary of items which I will sometimes want random access
> to, but sometimes I'll want to be able to step through the items in a
> fixed order as well. Any good way to do that?
>
> The best I've come up with so far is to keep a parallel list of the
> dictionary keys in sorted order and use that to step through when I need
> to:
>
> for key in keylist:
> do_stuff (dict[key])
>
> which will work, but seems kind of clumsy. Anything smoother I can do?

Look here:
Probably seqdict is best for you. Look at

http://www.germany.net/teilnehmer/100,366919/Python/Modules/Modules.html

from seqdict import seqdict
dict = seqdict()
.
.
.
for key,value in dict.items():
do_stuff(key,value)

I think this works for you. But seqdict and mseqdict brings much, much
more
new operations on sequential dictionaries. Tell me what your think.

Wolfgang
--------------76166A5423E2C203D9B306C9
Content-Type: text/x-vcard; charset=us-ascii;
name="wolfgang.grafen.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Wolfgang Grafen
Content-Disposition: attachment;
filename="wolfgang.grafen.vcf"

begin:vcard
n:Grafen;Wolfgang
tel;fax:+49 7191 13-4321
tel;work:+49 7191 13-3238
x-mozilla-html:FALSE
org:Bosch Telecom
version:2.1
email;internet:wolfgang.grafen@de.bosch.com
adr;quoted-printable:;;Abt. UC-ON/EUA1=0D=0ABosch Telecom GmbH;D-71520 Backnang;;;Germany
x-mozilla-cpt:;-3688
fn:Wolfgang Grafen
end:vcard

--------------76166A5423E2C203D9B306C9--

On Mon, 26 Jul 1999 07:45:29 -0700, Emile van Sebille wrote:
[...]
> > But how much time requires the keylist generation?
>
> I tried this test and found that the results varied on the number of
> items. For example,
[snip]

You are right, my question was a bit naive...

> > That is, the keylist is made traversing all the dictionary nodes or is
> > cached inside it?
>
> I can't help you with this one...

AFAICT (from you test program) the nodes are linked in a list and the
key-sequence is generated traversing this list. Moreover the sequence
is not cached:

import time
d = {}
r = ('spam','eggs','eggs','bacon','eggs','and','spam')
k = []
for i in xrange(1000000):
d[i] = i, 2*i, r
k.append(i)

test1start = time.clock()
k = d.keys()
test1end = test2start = time.clock()
k = d.keys()
test2end = time.clock()

print 'test1: ',test1end - test1start
print 'test2: ',test2end - test2start

The last 2 prints give always the same results (about 0.8 seconds on
my Linux box).

> > --
> > Sorry for my bad English!
>
> Not bad at all.

Thanks :)

+++

Thanks for the reply (and to Skip Montanaro too), bye

--
Diego Dainese
--
To reply remove the numbers and the `x' from my address
--
Sorry for my bad English!