Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   Dict to "flat" list of (key,value) (http://www.velocityreviews.com/forums/t320328-dict-to-flat-list-of-key-value.html)

Nicolas Girard 07-30-2003 07:26 PM

Dict to "flat" list of (key,value)
 
Hi,

Forgive me if the answer is trivial, but could you tell me how to achieve
the following:

{k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]

The subtle point (at least to me) is to "flatten" values that are lists.

Thanks in advance,
Nicolas



----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

Bengt Richter 07-30-2003 08:06 PM

Re: Dict to "flat" list of (key,value)
 
On Wed, 30 Jul 2003 21:26:19 +0200, Nicolas Girard <Nicolas.nospam.Girard@removethis.nerim.net> wrote:

>Hi,
>
>Forgive me if the answer is trivial, but could you tell me how to achieve
>the following:
>
>{k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]
>
>The subtle point (at least to me) is to "flatten" values that are lists.
>

Assuming v3 and others like it can't be references to lists
(or how could you tell it from the format of k1's list?):

(I quoted your names to avoid haing to define them separately)

>>> d = {'k1':['v1','v2'],'k2':'v3'}
>>> flat = []
>>> for k,v in d.items():

... if isinstance(v,list):
... for v2 in v:
... flat.append([k,v2])
... else:
... flat.append([k,v])
...
>>> flat

[['k2', 'v3'], ['k1', 'v1'], ['k1', 'v2']]

Or would you prefer an inscrutable one-liner ;-)

Note that there is no guarantee of any particular order in d.items(),
though you could sort them:

>>> d = {'k1':['v1','v2'],'k2':'v3'}
>>> flat = []
>>> items = d.items()
>>> items.sort() # on keys
>>> for k,v in items:

... if isinstance(v,list):
# Note that v is a list here, but does have pre-existing order you might want to keep.
# If you wanted to guarantee sorted output of the v2's, you could
# do v.sort() here, though you might surprise others holding references
# to those lists, since they would see the sorting. To avoid that, make a copy first, e.g.,
# v = v[:]; v.sort() #(untested, but I think it should work ;-)

... for v2 in v:
... flat.append([k,v2])
... else:
... flat.append([k,v])
...
>>> flat

[['k1', 'v1'], ['k1', 'v2'], ['k2', 'v3']]

Regards,
Bengt Richter

Brandon Beck 07-30-2003 08:31 PM

Re: Dict to "flat" list of (key,value)
 
Someone will definitely come up with a better solution than this, but
this could work for you at least as a first try

import types
def flatten(d, iterables=(types.ListType, types.TupleType)):
rv = []
for k, v in d.items():
if type(v) in iterables:
rv += [[k,x] for x in v]
else:
rv += [[k,v]]
return rv

If you want to change the types of things that get iterated over, just
pass in a second parameter of your own.

Hope that helps,
Brandon



"Nicolas Girard" <Nicolas.nospam.Girard@removethis.nerim.net> wrote in
message news:pan.2003.07.30.19.26.18.41642@removethis.neri m.net...
> Hi,
>
> Forgive me if the answer is trivial, but could you tell me how to

achieve
> the following:
>
> {k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]
>
> The subtle point (at least to me) is to "flatten" values that are

lists.
>
> Thanks in advance,
> Nicolas
>
>
>
> ----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet

News==----
> http://www.newsfeed.com The #1 Newsgroup Service in the World!
>100,000 Newsgroups
> ---= 19 East/West-Coast Specialized Servers - Total Privacy via

Encryption =---



David C. Fox 07-30-2003 08:38 PM

Re: Dict to "flat" list of (key,value)
 
Nicolas Girard wrote:
> Hi,
>
> Forgive me if the answer is trivial, but could you tell me how to achieve
> the following:
>
> {k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]
>
> The subtle point (at least to me) is to "flatten" values that are lists.


Well, I can get you at least part way, but there is an ambiguity in your
original data structure which causes problems:

1. d.items() will get you

[(k1, [v1, v2]), (k2, v3), ...]

2. Now, you want to expand out the list elements where the second part
of each tuple is a list, which you can do with.

flatten = lambda u: map(lambda x: (u[0], x), u[1])

or, if the double lambda expression is confusing:

def flatten(u):
return map(lambda x: (u[0], x), u[1])

(I've used a tuple (u[0], x) instead of a list, because your [k1, vn]
are always pairs, but you can use a list if you prefer)

Then flatten will take the nested element

(k1, [v1, v2])

and convert it to a list of tuples

[(k1, v1), [k2, v2])]

3. You want to apply flatten to each element of d.items(), which you
can do with

lol = map(flatten, d.items())

which will give you a list of lists of tuples,

4. and then reduce that to a list of tuples with

reduce(operator.add, lol)


Unfortunately, this doesn't quite work with your example above, because
flatten won't work properly when applied to (k2, v3). If v3 is a
sequence, it will instead give you [(k2, v3[0]), (k2, v3[1]), ...],
which is probably not what you want (especially if v3 is a string - try
flatten manually and see what happens). If v3 is not a sequence, you'll
get a TypeError saying that argument 2 to map() must support iteration.

If you *know* that v3 will NEVER be a list, you can modify flatten to
handle the special case like so:

def flatten(u):
if isinstance(u[1], type([])):
return (u[1], [u[2]])
return map(lambda x: (u[0], x), u[1])

Alternatively, if you can modify how the initial dictionary is generated
to ensure that cases where a key has a single value always appear as
k2: [v3] instead of k2: v3, then you can use the steps above without
modification. This is probably better if it is feasible, because your
original data structure is inherently ambiguous unless you know that v3
will never be a list.

David




>
> Thanks in advance,
> Nicolas
>
>
>
> ----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
> http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
> ---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---



David C. Fox 07-30-2003 08:57 PM

Re: Dict to "flat" list of (key,value)
 
David C. Fox wrote:

Oops - a mistake and an omission

> 4. and then reduce that to a list of tuples with
>
> reduce(operator.add, lol)


You need to import the operator module first.

> def flatten(u):
> if isinstance(u[1], type([])):
> return (u[1], [u[2]])
> return map(lambda x: (u[0], x), u[1])


I got my cases reversed - that should be "if not isinstance...


Mike Rovner 07-31-2003 12:02 AM

Re: Dict to "flat" list of (key,value)
 
Nicolas Girard wrote:
> Forgive me if the answer is trivial, but could you tell me how to
> achieve the following:
>
> {k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]

[list(i) for i in d.items()]

Mike





Mike Rovner 07-31-2003 12:30 AM

Re: Dict to "flat" list of (key,value)
 
Mike Rovner wrote:
> Nicolas Girard wrote:
>> Forgive me if the answer is trivial, but could you tell me how to
>> achieve the following:
>>
>> {k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]

>
>[list(i) for i in d.items()]


Sorry, I missed v1,v2 flattening.





Raymond Hettinger 08-02-2003 12:41 PM

Re: Dict to "flat" list of (key,value)
 

"Nicolas Girard" <Nicolas.nospam.Girard@removethis.nerim.net> wrote in message
news:pan.2003.07.30.19.26.18.41642@removethis.neri m.net...
> Hi,
>
> Forgive me if the answer is trivial, but could you tell me how to achieve
> the following:
>
> {k1:[v1,v2],k2:v3,...} --> [[k1,v1],[k1,v2],[k2,v3],...]
>
> The subtle point (at least to me) is to "flatten" values that are lists.


The other posters answered the question (as asked)
by showing a loop that differentiated the two cases
of inner lists vs single values. One further thought,
is that the original data structure could be improved
by building it so that every value is in a list:

{k1:[v1,v2],k2:[v3],...}

This is typically done by building the values with setdefault:

index = {}
for pagenum in range(len(pages)):
page = pages[pagenum]
for word in page:
index.setdefault(word, []).append(pagenum)

The new structure is much more easily flattened:

[(k,v) for k, values in newstruct.iteritems() for v in values]


it-all-starts-with-a-good-data-structure-ly yours,


Raymond Hettinger



John Machin 08-03-2003 12:28 AM

Re: Dict to "flat" list of (key,value)
 
On Sat, 02 Aug 2003 12:41:19 GMT, "Raymond Hettinger"
<vze4rx4y@verizon.net> wrote:


>it-all-starts-with-a-good-data-structure-ly yours,


Amen, brother.

Even worse: I recall seeing code somewhere that had a data structure
like this:

{k1: [v1,v2], k2: v3, k3: None, ...}
instead of
{k1: [v1,v2], k2: [v3], k3: [], ...}

I liked the elegant code example for building a book index. However in
practice the user requirement would be not to have duplicated page
numbers when a word occurs more than once on the same page. If you can
achieve that elegantly, please post it!

Cheers,
John



Scott David Daniels 08-03-2003 03:42 AM

Re: Dict to "flat" list of (key,value)
 
John Machin wrote:

> On Sat, 02 Aug 2003 12:41:19 GMT, "Raymond Hettinger"
> <vze4rx4y@verizon.net> wrote:
>>

[a perfectly fine chunk of code]
>>it-all-starts-with-a-good-data-structure-ly yours,

>
> I liked the elegant code example for building a book index. However in
> practice the user requirement would be not to have duplicated page
> numbers when a word occurs more than once on the same page. If you can
> achieve that elegantly, please post it!


OK, I'll bite:
def genindex(pages):
index = {}
for pagenum in range(len(pages)):
page = pages[pagenum]
for word in page:
index.setdefault(word, {})[pagenum] = None

or with 2.3:
def genindex(pages):
index = {}
for pagenum, page in enumerate(pages):
for word in page:
index.setdefault(word, {})[pagenum] = None
return index

With either one, flattening looks like:
def flatten(index):
flattened = [(word, list(pages)) for word, pages
in index.items()]
for word, pages in flattened:
pages.sort()
flattened.sort()
return flatten

For fun, try:

book = ['this is a test'.split(),
'this is only a test'.split(),
'had this been a real function, you care a bit'.split()]
for word, pages in flatten(index(book)):
print word, pages

-Scott David Daniels
Scott.Daniels@Acm.Org



All times are GMT. The time now is 10:18 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.