swift2 代码化GenomicRangeQuery算法速度比较Java与Swift

mec1mxoz  于 2022-11-06  发布在  Swift
关注(0)|答案(3)|浏览(167)

我把解决GenomicRangeQuery任务的代码从Java重写到Swift。Jave中的代码得到了100/100的分数,但是Swift中的代码没有通过所有的性能测试。我试图理解为什么代码中的逻辑是相同的。我想知道为什么Swift代码执行这么长时间。我是否在我的Swift代码中使用了一些我不知道的非常慢的部分。请看一下从here复制的Java代码。

class Solution {
  public int[] solveGenomicRange(String S, int[] P, int[] Q) {
    //used jagged array to hold the prefix sums of each A, C and G genoms
    //we don't need to get prefix sums of T, you will see why.
    int[][] genoms = new int[3][S.length()+1];
    //if the char is found in the index i, then we set it to be 1 else they are 0
    // 3 short values are needed for this reason
    short a, c, g;
    for (int i=0; i<S.length(); i++) {
      a = 0; c = 0; g = 0;
      if ('A' == (S.charAt(i))) {
        a=1;
      }
      if ('C' == (S.charAt(i))) {
        c=1;
      }
      if ('G' == (S.charAt(i))) {
        g=1;
      }
      //here we calculate prefix sums. To learn what's prefix sums look at here https://codility.com/media/train/3-PrefixSums.pdf
      genoms[0][i+1] = genoms[0][i] + a;
      genoms[1][i+1] = genoms[1][i] + c;
      genoms[2][i+1] = genoms[2][i] + g;
    }

    int[] result = new int[P.length];
    //here we go through the provided P[] and Q[] arrays as intervals
    for (int i=0; i<P.length; i++) {
      int fromIndex = P[i];
      //we need to add 1 to Q[i],
      //because our genoms[0][0], genoms[1][0] and genoms[2][0]
      //have 0 values by default, look above genoms[0][i+1] = genoms[0][i] + a;
      int toIndex = Q[i]+1;
      if (genoms[0][toIndex] - genoms[0][fromIndex] > 0) {
        result[i] = 1;
      } else if (genoms[1][toIndex] - genoms[1][fromIndex] > 0) {
        result[i] = 2;
      } else if (genoms[2][toIndex] - genoms[2][fromIndex] > 0) {
        result[i] = 3;
      } else {
        result[i] = 4;
      }
    }
    return result;
  }
}

这里同样的代码被重写为Swift 2.1

public func solution(inout S:String, inout _ P:[Int], inout _ Q:[Int]) -> [Int] {
  let len = S.characters.count

  //used jagged array to hold the prefix sums of each A, C and G genoms
  //we don't need to get prefix sums of T, you will see why.
  var genoms = [[Int]](count: 3, repeatedValue: [Int](count: len+1, repeatedValue: 0))

  //if the char is found in the index i, then we set it to be 1 else they are 0
  // 3 short values are needed for this reason
  var a,c,g:Int
  for i in 0..<len {
    a=0; c=0; g=0
    let char = S[S.startIndex.advancedBy(i)]
    switch char {
    case "A": a=1;
    case "C": c=1;
    case "G": g=1;
    default: ()
    }

    //here we calculate prefix sums. To learn what's prefix sums look at here https://codility.com/media/train/3-PrefixSums.pdf
    genoms[0][i+1] = genoms[0][i] + a
    genoms[1][i+1] = genoms[1][i] + c
    genoms[2][i+1] = genoms[2][i] + g

  }

  var result: [Int] = [Int](count: P.count, repeatedValue: 0)
  //here we go through the provided P[] and Q[] arrays as intervals
  for i in 0..<P.count {
    let fromIndex = P[i]
    //we need to add 1 to Q[i],
    //because our genoms[0][0], genoms[1][0] and genoms[2][0]
    //have 0 values by default, look above genoms[0][i+1] = genoms[0][i] + a;
    let toIndex = Q[i] + 1

    if (genoms[0][toIndex] - genoms[0][fromIndex] > 0) {
      result[i] = 1;
    } else if (genoms[1][toIndex] - genoms[1][fromIndex] > 0) {
      result[i] = 2;
    } else if (genoms[2][toIndex] - genoms[2][fromIndex] > 0) {
      result[i] = 3;
    } else {
      result[i] = 4;
    }
  }
  return result
}

有人知道为什么Java代码通过了所有的测试,而Swift代码却没有通过所有的性能测试吗?我想我碰到了Swift中的某个敏感的瓶颈,但我不知道在哪里。
如果有人没有意识到编码,这是任务的link

mrphzbgm

mrphzbgm1#

这段针对GenomicRangeQuery问题的Java代码在编码性上得分为100%。它使用了4个简单的数组来做前缀求和。我把它作为一种替代方法贴在这里。时间复杂度为O(n+m)

public int[] solution4(String S, int[] P, int[] Q){

    char[]chars=S.toCharArray();
    int n=chars.length;

    int[]contaA=new int[n+1];
    int[]contaC=new int[n+1];
    int[]contaG=new int[n+1];
    int[]contaT=new int[n+1];

    for (int i=1;i<n+1;i++){
        contaA[i]=contaA[i-1];
        contaC[i]=contaC[i-1];
        contaG[i]=contaG[i-1];
        contaT[i]=contaT[i-1];
        if (chars[i-1]=='A')contaA[i]+=1;
        if (chars[i-1]=='C')contaC[i]+=1;
        if (chars[i-1]=='G')contaG[i]+=1;
        if (chars[i-1]=='T')contaT[i]+=1;
    }

    int[] arrayContadores=new int[P.length];

    for (int i=0;i<P.length;i++){
        int primeiro=P[i];
        int ultimo=Q[i];

        int A=contaFatia(contaA,primeiro,ultimo);
        int C=contaFatia(contaC,primeiro,ultimo);
        int G=contaFatia(contaG,primeiro,ultimo);
        int T=contaFatia(contaT,primeiro,ultimo);

        if (A>0){arrayContadores[i]=1;
        }else if (C>0) {
            arrayContadores[i] = 2;
        }else if(G>0){
            arrayContadores[i]=3;
        }else if (T>0){
            arrayContadores[i]=4;
        }

    }
    return arrayContadores;
}

public int contaFatia(int[]P,int x,int y){
    return P[y+1]-P[x];
}
ttvkxqim

ttvkxqim2#

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {

   var retArr = [Int]()
   var chrArr = [Character]()

   for chr in S {
       chrArr.append(chr)
   }

   for i in 0..<P.count {

       var minFactor = 4

       if P[i] - Q[i] == 0 {
           if chrArr[P[i]] == "A"{
               minFactor = 1
           }else if chrArr[P[i]] == "C"{
               minFactor = 2
           }else if chrArr[P[i]] == "G"{
               minFactor = 3
           }
       }else {
           for j in P[i]...Q[i] {

               if chrArr[j] == "A"{
                   minFactor = 1
                       break
               }else if chrArr[j] == "C"{
                       minFactor = 2
               }else if chrArr[j] == "G"{
                       if minFactor > 2 {
                           minFactor = 3
                           }
                   }
               }
       }

       retArr.append(minFactor)
   }

   return retArr
}
tp5buhyn

tp5buhyn3#

我已经在斯威夫特玩了一段时间的东西,试图拿出正确的解决方案。这是我最接近的一次。

public func solution(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
    let N = S.count + 1
    var outerImpacts: ContiguousArray<ContiguousArray<Int>> = []
    outerImpacts.reserveCapacity(N)
    for i in 0..<N {
        if i > 0 {
            var innerImpacts = outerImpacts[i - 1]
            switch S[S.index(S.startIndex, offsetBy: i - 1)] {
            case "A":
                innerImpacts[0] += 1
            case "C":
                innerImpacts[1] += 1
            case "G":
                innerImpacts[2] += 1
            case "T":
                innerImpacts[3] += 1
            default:
                break
            }
            outerImpacts.append(innerImpacts)
        } else {
            outerImpacts.append(ContiguousArray<Int>(repeating: 0, count: 4))
        }
    }

    let M: Int = P.count
    var minimalImpacts: [Int] = []
    minimalImpacts.reserveCapacity(M)
    for i in 0..<M {
        for j in 0..<4 where (outerImpacts[Q[i] + 1][j] - outerImpacts[P[i]][j]) > 0 {
            minimalImpacts.append(j + 1)
            break
        }
    }

    return minimalImpacts
}

相关问题