通过 LeetCode 最简单的一道题探究 Swift 源码

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看277 回复回复2 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 277|回复: 2
收起左侧

通过 LeetCode 最简单的一道题探究 Swift 源码

[复制链接]
cocoaswift 发表于 2016-7-5 18:37:00 | 显示全部楼层 |阅读模式
快来登录
获取优质的苹果资讯内容
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
订阅梳理好了的知识点专辑
闲来无事,突然想到一直都没有完成的刷爆 LeetCode 的成就,于是就又跃跃欲试了。

之前通过 Java 和 Python 刷过十几道题,然后就不了了之了。现在 LeetCode 也支持 Swift 了,所以就想用 Swift 解锁成就。

我是个算法渣,在这方面从来没有过自信,《算法导论》中那些面试经常提到的算法看了三四遍也始终无法牢牢把握,前几天又入手了据说更适合实际应用的“算法”,心想一定要偿还这部分的技术负债。

打开 LeetCode 网站,直接按难易度排序,先从最简单的开始。

通过 LeetCode 最简单的一道题探究 Swift 源码 1 leetcode

通过 LeetCode 最简单的一道题探究 Swift 源码 - 敏捷大拇指 - 通过 LeetCode 最简单的一道题探究 Swift 源码 1 leetcode

LeetCode

第一道题,Reverse String,反转字符串。没什么特别复杂的,就是纯逐个字符反转,并不是反转单词。

第一想法非常简单,就是创建一个空字符串,遍历给定的字符串,挨个字符插入到新字符串的第一位置,这样遍历结束后新的字符串就是反转后的结果,so easy!

打开 Playground,分分钟就写好了下面的代码:

Reverse String Version 1

[Swift] 纯文本查看 复制代码
class Solution {
    func reverseString(s: String) -> String {
        var ret: String = ""
        for c in s.characters {
            ret.insert(c, atIndex: ret.startIndex)
        }
        return ret
    }
}


复制到 LeetCode 中,先是猛击 Run Code,没毛病,然后就猛击 Submit Solution 了。果不其然,Time Limit Exceeded……败在了一个无比长的字符串手里。

于是就顺其自然地想到了第二个解决方案:交换字符位置。Swift 的 String,所有的字符都是放在 characters 这个属性里的(看命名是个集合,其实真正的类型是 String.CharacterView,这个类封装了对于字符集合的各种操作),所以操作这个 characters 的索引,应该就可以达到交换字符的目的。正当我准备动手的时候,Xcode 的自动补全蹦出个 reverse() 方法,原来 Swift 已经提供了反转功能,这下子可方便多了,一句代码的事,这个 solution 也通过了:

Reverse String Version 2

[Swift] 纯文本查看 复制代码
func reverseString(s: String) -> String {
    return String(s.characters.reverse())
}


这里值得一提的是:在 Dash 的文档里,这个 reverse() 是 Swift 3 之前的 API,返回的是一个 [Character],复杂度是 O(N)。到了 Swift 3,这个方法改为了 reversed(),复杂度也变成了 O(1),返回的是 ReversedCollection<String.CharacterView>。对于这两种返回值,String 都可以直接作为参数来初始化。



=======呓语开始=======

不知道为什么,在 Xcode 7.3.1 中这个 reverse() 自动补全会有两个:

通过 LeetCode 最简单的一道题探究 Swift 源码 2 reverse_autocomplete

通过 LeetCode 最简单的一道题探究 Swift 源码 - 敏捷大拇指 - 通过 LeetCode 最简单的一道题探究 Swift 源码 2 reverse_autocomplete

reverse() in autocomplete

但 option+click 显示的是:

通过 LeetCode 最简单的一道题探究 Swift 源码 3 reverse_xcode

通过 LeetCode 最简单的一道题探究 Swift 源码 - 敏捷大拇指 - 通过 LeetCode 最简单的一道题探究 Swift 源码 3 reverse_xcode

reverse() in doc

返回 ReversedCollection<String.CharacterView> 应该是 Swift 3 才有的,但是 cmd+click 进去发现这个方法声明在 CollectionType 的一个 extension 中,在2.2的源代码中也发现了:

通过 LeetCode 最简单的一道题探究 Swift 源码 4 reverse_source

通过 LeetCode 最简单的一道题探究 Swift 源码 - 敏捷大拇指 - 通过 LeetCode 最简单的一道题探究 Swift 源码 4 reverse_source

reverse() in source

从这段代码里也可以看出这个方法的复杂度是 O(1),而且在 Swift 3 中也要改名为 reversed()。

奇怪,文档中明明写的是 O(N) 的版本,但是 Playground 却显示的是这个,不知道 Swift 是如何动态选择到这个方法的。这个 ReversedCollection 我看了初始化方法的实现过程,也没有发现有实现反转的代码,也搞不清楚是如何做到 O(1)的。

所以下面的分析都是针对 O(N) 版本的 reverse()。

=======呓语结束=======



一句代码就解决了这个问题,成就感不是很大啊,于是我就想看看 Swift 是如何实现这个方法的。通过查文档(Swift 2.2),发现这个 String.CharacterView 采纳(沿用了 The Swift Programming Language 中文版里的翻译)的协议有 RangeReplaceableCollectionType, CollectionType, SequenceType :

通过 LeetCode 最简单的一道题探究 Swift 源码 5 reverse

通过 LeetCode 最简单的一道题探究 Swift 源码 - 敏捷大拇指 - 通过 LeetCode 最简单的一道题探究 Swift 源码 5 reverse

reverse() in String.CharacterView

这个方法最后发现是在 SequenceType 这个协议中声明的:

通过 LeetCode 最简单的一道题探究 Swift 源码 6 reverse_sequence_type

通过 LeetCode 最简单的一道题探究 Swift 源码 - 敏捷大拇指 - 通过 LeetCode 最简单的一道题探究 Swift 源码 6 reverse_sequence_type

reverse() in SequenceType


但是在源码中的 SequenceType.swift 这个文件中并没有找到关于这个方法的任何声明,通过对源码的全局搜索,找到这个方法的实现是写在 SequenceAlgorithms.swift.gyb 这个文件中(关于 gyb 文件是什么,请点击这里):

reversed() implementation

[Swift] 纯文本查看 复制代码
//===----------------------------------------------------------------------===//
// reverse()
//===----------------------------------------------------------------------===//

extension SequenceType {
  /// Returns an `Array` containing the elements of `self` in reverse
  /// order.
  ///
  /// Complexity: O(N), where N is the length of `self`.
  @swift3_migration(renamed="reversed")
  @warn_unused_result
  public func reverse() -> [${GElement}] {
    // FIXME(performance): optimize to 1 pass?  But Array(self) can be
    // optimized to a memcpy() sometimes.  Those cases are usually collections,
    // though.
    var result = Array(self)
    let count = result.count
    for i in 0..<count/2 {
      swap(&result[ i ], &result[count - i - 1])
    }
    return result
  }
}


这段代码写的很明白了,就是不断向数组的中间靠近,交换首尾的元素。还有值得挖的就是 swap 的实现了,这个方法是在 Sort.swift.gyb 中:

swap() implementation

[Swift] 纯文本查看 复制代码
/// Exchange the values of `a` and `b`.
///
/// - Requires: `a` and `b` do not alias each other.
public func swap<T>(inout a : T, inout _ b : T) {
  // Semantically equivalent to (a, b) = (b, a).
  // Microoptimized to avoid retain/release traffic.
  let p1 = Builtin.addressof(&a)
  let p2 = Builtin.addressof(&b)
  _debugPrecondition(
    p1 != p2,
    "swapping a location with itself is not supported")

  // Take from P1.
  let tmp : T = Builtin.take(p1)
  // Transfer P2 into P1.
  Builtin.initialize(Builtin.take(p2) as T, p1)
  // Initialize P2.
  Builtin.initialize(tmp, p2)
}


这段代码也是交换的基本操作了,显示比较两个元素的地址,如果地址相同就不做交换,然后就是通过中间变量来交换两个元素的值。





相关内容:

通过 LeetCode 最简单的一道题探究 Swift 源码

Swift GYB 简易教程,一个 Swift 内部使用的模板生成源文件工具

iOS Xcode制作模板类

总结一些iOS项目中组织代码的方法 clean code

Swift实战-模板模式




作者:vulgur

都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

强者更强 发表于 2016-7-7 03:52:04 | 显示全部楼层
Swift就跑到Swifthumb上来刷题是吧?
3rdev 发表于 2016-7-8 16:45:34 | 显示全部楼层
强者更强 发表于 2016-7-7 03:52
Swift就跑到Swifthumb上来刷题是吧?

Swifthumb上很多资料的,收集了很多Swift面试题
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表