1
$\begingroup$

I discussed a question with @gaspanic Python/Biopython - Replace amino acid residue on MSA with "z" from a list of unaligned positions . The issue emerged was speeding up lists in Python. The solutions we discussed were

  1. Raw code
  2. Predefining a list size
  3. deque
1. @gaspanic my code 2. @gaspanic my code 3. @gaspanic my code
3.45-3.48 7.17-7.2 4.38-4.85 7.09-7.23 3.44-3.53 7.21-7.39

Run timings are seconds (3 replicated) above with @gaspanic's code being faster.

What improvements would speed this up?

Here I extended the data set

from itertools import repeat
def iterit(x):
    seq = 'M----KFLAFLCLLGFANAQ-------------D-GKCG----TLSNKSPS--------------------K'
    return ''.join(list(repeat(seq, x)))

if __name__ == '__main__':
    seqE3 = iterit(2800) # length is 201600
    seqE4 = iterit(28000) # length is 2016000
    seqE5 = iterit(280000) # length is 20160000

@gaspanic code

for seqbit in [seqE3,seqE4,seqE5]:
    seq = seqbit
    pos = [2, 5, 10, 11, 14]    
    new_seq = []
    count = 0
    for s in seq:
        if s == "-":
            new_seq.append(s)
        else:
            count += 1
            if count in pos:
                new_seq.append('Z')
            else:
                new_seq.append(s)
   # print(''.join(new_seq))

My code:

# same variables and loop structure
newseq = list()
count = 0
for n,s in enumerate(prot):    
    if str(s) == '-':
        count += 1
        s = '-'
    else:
        if (n + 1 - count) in pos:
            s = 'Z'
    newseq.append(s)
# print(''.join(newseq))

Predefining lists code (additional counter needed for @gaspanic's code:

# same variables and loop structure
new_seq = [] * len(seq)
count = 0
for n,s in enumerate(prot):    
    if str(s) == '-':
        count += 1
        s = '-'
    else:
        if (n + 1 - count) in pos:
            s = 'Z'
    newseq[n] = s

Deque code simply any of the above substituting

newseq = list() 

with

from collections import deque 
newseq = deque()

Suggestions for efficiency improvements welcome.

A solution in Cython code would be cool. PyPI is not sought here.

$\endgroup$

2 Answers 2

2
$\begingroup$

I'd start by saying that Python is inherently slow and this feels like a case of perhaps unnecessary optimisation. With that in mind here are my suggested (untested) optimisations of @gaspanic code:

pos = {2, 5, 10, 11, 14} # make pos a set for O(1) member testing, and don't define inside the loop
for seq in (seqE3,seqE4,seqE5): # Define seq here rather than inside the loop, and use an immutable tuple instead of a mutable list  
    new_seq = []
    count = 0
    for s in seq:
        if s == "-":
            new_seq.append(s)
        else:
            count += 1
            new_seq.append('Z' if count in pos else s) # use ternary operator
$\endgroup$
1
  • $\begingroup$ Thanks, the tuple did add speed, particularly tuple the iterator output. Using a set (the {} brackets) was a good solution and reduced runtime by ~0.5 seconds, which I'd not considered. It was better than tuple in this example. Repositioning pos adds a tiny amount, but agree its better practice and depends on the size of pos (in this case its small). Happy to discuss Python's slow speed in a summary. $\endgroup$
    – M__
    Aug 4, 2022 at 11:42
1
$\begingroup$

Huge thanks to @Chris_Rands, this solution increases runtime by ~ 0.5 seconds uniformly across all coded solutions, so this code has a runtime of just over 3 seconds runtime on the benchmark machine. I incorporated my solution with @Chris_Rands solution and the final runtime I got was:

@gaspanic

1.7 - 1.8 seconds

This being twice the fastest speed in the question and four times the speed of my raw code.

My code

4.4 - 4.5 seconds

However a unique combination is needed:

  1. tuple (Chris Rands)
  2. set - important (Chris Rands)
  3. an iterator
  4. a list comprehension

In particular 3. and 4. are needed in combination. This is explained below.

def iterit(x):
    seq = 'M----KFLAFLCLLGFANAQ-------------D-GKCG----TLSNKSPS--------------------K'
    return tuple(''.join(list(repeat(seq, x))))

def mIterit(seqE3,seqE4,seqE5):
    pos = {2, 5, 10, 11, 14}
    for seqbit in (seqE3,seqE4,seqE5):
        seq = seqbit
        count = 0
        # loc = 0
        for s in seq:
            if s == "-":
                yield '-'
            else:
                count += 1
                if count in pos:
                    yield 'Z'
                else:
                    yield s

f __name__ == '__main__':
    
    seqE3 = iterit(2800) # length is 201600
    seqE4 = iterit(28000) # length is 2016000
    seqE5 = iterit(280000) # length is 20160000
    
    listComp = [i for i in mIterit(seqE3,seqE4,seqE5)]
    

The list comprehension (variable listComp) is the very last line and is crucial to the solution otherwise there is little increase in speed to @Chris_Rand's code. This alternative is to replace the last line with:

newseq = list()
for i in mIterit(seqE3,seqE4,seqE5):
    newseq.append(i)   

A simple:

for i in mIterit(seqE3,seqE4,seqE5):
    pass

Is the same speed as the list comprehension, but its of no value because the output isn't saved to anything.

I was impressed by the interaction between the iterator and list comprehension. The other notable influence on speed is the set described by @Chris_Rand.

How does it work? tuples do increase speed by removing some functional of a list (immutability). Here the gain is small. Placing the pos variable outside the loop speaks for itself (0.1 seconds gain). set is interesting.

The iterator spews out a stream of results via yield which is where it attains its speed. The problem is capturing that stream outside the iterator is expensive. However list comprehensions are faster than standard loops and in this scenerio carry little/no detectable overhead. I was impressed. Up to this point I thought list comprehensions were a bit faster and a lot 'cooler' than loops. I hadn't understood there was a synergy with an iterator.

Is it all worth it? Python can easily achieve faster run times than Java using Cython but I will place the discussion in the chat forum next week.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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