Question

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

let a = "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGA"

let keysize = 2
let size = a.count + 1 - keysize
var counts: [String: Int] = [:]

var i = 0
while i < size {
   let start_offset = a.index(seq.startIndex, offsetBy: i)
   let end = a.index(start_offset, offsetBy: keysize)     
   if let key = String( a[start_offset..<end] ) {   
      if let v = counts[key] {   
         counts[key] = v + 1  
      } else {
         counts[key] = 1 
      }
   }
   i += 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

你现在的代码有什么不好的？我认为这样就没问题了。 — 
@Alexander OP 的代码正在执行windows(ofCount: 2)，而不是chunks。 — 
.chunks(of:)行不通。原帖作者想要一串"123456"来生成["12", "23", "45", "56"]。.chunks(of:2)只会生成["12", "34", "56"] —

Accepted Answer

你可以尝试使用这个。在 Xcode 16.0 中测试

let seq = "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGA"
let keysize = 2
var counts: [String: Int] = [:] 
for i in seq.indices.dropLast(keysize - 1) { 
let key = String(seq[i..<seq.index(i, offsetBy: keysize)])
 counts[key, default: 0] += 1 
}

非常优雅的解决方案。（已投票）。我喜欢使用indices.dropLast、和counts[key, default: 0] += 1。当它首次添加到语言中时，我读到了它，但没有使用过它，所以忘记了它。 —

Answer 2

官方的包可以简化这一工作，使用：

import Algorithms

let counts = seq
    .windows(ofCount: 2)
    .reduce(into: [:]) { counts, window in
        counts[window, default: 0] += 1
    }

counts
    .sorted { $0.value > $1.value } // Optional: sort before printing
    .forEach { k, v in print("\(k): \(v)") }

7

有趣。@Sweeper 有点暗示但又有点没有？

–
错误：没有这样的模块“算法”

–
1

您需要将其添加为依赖项： … 请参阅

–
考虑到具体问题及其规模，我预计这将极大地受益于将文件读取为Data而不是构造字符串。Alexander 的代码对于数据的工作方式相同，除了位print，您需要使用将其重新转换为字符串String(decoding: k, as: UTF8.self)。在您的情形下，您可能能够避免制作许多字符串，这很好。避免这种情况可能会大大提高性能，特别是如果您使用读取文件Data(contentsOf: url, options: [.mappedIfSafe])，这可以避免将文件一次性加载到内存中。

–
@igouy 阅读我链接的包的说明。它显示了如何将其添加到您的项目中。此外，如果性能是一个问题，Rob 建议直接使用数据，这很好。

–

|

Answer 3

在内部，String 对象可以以不同的编码保存其数据。例如，UTF8 使用可变数量的字节来存储每个字形。因此，按索引获取字形的成本相对较高。String.Index使您能够编写快速高效地遍历字符串的代码，但从第一个字形（使用index(:offsetBy:)）开始索引，并使用计数到末尾的索引，O(n)每次调用都有时间复杂度。因此，您的代码将具有 ≈ O(n^2)（又称“n 平方”）时间复杂度。对于短字符串，这不是什么大问题，但如果您尝试将其应用于较长的字符串，其性能将变得非常糟糕。

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

将字符串转换为数组的方法Character可能如下所示：

import Foundation

let seq = "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGA"

let array = Array(seq)
let pairs = NSCountedSet()
for index in 0..<array.count-1 {
    let pair = "\(array[index])\(array[index+1])"
    pairs.add(pair)
}
pairs.forEach { print($0, pairs.count(for: $0))}

（NSCountedSet似乎比字典更适合您的应用程序，尽管您当然可以使用字典。）

我编写了一些代码，使用字符数组将您的方法与我的方法进行比较：

import Foundation

let alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
let alphaArray = Array(alphabet)
var seq = ""
var counts: [String: Int] = [:]

func addPair(aPair: String) {
    if let v = counts[aPair] {
       counts[aPair] = v + 1
    } else {
       counts[aPair] = 1
    }
}

for _ in 0...100_000 {
    seq.append(alphaArray[Int.random(in:0..<alphaArray.count)] )
}
var start = Date()
let array = Array(seq)
let pairs = NSCountedSet()
for index in 0..<array.count-1 {
    let pair = "\(array[index])\(array[index+1])"
    pairs.add(pair)
}
let elapsed1 = -start.timeIntervalSinceNow
print(elapsed1)

start = Date()
let keysize = 2
let lasti = seq.count - keysize

counts = [:]

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] )
    pairs.add(key)
}
let elapsed2 = -start.timeIntervalSinceNow
print(elapsed2)
print("Array processing is \(elapsed2/elapsed1) times faster")

输出为

0.03937792778015137
25.516054034233093
Array processing is 647.9785878193057 times faster

因此，对于 100_000 个字符，基于数组的方法几乎快 650 倍。对于较大的字符串，从起始位置偏移的方法会变得非常非常慢。（对于大型数据集，N 平方的性能会很快下降。）

>您应该尝试重写它以使用基于前一个索引的 String.Index。<是的，我需要一个示例来说明如何做到这一点。 — 
我使用数组添加了一个答案。请参阅 Kendar Sukerkar 关于使用索引的代码的出色答案。 — 
对于 250MB 长的字符串，您的解决方案很可能无法在您的一生中完成。（对于大型数据集，n 平方时间性能非常差。对于 250MB，这大约是68,719,476,736,000,000 次操作。） — 
我对原来的程序做了一些小的调整，但似乎性能发生了根本性的改变。 — 
Kedar Sukerkar 的答案可能是最好的。它应该表现得非常好，并且可以处理您需要的任何块大小。 —

Answer 4

.utf8性能更佳（250MB输入）。

let seq = "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGA"
let a = seq.utf8

let keysize = 2
let size = a.count + 1 - keysize
var counts: [String: Int] = [:]

var i = 0
while i < size {
   let start_offset = a.index(seq.startIndex, offsetBy: i)
   let end = a.index(start_offset, offsetBy: keysize)     
   if let key = String( a[start_offset..<end] ) {   
      if let v = counts[key] {   
         counts[key] = v + 1  
      } else {
         counts[key] = 1 
      }
   }
   i += 1     
}

我必须调整一些方法参数String.UTF8View

utf8 仅适用于扩展 ASCII 字符集中的字符。如果您使用 UTF8 中占用多个字节的字符，您的代码将完全混乱。（重音字符、希腊字母或其他非罗马字母等。尝试将“AÄBÇñüÉÈ”作为字符串，仅作为示例。 — 
将字符串转换为 utf16 会对更大组字符产生良好的结果。（想想需要超过 16 位的汉字字符仍然会使其混淆。 — 
@igouy 我很惊讶这里的性能差异如此之大。如果我没记错的话，String对像这样的 ascii 字符串进行了优化，这使得索引比一般的 unicode 情况快得多。你确定你是用优化的（发布）版本测试的吗？ — 
此外，如果该utf8技巧确实有助于提高性能，您可以非常轻松地将其应用于我的答案。您只需添加.utf8和.map { String($0)! }阶段，如下所示：seq.utf8.windows(ofCount: 2).map { String($0)! }.reduce(into: [:]) { counts, window in counts[window, default: 0] += 1 }。 —

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

最佳答案
4

最佳答案 4

最佳答案
4