我将解决 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,这是任务的链接。
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];
}
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
}
我已经在 Swift 中尝试了一段时间,试图找到正确的解决方案。这是我最近的一次。
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
}
快速 100% 解决方案。 主要原因是使用
NSString
而不是 String.index(_:offsetBy:)
函数,因为 index
根据 documentation有
O(N)
func solution2(_ S : inout String, _ P : inout [Int], _ Q : inout [Int]) -> [Int] {
let S = S as NSString
var solution = Array(repeating: 0, count: P.count)
var pA = Array(repeating: 0, count: S.length + 1)
var pC = Array(repeating: 0, count: S.length + 1)
var pG = Array(repeating: 0, count: S.length + 1)
for i in 1..<S.length + 1 {
let character = S.character(at: i - 1)
pA[i] = pA[i - 1] + (character == 65 ? 1 : 0)
pC[i] = pC[i - 1] + (character == 67 ? 1 : 0)
pG[i] = pG[i - 1] + (character == 71 ? 1 : 0)
}
for i in 0..<P.count {
let upperBound = Q[i] + 1
let lowerBound = P[i]
if pA[upperBound] - pA[lowerBound] > 0 {
solution[i] = 1
} else if pC[upperBound] - pC[lowerBound] > 0 {
solution[i] = 2
} else if pG[upperBound] - pG[lowerBound] > 0 {
solution[i] = 3
} else {
solution[i] = 4
}
}
return solution
}