не может пройти производительность в тесте Codility GenomicRangeQuery

Question

Не могли бы вы проверить код и сообщить, что мне нужно сделать, чтобы повысить производительность? Эта проблема производительности заставляет меня злиться на Codility. Вот вопрос и мой код ниже.

Спасибо за вашу помощь отныне.

Тест:

спросите описание Последовательность ДНК может быть представлена ​​в виде строки, состоящей избукв A, C, G и T, которые соответствуют типам последовательных нуклеотидов в последовательности. Каждый нуклеотид имеет ударный фактор, который является целым числом. Нуклеотиды типов A, C, G и T имеют импакт-факторы 1, 2, 3 и 4 соответственно. Вы собираетесь ответить на несколько запросов в форме: Каков минимальный импакт-фактор нуклеотидов, содержащихся в определенной части данной последовательности ДНК?

Последовательность ДНК дана в виде непустой строки S = ​​S[0] S [1] ... S [N-1], состоящий из N символов. Есть M запросов, которые даны в непустых массивах P и Q, каждый из которых состоит из M целых чисел. K-й запрос (0 ≤ K

Например,рассмотрим строку S = CAGCCTA и массивы P, Q такие, что:

P[0] = 2    Q[0] = 4
P[1] = 5    Q[1] = 5
P[2] = 0    Q[2] = 6

Ответы на эти запросы M = 3 следующие:

Часть ДНК между позициями 2 и4 содержит нуклеотиды G и C (дважды), факторы воздействия которых равны 3 и 2 соответственно, поэтому ответ равен 2. Часть между позициями 5 и 5 содержит один нуклеотид T, фактор воздействия которого равен 4, поэтому ответ равен 4. Часть между позициями 0 и 6 (вся строка) содержит все нуклеотиды, в частности нуклеотид A, коэффициент воздействия которого равен 1, поэтому ответ равен 1. Напишите функцию:

class Solution {public int [] solution(Строка S, int [] P, int [] Q);}

что, учитывая непустую строку S, состоящую из N символов и два непустых массива P и Q, состоящие из M целых чисел, возвращает массив, состоящий из M целых чисел, задающих последовательные ответы на все запросы.

Массив результатов должен быть возвращен в виде массива целых чисел.

Например, если задана строка S = CAGCCTA и массивы P, Q такие, что:

P[0] = 2    Q[0] = 4
P[1] = 5    Q[1] = 5
P[2] = 0    Q[2] = 6

функциядолжен вернуть значения [2, 4, 1], как описано выше.

Напишите эффективный алгоритм для следующих предположений:

N - целое число в диапазоне [1..100,000];М представляет собой целое число в диапазоне [1,50 000];каждый элемент массивов P, Q представляет собой целое число в диапазоне [0..N - 1];P [K] ≤ Q [K], где 0 ≤ K

Мое решение:

  public static int[] solution(String S, int[] firstArray, int[] secondArray) {
    String subStr="";
    int[] result = new int[firstArray.length];
    for(int i=0; i < firstArray.length; i++)  {
        subStr = S.substring(firstArray[i], secondArray[i] + 1);
        if(subStr.contains("A")) { result[i] = 1; }
        else if(subStr.contains("C")){ result[i] = 2; }
        else if(subStr.contains("G")){ result[i] = 3;
        } else if(subStr.contains("T")){ result[i] = 4;
        }
    }

return result;}

Answer 1

Ваше решение имеет сложность O (M * N).
Внешний цикл: для (int i = 0; i Внутренний цикл: оценка списка S изРазмер N для построения subStr (Сложность - MxN на данный момент)
Тот же Внутренний цикл: проверьте каждый subStr, если он содержит каждую из 4 букв (Сложность - MxN на данный момент)

Для повышения производительности, вашРешение должно покончить с внутренней петлей. Один из способов сделать это - преобразовать S в форму, в которой мы можем получить доступ к соответствующим значениям напрямую, а не выполнять итерацию (т. Е. Построить subStr).

Один из способов преобразовать S в нечто релевантное, доступное напрямую, - этосохраните последнюю наблюдаемую позицию для каждого из 4 нуклеотидов (A / C / G / T) в каждой позиции в последовательности.

Например, если S = ​​"CGGT", мы можем преобразовать его в-1 со ссылкой на «еще не наблюдалось»:

Idx A, C, G, T  
0  [-1, 0,-1,-1]  
1  [-1, 0, 1,-1]  
2  [-1, 0, 2,-1]  
3  [-1, 0, 2, 3]

С помощью этой матрицы мы теперь можем напрямую обращаться к ней, чтобы получить соответствующие значения. В этом случае, если мы пытаемся получить соответствующие значения для subStr «GG», то есть P [0] = 1 и Q [0] = 2, то нам просто нужно получить доступ к индексу 2. В этом случае [-1, 0, 2, -1] говорит нам, что только индекс G последний раз наблюдался после индекса 1, следовательно, минимальное влияние - это отображение G на его фактор воздействия.

Построение матрицы имеет сложность O (N). Итерация по P и Q имеет сложность O (M). Поскольку нет вложенных циклов, общая сложность составляет O (N + M).

Ниже приведен фрагмент реализации в Python:

def solution(S,P,Q):
    l = len(S)    
    lastSeen = [[-1,-1,-1,-1] for x in range(l)]
    for x in range(len(S)):
        for i,j in enumerate(list("ACGT")):
            if S[x] == j:
                lastSeen[x][i] = x
            elif x>0: 
                lastSeen[x][i] = lastSeen[x-1][i]

    res = []
    for x in range(len(P)):
        startIdx = P[x]
        relevantLastSeen = lastSeen[Q[x]]
        res.append((min([i+1 for i,x in enumerate(relevantLastSeen) if x>=startIdx])))

    return res