CODEWITHSUNDEEP
pythonalgorithmlistsorting
DADI
DADI

Reputation: 41

what's the fastest way to sort/filter/sum increasing digits of numbers in a list

example: 

L = [12,14,22,41,21,23]

and I want the result to be:

R == [12,14,22,23]

The digits of the number must be in an increasing order, following are my solutions and they both work, but they both are too slow.

What's the fastest way of sorting it?

solution one:

R = filter(lambda j: int(''.join(sorted(str(j))))==j , L)

solution two:

for j in L:
      if int(''.join(sorted(str(j))))==j:
          R.append(j)

Question 2 - additionally, I want the sum of adding these corresponding digits equal to 5.

Here are my solutions, again, they do work but are too slow.

So what is the fastest way of doing it.

newR_should_be == [14,23]

one:

newR = filter(lambda i: sum([int(x) for x in str(i)])==5 ,R)

two:

for i in R:
         if sum([int(x) for x in str(i)])==5:
             newR.append(i)

Any help would be appreciated.

Upvotes: 0

Views: 172

Answers (4)

alexdor
alexdor

Reputation: 866

Olivier Melançon solution is very elegant. However, if you are willing to write code that is a little uglier, you can get it to run quite a bit faster by avoiding string conversions and doing both tests at once. I implemented your solution ast1, Olivier Melançon as t2, and mine as t3.

def FastFilter(n):
    x = n % 10
    s = x
    n //= 10
    while n:
        y = n % 10
        s += y
        if (x < y):
            return False
        x = y;
        n //= 10
    return s==5

def sort_by_digits(l):
    return sorted(set(int(''.join(sorted(str(x)))) for x in l))

def filter_by_sum(l, total=5):
    return [x for x in map(str, l) if sum(map(int, x)) == total]

def t1(L):
    R = filter(lambda j: int(''.join(sorted(str(j))))==j , L)
    newR = filter(lambda i: sum([int(x) for x in str(i)])==5 ,R)
    return sorted(newR)

def t2(l):
    return sort_by_digits(filter_by_sum(l))

def t3(l):
    return sorted(filter(FastFilter, l))

l = [12, 14, 22, 41, 21, 23]

%timeit t1(l)
%timeit t2(l)
%timeit t3(l)

Gives

11.2 µs ± 24.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
8.88 µs ± 24.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
2.71 µs ± 12.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Upvotes: 4

Richard
Richard

Reputation: 61399

This is one reason I don't like Python: the simple solution you propose, which would work well enough in most languages, is probably as slow as molasses in Python. Too many high-level operations.

But we can work around this by using Numpy as follows:

#!/usr/bin/env python3

import numpy as np

COUNT      = 1000
MAXNUM     = 100000
MAXDIGITS  = 6
prevremain = 99*np.ones(COUNT)                        #The previous digit we removed from the RHS
origdata   = np.random.randint(0,MAXNUM,size=COUNT)   #Original data
quot       = origdata.copy()                          #What's left when we remove a digit from the RHS
good       = np.ones(COUNT)                           #Whether the number's digits are monotonically decreasing from right to left

for i in range(1,MAXDIGITS):                          #Pull digits off of the numbers one at a time
  quot, remain = np.divmod(quot,10)                   #quot is the rest of the number, remain is the right-most digit
  #Check to see if this digit was smaller, or equal to, than the last one we
  #removed. NOTE: If you have numbers with an unequal number of digits, you'll
  #need to think carefully about whether `<=` might work better for you.
  good         = np.logical_and(good, (remain < prevremain))
  prevremain   = remain

#These are the numbers you want
print(origdata[good])

Numpy offloads more of the computation to low-level libraries which work quickly. In this case, it can use vectorized math operations to perform digit checks across your entire input quickly. You can then use these as a filter.

Upvotes: 0

Olivier Melan&#231;on
Olivier Melan&#231;on

Reputation: 22324

Relying on Python built-in is often the most efficient way to go. It also allow to do a lot with only a few lines of code.

l = [12, 14, 22, 41, 21, 23]

def sort_by_digits(l):
    return sorted(set(int(''.join(sorted(str(x)))) for x in l))

sort_by_digits(l) # [12, 14, 21, 23]

As for the sum, you can do something similar.

def filter_by_sum(l, total=5):
    return [x for x in map(str, l) if sum(map(int, x)) == total]

sort_by_digits(filter_by_sum(l)) # [14, 23]

Upvotes: 0

Ajax1234
Ajax1234

Reputation: 71461

If you are attempting a functional approach, i.e filter, you can try this:

L = [12,14,22,41,21,23]
while not all(L[i] <= L[i+1] for i in range(len(L)-1)):
  L = map(lambda x:x[-1], filter(lambda x:L[x[0]+1] >= x[-1] if x[0]+1 < len(L) else True, zip(range(len(L)), L)))

print(L)

Output:

[12, 14, 21, 23]

Upvotes: 0

Related Questions