swift6 如何使用 String.Index 创建子字符串键来计算所有大小为 2 的子字符串的所有出现次数

Question

我对 String.Index 不熟悉，有没有比这更好的方法制作子字符串键：

let seq = "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGA"
let keysize = 2
let lasti = seq.count - keysize
var counts: [String: Int] = [:]

for i in 0...lasti { 
   let ii = seq.index(seq.startIndex, offsetBy: i)
   let jj = seq.index(ii, offsetBy: keysize)     
   
   let key = String( seq[ii..<jj] )     
   if let v = counts[key] {   
      counts[key] = v + 1  
   } else {
      counts[key] = 1 
   }
}
for (k,v) in counts {
   print("\(k): \(v)")   
}

结果：

CC: 5
TA: 1
TG: 3
GC: 9
CG: 7
GT: 2
GA: 3
CA: 3
AC: 2
TC: 2
AG: 3
AT: 1
TT: 2
GG: 12
AA: 1
CT: 3

Answer 1

在内部，String 对象可以以不同的编码保存数据。例如，UTF8 使用可变的字节数来存储每个字形。因此，通过索引获取字形的成本相对较高。

String.Index

使您能够编写快速高效地遍历字符串的代码，但是从第一个字形开始索引（使用

index(:offsetBy:)

）并使用计数到末尾的索引，每次调用的时间复杂度都为

O(n)

。因此，您的代码将具有 ≈

O(n^2)

（又名“n 平方”）时间复杂度。对于短字符串，这不会是一个大问题，但如果你尝试将其应用于更长的字符串，它的性能会变得非常糟糕。

您应该尝试重写它以使用基于先前索引的 String.Index 。或者，您可以将字符串转换为字符数组，并使用整数索引对其进行索引。这很快，但需要更多内存。