Take into consideration Long Arrays/Strings-CodePudding

I've been trying the challenges/Exercises of codility and I've come across a problem. When it tests Large Arrays/Strings my code always results in Timeout Errors. An example of this would be the following challenge: "GenomicRangeQuery"

A non-empty zero-indexed string S is given. String S consists of N characters from the set of upper-case English letters A, C, G, T.

This string actually represents a DNA sequence, and the upper-case letters represent single nucleotides.

You are also given non-empty zero-indexed arrays P and Q consisting of M integers. These arrays represent queries about minimal nucleotides. We represent the letters of string S as integers 1, 2, 3, 4 in arrays P and Q, where A = 1, C = 2, G = 3, T = 4, and we assume that A < C < G < T.

Query K requires you to find the minimal nucleotide from the range (P[K], Q[K]), 0 ≤ P[i] ≤ Q[i] < N.

For example, consider string S = GACACCATA and arrays P, Q such that:

P[0] = 0    Q[0] = 8
P[1] = 0    Q[1] = 2
P[2] = 4    Q[2] = 5
P[3] = 7    Q[3] = 7

The minimal nucleotides from these ranges are as follows:

(0, 8) is A identified by 1,
(0, 2) is A identified by 1,
(4, 5) is C identified by 2,
(7, 7) is T identified by 4.

Write a function:

class Solution { public int[] solution(String S, int[] P, int[] Q); }

that, given a non-empty zero-indexed string S consisting of N characters and two non-empty zero-indexed arrays P and Q consisting of M integers, returns an array consisting of M characters specifying the consecutive answers to all queries.

For example, given the string S = GACACCATA and arrays P, Q such that:

P[0] = 0    Q[0] = 8
P[1] = 0    Q[1] = 2
P[2] = 4    Q[2] = 5
P[3] = 7    Q[3] = 7

the function should return the values [1, 1, 2, 4], as explained above.

Assume that:

N is an integer within the range [1..100,000];
M is an integer within the range [1..50,000];
each element of array P, Q is an integer within the range [0..N − 1];
P[i] ≤ Q[i];
string S consists only of upper-case English letters A, C, G, T.

Below is the code I've come up with but unfortunately always gives me the Timeout Error when going against Large Arrays/Strings. If you have suggestions on how to improve or wipe out that error please don't hesitate! I'm always trying to think outside of the box and come up with solutions of my own but that error has been plaguing me for a while.

import java.util.Arrays;

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        // A impact = 1; C=2, G=3; T=4
        // S not empty
        // minimal impact
        String[] split;
        int[] stringToIntegers = new int[S.length()];
        int[] solution = new int[P.length];

        if(S.isEmpty()) return solution;
        if(P.length != Q.length) return solution;
        split = S.split("");

        for(int k=0;k<split.length;k  ){
            switch(split[k]){
                case "A":
                    stringToIntegers[k] = 1;
                    break;
                case "C":
                    stringToIntegers[k] = 2;
                     break;
                case "G":
                    stringToIntegers[k] = 3;
                    break;
                case "T":
                    stringToIntegers[k] = 4;
                    break;
            }
        }
        for(int i =0; i<solution.length;i  ){
                solution[i] = LowestValue(stringToIntegers, P[i], Q[i]);
        }
        return solution;
    }

    public int LowestValue(int[] stringToIntegers, int pValue, int qValue){
        int minimalImpact = 4;
        for(int j = pValue; j <= qValue; j  ){
            if(stringToIntegers[j] < minimalImpact){
                minimalImpact = stringToIntegers[j];
            }
        }
        return minimalImpact;
    }
}

CodePudding user response：

One simple optimization would be to short-circuit the innermost loop when you have found the value 1 (as you will not be able to find a lower value):

for(int j = pValue; j <= qValue; j  ){
   if(stringToIntegers[j] < minimalImpact){
      minimalImpact = stringToIntegers[j];
      if(minimalImpact == 1)
         return 1;
   }
}
return minimalImpact;

CodePudding user response：

HMMMMMMMM OH WOW MAN ... WOW ... a timeout you say ... WOW .... Did someone mention Deoxy Ribo Nucleic Acid? i think the problem you have is more you may be using a large PC not a "Super Cradle" !!!!!!!!!!!!!!!!!!!!!

Do not use String/arrays unless there may be ISO character set problems, then those should be char[] arrays. Get the String data to match and chew through it reading it from a file into a temporary handlable String[] array looping over it, such as a java.io.RandomAccessFile com.nicephotog.tools.discfileifc Interface FileUnitisedByteRead may be useful https://drive.google.com/file/d/1IBbsBY9zWewKaq7hYnTzdI4M1XcVWELS/view?usp=sharing *note randomacessfile can have its file length extended or created at size required.

First, setup your java program command line for https://docs.oracle.com/javase/8/docs/technotes/tools/unix/java.html

-Xss1024k (1mb is maximum under Linux or Win X64) this is your maximum stack size memory reserved, it is the most important because it will allow the variables and methods to shift the values and operations around in the registers.

Then the others used usually in the startup java command https://docs.oracle.com/cd/E15289_01/JRPTG/memman.htm

-Xms

-Xmx

-XX:ErrorFile=filename

You cannot do that with a string that long, chew along it in pieces. A regex would have the same memory problem. You should also asses whether your data contains "2 byte" characters to match in the charset data that may need searching the extracted array section first before to find them and the array end last element whether it is suspected part of a 2 byte character. This last scenario has array length and file read skip over single element problems to custom write into the code.