Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.
 Entire forum ➜ MUSHclient ➜ Python ➜ Python dictionaries - iteration

Python dictionaries - iteration

It is now over 60 days since the last post. This thread is closed.     Refresh page


Posted by Alca   (20 posts)  Bio
Date Tue 22 Dec 2009 08:16 PM (UTC)
Message
Okay, so I started working with dictionaries because, well, they're more powerful than simple lists, and easier to use as well.

From a script someone else made in Lua, I've been able to deduct that when iterating over a Lua array, it does so in the order that was given.

However, when trying to replicate that using Python dictionaries, I fail. Python iterates over its dictionaries in an arbitrary way, but unfortunately not in the order the keys were provided.

My questions:

- Am I right about the Lua arrays behaviour? If not, disregard the following questions.
- Is it possible to have custom iteration over Python dictionaries? And if yes:
- How exactly?
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #1 on Tue 22 Dec 2009 09:43 PM (UTC)
Message
Quote:
- Am I right about the Lua arrays behaviour? If not, disregard the following questions.

Yes and no. Keys in Lua tables are iterated over in arbitrary order -- when using the 'pairs' function. But 'ipairs' behaves differently; it only iterates over the integer keys (more precisely, the integer keys of the array section of the table), and does so in order.

By using a dictionary instead of a list, you are essentially making the fact that the keys are ordered numbers incidental. In Lua, it works because you are (I presume) using ipairs, but were you to use pairs, it's unclear that it would work.

Note that "the order that was given" isn't necessarily the order of insertion.


Quote:
- Is it possible to have custom iteration over Python dictionaries? And if yes:
- How exactly?

Yes, it's possible. You'd have to create a subclass that override __iter__ such that it first sorted the keys, and then iterated over those (sorted) keys providing the appropriate values.


A better question perhaps is why you are using a dictionary if what you really want is a list of items each with an index. You could also convert the dictionary to a list by sorting its keys:


In [1]: d = {1: 'foo', 2: 'bar', 3: 'bla'}

In [2]: print [(x,d[x]) for x in d]
[(1, 'foo'), (2, 'bar'), (3, 'bla')]

In [3]: new_list = list(d[x] for x in sorted(d.keys()))

In [4]: new_list
Out[4]: ['foo', 'bar', 'bla']

In [5]: 


Here, it's accidental that the dictionary printed out the way we wanted.

This line:
In [3]: new_list = list(d[x] for x in sorted(d.keys()))
means:
Construct a list composed of d[x] for each x appearing in d's sorted list of keys.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Rakon   USA  (123 posts)  Bio
Date Reply #2 on Tue 22 Dec 2009 09:50 PM (UTC)
Message
Can you show us the code you're porting to Python; perhaps your Python code as well??

How are you iterating over the dict? Keys? Values? Both?

In a Python dictionary you can sort the keys/values as needed, and then iterate over those. Or, you can iterate the key/value pair and then sort that.

The basics of dictionary iteration:

Over both key/value:


numberDict = {1:'one',2:'two',3:'three'}

for key,value in numberDict.items():
    print key, value



Over both key/value, sorted:

numberDict = {1:'one',2:'two',3:'three'}

for key,value in numberDict.items():
    print key, value



To iterate a dictionary in order (not sorted) I believe the following should work:

numberDict = {1:'one',2:'two',3:'three'}

for key in numberDict:
    print key, numberDict[key]


Yes, I am a criminal.
My crime is that of curiosity.
My crime is that of judging people by what they say and think, not what they look like.
My crime is that of outsmarting you, something that you will never forgive me for.
Top

Posted by Alca   (20 posts)  Bio
Date Reply #3 on Tue 22 Dec 2009 09:59 PM (UTC)
Message
Thanks for the pointers so far, especially those about Lua.

This wasn't really what I meant though, so I'll be a little more specific.

This is part of the Python dict I want to iterate over:


affdict = {
    "sadness": "0",
    "selfpity": "0",
    "baldness": "0",
    "dementia": "0",
    "stupidity": "0",
    "clumsiness": "0"
}


No integer keys here, or a simple sort would've been the obvious solution.

I want it to iterate over the keys in the order I set; in this case, starting with sadness, then selfpity, then baldness, etc.

I was under the impression Lua did this automatically, now I'm not so sure anymore.

Anyway, is there a way to achieve this in Python? For now, I'm using a list in which I call for the keys in the order I want them called. I was just wondering if this could be done shorter and more efficient.
Top

Posted by Nick Gammon   Australia  (23,120 posts)  Bio   Forum Administrator
Date Reply #4 on Tue 22 Dec 2009 10:28 PM (UTC)
Message
The equivalent to that in Lua would be:


affdict = {
   { "sadness", "0", },
   { "selfpity", "0", },
   { "baldness", "0", },
   { "dementia", "0", },
   { "stupidity", "0", },
   { "clumsiness", "0" },
}


That is a table of tables, where the outer table is in insertion order. In other words, there are implied keys, as if you wrote:


affdict = {
  [1] = { "sadness", "0", },
  [2] = { "selfpity", "0", },
  [3] = { "baldness", "0", },
  [4] = { "dementia", "0", },
  [5] = { "stupidity", "0", },
  [6] = { "clumsiness", "0" },
}

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Nick Gammon   Australia  (23,120 posts)  Bio   Forum Administrator
Date Reply #5 on Wed 23 Dec 2009 04:13 AM (UTC)
Message
Of course, if "sadness" is a key, then it could be:


affdict = {
   { sadness = 0 },
   { selfpity = 0 },
   { baldness = 0 },
   { dementia = 0 },
   { stupidity = 0, },
   { clumsiness = 0 },
}


But that doesn't make a heap of sense because you have a lot of subtables with only one item in each one.

Still, you could iterate through the main table, in order, and then for each item in the main table is a single entry, being a key/value pair, where the key is the affliction (like sadness) and the value is the number (like 0).

Still this is probably irrelevant because I am talking Lua here and you want a Python solution. :)

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #6 on Wed 23 Dec 2009 03:20 PM (UTC)
Message
Quote:
I want it to iterate over the keys in the order I set; in this case, starting with sadness, then selfpity, then baldness, etc.

Right; this is not done by default and you must implement it yourself.

Quote:
I was under the impression Lua did this automatically, now I'm not so sure anymore.

It's hard to know what exactly you were seeing without the code, but no, Lua tables with string keys are not at all sensitive to the order in which you inserted things, or to the natural sort order of the keys.

Quote:
Anyway, is there a way to achieve this in Python? For now, I'm using a list in which I call for the keys in the order I want them called. I was just wondering if this could be done shorter and more efficient.

What's inefficient about this? And what other choice could you possibly have, if you want it to be a dictionary? You can encapsulate the list in a subclass of dict, that is aware of the insertion order of keys, and iterates over keys in that order. Another option would be to have a list of pairs, which makes iteration easy but lookup harder.

But if you only have that many effects, it might be easier to just define your own mini-container that respects the dict protocol and implements iter to return keys in a predefined order. It's unclear to me at this point if you want a general data structure for order-of-insertion-preserving maps, or if you're trying to solve a far more specific problem.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Alca   (20 posts)  Bio
Date Reply #7 on Wed 23 Dec 2009 03:23 PM (UTC)
Message
Actually, that explanation helped me realize I probably won't be able to do what I want to in Python. As far as I'm aware, Python dicts don't have implied keys.

I also made a mistake when interpreting the Lua code, so yeah, I'm going to stick to my list, for now. All in all, it's probably the easier (if not only) approach.

Thanks for the help, anyways.
Top

Posted by CJI   Poland  (7 posts)  Bio
Date Reply #8 on Wed 14 Jul 2010 11:09 AM (UTC)
Message
There's SortedDict class from Django source code: http://code.djangoproject.com/browser/django/trunk/django/utils/datastructures.py


class SortedDict(dict):
    """
    A dictionary that keeps its keys in the order in which they're inserted.
    """
    def __new__(cls, *args, **kwargs):
        instance = super(SortedDict, cls).__new__(cls, *args, **kwargs)
        instance.keyOrder = []
        return instance

    def __init__(self, data=None):
        if data is None:
            data = {}
        elif isinstance(data, GeneratorType):
            # Unfortunately we need to be able to read a generator twice.  Once
            # to get the data into self with our super().__init__ call and a
            # second time to setup keyOrder correctly
            data = list(data)
        super(SortedDict, self).__init__(data)
        if isinstance(data, dict):
            self.keyOrder = data.keys()
        else:
            self.keyOrder = []
            for key, value in data:
                if key not in self.keyOrder:
                    self.keyOrder.append(key)

    def __deepcopy__(self, memo):
        return self.__class__([(key, deepcopy(value, memo))
                               for key, value in self.iteritems()])

    def __setitem__(self, key, value):
        if key not in self:
            self.keyOrder.append(key)
        super(SortedDict, self).__setitem__(key, value)

    def __delitem__(self, key):
        super(SortedDict, self).__delitem__(key)
        self.keyOrder.remove(key)

    def __iter__(self):
        return iter(self.keyOrder)

    def pop(self, k, *args):
        result = super(SortedDict, self).pop(k, *args)
        try:
            self.keyOrder.remove(k)
        except ValueError:
            # Key wasn't in the dictionary in the first place. No problem.
            pass
        return result

    def popitem(self):
        result = super(SortedDict, self).popitem()
        self.keyOrder.remove(result[0])
        return result

    def items(self):
        return zip(self.keyOrder, self.values())

    def iteritems(self):
        for key in self.keyOrder:
            yield key, self[key]

    def keys(self):
        return self.keyOrder[:]

    def iterkeys(self):
        return iter(self.keyOrder)

    def values(self):
        return map(self.__getitem__, self.keyOrder)

    def itervalues(self):
        for key in self.keyOrder:
            yield self[key]

    def update(self, dict_):
        for k, v in dict_.iteritems():
            self[k] = v

    def setdefault(self, key, default):
        if key not in self:
            self.keyOrder.append(key)
        return super(SortedDict, self).setdefault(key, default)

    def value_for_index(self, index):
        """Returns the value of the item at the given zero-based index."""
        return self[self.keyOrder[index]]

    def insert(self, index, key, value):
        """Inserts the key, value pair before the item with the given index."""
        if key in self.keyOrder:
            n = self.keyOrder.index(key)
            del self.keyOrder[n]
            if n < index:
                index -= 1
        self.keyOrder.insert(index, key)
        super(SortedDict, self).__setitem__(key, value)

    def copy(self):
        """Returns a copy of this object."""
        # This way of initializing the copy means it works for subclasses, too.
        obj = self.__class__(self)
        obj.keyOrder = self.keyOrder[:]
        return obj

    def __repr__(self):
        """
        Replaces the normal dict.__repr__ with a version that returns the keys
        in their sorted order.
        """
        return '{%s}' % ', '.join(['%r: %r' % (k, v) for k, v in self.items()])

    def clear(self):
        super(SortedDict, self).clear()
        self.keyOrder = []


It's a drop-in replacement for built-in dict wherever you need to remember order of insertion.

Right, I have to stop digging here or else I'll start answering to topics from years ago :)
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #9 on Wed 14 Jul 2010 03:19 PM (UTC)
Message
IMHO 'SortedDict' is a poor choice of name because it's not so much sorted as merely inserted in order. (For example, if you insert 2 and then 1, 2 comes before 1 which is not sorted.)

Note that Python 2.7 introduces an OrderedDict that does what you want:
http://docs.python.org/library/collections.html#collections.OrderedDict

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


33,331 views.

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum


[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.