is it possible to convert this loop into a list comprehension in python

Question

I have this small bit of code which I want to know if it could be written in list comprehension. The while loop part is what I am interested in condensing.

>>> sum=33
>>> final_list=[]
>>> LastCoin=[0, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 
           1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 1]
>>> while sum>0:
...    final_list.append(LastCoin[sum])
...    sum-=LastCoin[sum]
... 
>>> print final_list
[1, 2, 5, 5, 5, 5, 5, 5]
>>> 

Answer 1

I maybe a bit late to the party. With python 3.9, we can use walrus operator (:=)

If we use that, we can do the following and reduce the while statement to one line.

LastCoin=[0, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5, 1, 2,
          1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5,
          1, 2, 1, 2, 5, 1, 2, 1]

s = 33

final_list = [LastCoin[s]]
while (s:=s-LastCoin[s]) > 0: final_list.append(LastCoin[s])

print (final_list)

The output of this will be:

[1, 2, 5, 5, 5, 5, 5, 5]

Answer 2

Yes, it's possible:

counter = 33 # your sum variable
LastCoin = [0, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5, 1, 2,
            1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 1]

final_list = [LastCoin[reduce(lambda x, y: x - LastCoin[x],
                              range(counter, i, -1))]

              for i in range(counter -1, 0, -1)

              if reduce(lambda x, y: x - LastCoin[x],
                        range(counter, i, -1))
              ]

print(final_list)
# [1, 2, 5, 5, 5, 5, 5, 5]

But, it's not way of import this !

Answer 3

Edit

Better solution

Not trying to use a list comprehension. Using recursion instead.
Simpler, and time of execution divided by 3 compared to my former solution.

LastCoin=[0, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5, 1, 2,
          1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5,
          1, 2, 1, 2, 5, 1, 2, 1]

def nekst(x,L,rec=None):
    if rec is None: rec = []
    rec.append(L[x])
    if x-L[x]>0: nekst(x-L[x],L,rec)
    return rec

print nekst(33,LastCoin)

result

[1, 2, 5, 5, 5, 5, 5, 5]

Comparing execution times

NB: the following tests are done with recursive functions that haven't the line
if rec is None: rec = [].
The presence of this line increases a little (+12%) the execution time of the solution with a recursive function.

from time import clock

iterat = 10000
N = 100

LastCoin=[0, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5, 1, 2,
          1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5,
          1, 2, 1, 2, 5, 1, 2, 1]

counter = 33
te = clock()
for i in xrange(iterat):
    final_list = [LastCoin[reduce(lambda x, y: x - LastCoin[x],
                                   range(counter, i, -1))]
                   for i in range(counter -1, 0, -1)
                   if reduce(lambda x, y: x - LastCoin[x],
                             range(counter, i, -1))]
print clock()-te,'Omid Raha'

st=33
E1 = []
for n in xrange(N):
    te = clock()
    for i in xrange(iterat):
        susu2 = [st]
        susu2.extend(x for x in xrange(st,0,-1)
                     if x==(susu2[-1]-LastCoin[susu2[-1]]))
        fifi2 = [LastCoin[x] for x in susu2]
        del fifi2
    E1.append(clock()-te)
t1 = min(E1)
print t1,'eyquem 1'

E2 = []
for n in xrange(N):
    te = clock()
    for i in xrange(iterat):
        def nekst(x,L,rec):
            rec.append(L[x])
            if x-L[x]>0: nekst(x-L[x],L,rec)
            return rec
        fifi3 = nekst(st,LastCoin,[])
        del fifi3,nekst
    E2.append(clock()-te)
t2 = min(E2)
print t2,'eyquem 2, nekst redefined at each turn of the measurement loop'

def nekst(x,L,rec):
    rec.append(L[x])
    if x-L[x]>0: nekst(x-L[x],L,rec)
    return rec

E22 = []
for n in xrange(N):
    te = clock()
    for i in xrange(iterat):
        fifi3 = nekst(st,LastCoin,[])
        del fifi3
    E22.append(clock()-te)
t22 = min(E22)
print t22,'eyquem 2, nekst defined outside of the measurement loop'

W = []
for n in xrange(N):
    te = clock()
    for i in xrange(iterat):
        y = 33
        final_list=[]
        while y>0:
            final_list.append(LastCoin[y])
            y-=LastCoin[y]
        del final_list,y
    W.append(clock()-te)
tw = min(W)
print tw,'while-loop == %.1f %% of %s' % (100*min(W)/min(E22),min(E22))

result

4.10056836833 Omid Raha
0.29426393578 eyquem 1
0.114381576429 eyquem 2, nekst redefined at each turn of the measurement loop
0.107410299354 eyquem 2, nekst defined outside of the measurement loop
0.0820501882362 while-loop == 76.4 % of 0.107410299354

It's a little faster if the definition of the function nekst() is executed outside the timing loop.

.

Original answer slightly edited

I couldn't do better than that:

sum=33
LastCoin=[0, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5, 1, 2,
          1, 2, 5, 1, 2, 1, 2, 5, 1, 2, 1, 2, 5,
          1, 2, 1, 2, 5, 1, 2, 1]

susu = [sum]
susu.extend(x for x in xrange(sum,0,-1)
            if x==(susu[-1]-LastCoin[susu[-1]]))
fifi = [LastCoin[x] for x in susu]

print 'susu  == %r\n'\
      'fifi  == %r\n'\
      'wanted : %r' % (susu,fifi,[1, 2, 5, 5, 5, 5, 5, 5])

result

susu  == [33, 32, 30, 25, 20, 15, 10, 5]
fifi  == [1, 2, 5, 5, 5, 5, 5, 5]
wanted : [1, 2, 5, 5, 5, 5, 5, 5]

.

The edit is:

x for x in xrange(sum,0,-1) if x==(susu[-1]-LastCoin[susu[-1]])
instead of original
x for x in xrange(sum,-1,-1) if x==(susu[-1]-LastCoin[susu[-1]])!=0

Answer 4

Is there any good reason you are trying to use a list comprehension?

I see personally a lot of people trying to wedge list comprehensions where they don't belong, because, you know, 'list comprehensions are faster - they're in native C! whereas your boring loop is in interpreted Python'. That's not always true.

Just as a reference, if we compare your original solution, which is concise and readable, against the two proposed answers, you may find your assumptions violated:

In [5]: %%timeit
   ...: sum=33
   ...: while sum > 0:
   ...:     final_list.append(LastCoin[sum])
   ...:     sum -= LastCoin[sum]
   ...:
100000 loops, best of 3: 1.96 µs per loop

In [6]: %%timeit
   ...: sum=33
   ...: susu = [sum]
   ...: susu.extend(x for x in xrange(sum,-1,-1)
   ...:             if x==(susu[-1]-LastCoin[susu[-1]])!=0)
   ...: fifi = [LastCoin[x] for x in susu]
   ...:
100000 loops, best of 3: 10.4 µs per loop
# 5x slower

In [10]: %timeit final_list = [LastCoin[reduce(lambda x, y: x - LastCoin[x], range(counter, i, -1))] for i in range(counter -1, 0, -1) if reduce(lambda x, y: x - LastCoin[x], range(counter, i, -1))]
10000 loops, best of 3: 128 µs per loop
# More than 60x slower!!

A list comprehension is a good choice if you are trying to do something for every element in a list - filtering (test every element for true/false), translation, etc. where the operation is separate for every element (and, theoretically, could often be parallelized). It's not very good at loops which do processing and change state during the loop, and they usually look ugly when you try. In this particular case, you only look at 8 items as you go through the list, because you are manually calculating indices to look at. In the list comprehension case, you would have to at least look at all 33.

I don't know if that's your motivation, but if it is, just leave it as a loop. Python loops aren't that bad after all!