自相关算法中数组带偏移量自异或的高效实现问题

你需要计算布尔数组在不同偏移量下，对应位置元素异或为true的次数（本质是统计偏移后不同元素的对数），原嵌套循环的时间复杂度为O(M*N)（M是偏移量范围大小，N是数组长度），对于大数据组效率很低，以下是两种高效优化方案：

方案一：二进制打包+位运算优化 #

将布尔数组打包成64位整数，利用位运算批量处理元素，借助硬件加速的位计数功能大幅提升效率：

步骤1：布尔数组转64位整数数组 #

func packBools(_ bools: [Bool]) -> [UInt64] {
    var packed = [UInt64]()
    var current: UInt64 = 0
    for (idx, bool) in bools.enumerated() {
        if bool {
            current |= 1 << (idx % 64)
        }
        // 每64个元素打包成一个UInt64
        if (idx + 1) % 64 == 0 {
            packed.append(current)
            current = 0
        }
    }
    // 处理剩余不足64个的元素
    if !bools.isEmpty && bools.count % 64 != 0 {
        packed.append(current)
    }
    return packed
}

步骤2：基于打包数组计算自相关 #

func optimizedAutocorrelation(data: [Bool], startOffset: Int, endOffset: Int) -> [Int] {
    let dataCount = data.count
    var result = Array(repeating: 0, count: endOffset - startOffset)
    let packedData = packBools(data)
    let bitsPerPack = 64
    
    for resultIdx in 0..<result.count {
        let offset = startOffset + resultIdx
        guard offset < dataCount else { continue }
        
        let validPairCount = dataCount - offset
        var totalDiff = 0
        
        // 处理完整的64位块
        let fullPacks = validPairCount / bitsPerPack
        for packIdx in 0..<fullPacks {
            let leftPack = packedData[packIdx]
            let rightPackBaseIdx = packIdx + offset / bitsPerPack
            let bitShift = offset % bitsPerPack
            
            // 计算偏移后的右块（处理跨64位边界的情况）
            var shiftedRightPack = leftPack // 初始化占位，后续覆盖
            if bitShift == 0 {
                shiftedRightPack = packedData[rightPackBaseIdx]
            } else {
                shiftedRightPack = packedData[rightPackBaseIdx] >> bitShift
                if rightPackBaseIdx + 1 < packedData.count {
                    shiftedRightPack |= packedData[rightPackBaseIdx + 1] << (bitsPerPack - bitShift)
                }
            }
            
            // 异或后统计1的位数（即不同元素的数量）
            totalDiff += (leftPack ^ shiftedRightPack).nonzeroBitCount
        }
        
        // 处理剩余不足64位的元素
        let remainingBits = validPairCount % bitsPerPack
        if remainingBits > 0 {
            let lastPackIdx = validPairCount / bitsPerPack
            let leftPack = packedData[lastPackIdx]
            let rightPackBaseIdx = lastPackIdx + offset / bitsPerPack
            let bitShift = offset % bitsPerPack
            
            var shiftedRightPack: UInt64 = 0
            if bitShift == 0 {
                shiftedRightPack = packedData[rightPackBaseIdx]
            } else {
                shiftedRightPack = packedData[rightPackBaseIdx] >> bitShift
                if rightPackBaseIdx + 1 < packedData.count {
                    shiftedRightPack |= packedData[rightPackBaseIdx + 1] << (bitsPerPack - bitShift)
                }
            }
            
            // 只统计前remainingBits位的异或结果
            let mask = (1 << remainingBits) - 1
            totalDiff += ((leftPack & mask) ^ (shiftedRightPack & mask)).nonzeroBitCount
        }
        
        result[resultIdx] = totalDiff
    }
    
    return result
}

方案二：SIMD单指令多数据优化 #

利用Swift的SIMD框架，一次处理8/16/32个元素，充分发挥CPU并行计算能力：

import simd

func simdAutocorrelation(data: [Bool], startOffset: Int, endOffset: Int) -> [Int] {
    let dataCount = data.count
    var result = Array(repeating: 0, count: endOffset - startOffset)
    // 将布尔值转换为UInt8（0/1），适配SIMD处理
    let uintData = data.map { $0 ? 1 : 0 }
    let simdBatchSize = 8 // 可根据CPU支持调整为16/32
    
    for resultIdx in 0..<result.count {
        let offset = startOffset + resultIdx
        guard offset < dataCount else { continue }
        
        let validPairCount = dataCount - offset
        var totalDiff = 0
        
        // 批量处理SIMD批次大小的元素
        let fullBatches = validPairCount / simdBatchSize
        for batchIdx in 0..<fullBatches {
            let baseIdx = batchIdx * simdBatchSize
            let left = SIMD8<UInt8>(uintData[baseIdx..<baseIdx+simdBatchSize])
            let right = SIMD8<UInt8>(uintData[baseIdx+offset..<baseIdx+offset+simdBatchSize])
            let xorResult = left ^ right
            // 求和异或结果中的1的数量
            totalDiff += xorResult.reduce(0, { $0 + Int($1) })
        }
        
        // 处理剩余不足一个批次的元素
        let remaining = validPairCount % simdBatchSize
        for idx in 0..<remaining {
            let currentIdx = fullBatches * simdBatchSize + idx
            if uintData[currentIdx] != uintData[currentIdx + offset] {
                totalDiff += 1
            }
        }
        
        result[resultIdx] = totalDiff
    }
    
    return result
}

优化说明 #

1. 时间复杂度优化：原嵌套循环为O(MN)，两种优化方案均将复杂度降至O(M(N/K))，其中K为批量处理的元素数（64或8/16/32），大幅减少循环次数。
2. 硬件加速：UInt64.nonzeroBitCount和SIMD指令均由CPU硬件加速，计算效率远高于逐元素遍历。
3. 注意点：原代码中data[index + frequency]疑似笔误，应为data[index + offset]，需修正变量名避免逻辑错误。

内容的提问来源于stack exchange，提问作者lancylot2004