Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #87921 > unrolled thread

Newbie looking for elegant solution

Back to article view | Back to comp.lang.python

Contents

  Newbie looking for elegant solution otaksoftspamtrap@gmail.com - 2015-03-24 20:13 -0700
    Re: Newbie looking for elegant solution Chris Angelico <rosuav@gmail.com> - 2015-03-25 14:28 +1100
      Re: Newbie looking for elegant solution otaksoftspamtrap@gmail.com - 2015-03-24 20:31 -0700
    Re: Newbie looking for elegant solution Paul Rubin <no.email@nospam.invalid> - 2015-03-24 21:04 -0700
      Re: Newbie looking for elegant solution kai.peters@gmail.com - 2015-03-24 21:19 -0700
      Re: Newbie looking for elegant solution Chris Angelico <rosuav@gmail.com> - 2015-03-25 15:19 +1100
        Re: Newbie looking for elegant solution kai.peters@gmail.com - 2015-03-24 21:46 -0700
          Re: Newbie looking for elegant solution Chris Angelico <rosuav@gmail.com> - 2015-03-25 16:05 +1100
          Re: Newbie looking for elegant solution Ben Finney <ben+python@benfinney.id.au> - 2015-03-25 16:28 +1100
          Re: Newbie looking for elegant solution Paul Rubin <no.email@nospam.invalid> - 2015-03-24 22:52 -0700
            Re: Newbie looking for elegant solution Rustom Mody <rustompmody@gmail.com> - 2015-03-24 23:32 -0700
    Re: Newbie looking for elegant solution Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-03-25 16:24 +1100
    Re: Newbie looking for elegant solution Dave Farrance <DaveFarrance@OMiTTHiSyahooANDTHiS.co.uk> - 2015-03-25 06:05 +0000
    Re: Newbie looking for elegant solution Travis Griggs <travisgriggs@gmail.com> - 2015-03-25 11:49 -0700
    Re: Newbie looking for elegant solution kai.peters@gmail.com - 2015-03-25 16:14 -0700
      Re: Newbie looking for elegant solution Paul Rubin <no.email@nospam.invalid> - 2015-03-25 16:30 -0700
      Re: Newbie looking for elegant solution Irmen de Jong <irmen.NOSPAM@xs4all.nl> - 2015-03-26 00:34 +0100
    Re: Newbie looking for elegant solution kai.peters@gmail.com - 2015-03-25 17:38 -0700
      Re: Newbie looking for elegant solution Paul Rubin <no.email@nospam.invalid> - 2015-03-25 18:09 -0700
        Re: Newbie looking for elegant solution kai.peters@gmail.com - 2015-03-25 18:29 -0700
          Re: Newbie looking for elegant solution Paul Rubin <no.email@nospam.invalid> - 2015-03-25 19:53 -0700

Page 1 of 2  [1] 2  Next page →

#87921 — Newbie looking for elegant solution

I have a list containing 9600 integer elements - each integer is either 0 or 1.

Starting at the front of the list, I need to combine 8 list elements into 1 by treating them as if they were bits of one byte with 1 and 0 denoting bit on/off (the 8th element would be the rightmost bit of the first byte).

The end result should be a new list that is 8 x shorter than the original list containing integers between 0 and 255.

Speed is not of utmost importance - an elegant solution is. Any suggestions?

Thanks for all input,
Kai

[toc] | [next] | [standalone]

#87923

On Wed, Mar 25, 2015 at 2:13 PM,  <otaksoftspamtrap@gmail.com> wrote:
> I have a list containing 9600 integer elements - each integer is either 0 or 1.
>
> Starting at the front of the list, I need to combine 8 list elements into 1 by treating them as if they were bits of one byte with 1 and 0 denoting bit on/off (the 8th element would be the rightmost bit of the first byte).
>
> Speed is not of utmost importance - an elegant solution is. Any suggestions?

Oooh fun!

>>> l = [1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]
>>> list(int(''.join(str(i) for i in l),2).to_bytes(len(l)//8,'big'))
[177, 105, 117]

Convert it into a string, convert the string to an integer
(interpreting it as binary), then convert the integer into a series of
bytes, and interpret those bytes as a list of integers.

Example works in Python 3. For Python 2, you'll need ord() to get the
integers at the end.

I'm not sure how elegant this is, but it's a fun trick to play with :)

Next idea please! I love these kinds of threads.

ChrisA

[toc] | [prev] | [next] | [standalone]

#87924

On Tuesday, March 24, 2015 at 8:29:24 PM UTC-7, Chris Angelico wrote:
> On Wed, Mar 25, 2015 at 2:13 PM,  <nobody> wrote:
> > I have a list containing 9600 integer elements - each integer is either 0 or 1.
> >
> > Starting at the front of the list, I need to combine 8 list elements into 1 by treating them as if they were bits of one byte with 1 and 0 denoting bit on/off (the 8th element would be the rightmost bit of the first byte).
> >
> > Speed is not of utmost importance - an elegant solution is. Any suggestions?
> 
> Oooh fun!
> 

> >>> l = [1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]
> >>> list(int(''.join(str(i) for i in l),2).to_bytes(len(l)//8,'big'))
> [177, 105, 117]
> 
> Convert it into a string, convert the string to an integer
> (interpreting it as binary), then convert the integer into a series of
> bytes, and interpret those bytes as a list of integers.
> 
> Example works in Python 3. For Python 2, you'll need ord() to get the
> integers at the end.
> 
> I'm not sure how elegant this is, but it's a fun trick to play with :)
> 
> Next idea please! I love these kinds of threads.
> 
> ChrisA


Impressive - thanks!

[toc] | [prev] | [next] | [standalone]

#87925

otaksoftspamtrap@gmail.com writes:
> I have a list containing 9600 integer elements - each integer is
> either 0 or 1.

Is that a homework problem?  This works for me in Python 2.7 but I think
Python 3 gratuitously broke tuple unpacking so it won't work there:

================================================================

from itertools import count, groupby
old = [0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1]
new = [reduce(lambda x,(y,i):x*2+y, g, 0)
       for k,g in groupby(zip(old,count()), lambda (a,b): b//8)]
print new

>>> [18, 222, 53]
================================================================

[toc] | [prev] | [next] | [standalone]

#87926

On Tuesday, 24 March 2015 21:04:37 UTC-7, Paul Rubin  wrote:
> nobody writes:
> > I have a list containing 9600 integer elements - each integer is
> > either 0 or 1.
> 
> Is that a homework problem?  This works for me in Python 2.7 but I think
> Python 3 gratuitously broke tuple unpacking so it won't work there:
> 
> ================================================================
> 
> from itertools import count, groupby
> old = [0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1]
> new = [reduce(lambda x,(y,i):x*2+y, g, 0)
>        for k,g in groupby(zip(old,count()), lambda (a,b): b//8)]
> print new
> 
> >>> [18, 222, 53]
> ================================================================

no homework - real life. thanks for your contribution 

[toc] | [prev] | [next] | [standalone]

#87927

On Wed, Mar 25, 2015 at 3:04 PM, Paul Rubin <no.email@nospam.invalid> wrote:
> This works for me in Python 2.7 but I think
> Python 3 gratuitously broke tuple unpacking so it won't work there:
>
> ================================================================
>
> from itertools import count, groupby
> old = [0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1]
> new = [reduce(lambda x,(y,i):x*2+y, g, 0)
>        for k,g in groupby(zip(old,count()), lambda (a,b): b//8)]
> print new
>
>>>> [18, 222, 53]
> ================================================================

You don't need tuple unpacking. Here's the Py3 version of the above:

from functools import reduce
new = [reduce(lambda x,y:x*2+y[0], g, 0)
    for k,g in groupby(zip(old,count()), lambda a: a[1]//8)]

ChrisA

[toc] | [prev] | [next] | [standalone]

#87928

On Tuesday, 24 March 2015 21:20:11 UTC-7, Chris Angelico  wrote:
> On Wed, Mar 25, 2015 at 3:04 PM, Paul Rubin <nobody> wrote:
> > This works for me in Python 2.7 but I think
> > Python 3 gratuitously broke tuple unpacking so it won't work there:
> >
> > ================================================================
> >
> > from itertools import count, groupby
> > old = [0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1]
> > new = [reduce(lambda x,(y,i):x*2+y, g, 0)
> >        for k,g in groupby(zip(old,count()), lambda (a,b): b//8)]
> > print new
> >
> >>>> [18, 222, 53]
> > ================================================================
> 
> You don't need tuple unpacking. Here's the Py3 version of the above:
> 
> from functools import reduce
> new = [reduce(lambda x,y:x*2+y[0], g, 0)
>     for k,g in groupby(zip(old,count()), lambda a: a[1]//8)]
> 
> ChrisA


Now I have just read the latest spec and speed/memory may become issues:

1 bit images of a size of 1024 x 1280 need to be processed this way, so
1310720 list elements. Also needs to be 2.7 only.

Any recommendations?

[toc] | [prev] | [next] | [standalone]

#87931

On Wed, Mar 25, 2015 at 3:46 PM,  <kai.peters@gmail.com> wrote:
> Now I have just read the latest spec and speed/memory may become issues:
>
> 1 bit images of a size of 1024 x 1280 need to be processed this way, so
> 1310720 list elements. Also needs to be 2.7 only.
>
> Any recommendations?

2.7 only? Then my solution won't work (I just tried to port it, and
integers don't have to_bytes). Paul's solution works. Here's an
alternative:

>>> import numpy
>>> list(numpy.packbits(numpy.array(l),-1))
[177, 105, 117]

Of course, this does mean installing numpy. It is crushing the nut
with the triphammer - an absurd extravagance of energy, but the nut is
effectively crushed all the same.

ChrisA

[toc] | [prev] | [next] | [standalone]

#87933

Chris Angelico <rosuav@gmail.com> writes:

> Of course, this does mean installing numpy. It is crushing the nut
> with the triphammer - an absurd extravagance of energy, but the nut is
> effectively crushed all the same.

It also has the advantage that it hopefully won't be acceptable for a
homework assignment.

Whether homework assignment or not, the original poster is well advised
to try the problem themselves, and present their code for us to discuss.

-- 
 \             “Skepticism is the highest duty and blind faith the one |
  `\               unpardonable sin.” —Thomas Henry Huxley, _Essays on |
_o__)                                   Controversial Questions_, 1889 |
Ben Finney

[toc] | [prev] | [next] | [standalone]

#87934

kai.peters@gmail.com writes:
> 1 bit images of a size of 1024 x 1280 need to be processed this way,
> so 1310720 list elements. Also needs to be 2.7 only.

Where are these lists going to come from?  Files?  Process the file
differently, probably.  Use generators instead of lists, maybe.  Or
process one scan line at a time instead of the whole image.  Or
something.  Basically your plan and your question seem kind of naive.
If you can describe the ACTUAL application, you might be able to get
some better answers.  E.g. if it's image conversion, maybe there's an
existing tool for the formats you want.

How many of these images do you want to process?  If just a few, who
cares if it takes a little while?  If a lot, think about writing a C
program.

[toc] | [prev] | [next] | [standalone]

#87936

On Wednesday, March 25, 2015 at 11:23:08 AM UTC+5:30, Paul Rubin wrote:
> kai.peters  writes
> > 1 bit images of a size of 1024 x 1280 need to be processed this way,
> > so 1310720 list elements. Also needs to be 2.7 only.
> 
> Where are these lists going to come from?  Files?  Process the file
> differently, probably.  Use generators instead of lists, maybe.  

Some C-ish solutions and then two loop-unrollings:

def foo(lst):
    i = 0
    while i < len(lst):
        acc = 0
        for j in range(8):
            acc = 2*acc+lst[i]
            i += 1
        yield acc

def bar(lst):
    i = 0
    while i < len(lst):
        acc = 0
        acc = 2*acc+lst[i]
        acc = 2*acc+lst[i+1]
        acc = 2*acc+lst[i+2]
        acc = 2*acc+lst[i+3]
        acc = 2*acc+lst[i+4]
        acc = 2*acc+lst[i+5]
        acc = 2*acc+lst[i+6]
        acc = 2*acc+lst[i+7]
        i += 8
        yield acc

def baz(lst):
    i = 0
    while i < len(lst):
        acc = (128*lst[i] + 64*lst[i+1] + 32*lst[i+2] + 16*lst[i+3] +
               8*lst[i+4] + 4*lst[i+5] + 2*lst[i+6] + lst[i+7])
        i += 8
        yield acc

[toc] | [prev] | [next] | [standalone]

#87932

On Wednesday 25 March 2015 14:13, otaksoftspamtrap@gmail.com wrote:

> I have a list containing 9600 integer elements - each integer is either 0
> or 1.
> 
> Starting at the front of the list, I need to combine 8 list elements into
> 1 by treating them as if they were bits of one byte with 1 and 0 denoting
> bit on/off (the 8th element would be the rightmost bit of the first byte).
> 
> The end result should be a new list that is 8 x shorter than the original
> list containing integers between 0 and 255.
> 
> Speed is not of utmost importance - an elegant solution is. Any
> suggestions?

Collate the list into groups of 8. Here, I pad the list with zeroes at the 
end. If you prefer to drop any excess bits instead of padding them, use 
itertools.izip instead of izip_longest.


import itertools
mylist = [1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1]
grouped = itertools.izip_longest(*([iter(mylist)]*8), fillvalue=0)



Now convert each group of eight into a byte:

def byte(bits):
    n = 0
    for b in bits:
        assert b in (0, 1)
        n = n*2 + b
    return n

[byte(x) for x in grouped]


Or if you prefer using built-ins:

[int(''.join(str(b) for b in x), 2) for x in grouped]

I have no idea which will be faster.


Exercise for the reader: izip will drop any bits that don't make up an 
octet. izip_longest will pad with zeroes on the least-significant side, e.g. 
[1, 1] -> 192. How to pad on the most-significant side, or equivalently, 
don't pad at all, so that [1, 1] -> 3?



-- 
Steve

[toc] | [prev] | [next] | [standalone]

#87935

otaksoftspamtrap@gmail.com wrote:

>I have a list containing 9600 integer elements - each integer is either 0 or 1.
>Starting at the front of the list, I need to combine 8 list elements into 1 by treating them as if they were bits of one byte with 1 and 0 denoting bit on/off (the 8th element would be the rightmost bit of the first byte).
>The end result should be a new list that is 8 x shorter than the original list containing integers between 0 and 255.
>Speed is not of utmost importance - an elegant solution is. Any suggestions?
>Thanks for all input,

Here's another way. Works in Python 2 and 3.

>>> x = [1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]
>>> [int(''.join( str(y) for y in x[z:z+8]),2) for z in range(0, len(x), 8)]
[177, 105, 117]

[toc] | [prev] | [next] | [standalone]

#87964

> On Mar 24, 2015, at 8:28 PM, Chris Angelico <rosuav@gmail.com> wrote:
> 
> On Wed, Mar 25, 2015 at 2:13 PM,  <otaksoftspamtrap@gmail.com> wrote:
>> I have a list containing 9600 integer elements - each integer is either 0 or 1.
>> 
>> Starting at the front of the list, I need to combine 8 list elements into 1 by treating them as if they were bits of one byte with 1 and 0 denoting bit on/off (the 8th element would be the rightmost bit of the first byte).
>> 
>> Speed is not of utmost importance - an elegant solution is. Any suggestions?
> 
> Oooh fun!
> 
>>>> l = [1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]
>>>> list(int(''.join(str(i) for i in l),2).to_bytes(len(l)//8,'big'))
> [177, 105, 117]
> 
> Convert it into a string, convert the string to an integer
> (interpreting it as binary), then convert the integer into a series of
> bytes, and interpret those bytes as a list of integers.
> 
> Example works in Python 3. For Python 2, you'll need ord() to get the
> integers at the end.
> 
> I'm not sure how elegant this is, but it's a fun trick to play with :)
> 
> Next idea please! I love these kinds of threads.

Me too. These are my favorite threads. Here’s my entry:

[sum(b << (7 - i) for i, b in enumerate(bits)) for bits in zip(*[l[n::8] for n in range(8)])]

I think there has to be a better way to do the left hand part, but I liked the zipped iterators on 8 slices.

[toc] | [prev] | [next] | [standalone]

#87992

On Tuesday, 24 March 2015 20:14:06 UTC-7, otaksoft...@gmail.com  wrote:
> I have a list containing 9600 integer elements - each integer is either 0 or 1.
> 
> Starting at the front of the list, I need to combine 8 list elements into 1 by treating them as if they were bits of one byte with 1 and 0 denoting bit on/off (the 8th element would be the rightmost bit of the first byte).
> 
> The end result should be a new list that is 8 x shorter than the original list containing integers between 0 and 255.
> 
> Speed is not of utmost importance - an elegant solution is. Any suggestions?
> 
> Thanks for all input,
> Kai



The list comes from PILLOW:

getdata #

im.getdata() => sequence

Returns the contents of an image as a sequence object containing pixel values. The sequence object is flattened, so that values for line one follow directly after the values of line zero, and so on.

Note that the sequence object returned by this method is an internal PIL data type, which only supports certain sequence operations, including iteration and basic sequence access. To convert it to an ordinary sequence (e.g. for printing), use list(im.getdata()).

[toc] | [prev] | [next] | [standalone]

#87993

kai.peters@gmail.com writes:
> im.getdata() => sequence
> Returns the contents of an image as a sequence object containing pixel
> values. The sequence object is flattened, so that values for line one
> follow directly after the values of line zero, and so on.

And this is a list of 1's and 0's, I guess for a bitonal picture?

Anyway, the code I posted should be able to take in the sequence
directly (lazily) without needing an intermediate list.  If you change
the outer list comprehension to a generator expression (i.e. in Python
2.x, replace the square brackets with parentheses) it will produce a
lazy sequence at the output, that you can then process one line at a
time or whatever.  Also, on computers these days, a million element list
isn't a big problem.

What are you going to do with the output?  That might also help people
find suggestions.

[toc] | [prev] | [next] | [standalone]

#87994

On 26-3-2015 0:14, kai.peters@gmail.com wrote:
> On Tuesday, 24 March 2015 20:14:06 UTC-7, otaksoft...@gmail.com  wrote:
>> I have a list containing 9600 integer elements - each integer is either 0 or 1.
>>
>> Starting at the front of the list, I need to combine 8 list elements into 1 by treating them as if they were bits of one byte with 1 and 0 denoting bit on/off (the 8th element would be the rightmost bit of the first byte).
>>
>> The end result should be a new list that is 8 x shorter than the original list containing integers between 0 and 255.
>>
>> Speed is not of utmost importance - an elegant solution is. Any suggestions?
>>
>> Thanks for all input,
>> Kai
> 
> 
> 
> The list comes from PILLOW:
> 
> getdata #
> 
> im.getdata() => sequence
> 

Don't you want to use Image.tobytes() instead? Or, Image.save() directly if you want to
store the image somewhere else perhaps?
In other words, what are you going to do with the -internal- data returned from getdata,
perhaps you don't even want to call it, and skip dealing with the raw pixel bits
altogether...

Irmen

[toc] | [prev] | [next] | [standalone]

#88008

On Tuesday, 24 March 2015 20:14:06 UTC-7, otaksoft...@gmail.com  wrote:
> I have a list containing 9600 integer elements - each integer is either 0 or 1.
> 
> Starting at the front of the list, I need to combine 8 list elements into 1 by treating them as if they were bits of one byte with 1 and 0 denoting bit on/off (the 8th element would be the rightmost bit of the first byte).
> 
> The end result should be a new list that is 8 x shorter than the original list containing integers between 0 and 255.
> 
> Speed is not of utmost importance - an elegant solution is. Any suggestions?
> 
> Thanks for all input,
> Kai

I though that the bytes type is Python 3 only? If so, I cannot use it.

Using PILLOW, I am generating images from text and these are then sent to a black & white image rendering device which expects 8 one bit pixels as one byte (as a condensed format I guess). This device then "turns" bits into pixels again and displays the image that way.

If that is clear enough for you to suggest a better way to achieve what I am after, I'd like to hear it.

Kai

[toc] | [prev] | [next] | [standalone]

#88009

kai.peters@gmail.com writes:
> I though that the bytes type is Python 3 only? If so, I cannot use it.

In Python 2, the regular string type (str) is a byte vector, though it
is immutable.  Do you send one scan line at a time to the rendering
device, or the whole file all at once, or what?  Do you want to dump the
output to a disk file and send that to the rendering device as a
separate step?  Anyway, use the chr function to turn a number like 65
into a character like 'A'.

[toc] | [prev] | [next] | [standalone]

#88012

On Wednesday, 25 March 2015 18:10:00 UTC-7, Paul Rubin  wrote:
> nobody writes:
> > I though that the bytes type is Python 3 only? If so, I cannot use it.
> 
> In Python 2, the regular string type (str) is a byte vector, though it
> is immutable.  Do you send one scan line at a time to the rendering
> device, or the whole file all at once, or what?  Do you want to dump the
> output to a disk file and send that to the rendering device as a
> separate step?  Anyway, use the chr function to turn a number like 65
> into a character like 'A'.

The whole file. The device polls a storage area for incoming files and display them.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web