Genomic Range Query in Python

Question

Recently, I worked on one of the Codility Training - Genomic Range Query (please refer to one of the evaluation report for the detail of the task.

The solution in Python is based on prefix sum, and was adjust in accordance to this article.

import copy

def solution(S, P, Q):
    length_s = len(S)
    length_q = len(Q)

    char2digit_dict = {'A':1, 'C':2, 'G':3, 'T':4}
    str2num = [0]*length_s

    count_appearances = [[0, 0, 0, 0]]*(length_s+1)
    cur_count = [0, 0, 0, 0]

    for i in range(0, length_s):
        str2num[i] = char2digit_dict[S[i]]

        cur_count[str2num[i]-1] += 1
        count_appearances[i+1] = copy.deepcopy(cur_count)

    results = []
    for i in range(0, length_q):
        if Q[i] == P[i]:
            results.append(str2num[Q[i]])

        elif count_appearances[Q[i]+1][0] > count_appearances[P[i]][0]:
            results.append(1)
        elif count_appearances[Q[i]+1][1] > count_appearances[P[i]][1]:
            results.append(2)
        elif count_appearances[Q[i]+1][2] > count_appearances[P[i]][2]:
            results.append(3)
        elif count_appearances[Q[i]+1][3] > count_appearances[P[i]][3]:
            results.append(4)

    return results

However, the evaluation report said that it exceeds the time limit for large-scale testing case (the report link is above).

The detected time complexity is \$O(M * N)\$ instead of \$O(M + N)\$. But in my view, it should be \$O(M + N)\$ since I ran a loop for \$N\$ and \$M\$ independently (\$N\$ for calculating the prefix sum and \$M\$ for getting the answer).

Could anyone help me to figure out what the problem is for my solution? I get stuck for a long time. Any performance improvement trick or advice will be appreciated.

Answer 1

I'm not sure that I trust Codility's detected time complexity. As far as I know, it's not possible to programmatically calculate time complexity, but it is possible to plot out a performance curve over various sized datasets and make an estimation.

That being said, there are a number of unnecessary overhead in your code and so it is possible that Codility is interpreting that overhead as a larger time complexity.

As for your code, Python is all about brevity and readability and generally speaking, premature optimization is the devil.

1. Some of your variable names are not in proper snake case (str2num, char2digit_dict).

2. List memory allocation increases by a power of 2 each time it surpasses capacity, so you really don't have to pre-allocate the memory for it, it's marginal.

3. You convert your string into a list of digits, but then only ever use it in a way that could be fulfilled with your original dict. The list of digits is not really needed since you are already computing a list of prefix sums.

4. In the C solution it was important to calculate the len of the P/Q list first so that it's not recalculated every time, but in Python, range (xrange in Python2) is evaluated for i exactly once.

5. It's not necessary to deepcopy cur_count as it only contains integers, which are immutable. You can copy the list by just slicing itself, list[:]

6. Instead of constantly making references to count_appearances (up to 4x each iteration), you could just make the reference once and store it. This will also make it easier to update your references if the structure of P and Q were to change in any way.

Cleaning up your code in the ways I mentioned gives me:

def solution(S, P, Q):
    cost_dict = {'A':1, 'C':2, 'G':3, 'T':4}

    curr_counts = [0,0,0,0]
    counts = [curr_counts[:]]
    for s in S:
        curr_counts[cost_dict[s]-1] += 1
        counts.append(curr_counts[:])

    results = []
    for i in range(len(Q)):
        counts_q = counts[Q[i] + 1]
        counts_p = counts[P[i]]

        if Q[i] == P[i]:
            results.append(cost_dict[S[Q[i]]])
        elif counts_q[0] > counts_p[0]:
            results.append(1)
        elif counts_q[1] > counts_p[1]:
            results.append(2)
        elif counts_q[2] > counts_p[2]:
            results.append(3)
        elif counts_q[3] > counts_p[3]:
            results.append(4)

    return results

which gets a perfect score on Codility.