1
\$\begingroup\$

Consider the infinite sequence u, where u is defined as follows:

  • The number u(0) = 1 is the first one in u.
  • For every x in u, then y = 2 * x + 1 and z = 3 * x + 1 are also in u.
  • There are no other numbers in u.
  • u is sorted in increasing order, with no duplicates

The sequence:

u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, …… ]

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on...

Task:

Given parameter n, the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered sequence u.

The code:

def dbl_linear(n):

    u = [1]
    
    if n > 0:
        
        y, z = 2*1+1, 3*1+1
                
        u.append(y), u.append(z)
        
        for i in range(1,n):
            
            y, z = u[i]*2+1, u[i]*3+1
            
            u.append(y), u.append(z)
            
               
            u = sorted(u)
            
    u = sorted(list(set(u))) 
    
    

    return u[n]

The code passed the initial tests, but failed others due to execution timing out. Can I optimize the code (or algorithm) to increase speed?

\$\endgroup\$
1
  • 5
    \$\begingroup\$ The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How do I ask a good question?. \$\endgroup\$
    – BCdotWEB
    Jun 29 at 6:52
3
\$\begingroup\$

Profiling

The first thing you should do when trying to optimize your code is profile. Don't guess what the problem is, Python makes profiling easy and you should use that to your advantage.

This answer will help you get started with profiling, and in combination with the comments on it, you can run the following in your terminal:

python -m cProfile -s time path_to_script.py

This is just one way to profile, and I'm new to using the profiler myself but this one line tells you a lot of information. What I have done, is appended the following to your script

n = 10_000
result = dbl_linear(n)

Running the script with the cProfile command as I have listed above sorts all of the function calls by the amount of time they took to run, and right at the top is your calls to sorted, with a tottime about 5 times longer than the next slowest function, which is your function dbl_linear. This tells us that our main priority should be to try to "speed up" sorted (in fact, we will try to remove sorted where possible).

This answer explains the difference between tottime vs cumtime: cumtime is the total amount of time spent in a function, and tottime is the amount of time spent in a function but not in another function. So, for dbl_linear, the tottime does not include the time spent in sorted, but the cumtime does include the time spent in sorted.

Sorted vs Sort

A quick fix that helps a little is to use inplace sorting by calling u.sort(), as the python docs point out that it is slightly more efficient that sorted. However, this isn't going to be sufficient, it's just something to note.

Bisect

A better solution is to use the fact that you already have a sorted list and use the built-in bisect module. Then, you can replace dbl_linear with

def dbl_linear(n):
    u = [1]
    if n > 0:
        y, z = 2*1+1, 3*1+1
        bisect.insort_left(u, y)
        bisect.insort_left(u, z)
        for i in range(1, n):
            y, z = u[i]*2+1, u[i]*3+1
            bisect.insort_left(u, y)
            bisect.insort_left(u, z)
    u = sorted(list(set(u)))
    return u[n]

bisect.insort_left(a, x) means insert x into a in sorted order. This cuts down on the execution time by a lot because now, instead of sorting each time, you are simply inserting an element in sorted order. The lengthy part of this process is just moving the elements back to create a space for your insertion.

Further improvements

If you remove this line

u = sorted(list(set(u)))

by checking for duplicates before inserting an element in sorted order, you don't have to insert it at all and you can avoid this duplicate elimination line. Then, you can make the adjustment:

for i in range(1, n):
    y, z = u[i]*2+1, u[i]*3+1
    if len(u) > n and u[n] < y:
        break
    insert_no_dups(u, y)
    insert_no_dups(u, z)

Because y is the largest number that can be inserted if u is always sorted. This allows you to avoid computing more values in u than necessary. As it is currently written, your code always computes more elements than necessary.

Incorporating all of these adjustments, here is what I have created for final code:

import bisect

def insert_no_dups(a, x):
    """Insert x into a in sorted order if x isn't in a"""
    position = bisect.bisect_left(a, x)
    if position == len(a):
        a.append(x)
    elif a[position] == x:
        pass
    else:
        a.insert(position, x)

def dbl_linear(n):
    u = [1]
    if n > 0:
        y, z = 2*1+1, 3*1+1
        insert_no_dups(u, y)
        insert_no_dups(u, z)
        for i in range(1, n):
            y, z = u[i]*2+1, u[i]*3+1
            if len(u) > n and u[n] < y:
                break
            insert_no_dups(u, y)
            insert_no_dups(u, z)
    return u[n]
\$\endgroup\$
1
\$\begingroup\$

Algorithm

Because we keep all the duplicates until we've finished generating the list, we're doing much more work than we need to. For each number we reach, we generate two more, and since we're not merging duplicates at that time, that means our work scales as O(2ⁿ). Merging as we go (as recommended by Kraigolas) reduces that, and reduces the storage required to O(n).

Implementation

Since there's only one sequence, but we may want to access it several times during the program, it's worth memoizing the work done so far, to avoid repeating the calculations. We just need to keep the sorted set of results, and the position up to which we have computed additional elements for.

Alternative algorithm

It might be worth considering working from the result set: consider every number in turn and decide whether it's a member of the sequence (x is a member only if either of (x-1)/2 and (x-1)/3 is a member). This requires only the members of the sequence up to x to be stored.

That approach would look something like this:

import bisect
import itertools

u = [1]                         # The sequence

def contains(a, x):
    """
    True if sorted list a contains element x
    >>> contains([1, 2, 3, 4], 2)
    True
    >>> contains([1, 2, 3, 4], 5)
    False
    """
    i = bisect.bisect_left(a, x)
    return i != len(a) and a[i] == x

def dbl_linear(n):
    """
    Finds the nth element from the list beginning with 1,
    where 2n+1 and 3n+1 are members for each n that's a member

    >>> dbl_linear(0)
    1
    >>> dbl_linear(1)
    3
    >>> dbl_linear(2)
    4
    >>> dbl_linear(10)
    22
    """
    global u
    if n < len(u):
        return u[n]
    for x in itertools.count(u[-1]+1):
        if contains(u, (x-1)/2) or contains(u, (x-1)/3):
            u += [x]
            if n < len(u):
                return u[n]



if __name__ == "__main__":
    import doctest
    doctest.testmod()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.