performance - codility GenomicRangeQuery 算法速度比较 Java 与 Swift

Question

我将解决 GenomicRangeQuery 任务的代码从 Java 重写为 Swift。 Jave 中的代码获得 100/100 分数，但 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 中的一些敏感瓶颈，但我不知道在哪里。

如果有人不知道codility，这就是link到任务。

Answer 1

这个针对 GenomicRangeQuery 问题的 Java 代码在 codility 上得分为 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];
}