transforming a list into a string

[jblazi]

Let us assume I have a list like

['1','2','7','8' ,'12','13]

and would like to transoform it into the string

'{1,2},{7,8},{1 2,13}'

Which is the simplest way of achiebing this? (The list is in fact much
longer and I may have to cut the resulting strings into chunks of 100 or
so.)

TIA,

jb

[Peter Otten]

Re: transforming a list into a string

jblazi wrote:
[color=blue]
> Let us assume I have a list like
>
> ['1','2','7','8' ,'12','13]
>
> and would like to transoform it into the string
>
> '{1,2},{7,8},{1 2,13}'
>
> Which is the simplest way of achiebing this? (The list is in fact much
> longer and I may have to cut the resulting strings into chunks of 100 or
> so.)[/color]
[color=blue][color=green][color=darkred]
>>> from itertools import izip
>>> items = ['1','2','7','8' ,'12','13']
>>> it = iter(items)
>>> ",".join(["{%s,%s}" % i for i in izip(it, it)])[/color][/color][/color]
'{1,2},{7,8},{1 2,13}'


Peter

[Roy Smith]

Re: transforming a list into a string

In article <pan.2004.07.31 .12.27.23.54700 0@hotmail.com>,
jblazi <jblazi@hotmail .com> wrote:
[color=blue]
> Let us assume I have a list like
>
> ['1','2','7','8' ,'12','13][/color]

I'm assuming there's supposed to be another single-quote after the 13?
[color=blue]
> and would like to transoform it into the string
>
> '{1,2},{7,8},{1 2,13}'[/color]

This works, and is pretty straight-forward:

source = ['1','2','7','8' ,'12','13']
temp = []

while source:
x = source.pop(0)
y = source.pop(0)
temp.append ('{%s,%s}' % (x, y))

result = ','.join (temp)
print result

This prints what you want:

$ /tmp/list2string.py
{1,2},{7,8},{12 ,13}

Accumulating the repeating bits of the result string in a list, and then
putting them together with a join operation is a common idiom in python.
You can build up strings by doing string addition:

temp = temp + '{%s,%s}' % (x, y)

This will have the same result, but suffers from quadratic run times as
it keeps building and destroying immutable strings.
[color=blue]
> Which is the simplest way of achiebing this? (The list is in fact much
> longer and I may have to cut the resulting strings into chunks of 100 or
> so.)[/color]

How long is "much longer", and how important is it that this runs fast?
The code above runs in O(n). You can probably play some tricks to tweak
the speed a little, but in the big picture, you're not going to do any
better than O(n).

The above code also assumes you have an even number of items in source,
and will bomb if you don't. You probably want to fix that :-)

[Jp Calderone]

Re: transforming a list into a string

> In article <pan.2004.07.31 .12.27.23.54700 0@hotmail.com>,[color=blue]
> [snip]
>
> This works, and is pretty straight-forward:
>
> source = ['1','2','7','8' ,'12','13']
> temp = []
>
> while source:
> x = source.pop(0)
> y = source.pop(0)
> temp.append ('{%s,%s}' % (x, y))
>
> result = ','.join (temp)
> print result
>
> [snip]
>
> How long is "much longer", and how important is it that this runs fast?
> The code above runs in O(n). You can probably play some tricks to tweak
> the speed a little, but in the big picture, you're not going to do any
> better than O(n).
>[/color]

Are you sure? Did you consider the complexity of list.pop(0)?

Jp

[Roy Smith]

Re: transforming a list into a string

I wrote:[color=blue][color=green]
> > The code above runs in O(n).[/color][/color]

Jp Calderone <exarkun@divmod .com> wrote:[color=blue]
> Are you sure? Did you consider the complexity of list.pop(0)?[/color]

I'm assuming list.pop() is O(1), i.e. constant time. Is it not?

Of course, one of my pet peeves about Python is that the complexity of
the various container operations are not documented. This leaves users
needing to guess what they are, based on assumptions of how the
containers are probably implemented.

[Terry Reedy]

Re: transforming a list into a string


"Roy Smith" <roy@panix.co m> wrote in message
news:roy-982174.13075831 072004@reader1. panix.com...[color=blue][color=green]
> > Are you sure? Did you consider the complexity of list.pop(0)?[/color]
>
> I'm assuming list.pop() is O(1), i.e. constant time. Is it not?[/color]

Yes, list.pop() (from the end) is O(1) (which is why -1 is the default arg
;-).
However, list.pop(0) (from the front) was O(n) thru 2.3.
The listobject.c code has been rewritten for 2.4 and making the latter O(1)
also *may* have been one of the results. (This was discussed as desireable
but I don't know the result.)
[color=blue]
> Of course, one of my pet peeves about Python is that the complexity of
> the various container operations are not documented.[/color]

So volunteer a doc patch, or contribute $ to hire someone ;-).

Terry J. Reedy

[Tim Peters]

Re: transforming a list into a string

[Terry Reedy][color=blue]
> However, list.pop(0) (from the front) was O(n) thru 2.3.
> The listobject.c code has been rewritten for 2.4 and making the latter O(1)
> also *may* have been one of the results. (This was discussed as desireable
> but I don't know the result.)[/color]

Didn't happen -- it would have been too disruptive to the basic list
type. Instead, Raymond Hettinger added a cool new dequeue type for
2.4, with O(1) inserts and deletes at both ends, regardless of access
pattern (all the hacks suggested for the base list type appeared to
suffer under *some* pathological (wrt the hack in question) access
pattern). However, general indexing into a deque is O(N) (albeit with
a small constant factor). deque[0] and deque[-1] are O(1).

[Roy Smith][color=blue][color=green]
>> Of course, one of my pet peeves about Python is that the complexity of
>> the various container operations are not documented.[/color][/color]

Lists and tuples and array.arrays are contiguous vectors, dicts are
hash tables. Everything follows from that in obvious ways -- butyou
already knew that. The *language* doesn't guarantee any of it,
though; that's just how CPython is implemented. FYI, the deque type
is implemented as a doubly-linked list of blocks, each block a
contiguous vector of (at most) 46 elements.

[Roy Smith]

Re: transforming a list into a string

Tim Peters <tim.peters@gma il.com> wrote:[color=blue]
> Lists and tuples and array.arrays are contiguous vectors, dicts are
> hash tables. Everything follows from that in obvious ways -- but you
> already knew that.[/color]

OK, so it sounds like you want to reverse() the list before the loop,
then pop() items off the back. Two O(n) passes [I'm assuming reverse()
is O(N)] beats O(n^2).

[Tim Peters]

Re: transforming a list into a string

[Roy Smith][color=blue]
> OK, so it sounds like you want to reverse() the list before the loop,
> then pop() items off the back. Two O(n) passes [I'm assuming reverse()
> is O(N)][/color]

Yes.
[color=blue]
> beats O(n^2).[/color]

Absolutely. Note that Peter Otten previously posted a lovely O(N)
solution in this thread, although it may be too clever for some
tastes:
[color=blue][color=green][color=darkred]
>>> from itertools import izip
>>> items = ['1','2','7','8' ,'12','13']
>>> it = iter(items)
>>> ",".join(["{%s,%s}" % i for i in izip(it, it)])[/color][/color][/color]
'{1,2},{7,8},{1 2,13}'[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

[Roy Smith]

Re: transforming a list into a string

Tim Peters <tim.peters@gma il.com> wrote:[color=blue]
> Note that Peter Otten previously posted a lovely O(N)
> solution in this thread, although it may be too clever for some
> tastes:
>[color=green][color=darkred]
> >>> from itertools import izip
> >>> items = ['1','2','7','8' ,'12','13']
> >>> it = iter(items)
> >>> ",".join(["{%s,%s}" % i for i in izip(it, it)])[/color][/color]
> '{1,2},{7,8},{1 2,13}'[/color]

Personally, I'm not a big fan of clever one-liners. They never seem
like such a good idea 6 months from now when you're trying to figure out
what you meant when you wrote it 6 months ago.

[Andrew Bennetts]

Re: transforming a list into a string

On Sat, Jul 31, 2004 at 08:43:52PM -0400, Roy Smith wrote:[color=blue]
> Tim Peters <tim.peters@gma il.com> wrote:[color=green]
> > Note that Peter Otten previously posted a lovely O(N)
> > solution in this thread, although it may be too clever for some
> > tastes:
> >[color=darkred]
> > >>> from itertools import izip
> > >>> items = ['1','2','7','8' ,'12','13']
> > >>> it = iter(items)
> > >>> ",".join(["{%s,%s}" % i for i in izip(it, it)])[/color]
> > '{1,2},{7,8},{1 2,13}'[/color]
>
> Personally, I'm not a big fan of clever one-liners. They never seem
> like such a good idea 6 months from now when you're trying to figure out
> what you meant when you wrote it 6 months ago.[/color]

It's a two-liner, not a one-liner (although it could be made into a
one-liner with enough contortions...) .

The only other way I could see to expand this solution would be to write it
as:
it = iter(items)
pairs = izip(it, it)
s = ",".join(["{%s,%s}" % i for i in pairs])

I don't know if three-liners meet your threshold for verbosity ;)

Well, you could write it as:

pairs = []
it = iter(items):
while True:
try:
pair = it.next(), it.next()
except StopIteration:
break
pairs.append(pa ir)
s = ",".join(["{%s,%s}" % i for i in pairs])

But at that point, the scaffolding is large enough that it obscures the
purpose -- I definitely find this harder to read than the two-liner.

I find Peter's original form easy to read -- if you understand how "izip(it,
it)" works (which is a very simple and elegant way to iterate over (it[n],
it[n+1]) pairs), the rest is very clear.

-Andrew.

[Roy Smith]

Re: transforming a list into a string

Andrew Bennetts <andrew-pythonlist@puzz ling.org> wrote:[color=blue]
> It's a two-liner, not a one-liner (although it could be made into a
> one-liner with enough contortions...) .
>
> The only other way I could see to expand this solution would be to write it
> as:
> it = iter(items)
> pairs = izip(it, it)
> s = ",".join(["{%s,%s}" % i for i in pairs])
>
> I don't know if three-liners meet your threshold for verbosity ;)[/color]

It's better, but I'd unroll it one more step and write:

it = iter (items)
pairs = izip (it, it)
strings = ["{%s,%s}" % i for i in pairs]
s = ",".join (strings)

I'm also not particularly happy about the choice of "it" as a variable
name. The "izip (it, it)" construct makes me think of Dr. Evil :-)
[color=blue]
> I find Peter's original form easy to read -- if you understand how "izip(it,
> it)" works (which is a very simple and elegant way to iterate over (it[n],
> it[n+1]) pairs), the rest is very clear.[/color]

It's not the izip bit that bothers me in the original, it's the deeply
nested construct of

",".join(["{%s,%s}" % i for i in izip(it, it)])

There's too much going on in that one line to get your head around
easily. I suppose people who are really into functional programming
might find it understandable, but I find it rather obtuse.

[jblazi]

Re: transforming a list into a string

Thx. Your solution is perfect for me as speed is not an issue here.

jb

[Michel Claveau - abstraction méta-galactique non t]

Re: transforming a list into a string

+1

--
Michel Claveau

[Bengt Richter]

Re: transforming a list into a string

On Sun, 1 Aug 2004 11:00:32 +1000, Andrew Bennetts <andrew-pythonlist@puzz ling.org> wrote:
[color=blue]
>On Sat, Jul 31, 2004 at 08:43:52PM -0400, Roy Smith wrote:[color=green]
>> Tim Peters <tim.peters@gma il.com> wrote:[color=darkred]
>> > Note that Peter Otten previously posted a lovely O(N)
>> > solution in this thread, although it may be too clever for some
>> > tastes:
>> >
>> > >>> from itertools import izip
>> > >>> items = ['1','2','7','8' ,'12','13']
>> > >>> it = iter(items)
>> > >>> ",".join(["{%s,%s}" % i for i in izip(it, it)])
>> > '{1,2},{7,8},{1 2,13}'[/color]
>>
>> Personally, I'm not a big fan of clever one-liners. They never seem
>> like such a good idea 6 months from now when you're trying to figure out
>> what you meant when you wrote it 6 months ago.[/color]
>
>It's a two-liner, not a one-liner (although it could be made into a
>one-liner with enough contortions...) .
>[/color]
Assuming items definition doesn't count in the line count,
[color=blue][color=green][color=darkred]
>>> items = ['1','2','7','8' ,'12','13'][/color][/color][/color]

then one line seems to do it, not that obscurely (depending on your glasses ;-)
[color=blue][color=green][color=darkred]
>>> ",".join(["{%s,%s}"%(n(), n()) for n in [iter(items).nex t] for i in xrange(0,len(it ems),2)])[/color][/color][/color]
'{1,2},{7,8},{1 2,13}'
[color=blue]
>The only other way I could see to expand this solution would be to write it
>as:
> it = iter(items)
> pairs = izip(it, it)
> s = ",".join(["{%s,%s}" % i for i in pairs])
>
>I don't know if three-liners meet your threshold for verbosity ;)
>
>Well, you could write it as:
>
> pairs = []
> it = iter(items):
> while True:
> try:
> pair = it.next(), it.next()
> except StopIteration:
> break
> pairs.append(pa ir)
> s = ",".join(["{%s,%s}" % i for i in pairs])
>
>But at that point, the scaffolding is large enough that it obscures the
>purpose -- I definitely find this harder to read than the two-liner.
>
>I find Peter's original form easy to read -- if you understand how "izip(it,
>it)" works (which is a very simple and elegant way to iterate over (it[n],
>it[n+1]) pairs), the rest is very clear.[/color]
Agreed.

Regards,
Bengt Richter