【喵神】 @StateObject 和 @ObservedObject 的区别和使用

WWDC 2020 中,SwiftUI 迎来了非常多的变更。相比于 2019 年的初版,可以说 SwiftUI 达到了一个相对可用的状态。从这篇文章开始,我打算写几篇文章来介绍一些重要的变化和新追加的内容。如果你需要 SwiftUI 的入门和基本概念的材料,我参与的两本书籍《SwiftUI 与 Combine 编程》《SwiftUI 编程思想》依然会是很好的选择。

字太多,不想看,长求总

@ObservedObject 不管存储,会随着 View 的创建被多次创建。而 @StateObject 保证对象只会被创建一次。因此,如果是在 View 里自行创建的 ObservableObject model 对象,大概率来说使用 @StateObject 会是更正确的选择。@StateObject 基本上来说就是一个针对 class 的 @State 升级版。

如果你对详细内容感兴趣,想知道整个故事的始末,可以继续阅读。

初版 SwiftUI 的状态管理

在 2019 年 SwiftUI 刚问世时,除去专门用来管理手势的 @GestureState 以外,有三个常用的和状态管理相关的 property wrapper,它们分别是 @State@ObservedObject@EnvironmentObject。根据职责和作用范围不同,它们各自的适用场景也有区别。一般来说:

  • @State 用于 View 中的私有状态值,一般来说它所修饰的都应该是 struct 值,并且不应该被其他的 view 看到。它代表了 SwiftUI 中作用范围最小,本身也最简单的状态,比如一个 Bool,一个 Int 或者一个 String。简单说,如果一个状态能够被标记为 private 并且它是值类型,那么 @State 是适合的。
  • 对于更复杂的一组状态,我们可以将它组织在一个 class 中,并让其实现 ObservableObject 协议。对于这样的 class 类型,其中被标记为 @Published 的属性,将会在变更时自动发出事件,通知对它有依赖的 View 进行更新。View 中如果需要依赖这样的 ObservableObject 对象,在声明时则使用 @ObservedObject 来订阅。
  • @EnvironmentObject 针对那些需要传递到深层次的子 View 中的 ObservableObject 对象,我们可以在父层级的 View 上用 .environmentObject 修饰器来将它注入到环境中,这样任意子 View 都可以通过 @EnvironmentObject 来获取对应的对象。

这基本就是初版 SwiftUI 状态管理的全部了。

看起来对于状态管理,SwiftUI 的覆盖已经很全面了,那为什么要新加一个 @StateObject property wrapper 呢?为了弄清这个问题,我们先要来看看 @ObservedObject 存在的问题。

@ObservedObject 有什么问题

我们来考虑实现下面这样的界面:

点击“Toggle Name”时,Current User 在真实名字和昵称之间转换。点击 “+1” 时,无条件为这个 View 续一秒 显示的 Score 增加 1。

来看看下面的代码,算上空行也就五十行不到:

struct ContentView: View {
    @State private var showRealName = false
    var body: some View {
        VStack {
            Button("Toggle Name") {
                showRealName.toggle()
            }
            Text("Current User: \(showRealName ? "Wei Wang" : "onevcat")")
            ScorePlate().padding(.top, 20)
        }
    }
}

class Model: ObservableObject {
    init() { print("Model Created") }
    @Published var score: Int = 0
}

struct ScorePlate: View {

    @ObservedObject var model = Model()
    @State private var niceScore = false

    var body: some View {
        VStack {
            Button("+1") {
                if model.score > 3 {
                    niceScore = true
                }
                model.score += 1
            }
            Text("Score: \(model.score)")
            Text("Nice? \(niceScore ? "YES" : "NO")")
            ScoreText(model: model).padding(.top, 20)
        }
    }
}

struct ScoreText: View {
    @ObservedObject var model: Model

    var body: some View {
        if model.score > 10 {
            return Text("Fantastic")
        } else if model.score > 3 {
            return Text("Good")
        } else {
            return Text("Ummmm...")
        }
    }
}

简单解释一下行为:

对于 Toggle Name 按钮和 Current User 标签,直接写在了 ContentView 中。+1 按钮和显示分数以及分数状态的部分,则被封装到一个叫 ScorePlateView 里。它需要一个模型来记录分数,也就是 Model。在 ScorePlate 中,我们将它声明为了一个 @ObservedObject 变量:

struct ScorePlate: View {
    @ObservedObject var model = Model()
    //...
}

除了 Model 外,我们还在 ScorePlate 里添加了另一个私有的布尔状态 @State niceScore。每次 +1 时,除了让 model.score 增加外,还检查了它是否大于三,并且依此设置 niceScore。我们可以用它来考察 @State@ObservedObject 行为上的不同。

最后,最下面一行是另外一个 ViewScoreText。它也含有一个 @ObservedObjectModel,并根据 score 值来决定要显示的文本内容。这个 model 会在初始化时传入:

struct ScorePlate: View {
    var body: some View {
        // ...
        ScoreText(model: model).padding(.top, 20)
    }
}

当然,在这个例子中,其实使用一个简单的 @StateInt 值就够了,但是为了说明问题,还是生造了一个 Model 这把牛刀来杀鸡。实际项目中 Model 肯定是会比一个 Int 要来得更复杂。

当我们尝试运行的时候,“+1” 按钮可以完美工作,“Nice” 和 “Ummmm…” 文本也能够按照预期改变,一切都很完美…直到我们想要用 “Toggle Name” 改变一下名字:

除了 (被 @State 驱动的) Nice 标签,ScorePlate 的其他文本都被一个看似不相关的操作重置了!这显然不是我们想要的行为。

(为节约流量和尊重 BLM,此处请自行脑补非洲裔问号图)

这是因为,和 @State 这种底层存储被 SwiftUI “全面接管” 的状态不同,@ObservedObject 只是在 ViewModel 之间添加订阅关系,而不影响存储。因此,当 ContentView 中的状态发生变化,ContentView.body 被重新求值时,ScorePlate 就会被重新生成,其中的 model 也一同重新生成,导致了状态的“丢失”。运行代码,在 Xcode console 中可以看到每次点击 Toggle 按钮时都伴随着 Model.init 的输出。

Nice 标签则不同,它是由 @State 驱动的:由于 View 是不可变的 struct,它的状态改变需要底层存储的支持。SwiftUI 将为 @State 创建额外的存储空间,来保证在 View 刷新 (也就是重新创建时),状态能够保持。但这对 @ObservedObject 并不适用。

保证单次创建的 @StateObject

只要理解了 @ObservedObject 存在的问题,@StateObject 的意义也就很明显了。@StateObject 就是 @State 的升级版:@State 是针对 struct 状态所创建的存储,@StateObject 则是针对 ObservableObject class 的存储。它保证这个 class 实例不会随着 View 被重新创建。从而解决问题。

在上面这个具体的例子中,只要把 ScorePlate 中的 @ObservedObject 改成 @StateObject,就万事大吉了:

struct ScorePlate: View {
    // @ObservedObject var model = Model()
    @StateObject var model = Model()
}

现在,ScorePlateScoreText 里的状态不会被重置了。

那么,一个自然而然引申出的问题是,我们是不是应该把所有的 @ObservedObject 都换成 @StateObject?比如上面例子中需要把 ScoreText 里的声明也进行替换吗?这看实际上你的 View 到底期望怎样的行为:如果不希望 model 状态在 View 刷新时丢失,那确实可以进行替换,这 (虽然可能会对性能有一些影响,但) 不会影响整体的行为。但是,如果 View 本身就期望每次刷新时获得一个全新的状态,那么对于那些不是自己创建的,而是从外界接受的 ObservableObject 来说,@StateObject 反而是不合适的。

更多的讨论

使用 @EnvironmentObject 保持状态

除了 @StateObject 外,另一种让状态 object 保持住的方式,是在更外层使用 .environmentObject

struct SwiftUINewApp: App {
    var body: some Scene {
        WindowGroup {
            ContentView().environmentObject(Model())
        }
    }
}

这样,model 对象将被注入到环境中,不再随着 ContentView 的刷新而变更。在使用时,只需要遵循普通的 environment 方式,把 Model 声明为 @EnvironmentObject 就行了:

struct ScorePlate: View {
    @EnvironmentObject var model: Model
    // ...
    
    // ScoreText(model: model).padding(.top, 20)
    ScoreText().padding(.top, 20)
}

struct ScoreText: View {
    @EnvironmentObject var model: Model
    // ...
}

@State 保持同样的生命周期

除了确保单次创建外,@StateObject 的另一个重要特性是和 @State 的“生命周期”保持统一,让 SwiftUI 全面接管背后的存储,也可以避免一些不必要的 bug。

ContentView 上稍作修改,把 ScorePlate() 放到一个 NavigationLink 中,就能看到结果:

var body: some View {
  NavigationView {
    VStack {
      Button("Toggle Name") {
        showRealName.toggle()
      }
      Text("Current User: \(showRealName ? "Wei Wang" : "onevcat")")
      NavigationLink("Next", destination: ScorePlate().padding(.top, 20))
    }
  }
}

当点击 “Next” 时,会导航到 ScorePlate 页面,可以在那里进行 +1 操作。当点击 Back button 回到 ContentView,并再次点击 “Next” 时,一般情况下我们会希望 ScorePlate 的状态被重置,得到一个全新的,从 0 开始的状态。此时使用 @StateObject 可以工作良好,因为 SwiftUI 帮助我们重建了 @State@StateObject。而如果我们将 ScorePlate 里的声明从 @StateObject 改回 @ObservedObject 的话,SwiftUI 将不再能够帮助我们进行状态管理,除非通过 “Toggle” 按钮刷新整个 ContentView,否则 ScorePlate 在再次展示时将保留原来的状态。

当然,如果你有意想要在 ScorePlate 保留这些状态的话,使用 @ObservedObject 或者上面的 @EnvironmentObject 的方式才是正确的选择。

总结

简单说,对于 View 自己创建的 ObservableObject 状态对象来说,极大概率你可能需要使用新的 @StateObject 来让它的存储和生命周期更合理:

struct MyView: View {
    @StateObject var model = Model()
}

而对于那些从外界接受 ObservableObjectView,究竟是使用 @ObservedObject 还是 @StateObject,则需要根据情况和需要确定。像是那些存在于 NavigationLinkdestination 中的 View,由于 SwiftUI 对它们的构建时机并没有做 lazy 处理,在处理它们时,需要格外小心。

不论哪种情况,彻底弄清楚两者的区别和背后的逻辑,可以帮助我们更好地理解一个 SwiftUI app 的行为模式。

June 25, 2020 at 11:00AM via OneV’s Den https://ift.tt/3eJKAvb

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【喵神】 一些关于 App Clips 的笔记

App clips 是今天 WWDC 上 iOS 14 的一个重要“卖点”,它提供了一种“即时使用”的方式,让用户可以在特定时间、特定场景,在不下载完整 app 的前提下,体验到你的 app 的核心功能。

装好 Xcode 12 以后第一时间体验了一下如何为 app 添加 app clip。它的创建和使用都很简单,也没有什么新的 API,所以要为 app 开发一个 clip 的话,难点更多地在于配置、代码的复用以及尺寸优化等。在阅读文档和实际体验的同时,顺便整理了一些要点,作为备忘。

App clips 的一些基本事实和添加步骤

在写作本文时 (2020.06.23),通过文档和实践能获知的关于 app clips 的几点情况:

  • 一个 app 能且只能拥有一个 app clip。
  • 通过在一个 app project 中添加 app clip target 就能很简单地创建一个 app clip 了。

  • App clip 的结构和普通的 app 毫无二致。你可以使用绝大多数的框架,包括 SwiftUI 和 UIKit (不能使用的都是一些冷门框架和隐私相关的框架,比如 CallKit 和 HomeKit 等 )。所以 app clip 的开发非常简单,你可以使用所有你已经熟知的技术:创建 UIViewController,组织 UIView,用 URLSession 发送请求等等。和小程序这种 H5 技术不同,app clip 就是一个 native 的几乎“什么都能做”的“简化版”的 app。
  • App clip 所包含的功能必须是 main app 的子集。App clip 的 bundle ID 必须是 main app 的 bundle ID 后缀加上 .Clip (在 Xcode 中创建 app clip target 时会自动帮你搞定)。
  • 域名和 server 配置方面,和支持 Universal Link 以及 Web Credentials 的时候要做的事情非常相似:你需要为 app clip 的 target 添加 Associated Domain,格式为 appclips:yourdomain.com;然后在 server 的 App Site Association (通常是在网站 .well-known 下的 apple-app-site-association 文件) 中添加这个域名对应的 appclips 条目:
{
  "appclips": {
    "apps": ["ABCED12345.com.example.MyApp.Clip"]
  }
} 
  • 默认最简单的情况下,app clip 通过 Safari App Banner 或者 iMessage app 中的符合 domain 要求的 URL 下载和启动。普通的网页链接是无法启动 app clip 的。这种启动方式叫做 Default App Clip Experience。

  • 一个能够启动 app clip 的 App Banner 形式如下:

<meta 
  name="apple-itunes-app" 
  content="app-id=myAppStoreID, app-clip-bundle-id=appClipBundleID
>
  • 你的 app clip 在被真正调用前,系统会显示一个 app clip card。对于 Default App Clip Experience,你可以在 App Store Connect 中为这种启动方式提供固定的图片,标题文本和按钮文本。(现在版本的 App Store Connect 中似乎还没有设置的地方,应该是 iOS 14 正式发布后会添加)。

  • App clip card 显示时,你的 app clip 就已经开始下载了。App clip 的体积必须在 10MB 以内。这样,大概率在用户选择打开你的 app clip 之前,就能下载完成,以提供良好体验。
  • 用户点击 banner 或者 iMessage 链接,且继续点击打开按钮后,app clip 的 user activity 关联的生命周期函数将被调用,根据你所使用的技术不同,它将是 onContinueUserActivity(_:perform:) (SwiftUI),scene(_:willContinueUserActivityWithType:) (Scene-Based app) 或者 application(_:continue:restorationHandler:) (App Delegate app) 之一。获取到唤醒 app clip 的 NSUserActivity 后,就可以通过 webpageURL 获取到调用的链接了(Banner 所在页面的链接,或 iMessage 中点击的链接)。
  • 根据唤醒 app clip 的 URL,用 UIKit 或 SwiftUI 完成对应的 UI 构建和展示。因为 App Clip 需要是 main app 的子集,因此一般来说这些 URL (以及对应的 NSUserActivity) 也需要能被 main app 处理。当 main app 已经被安装时,唤醒的会是 main app。
  • 对于更复杂的唤醒情况,可以根据 URL 的不同、甚至是地点的不同,来提供不一样的 app clip card。这部分内容也是通过 App Store Connect 进行配置的。这类启动方式被称为 Advanced App Clip Experiences。
  • 在开发时,可以通过设置 _XCAppClipURL 这个环境变量,并运行 app clip target 来“模拟”通过特定 URL 点击后的情况。当 Associated Domain 设置正确后,在 Xcode 中运行 app clip,就可以拿到包含这个环境值的 NSUserActivity。这样在 Beta 期间的本地开发就不需要依赖外部 server 环境了。

  • 关于代码和资源的组织。很大机率 main app 和 app clip 是需要共用代码的,可以无脑地选择将源码放到 main app 和 app clip 两个 target 中,也可以选择打成 framework 或者 local Swift Package。不管如何,这部分共用的 binary 都会同时存在于 main app bundle 和 app clip bundle 中。图片等素材资源也类似。简单说,app clip 其实就是一个完整但尺寸有所限制、并且和某个域名绑定,因此不需要用户认证 Apple ID 就可以下载的 app。
  • 部分 app clip 是“用完就走”的,但是也有部分 app clip 是为了导流到 main app。可以通过 SKOverlaySKStoreProductViewController 来显示一个指向 main app 的推广窗:
func scene(_ scene: UIScene, continue userActivity: NSUserActivity) {
  // 处理 userActivity ...
  
  if let scene = scene as? UIWindowScene {
    let overlay = SKOverlay(configuration: SKOverlay.AppClipConfiguration(position: .bottom))
    overlay.present(in: scene)
  }
}

  • 如果在 app clip 中有用户注册/登录和支付需求的话,Apple 推荐使用 Sign in with Apple 和 Apple Pay 来简化流程。虽然在 app clip 中,所有的 UI 操作和导航关系都是支持的 (手势,modal present,navigation push 等等),但 app clip 应该尽量避免 tab 或者很长的表单这类复杂交互,让用户能直奔主题。

一些初步的思考和展望

所以今后,一个有追求的 iOS app 将会有两个 .app 的 bundle:一个完整的原始版本,一个快速搞定核心功能的 lite 版本。不过悲剧的是,国内的 iOS 生态面临崩溃,微信小程序的地位不可撼动,所以 app clip 能在多大程度上吸引开发者是存有疑问的:因为很难说服一个跨 iOS 和 Android 平台的成熟服务将 app clip 作为核心部分进行开发,而 iPhone 的市场占有率又决定了这样的开发能够覆盖的用户十分有限。

不过好处在于,很大程度上,为现有的 app 提供一个 app clip 需要花费的精力并不会很多:在确定了方向和提供的核心功能后,大量的 main app 中的既有代码和素材都可以重复使用。App clip 和小程序定位也完全不同。前者并没有改变以 app 为中心、以提高体验和快捷使用为基本点的方针:它更像一种为 main app 做 promotion 的手段,让 main app 多一些被曝光和试用的机会。对于线下获取用户来说,也许会有一定效果。从体验上来说,可以肯定的是,基于 native 和成熟开发框架 (此处专指 UIKit,暂不包含 SwiftUI) 的 app clip 一定是胜过小程序很多的。但是,究竟有多少注重体验的高端用户,愿意为其买单,我个人只能抱有谨慎乐观的态度。

June 23, 2020 at 11:00AM via OneV’s Den https://ift.tt/3hMye7n

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 使用树莓派和 Plex 架设照片服务

我用手机拍了很多照片,平时都保存在一台 Windows 台式机上,这台机器硬盘空间大,主要干两个事情,一个是我打游戏,一个就是存放多媒体数据(主要是照片)。有时候我需要它提供照片服务,以方便家人使用各种媒体终端(手机、电视盒子等)阅览,因此我使用 Plex 折腾了一下,但是由于台式机噪音等等的关系,不适合长期开机,因此当时那个方案还是残缺的。

现在打算彻底解决这个问题。大致总结一下,以下是我的主要的几个需求:

  • 照片服务要能够长期保持在线,私用可以方便地查看照片。开机不能有明显的噪音和功耗问题。
  • 我的照片经常是在 Windows 下进行处理的,因此需要很方便地同步到照片服务器。当然,我也会同步几个重要文件夹以作备份只用。
  • 私用,不愿意上传公有云。

最近树莓派比较火,因此我花了几十刀买了个第四代,想用它来满足上面的需求。

安装树莓派

这一步没有什么特别的,从 4 代开始,风扇显得更为重要,但是接针脚的时候,选择 1-6,而不是 4-6,因为 1 号针脚是 3V3,电压低一些,散热能力是弱一些,但风扇噪音也小一些,适合长期开机。考虑到我们的实际需求,这个够用了。

配置树莓派

配置 SSH

打开 SSH:

sudo raspi-config

但这样还不够,需要修改 /etc/ssh/sshd_config 添加:

IPQoS cs0 cs0

之后重启一下 ssh 服务:

sudo service ssh restart

还可以按照我在这篇文章中介绍的办法配置密钥访问,不过是私用,必要性不那么强。

关闭自动休眠

既然用作服务器,肯定不能自动休眠。

sudo apt-get install vim
sudo vim /etc/lightdm/lightdm.conf

添加如下:

xserver-command=X -s 0 -dpms

重启:

sudo reboot

安装 Plex

这一篇 PiMyLifeUp 上的教程很不错,我基本是照着做的。准备工作:

sudo apt-get install apt-transport-https
curl https://downloads.plex.tv/plex-keys/PlexSign.key | sudo apt-key add -
echo deb https://downloads.plex.tv/repo/deb public main | sudo tee /etc/apt/sources.list.d/plexmediaserver.list
sudo apt-get update

安装 Plex:

sudo apt-get install plexmediaserver

配置 Windows 主机

配置同步工具

Windows 机是我的一部分媒体文件的数据源,因此需要经常从 Windows 机同步数据到树莓派服务器。

一种方法是使用 Cygwin + rsync:

安装 Cygwin,这是一个可以在 Windows 下使用常见 Linux 命令的工具。基本上,默认选项即可,但是 rsync 一定要安装:

安装完成以后,Windows 下的磁盘全部被列在/cygdrive 下面。

但是我研究到一半的时候,发现了一个更好用的工具——Acrosync

第一次可以压缩并使用 scp 来传输文件,因为这样效率会更高,但以后就要通过上面的工具来同步了。

值得一提的是,如果空间不够,可以使用 du 这样的命令来查看罪魁祸首,不过我使用的参数因为 Linux 版本的关系,和我以往熟悉的比起来有点不同:

sudo du -s * | sort -nr | head

大功告成

在树莓派机器上安装 Plex 完毕后,在 Windows 下的浏览器中访问 http://192.168.0.28:32400/web 应该能看到 Plex 界面了。

之后,在各种终端上安装 Plex 应用,就可以很舒服地浏览照片了。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/3cx7HXz

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 从链表存在环的问题说起

有这样一个经典的算法题,说是一个单向链表,它内部可能存在环,也可能不存在,用怎样的方法,可以检测出,这个链表是否存在环。下图即是这个形成环的示意,如果单向链表的尾部,指向了链表中的一个节点,而不是指向空,那就构成环了。

接着的一个问题是,怎么检测出这个链表是否有环?

看到这个问题,也许你会觉得,太简单了,但是这个问题只是一个引子。在 《求第 K 个数的问题》一文中,我从简入深,逐步展开,把这 “第 K 个数” 的一系列问题翻了个底朝天。我想关于这个链表成环问题,我也利用类似的思路,看看我是不是也能把这一个问题前前后后讲清楚。

判断单向链表是否成环

在进一步思考怎样判断这个成环的问题以前,先考虑一件事情,如果成环,有没有可能成一个以上的环?

从图示上看,似乎说得通,可事实上却是不可能的,因为 M 点需要有两个后继节点,一个用于构成该处的环,一个用于指向 N 的方向,这显然对于一般我们说的单向链表来说,是不可能做到的。

那么,怎么检测单向链表是否成环呢?

网上能见到的最普遍的解决方法就是双指针,一快一慢,从链表头部开始,快的每次走两步,慢的一次走一步,交替进行,直到二者相遇或快指针抵达链表尾部。如果相遇说明存在环。

不过,这是一个巧妙的方法,是一个时间复杂度在 O(n)、空间复杂度在 O(1) 的好方法,却不是唯一的方法。还有一个思路是,用某种方式记录下走过的节点,如果再次遇到了,就说明成环了。这种方法只需要一个指针,且不会重复遍历走过了的节点,但缺点是存在记录走过节点的开销:

  • 如果链表节点允许使用某变量标记状态(例如 visited 这样的布尔值),当然可以,且不需要额外的空间复杂度;
  • 如果不允许,可以额外使用一个 HashSet 来记录节点,如果存在过,就找到节点了,这种方式的空间复杂度是 O(n)。

再回到那个一快一慢的双指针问题上,有一些基本的问题需要搞清楚。

一快一慢的双指针,在链表成环的情况下,它们一定会遇到吗,有没有可能恰好错过呢?

不会错过,一定会相遇。我们分两种情况考虑:

  • 一种情况是快指针恰好落后慢指针一个身位,那么显然慢指针之后的那个位置,就是它们下一个回合碰面的位置;
  • 另一种情况是快指针落后更多,那么快指针会慢慢赶上来,因为每一个回合快指针走两步,而慢指针走一步,因此每一个回合二者都可以缩短长度为 1 的距离,直到前面说到的只差一个身位的情况出现。

寻找环入口

那么,下一个自然的问题是,怎样找到那个从单向链表进入环的节点(环入口)?

乍一看这个问题,可能很难找到一个高效的解决方法。我们先退一步,仔细分析一下刚才判断成环的步骤,这里面利用了一个事实,如果链表成环,那么快慢指针一定会相遇。那么一个很自然的问题是,它们会在哪里相遇?

首先,它们肯定在环上相遇,因为直线部分 SN 不可能出现 “追上” 的现象。那么,假设它们相遇的点为 P:

  • 对于快指针来说,从起点 S 走到 P 点,假如说绕了 m 圈,环周长为 p,那么一共走了 SN + mp + NP,其中 NP 为最后一圈从 N 逆时针走到 P 的距离。
  • 而对于慢指针来说,从 S 走到 P 点,一定只绕了不到一圈,也就是一共走了 SN + NP 的距离。

这里有个问题,为什么慢指针从 S 走到 P 点,一定只绕了不到一圈?

因为对于慢指针来说,在 “运气最背” 的情况下,就是它刚抵达 N 点的时候,快指针恰好已经路过 N 了,因此在 N 没有相遇。那么按照快指针两倍于慢指针速度的情况来说,慢指针一圈之内,也就是快指针两圈之内一定可以发生 “赶上并超过”,那么也就一定会发生 “相遇”(由于前面的结论,它们不会错过)。因此,这种情况下,相遇的时候,慢指针一定还没有绕足一圈。

好,由于我们知道在 P 点相遇的时候,快指针实际走了慢指针两倍的距离,于是得到:

SN + mp +NP = 2 * (SN + NP)

所以,我们得到:

mp = SN + NP

这意味着什么?这意味着因为 SN+NP 是环周长的倍数,也就意味着在快慢指针相遇在 P 点的时候,如果这个慢指针继续走 SN 的距离,不管这个 SN 实际会绕多少圈,一定会最终停到 N 点

我们虽然还是不知道这个 SN 有多长,但是我们在快慢指针相遇在 P 点的时候,把快指针撤回起点,并且给了快指针一个新指令——你和慢指针一样,每次走一步。这样,慢指针从 P 点开始,逆时针向 N 逼近;快指针从 S 点开始,也以同样的速率向 N 逼近。等它们相遇的时候,恰好就是 N 点,也就是环入口。同时,也获知了 SN 的长度。

计算环周长

如果环入口准确定位了,那么环周长也自然不成问题了。

从环入口开始计数,直到若干步后,重新回到环入口。知道了环周长,根据前面获知的 SN,也就知道了 NP(从环入口 N 逆时针遍历到快慢指针相遇点 P)的距离。

判断链表相交

链表相交,指的是两个不同的链表,链表头不同,但是链表尾部却相同。如图所示:

其中,一个链表从头部 S 开始,另一个从头部 T 开始,二者相交在节点 N,最后共同收尾于 E。

怎样判断链表是否相交,如果是,又怎样找到相交的节点 N?

根据前面寻找环入口问题的启示,如果 SN 的长度等于 TN,那么一个指针从 S 开始,另一个从 T 开始,一样的速率前进,相交的地方就是 N。

但是 SN 和 TN 并不一定相等。

不过也没关系,先对于链表 S-N-E,遍历一遍,得到长度 l1;再对于链表 T-N-E,遍历一遍,得到长度 l2,对于二者中长度较长的一个,让这个指针单独先走一段(以下图为例,从 S 走到 Q),走的这段长度恰好为 l1 和 l2 的差值,把这段差值给抹平。这样一来,QN 就等于 TN 了,这样两个指针就可以同样速率往后前进了,相遇的 N 点就是相交的节点;如果一直不相遇,那就是没有相交。

链表相交和链表成环一起出现

都很简单是不是?有了前面的铺垫,下面来讨论最复杂的问题。

假如说,链表成环和链表相交一起出现,即分别有两个链表,它们可能成环,也可能相交,还可能既成环、又相交。现在,怎样判断它们是否成环,如果成环,环入口在哪里?是否相交,如果相交,相交点又在哪里?

看起来似乎问题一下子复杂了很多,可是仔细观察一下这两个问题,它们的地位不是均等的——

  • 成环的判断,并不依赖于相交的判断。换言之,无论两个链表是否相交,都可以利用前面所述的成环判断,和环入口的计算方式求得。
  • 可是相交的判断却依赖于成环的判断。换言之,要求相交的点需要知道链表的长度,而一旦链表成环了,这个长度就不再能用通用的方法来求解了。

因此,先判断链表是否成环,并且分别求出这两个链表的环入口(如果成环的话),之后再考虑链表相交的问题。

接着,关于成环和相交,有如下的结论:

  • 如果这两个链表,一个成环,而另一个不成环,那么它们二者肯定不相交。这个结论是显然的,因为相交,意味着这个环是共用的,那么自然不可能一个成环,而另一个不成环了。
  • 如果这两个链表都不成环,那么问题退化为前面讲的相交问题。
  • 如果这两个链表都成环,那么问题就比较有意思了,下面我们按照相交点出现的位置来分别讨论。

这种情况下,我们把环入口的点视作两个链表的尾部,然后可以用前面所述的算法求得相交的点。

如果在遍历到环入口以前,找到了两个链表相交的节点,那么我们遇到了情况一,相交的节点先于成环的节点出现

反之,如果遍历到环入口时,依然没有发现相交的节点,那么存在下面所述的情况二和情况三:

情况二,成环且不相交,相当于两个独立的带环链表

情况三,环入口和相交的节点一起出现

有没有可能有情况四,即先出现环入口,再出现相交的节点?

不可能。因为前面已经介绍了,相交就意味着一旦有环,这个环就是两个链表共用的,因此这个环入口一旦出现,就意味着一个链表连上了另一个链表的环,也就意味着相交点也出现了。因此,这种情况下二者是一起出现的,不可能出现环入口早于相交节点的情况。

那么现在的问题是,怎样区分情况二和情况三?

既然两个环入口都找到了,那么以任意一个环入口作为起点,开始遍历,绕环一周,如果期间遇到了另一个环入口,说明是情况三,否则则是情况二。

好,这个问题就讨论到这里。你也可以看到,如果单独拿出最后一个问题来,这是一个有着相当复杂度的问题。不过如果逐步深入进来的话,应该就好很多。

记得在差不多快要十年前了,我 “莫名其妙” 地参加了微软的面试,而电话面试问的题目就是本文一开始的链表成环判断的问题。由于对外企面试的玩法一无所知,我被虐得体无完肤。现在看起来这实在是一个太过普通的问题,但当时的我对于算法的认识是非常浅的,也没有给出一个非常好的解决办法。但是从那一天开始,我才真正算是逐步开始接触并学习算法,因此这篇文章,也算对它小小的纪念。

最后,我想说明的是,在分析上面这些问题的时候,我没有写一点代码。我觉得,这样的纯算法问题,只要思路清楚了,代码基本不是什么问题。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/3dzZcfr

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 哎,写代码的时间真的越来越少了……

还记得在读书的时候,就对程序员有种坐在电脑前疯狂敲代码的刻板印象。工作以后,逐渐理解了软件工程师的工作到底是怎么样的,可是写代码,作为软件工程师最重要的本职工作,还是占据了相当比重的时间。在面试别人的时候,也经常被问到这样的问题——“平均你每天有多少时间花在写代码上?”,这个问题看似简单,却能反映出一个问题,软件工程师,能否有足够的时间专注在最本职工作——写代码上。毫无疑问,我完全理解这样的问题,并且,我也一直以来想保持着自己一个 “纯粹” 程序员的身份。我觉得我的职业通道也是一条纯粹的技术人的道路,因而写代码,是一个如同每天吃饭喝水一样的基本操作。

可是,随着职业生涯的进展,特别是近半年来的一系列变化,我已经明显感受到,这已经发生了变化,曾经的理所应当不再是理所应当。这个变化会带来什么,除去不断的思考,时间会告诉我更多。

团队的变化

在建立初期,OCI 更偏向于招纳更有经验的工程师,因为那个时候 “打地基”、“搭框架” 的工作潜在的影响力,和犯错的可能更为巨大,这样的工作不只是云服务本身的建设,还包括团队和流程体系的打磨。但是逐渐地,随着团队的扩张,招人的策略也发生了明显的变化:

  • 更多的初级职位,更多地吸纳经验较少的工程师,特别是毕业生;
  • 对于高级别的职位,需求量减少,要求的标准相对而言可能有所提高。

其实这也没有什么难以理解的,现在无论是技术人还是管理人,不管是 IC(Individual Contributor)岗还是 M(Manager)岗,大家都对级别和对应的能力和贡献的期望愈发清晰。换言之,就是很明确什么样的工作,交给什么样能力的人去做。这样一来,大多数团队对具备不同能力和经验的软件工程师的需求,也变成了塔状,即经验较少的工程师占较大(60% 以上)的比重。于是,在能够达成目的的基础上,使用这样的模式,可以更好地控制团队的薪酬成本,同时,不同的工程师也可以得到相对合适的挑战。

另一方面,团队负责的项目的规模还在逐渐扩大。团队重新划分过几次,如今我们也肯定是一个全栈式团队(对全栈式团队有疑惑的可以参见我在专栏中的解读),而团队拥有的产品里面,既有数据中心的数据服务,有分布式工作流引擎,还有内部使用的可视化工具网站,并且可以说是既有平台,又有业务。因此对于大部分计算机相关专业毕业的软件工程师,都可以在我们团队找到感兴趣的方向。(题外话,目前由于新冠病毒造成的影响,OCI 的招聘暂停,但是预计在数周后会逐步恢复,对我们团队感兴趣的可以和我联系,不过工作地点只有西雅图。)

这三个产品可以说每一个所对应的最大挑战都不相同,但是配合起来,大的目标是一致的,就是为数据中心,特别是新建数据中心服务,既包括流程自动化,又包括数据存取和展示。

我自己的变化

回想工作最初的几年,特性和功能开发是时间花费最主要的地方,也是最多的 “写代码” 的原因。如今,这件事情肯定已经跌出前三了。

这半年来,我自身的角色也发生了比较大的变化,现在除去一如既往地负责单个产品本身的主要项目,还需要牵线那些各个产品负责的子团队协作来完成的工作。而在项目和团队中实际做的事情,也有了明显变化。总的来说,下面这些事情,时间占用出现了大幅度的上升:

产品或特性的规划

早些年我的理解,对于产品或特性的规划,应该是 TPM 或者产品经理这样的角色来完成的,但是其实这是不准确的。事实上,一方面,有很多工作确实是需要有足够技术背景的人去完成;而另一方面,本身对于多数项目来说这样的角色已经很模糊了,一个不深入理解业务和产品的 IC?不可能的。

对于我们团队来说,TPM 能够提供这样三个方面的帮助:业务、项目和客户。但是,有许多产品或特性的规划,基本上这三个都不相关,完全是工程师的活儿。比如说分布式工作流引擎,业务线和技术线是可以分得比较清楚的:下面的平台本身是业务无关的,而在其之上跑着的的业务工作流却相反。因此,对于其中技术层面的规划设计,也包括将业务怎样落地梳理清楚,只有工程师才能完成。

技术架构

这部分其实接近于我在读书时期对于架构师狭隘的理解。

事实上,我了解到,对于很多真正参与这方面工作的人来说,真正的纯技术架构工作,占比并不会非常大。这一方面是由于,并没有那么多产品长期处于 “初创期” 或者 “转型期”,需要大量的架构工作;另一方面,则是因为一切的技术架构都是建立在业务和需求清晰的基础之上,而做到这一基础已经需要巨大的时间精力投入了。

值得一提的是,这样的工作需要一些考察和探索,比如做技术选型和快速原型。有时候也会涉及一部分编码。总的来说,这其实是我比较喜欢的事情。

管理、沟通和协调

这部分我描述得很笼统,并且有一点像管理岗的工作了。或多或少,这是一个 IC 不可避免的职责。理想状况下研发经理理应承担更多这方面的工作,但是我们的团队人手方面,这样的角色数量不足够,因而 IC 需要更多地承担这方面的工作。当然,即便能做到理想状况,沟通和协调于我而言,依然会占据相当的比重。

对于我们团队而言,偏重技术方面的需求比较多,因此需要软件工程师更多的参与。事实上,我们每一个产品/子团队都有 lead,他们都会主导或重度参与每一个 Sprint 的任务规划。这也再一次印证了,对于 IC 来说,随着职业生涯的发展,角色定位就是会越来越 “模糊”。

Mentoring

在我们团队,目前工作经验较少的工程师比较多,因此 mentoring 是一件比较重要的事情(除此之外,这个状况也是对于 dev manager 需求比较强烈的原因之一)。当然,这部分时间开销,也可以归纳到上面的 “管理、沟通和协调” 当中去。

招聘

上面说的是团队内的时间开销,而在跨团队的 OCI 层面,有这样两项内容花费了显著的时间:一个是设计评审,另一个就是招聘。而对工程师来说,这件事基本围绕面试展开。对于这个话题,鉴于之前已经说过几次了(比如这一篇这一篇),在此就不展开了。

对于角色上的变化,我依然在逐步适应中,寻找最适合自己的方式。而对于写代码这个事情,时间确实是越来越少了,不知道一个合适的解决方法是什么?当然,我并不想去狭隘和片面地追求编码时间,但是我知道,编码是一件常练常新的基本功。在工作中,到底应该怎样更有效地分配时间,平衡包括编码在内的各种各样的事情,希望我可以很快把这个问题考虑清楚……

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/358H6y4

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 那些做了一半的项目

最近有一个项目做了一半不做了,准确地说是由于某些原因,项目需要别的团队来接手了,于是我想随便聊聊这个话题。我猜想,“项目做一半撒手”,这应该是一个很常见的现象,因为这样的事情无论大厂小厂,在软件的世界里不断上演。具体来说,有这样几种典型的情况:

  • 业务变动、组织调整,工作重心变了,项目做了一半直接砍掉,或者无限期停工。这大概是最常见的一种情形。
  • 由于前期的调研、设计的严重问题,或是市场等变化过于剧烈,项目做不下去了,静悄悄地黄了。
  • 项目还做,但是转交给某个其它的团队,这是我这一次遇到的情形。项目还存在,只不过所属关系已经发生变更。

文档和隐性成本

无论哪一种,有一点是毫无疑问的,那就是资源投入的浪费,无论是软件还是硬件。即便不砍掉,暂停一段时间,再恢复的时候,要捡起曾经的项目,一样需要一定的成本。而项目要转交给其它团队,软件的交接成本也相当可观。其实这没有什么奇怪的,这是软件的本质所决定的。具体来说,软件开发,特别是上规模的软件开发,就意味着大量的 “隐性成本”。

从项目管理的角度来说,我们当然希望规范而且具体,或者说,大家都照章办事,项目设计可以纸面化,事无巨细地把 “为什么要这样做”,和 “‘这样做’ 是 ‘怎样做’ 的” 这样的信息都落地成文字交代清楚。可是你我程序员都知道,这是遗憾到不可能发生的事情。我在中国的大厂待过,也在北美的大厂待过,有个别经历的团队和项目甚至被内部外部视作典范,可是客观地说,文档依然缺失,而且不是缺失一点,而是大量地缺失,再好的项目也是如此。

其实,这并不是什么不可理喻的事情,相反,如果一个一定规模的软件项目,文档清清楚楚,把项目事项和设计细节都交代得清清楚楚,我反而觉得这个项目有着猫腻。因为代码和文档永远有着显著而不可调和的矛盾。为什么呢?因为对于软件工程师来说,一个且只有一个真正的、准确的数据来源(Single Source of Truth),是值得推崇的最佳实践。这样的指导思想是根植于他们脑海中的,一个凡是对 Engineering Excellence 有着追求的程序员,一定会把它放在相当重要的位置。而在多数情况下,文档和代码就是两个数据来源,且无法被统一,但是你我都知道,真正工作的一定是代码,代码才是真正的 source of truth,文档只能成为不断过时的那一个。

我知道一定会有声音说,难道不能及时更新文档吗?比方说,代码逻辑修改了,修改的工程师也负责更新文档。没错,但这过于理想化了,而且,就好像软件的世界里一致性和可用性经常是难以调和的矛盾一样,文档的细致程度,和保持准确性的能力,也一样是难以调和的:文档越是细致,就约难以被及时更新,也就越容易成为过时的文档。文档的更新,不但涉及到工作量的问题,它本身也不符合很多工程师基于代码的思维习惯,因为它的读者有了变化,而且叙述的方式也有了变化;再者,真正在业务中直接生效的,也是代码,文档相应地,总是显得那么间接。

对于大多数工程师来说,特别是某些踏入职场时间并不长的工程师来说,文档的地位要更低一些。就好像 “talk is cheap, show me the code” 已经被不可思议地滥用一样,他们对于代码有着过度的狂热。这原本不是什么坏事,软件工程师总是要立足的代码的,可是,软件工程所谓工程,它一定是一个复杂的结合体,代码只能是其中一部分,有时甚至只是一小部分。随着时间和阅历的增加,越发觉得合适的文档在软件工程中的价值,比方说,就在几年前,关于文档我的一点思考记录在这里,现在其实也已经有了更新。

再回到隐性成本的话题上来。已经说了,在文档缺失或过时的情况下,程序员需要去理解需求,并阅读代码来理解前前后后整个故事,这里面的时间成本和试错成本可想而知,可退一步说,哪怕真的文档齐全,要把这些东西消化掉,也依然需要大量的时间。我们都说程序员是一个终生学习的职业,而每一个项目,就是一个可观测的学习的单元。

是勇气还是荒唐?

这样的决定很多时候并不容易做出。我经历过的多数情况,都来自自上而下的决策。有时候部门调整(reorg),结果一些项目的重要性就发生变更,直接砍掉了。而甚至有时候整个部门或团队都砍掉了,我在亚马逊的时候就经历了这么一回,一个原本负责商品在欧洲内各个国家之间方便流通的团队就这样直接砍掉了,当时作为团队里的一份子,我获得了几个 “下家” 团队的选项。也就是说,工程师重新回归资源池,重新分配归属团队。

但也经历过自下而上的,做过的某个内部应用,本来也是摸着石头过河,第一个版本做出交付了,却发现可用性还是比较差,具体说就是流程还是过于苛刻和冗长,而这个问题又不是一个比较容易解决的问题,很难把它继续推广开去,因此这个项目就烂在半途中了。虽说不能说项目砍掉了,但已经低优先级、无限期搁置了,也就和砍掉没有什么太大区别了。

多数时候,这样的损失并不只有纸面上能看到的 “浪费” 那么简单。除了上面所说的隐性成本,还有对团队士气的打击。但是,这里面有一个值得玩味的话题,当一个团队全身心地、毫无保留地投身奉献于一个项目的时候,这里的风险就很容易不可控了。有一位团队经理给下属画饼的时候说过,“你要把 xxx 项目当做你自己的孩子一样”,无疑这对于传递 ownership 的精神,是一个很形象的比喻,可是项目可能会黄,到时候该怎么收场呢?因此我觉得这不是一个特别职业的表达。

最后,回想起来,这种 “做了一半的项目” 还真是挺常见的。非常遗憾,可对于一个大型的组织来说,回头是岸,及时止损,通常可不是坏事。这样的决定无疑需要勇气,更糟的结果是继续这个项目,决策下的越晚损失越大。软件工程似乎就是这样一个无完美解的难题,处处充满了看似可以避免的弯路和糟糕实践,可是换个项目重来一遍的时候,还是一样有这样那样的问题。这有点像是人生,大道理我们都懂,可还是过不好这一生。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/2VpffFj

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【酷壳】 Rust语言的编程范式

总是有很多很多人来问我对Rust语言怎么看的问题,在各种地方被at,其实,我不是很想表达我的想法。因为在不同的角度,你会看到不同的东西。编程语言这个东西,老实说很难评价,在学术上来说,Lisp就是很好的语言,然而在工程使用的时候,你会发现Lisp没什么人用,而Javascript或是PHP这样在学术很糟糕设计的语言反而成了主流,你觉得C++很反人类,在我看来,C++有很多不错的设计,而且对于了解编程语言和编译器的和原理非常有帮助。但是C++也很危险,所以,出现在像Java或Go 语言来改善它,Rust本质上也是在改善C++的。他们各自都有各自的长处和优势

因为各个语言都有好有不好,因此,我不想用别的语言来说Rust的问题,或是把Rust吹成朵花以打压别的语言,写成这样的文章,是很没有营养的事。本文主要想通过Rust的语言设计来看看编程中的一些挑战,尤其是Rust重要的一些编程范式,这样反而更有意义一些,因为这样你才可能一通百通

这篇文章的篇幅比较长,而且有很多代码,信息量可能会非常大,所以,在读本文前,你需要有如下的知识准备

  • 你对C++语言的一些特性和问题比较熟悉。尤其是:指针、引用、右值move、内存对象管理、泛型编程、智能指针……
  • 当然,你还要略懂Rust,不懂也没太大关系,但本文不会是Rust的教程文章,可以参看“Rust的官方教程”(中文版

因为本文太长,所以,我有必要写上 TL;DR ——

Java 与 Rust 在改善C/C++上走了完全不同的两条路,他们主要改善的问题就是C/C++ Safety的问题。所谓C/C++编程安全上的问题,主要是:内存的管理、数据在共享中出现的“野指针”、“野引用”的问题。

  • 对于这些问题,Java用引用垃圾回收再加上强大的VM字节码技术可以进行各种像反射、字节码修改的黑魔法。
  • 而Rust不玩垃圾回收,也不玩VM,所以,作为静态语言的它,只能在编译器上下工夫。如果要让编译器能够在编译时检查出一些安全问题,那么就需要程序员在编程上与Rust语言有一些约定了,其中最大的一个约定规则就是变量的所有权问题,并且速要在代码上“去糖”,比如让程序员说明一些共享引用的生命周期。
  • Rust的这些所有权的约定造成了很大的编程上的麻烦,写Rust的程序时,基本上来说,你的程序再也不要想可能轻轻松松能编译通过了。而且,在面对一些场景的代码编写时,如:函数式的闭包,多线程的不变数据的共享,多态……开始变得有些复杂,并会让你有种找不到北的感觉。
  • Rust的Trait很像Java的接口,通过Trait可以实现C++的拷贝构造、重载操作符、多态等操作……
  • 学习Rust的学习曲线并不平,用Rust写程序,基本上来说,一旦编译通过,代码运行起来是安全的,bug也是很少的。

如果你对Rust的概念认识的不完整,你完全写不出程序,那怕就是很简单的一段代码这逼着程序员必需了解所有的概念才能编码。但是,另一方面也表明了这门语言并不适合初学者……

变量的可变性

首先,Rust里的变量声明默认是“不可变的”,如果你声明一个变量 let x = 5;  变量 x 是不可变的,也就是说,x = y + 10; 编译器会报错的。如果你要变量的话,你需要使用 mut 关键词,也就是要声明成 let mut x = 5; 表示这是一个可以改变的变量。这个是比较有趣的,因为其它主流语言在声明变量时默认是可变的,而Rust则是要反过来。这可以理解,不可变的通常来说会有更好的稳定性,而可变的会代来不稳定性。所以,Rust应该是想成为更为安全的语言,所以,默认是 immutable 的变量。当然,Rust同样有 const 修饰的常量。于是,Rust可以玩出这么些东西来:

  • 常量:const LEN:u32 = 1024; 其中的 LEN 就是一个u32 的整型常量(无符号32位整型),是编译时用到的。
  • 可变的变量: let mut x = 5; 这个就跟其它语言的类似, 在运行时用到。
  • 不可变的变量:let x= 5; 对这种变量,你无论修改它,但是,你可以使用 let x = x + 10; 这样的方式来重新定义一个新的 x。这个在Rust里叫 Shadowing ,第二个 x  把第一个 x 给遮蔽了。

不可变的变量对于程序的稳定运行是有帮助的,这是一种编程“契约”,当处理契约为不可变的变量时,程序就可以稳定很多,尤其是多线程的环境下,因为不可变意味着只读不写,其他好处是,与易变对象相比,它们更易于理解和推理,并提供更高的安全性。有了这样的“契约”后,编译器也很容易在编译时查错了。这就是Rust语言的编译器的编译期可以帮你检查很多编程上的问题。

对于标识不可变的变量,在 C/C++中我们用const ,在Java中使用 final ,在 C#中使用 readonly ,Scala用 val ……(在Javascript 和Python这样的动态语言中,原始类型基本都是不可变的,而自定义类型是可变的)。

对于Rust的Shadowing,我个人觉得是比较危险的,在我的职业生涯中,这种使用同名变量(在嵌套的scope环境下)带来的bug还是很不好找的。一般来说,每个变量都应该有他最合适的名字,最好不要重名。

变量的所有权

这个是Rust这个语言中比较强调的一个概念。其实,在我们的编程中,很多情况下,都是把一个对象(变量)传递过来传递过去,在传递的过程中,传的是一份复本,还是这个对象本身,也就是所谓的“传值还是传引用”的被程序员问得最多的问题。

  • 传递副本(传值)。把一个对象的复本传到一个函数中,或是放到一个数据结构容器中,可能需要出现复制的操作,这个复制对于一个对象来说,需要深度复制才安全,否则就会出现各种问题。而深度复制就会导致性能问题。
  • 传递对象本身(传引用)。传引用也就是不需要考虑对象的复制成本,但是需要考虑对象在传递后,会多个变量所引用的问题。比如:我们把一个对象的引用传给一个List或其它的一个函数,这意味着,大家对同一个对象都有控制权,如果有一个人释放了这个对象,那边其它人就遭殃了,所以,一般会采用引用计数的方式来共享一个对象。引用除了共享的问题外,还有作用域的问题,比如:你从一个函数的栈内存中返回一个对象的引用给调用者,调用者就会收到一个被释放了个引用对象(因为函数结束后栈被清了)。

这些东西在任何一个编程语言中都是必需要解决的问题,要足够灵活到让程序员可以根据自己的需要来写程序。

在C++中,如果你要传递一个对象,有这么几种方式:

  • 引用或指针。也就是不建复本,完全共享,于是,但是会出现悬挂指针(Dangling Pointer)又叫野指针的问题,也就是一个指针或引用指向一块废弃的内存。为了解决这个问题,C++的解决方案是使用 share_ptr 这样的托管类来管理共享时的引用计数。
  • 传递复本,传递一个拷贝,需要重载对象的“拷贝构造函数”和“赋值构造函数”。
  • 移动Move。C++中,为了解决一些临时对象的构造的开销,可以使用Move操作,把一个对象的所有权移动到给另外一个对象,这个解决了C++中在传递对象时的会产生很多临时对象来影响性能的情况。

C++的这些个“神操作”,可以让你非常灵活地在各种情况下传递对象,但是也提升整体语言的复杂度。而Java直接把C/C++的指针给废了,用了更为安全的引用 ,然后为了解决多个引用共享同一个内存,内置了引用计数和垃圾回收,于是整个复杂度大大降低。对于Java要传对象的复本的话,需要定义一个通过自己构造自己的构造函数,或是通过prototype设计模式的 clone() 方法来进行,如果你要让Java解除引用,需要明显的把引用变量赋成 null 。总之,无论什么语言都需要这对象的传递这个事做好,不然,无论提供相对比较灵活编程方法。

在Rust中,Rust强化了“所有权”的概念,下面是Rust的所有者的三大铁律:

  1. Rust 中的每一个值都有一个被称为其 所有者owner)的变量。
  2. 值有且只有一个所有者。
  3. 当所有者(变量)离开作用域,这个值将被丢弃。

这意味着什么?

如果你需要传递一个对象的复本,你需要给这个对象实现 Copy trait ,trait 怎么翻译我也不知道,你可以认为是一个对象的一些特别的接口(可以用于一些对像操作上的约定,比如:Copy 用于复制(类型于C++的拷贝构造),Display 用于输出(类似于Java的 toString()),还有 Drop 和操作符重载等等,当然,也可以是对象的方法,或是用于多态的接口定义,后面会讲)。

对于内建的整型、布尔型、浮点型、字符型、多元组都被实现了 Copy 所以,在进行传递的时候,会进行memcpy 这样的复制(bit-wise式的浅拷贝)。而对于对象来说,则不行,在Rust的编程范式中,需要使用的是 Clone trait。

于是,CopyClone 这两个相似而又不一样的概念就出来了,Copy 主要是给内建类型,或是由内建类型全是支持 Copy 的对象,而 Clone 则是给程序员自己复制对象的。嗯,这就是浅拷贝和深拷贝的差别,Copy 告诉编译器,我这个对象可以进行 bit-wise的复制,而 Clone 则是指深度拷贝。

String 这样的内部需要在堆上分布内存的数据结构,是没有实现Copy 的(因为内部是一个指针,所以,语义上是深拷贝),需要复制的话,必需手动的调用其 clone() 方法,如果不这样的的话,当在进行函数参数传递,或是变量传递的时候,所有权一下就转移了,而之前的变量什么也不是了(这里编译器会帮你做检查有没有使用到所有权被转走的变量)。这个相当于C++的Move语义。

参看下面的示例,你可能对Rust自动转移所有权会有更好的了解(代码中有注释了,我就不多说了)。

// takes_ownership 取得调用函数传入参数的所有权,因为不返回,所以变量进来了就出不去了
fn takes_ownership(some_string: String) {
    println!("{}", some_string);
} // 这里,some_string 移出作用域并调用 `drop` 方法。占用的内存被释放

// gives_ownership 将返回值移动给调用它的函数
fn gives_ownership() -> String {
    let some_string = String::from("hello"); // some_string 进入作用域.
    some_string // 返回 some_string 并移出给调用的函数
}

// takes_and_gives_back 将传入字符串并返回该值
fn takes_and_gives_back(mut a_string: String) -> String {
    a_string.push_str(", world");
    a_string  // 返回 a_string 将所有权移出给调用的函数
}

fn main()
{
    // gives_ownership 将返回值移给 s1
    let s1 = gives_ownership();
    // 所有权转给了 takes_ownership 函数, s1 不可用了
    takes_ownership(s1);
    // 如果编译下面的代码,会出现s1不可用的错误
    // println!("s1= {}", s1);
    //                    ^^ value borrowed here after move
    let s2 = String::from("hello");// 声明s2
    // s2 被移动到 takes_and_gives_back 中, 它也将返回值移给 s3。
    // 而 s2 则不可用了。
    let s3 = takes_and_gives_back(s2);
    //如果编译下面的代码,会出现可不可用的错误
    //println!("s2={}, s3={}", s2, s3);
    //                         ^^ value borrowed here after move
    println!("s3={}", s3);
}

这样的 Move 的方式,在性能上和安全性上都是非常有效的,而Rust的编译器会帮你检查出使用了所有权被move走的变量的错误。而且,我们还可以从函数栈上返回对象了,如下所示:

fn new_person() -> Person {
    let person = Person {
        name : String::from("Hao Chen"),
        age : 44,
        sex : Sex::Male,
        email: String::from("haoel@hotmail.com"),
    };
    return person;
}

fn main() {
   let p  = new_person();
}

因为对象是Move走的,所以,在函数上 new_person() 上返回的 Person 对象是Move 语言,被Move到了 main() 函数中来,这样就没有性能上的问题了。而在C++中,我们需要把对象的Move函数给写出来才能做到。因为,C++默认是设用拷贝构造函数的,而不是Move的。

Owner语义带来的复杂度

Owner + Move 的语义也会带来一些复杂度。首先,如果有一个结构体,我们把其中的成员 Move 掉了,会怎么样。参看如下的代码:

#[derive(Debug)] // 让结构体可以使用 `{:?}`的方式输出
struct Person {
    name :String,
    email:String,
}

let _name = p.name; // 把结构体 Person::name Move掉
println!("{} {}", _name, p.email); //其它成员可以正常访问
println!("{?:}", p); //编译出错 "value borrowed here after partial move"
p.name = "Hao Chen".to_string(); // Person::name又有了。
println!("{?:}", p); //可以正常的编译了

上面这个示例,我们可以看到,结构体中的成员是可以被Move掉的,Move掉的结构实例会成为一个部分的未初始化的结构,如果需要访问整个结构体的成员,会出现编译问题。但是后面把 Person::name补上后,又可以愉快地工作了。

下面我们再看一个更复杂的示例——这个示例模拟动画渲染的场景,我们需要有两个buffer,一个是正在显示的,另一个是下一帧要显示的。

struct Buffer {
    buffer : String,
}

struct Render {
    current_buffer : Buffer,
    next_buffer : Buffer,
}
//实现结构体 `Render` 的方法
impl Render { 
    //实现 update_buffer() 方法,
    //更新buffer,把 next 更新到 current 中,再更新 next
    fn update_buffer(& mut self, buf : String) {
        self.current_buffer = self.next_buffer;
        self.next_buffer = Buffer{ buffer: buf};
    }
}

上面这段代码,我们写下来没什么问题,但是 Rust 编译不会让我们编译通过。它会告诉我们如下的错误:

error[E0507]: cannot move out of `self.next_buffer` which is behind a mutable reference
--> /.........../xxx.rs:18:31
|
14 | self.current_buffer = self.next_buffer;
|                          ^^^^^^^^^^^^^^^^ move occurs because `self.next_buffer` has type `Buffer`,
                                            which does not implement the `Copy` trait

编译器会提示你,Buffer 没有 Copy trait 方法。但是,如果你实现了 Copy 方法后,你又不能享受 Move 带来的性能上快乐了。于是,到这里,你开始进退两难了,完全不知道取舍了

  • Rust编译器不让我们在成员方法中把成员Move走,因为 self 引用就不完整了。
  • Rust要我们实现 Copy Trait,但是我们不想要拷贝,因为我们就是想把 next_buffer move 到 current_buffer

我们想要同时 Move 两个变量,参数 buf move 到 next_buffer 的同时,还要把 next_buffer 里的东西 move 到 current_buffer 中。 我们需要一个“杂需”的技能。

这个需要动用 std::mem::replace(&dest, src) 函数了, 这个函数技把 src 的值 move 到 dest 中,然后把 dest 再返回出来(这其中使用了 unsafe 的一些底层骚操作才能完成)。Anyway,最终是这样实现的:

use std::mem::replace
fn update_buffer(& mut self, buf : String) { 
  self.current_buffer = replace(&mut self.next_buffer, Buffer{buffer : buf}); 
}

引用(借用)和生命周期

下面,我们来讲讲引用,因为把对象的所有权 Move 走了的情况,在一些时候肯定不合适,比如,我有一个 compare(s1: Student, s2: Student) -> bool 我想比较两个学生的平均份成绩, 我不想传复本,因为太慢,我也不想把所有权交进去,因为只是想计算其中的数据。这个时候,传引用就是一个比较好的选择,Rust同样支持传引用。只需要把上面的函数声明改成:compare(s1 :&Student, s2 : &Student) -> bool 就可以了,在调用的时候,compare (&s1, &s2);  与C++一致。在Rust中,这也叫“借用”(嗯,Rust发明出来的这些新术语,在语义上感觉让人更容易理解了,当然,也增加了学习的复杂度了)

引用(借用)

另外,如果你要修改这个引用对象,就需要使用“可变引用”,如:foo( s : &mut Student) 以及 foo( &mut s);另外,为了避免一些数据竞争需要进行数据同步的事,Rust严格规定了——在任意时刻,要么只能有一个可变引用,要么只能有多个不可变引用

这些严格的规定会导致程序员失去编程的灵活性,不熟悉Rust的程序员可能会在一些编译错误下会很崩溃,但是你的代码的稳定性也会提高,bug率也会降低。

另外,Rust为了解决“野引用”的问题,也就是说,有多个变量引用到一个对象上,还不能使用额外的引用计数来增加程序运行的复杂度。那么,Rust就要管理程序中引用的生命周期了,而且还是要在编译期管理,如果发现有引用的生命周期有问题的,就要报错。比如:

let r;
{
    let x = 10;
    r = &x;
}
println!("r = {}",r );

上面的这段代码,程序员肉眼就能看到 x 的作用域比 r  小,所以导致 rprintln() 的时候 r 引用的 x 已经没有了。这个代码在C++中可以正常编译而且可以执行,虽然最后可以打出“内嵌作用域”的 x 的值,但其实这个值已经是有问题的了。而在 Rust 语言中,编译器会给出一个编译错误,告诉你,“x dropped here while still borrowed”,这个真是太棒了。

但是这中编译时检查的技术对于目前的编译器来说,只在程序变得稍微复杂一点,编译器的“失效引用”检查就不那么容易了。比如下面这个代码:

fn order_string(s1 : &str, s2 : &str) -> (&str, &str) {
    if s1.len() < s2.len() {
        return (s1, s2);
    }
    return (s2, s1);
}

let str1 = String::from("long long long long string");
let str2 = "short string";

let (long_str, short_str) = order_string(str1.as_str(), str2);

println!(" long={} nshort={} ", long_str, short_str);

我们有两个字符串,str1str2 我们想通过函数 order_string() 把这两个字串符返回成 long_strshort_str  这样方便后面的代码进行处理。这是一段很常见的处理代码的示例。然而,你会发现,这段代码编译不过。编译器会告诉你,order_string() 返回的 引用类型 &str 需要一个 lifetime的参数 – “ expected lifetime parameter”。这是因为Rust编译无法通过观察静态代码分析返回的两个引用返回值,到底是(s1, s2) 还是 (s2, s1) ,因为这是运行时决定的。所以,返回值的两个参数的引用没法确定其生命周期到底是跟 s1 还是跟 s2,这个时候,编译器就不知道了。

生命周期

如果你的代码是下面这个样子,编程器可以自己推导出来,函数 foo() 的参数和返回值都是一个引用,他们的生命周期是一样的,所以,也就可以编译通过。

fn foo (s: &mut String) -> &String {
    s.push_str("coolshell");
    s
}

let mut s = "hello, ".to_string();
println!("{}", foo(&mut s))

而对于传入多个引用,返回值可能是任一引用,这个时候编译器就犯糊涂了,因为不知道运行时的事,所以,就需要程序员来标注了。

fn long_string<'c>(s1 : &'c str, s2 : &'c str) -> (&'c str, &'c str) {
    if s1.len() > s2.len() {
        return (s1, s2);
    }
    return (s2, s1);
}

上述的Rust的标注语法,用个单引号加一个任意字符串来标注('static除外,这是一个关键词,表示生命周期跟整个程序一样长),然后,说明返回的那两个引用的生命周期跟 s1s2 的生命周期相同,这个标注的目的就是把运行时的事变成了编译时的事。于是程序就可以编译通过了。(注:你也不要以为你可以用这个技术乱写生命周期,这只是一种声明,是帮助编译器理解其中的生命周期,如果违反实际生命周期,编译器也是会拒绝编译的)

这里有两个说明,

  • 只要你玩引用,生命周期标识就会来了。
  • Rust编译器不知道运行时会发生什么事,所以,需要你来标注声明

我感觉,你现在开始有点头晕了吧?接下来,我们让你再晕一下。比如:如果你要在结构体中玩引用,那必需要为引用声明个生命周期,如下所示:

// 引用 ref1 和 ref2 的生命周期与结构体一致
struct Test <'life> {
    ref_int : &'life i32,
    ref_str : &'life str,
}

其中,生命周期标识 'life 定义在结构体上,被使用于其成员引用上。意思是声明规则——“结构体的生命周期 <= 成员引用的生命周期

然后,如果你要给这个结构实现两个 set 方法,你也得带上 lifetime 标识。

imp<'life> Test<'life> {
    fn set_string(&mut self, s : &'life str) {
        self.ref_str = s;
    }
    fn set_int(&mut self,  i : &'life i32) {
        self.ref_int = i;
    }
}

在上面的这个示例中,生命周期变量 'life 声明在 impl 上,用于结构体和其方法的入参上。 意思是声明规则——“结构体方法的“引用参数”的生命周期 >= 结构体的生命周期

有了这些个生命周期的标识规则后,Rust就可以愉快地检查这些规则说明,并编译代码了。

闭包与所有权

这种所有权和引用的严格区分和管理,会影响到很多地方,下面我们来看一下函数闭包中的这些东西的传递。函数闭包又叫Closure,是函数式编程中一个不可或错的东西,又被称为lambda表达式,基本上所有的高级语言都会支持。在 Rust 语言中,其闭包函数的表示是用两根竖线(| |)中间加传如参数进行定义。如下所示:

// 定义了一个 x + y 操作的 lambda f(x, y) = x + y;
let plus = |x: i32, y:i32| x + y; 
// 定义另一个lambda g(x) = f(x, 5)
let plus_five = |x| plus(x, 5); 
//输出
println!("plus_five(10)={}", plus_five(10) );
函数闭包

但是一旦加上了上述的所有权这些东西后,问题就会变得复杂开来。参看下面的代码。

struct Person {
    name : String,
    age : u8,
}

fn main() {
    let p = Person{ name: "Hao Chen".to_string(), age : 44};
    //可以运行,因为 `u8` 有 Copy Trait
    let age = |p : Person| p.age; 
    // String 没有Copy Trait,所以,这里所有权就 Mov e走了
    let name = |p : Person | p.name; 
    println! ("name={}, age={}" , name(p), age(p));
}

上面的代码无法编译通过,因为Rust编译器发现在调用 name(p) 的时候,p 的所有权被移走了。然后,我们想想,改成引用的版本,如下所示:

let age = |p : &Person| p.age;
let name = |p : &Person | &p.name;

println! ("name={}, age={}" , name(&p), age(&p));

你会现在还是无法编译,报错中说:cannot infer an appropriate lifetime for borrow expression due to conflicting requirements

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> src/main.rs:11:31
   |
11 |     let name = |p : &Person | &p.name;
   |                               ^^^^^^^

然后你开始尝试加 lifetime,用尽各种Rust的骚操作(官方Github上的 #issue 58052),然后,还是无法让你的程序可以编译通过。最后,上StackOverflow 里寻找帮助,得到下面的正确写法(这个可能跟这个bug有关系:#issue 41078

//下面的声明可以正确译
let name: for<'a> fn(&'a Person) -> &'a String = |p: &Person| &p.name;

最后,我们再来看另一个问题,下面的代码无法编译通过:

let s = String::from("coolshell");
let take_str = || s;
println!("{}", s); //ERROR
println!("{}",  take_str()); // OK

Rust的编译器会告诉你,take_str  把 s 的所有权给拿走了(因为需要作成返回值)。所以,后面的输出语句就用不到了。这里意味着:

  • 对于内建的类型,都实现了 Copy 的 trait,那么闭包执行的是 “借用”
  • 对于没有实现 Copy 的trait,在闭包中可以调用其方法,是“借用”,但是不能当成返回值,当成返回值了就是“移动”。

虽然有了这些“通常情况下是借用的潜规则”,但是还是不能满足一些情况,所以,还要让程序员可以定义 move 的“明规则”。下面的代码,一个有 move 一个没有move,他们的差别也不一样。

//-----------借用的情况-----------
let mut num = 5;
{
    let mut add_num = |x: i32| num += x;
    add_num(5);
}
println!("num={}", num); //输出 10

//-----------Move的情况-----------
let mut num = 5;
{
    // 把 num(5)所有权给 move 到了 add_num 中,
    // 使用其成为闭包中的局部变量。
    let mut add_num = move |x: i32| num += x;
    add_num(5);
    println!("num(move)={}", num); //输出10
}
//因为i32实现了 `Copy`,所以,这里还可以访问
println!("num(move)={}", num); //输出5
线程闭包

通过上面的示例,我们可以看到, move 关键词,可以把闭包外使用到的变量给移动到闭包内,成为闭包内的一个局部变量。这种方式,在多线程的方式下可以让线程运行地更为的安全。参看如下代码:

let name = "CoolShell".to_string();
let t = thread::spawn(move || {
    println!("Hello, {}", name);
});
println!("wait {:?}", t.join());

首先,线程 thread::spawn() 里的闭包函数是不能带参数的,因为是闭包,所以可以使用这个可见范围内的变量,但是,问题来了,因为是另一个线程,所以,这代表其和其它线程(如:主线程)开始共享数据了,所以,在Rust下,要求把使用到的变量给 Move 到线程内,这就保证了安全的问题—— name 在编程中永远不会失效,而且不会被别人改了。

你可能会有一些疑问,你会质疑到

  • 一方面,这个 name 变量又没有声明成 mut 这意味着不变,没必要使用move语义也是安全的。
  • 另一方面,如果我想把这个 name 传递到多个线程里呢?

嗯,是的,但是Rust的线程必需是 move的,不管是不是可变的,不然编译不过去。如果你想把一个变量传到多个线程中,你得创建变量的复本,也就是调用 clone() 方法。

let name = "CoolShell".to_string();
let name1 = name.clone();
let t1 = thread::spawn(move || {
    println!("Hello, {}", name.clone());
})
let t2 = thread::spawn(move || {
    println!("Hello, {}", name1.clone());
});
println!("wait t1={:?}, t2={:?}", t1.join(), t2.join());

然后,你说,这种clone的方式成本不是很高?设想,如果我要用多线程对一个很大的数组做统计,这种clone的方式完全吃不消。嗯,是的。这个时候,需要使用另一个技术,智能指针了。

Rust的智能指针

如果你看到这里还不晕的话,那么,我的文章还算成功(如果晕的话,请告诉我,我会进行改善)。接下来我们来讲讲Rust的短能指针和多态。

因为有些内存需要分配在Heap(堆)上,而不是Stack(堆)上,Stack上的内存一般是编译时决定的,所以,编译器需要知道你的数组、结构构、枚举等这些数据类型的长度,没有长度是无法编译的,而且长度也不能太大,Stack上的内存大小是有限,太大的内存会有StackOverflow的错误。所以,对于更大的内存或是动态的内存分配需要分配在Heap上。学过C/C++的同学对于这个概念不会陌生。

Rust 作为一个内存安全的语言,这个堆上分配的内存也是需要管理的。在C中,需要程序员自己管理,而在C++中,一般使用 RAII 的机制(面向对象的代理模式),一种通过分配在Stack上的对象来管理Heap上的内存的技术。在C++中,这种技术的实现叫“智能指针”(Smart Pointer)。

在C++11中,会有三种智能指针(这三种指针是什么我就不多说了):

  • unique_ptr。独占内存,不共享。在Rust中是:std::boxed::Box
  • shared_ptr。以引用计数的方式共享内存。在Rust中是:std::rc::Rc
  • weak_ptr。不以引用计数的方式共享内存。在Rust中是:std::rc::Weak

对于独占的 Box 不多说了,这里重占说一下共享的 RcWeak

  • 对于Rust的 Rc 来说,Rc指针内会有一个 strong_count 的引用持计数,一旦引用计数为0后,内存就自动释放了。
  • 需要共享内存的时候,需要调用实例的 clone() 方法。如: let another = rc.clone()
  • 有这种共享的引用计数,就意味着有多线程的问题,所以,如果需要使用线程安全的智能指针,则需要使用std::sync::Arc
  • 可以使用 Rc::downgrade(&rc) 后,会变成 Weak 指针,Weak指针增加的是 weak_count 的引用计数,内存释放时不会检查它是否为 0。

我们简单的来看个示例:

use std::rc::Rc;
use std::rc::Weak

//声明两个未初始化的指针变量
let weak : Weak; 
let strong : Rc;
{
    let five = Rc::new(5); //局部变量
    strong = five.clone(); //进行强引用
    weak = Rc::downgrade(&five); //对局部变量进行弱引用
}
//此时,five已析构,所以 Rc::strong_count(&strong)=1, Rc::weak_count(&strong)=1
//如果调用 drop(strong),那个整个内存就释放了
//drop(strong);

//如果要访问弱引用的值,需要把弱引用 upgrade 成强引用,才能安全的使用
match  weak_five.upgrade() {
    Some(r) => println!("{}", r),
    None => println!("None"),
} 

上面这个示例比较简单,其中主要展示了,指针共享的东西。因为指针是共享的,所以,对于强引用来说,最后的那个人把引用给释放了,是安全的。但是对于弱引用来说,这就是一个坑了,你们强引用的人有Ownership,但是我们弱引用没有,你们把内存释放了,我怎么知道?

于是,在弱引用需要使用内存的时候需要“升级”成强引用 ,但是这个升级可能会不成功,有可能会升成不成,因为内存已经全没有了。所以,会返回一个 Option 的枚举值,Option::Some(T) 表示成功了,而 Option::None 则表示失改了。你会说,这么麻烦,我们为什么还要 Weak ? 这是因为强引用的 Rc 会有循环引用的问题……

另外,如果你要修改 Rc 里的值,Rust 会给你两个方法,一个是 get_mut(),一个是 make_mut() ,这两个方法都有副作用或是限制。

get_mut() 需要做一个“唯一引用”的检查,也就是没有任何的共享才能修改

//修改引用的变量 - get_mut 会返回一个Option对象
//但是需要注意,仅当(只有一个强引用 && 没有弱引用)为真才能修改
if let Some(val) = Rc::get_mut(&mut strong) {
    *val = 555;
}

make_mut() 则是会把当前的引用给clone出来,再也不共享了, 是一份全新的。

//此处可以修改,但是是以 clone 的方式,也就是让strong这个指针独立出来了。
*Rc::make_mut(&mut strong) = 555;

如果不这样做,就会出现很多内存不安全的情况。这些小细节一定要注意,不然你的代码怎么运作的你会一脸蒙逼的。

嗯,如果你想更快乐地使用智能指针,这里还有个选择 – CellRefCell,它们弥补了 Rust 所有权机制在灵活性上和某些场景下的不足。他们提供了 set()/get() 以及 borrow()/borrow_mut() 的方法,让你的程序更灵活,而不会被限制得死死的。参看下面的示例。

use std::cell::Cell;
use std::cell::RefCell

let x = Cell::new(1);
let y = &x; //引用(借用)
let z = &x; //引用(借用)
x.set(2); // 可以进行修改,x,y,z全都改了
y.set(3);
z.set(4);
println!("x={} y={} z={}", x.get(), y.get(), z.get());

let x = RefCell::new(vec![1,2,3,4]);
{
    println!("{:?}", *x.borrow())
}

{
    let mut my_ref = x.borrow_mut();
    my_ref.push(1);
}
println!("{:?}", *x.borrow());

通过上面的示例你可以看到你可以比较方便地更为正常的使用智能指针了。

线程与智能指针

前面,我们还有个问题没有解决,那就是——我想在多个线程中共享一个只读的数据,比如:一个很大的数组,我开多个线程进行并行统计。我们肯定不能对这个大数组进行clone,但也不能把这个大数组move到一个线程中。根据上述的智能指针的逻辑,我们可以通过智指指针来完成这个事,下面是一个例程:

const TOTAL_SIZE:usize = 100 * 1000; //数组长度
const NTHREAD:usize = 6; //线程数

let data : Vec<i32> = (1..(TOTAL_SIZE+1) as i32).collect(); //初始化一个数据从1到n数组
let arc_data = Arc::new(data); //data 的所有权转给了 ar_data
let result  = Arc::new(AtomicU64::new(0)); //收集结果的数组(原子操作)

let mut thread_handlers = vec![]; // 用于收集线程句柄

for i in 0..NTHREAD {
    // clone Arc 准备move到线程中,只增加引用计数,不会深拷贝内部数据
    let test_data = arc_data.clone(); 
    let res = result.clone(); 
    thread_handlers.push( 
        thread::spawn(move || {
            let id = i;
            //找到自己的分区
            let chunk_size = TOTAL_SIZE / NTHREAD + 1;
            let start = id * chunk_size;
            let end = std::cmp::min(start + chunk_size, TOTAL_SIZE);
            //进行求和运算
            let mut sum = 0;
            for  i in start..end  {
                sum += test_data[i];
            }
            //原子操作
            res.fetch_add(sum as u64, Ordering::SeqCst);
            println!("id={}, sum={}", id, sum );
        }
    ));
}
//等所有的线程执行完
for th in thread_handlers {
    th.join().expect("The sender thread panic!!!");
}
//输出结果
println!("result = {}",result.load(Ordering::SeqCst));

上面的这个例程,是用多线程的方式来并行计算一个大的数组的和,每个线程都会计算自己的那一部分。上面的代码中,

  • 需要向每个线程传入一个只读的数组,我们用Arc 智能指针把这个数组包了一层。
  • 需要向每个线程传入一个变量用于数据数据,我们用 Arc<AtomicU64> 包了一层。
  • 注意:Arc 所包的对象是不可变的,所以,如果要可变的,那要么用原子对象,或是用Mutex/Cell对象再包一层。

这一些都是为了要解决“线程的Move语义后还要共享问题”。

多态和运行时识别

通过Trait多态

多态是抽象和解耦的关键,所以,一个高级的语言是必需实现多态的。在C++中,多态是通过虚函数表来实现的(参看《C++的虚函数表》),Rust也很类似,不过,在编程范式上,更像Java的接口的方式。其通过借用于Erlang的Trait对象的方式来完成。参看下面的代码:

struct Rectangle {
    width : u32,
    height : u32,
} 

struct Circle {
    x : u32,
    y : u32,
    radius : u32,
}

trait  IShape  { 
    fn area(&self) -> f32;
    fn to_string(&self) -> String;
}

我们有两个类,一个是“长方形”,一个是“圆形”, 还有一个 IShape 的trait 对象(原谅我用了Java的命名方式),其中有两个方法:求面积的 area() 和 转字符串的 to_string()。下面相关的实现:

impl IShape  for Rectangle {
    fn area(&self) -> f32 { (self.height * self.width) as f32 }
    fn to_string(&self) ->String {
         format!("Rectangle -> width={} height={} area={}", 
                  self.width, self.height, self.area())
    }
}

use std::f64::consts::PI;
impl IShape  for Circle  {
    fn area(&self) -> f32 { (self.radius * self.radius) as f32 * PI as f32}
    fn to_string(&self) -> String {
        format!("Circle -> x={}, y={}, area={}", 
                 self.x, self.y, self.area())
    }
}

于是,我们就可以有下面的多态的使用方式了(我们使用独占的智能指针类 Box):

use std::vec::Vec;

let rect = Box::new( Rectangle { width: 4, height: 6});
let circle = Box::new( Circle { x: 0, y:0, radius: 5});
let mut v : Vec<Box> = Vec::new();
v.push(rect);
v.push(circle);

for i in v.iter() {
   println!("area={}", i.area() );
   println!("{}", i.to_string() );
}
向下转型

但是,在C++中,多态的类型是抽象类型,我们还想把其转成实际的具体类型,在C++中叫运行进实别RTTI,需要使用像 type_id 或是 dynamic_cast 这两个技术。在Rust中,转型是使用 ‘as‘ 关键字,然而,这是编译时识别,不是运行时。那么,在Rust中是怎么做呢?

嗯,这里需要使用 Rust 的 std::any::Any 这个东西,这个东西就可以使用 downcast_ref 这个东西来进行具体类型的转换。于是我们要对现有的代码进行改造。

首先,先得让 IShape 继承于 Any ,并增加一个 as_any() 的转型接口。

use std::any::Any;
trait  IShape : Any + 'static  {
    fn as_any(&self) -> &dyn Any; 
    …… …… …… 
}

然后,在具体类中实现这个接口:

impl IShape  for Rectangle {
    fn as_any(&self) -> &dyn Any { self }
    …… …… …… 
}
impl IShape  for Circle  {
    fn as_any(&self) -> &dyn Any { self }
    …… …… …… 
}

于是,我们就可以进行运行时的向下转型了:

let mut v : Vec<Box<dyn IShape>> = Vec::new();
v.push(rect);
v.push(circle);
for i in v.iter() {
    if let Some(s) = i.as_any().downcast_ref::<Rectangle>() {
        println!("downcast - Rectangle w={}, h={}", s.width, s.height);
    }else if let Some(s) = i.as_any().downcast_ref::<Circle>() {
        println!("downcast - Circle x={}, y={}, r={}", s.x, s.y, s.radius);
    }else{
        println!("invaild type");
    }
}

Trai 重载操作符

操作符重载对进行泛行编程是非常有帮助的,如果所有的对象都可以进行大于,小于,等于这亲的比较操作,那么就可以直接放到一个标准的数组排序的的算法中去了。在Rust中,在 std::ops 下有全载的操作符重载的Trait,在std::cmp 下则是比较操作的操作符。我们下面来看一个示例:

假如我们有一个“员工”对象,我们想要按员工的薪水排序,如果我们想要使用Vec::sort()方法,我们就需要实现这个对象的各种“比较”方法。这些方法在 std::cmp 内—— 其中有四个Trait : OrdPartialOrdEqPartialEq  。其中,Ord 依赖于 PartialOrdEq ,而Eq 依赖于 PartialEq,这意味着你需要实现所有的Trait,而Eq 这个Trait 是没有方法的,所以,其实现如下:

use std::cmp::{Ord, PartialOrd, PartialEq, Ordering};

#[derive(Debug)]
struct Employee {
    name : String,
    salary : i32,
}
impl Ord for Employee {
    fn cmp(&self, rhs: &Self) -> Ordering {
        self.salary.cmp(&rhs.salary)
    }
}
impl PartialOrd for Employee {
    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
        Some(self.cmp(rhs))
    }
}
impl Eq for Employee {
}
impl PartialEq for Employee {
    fn eq(&self, rhs: &Self) -> bool {
        self.salary == rhs.salary
    }
}

于是,我们就可以进行如下的操作了:

let mut v = vec![
    Employee {name : String::from("Bob"),     salary: 2048},
    Employee {name : String::from("Alice"),   salary: 3208},
    Employee {name : String::from("Tom"),     salary: 2359},
    Employee {name : String::from("Jack"),    salary: 4865},
    Employee {name : String::from("Marray"),  salary: 3743},
    Employee {name : String::from("Hao"),     salary: 2964},
    Employee {name : String::from("Chen"),    salary: 4197},
];

//用for-loop找出薪水最多的人
let mut e = &v[0];
for i in 0..v.len() {
    if *e < v[i] { 
        e = &v[i]; 
    }
}
println!("max = {:?}", e);

//使用标准的方法
println!("min = {:?}", v.iter().min().unwrap());
println!("max = {:?}", v.iter().max().unwrap());

//使用标准的排序方法
v.sort();
println!("{:?}", v);

小结

现在我们来小结一下:

  • 在Rust的中,最重要的概念就是“不可变”和“所有权”以及“Trait”这三个概念。
  • 在所有权概念上,Rust喜欢move所有权,如果需要借用则需要使用引用。
  • Move所有权会导致一些编程上的复杂度,尤其是需要同时move两个变量时。
  • 引用(借用)的问题是生命周期的问题,一些时候需要程序员来标注生命周期。
  • 在函数式的闭包和多线程下,这些所有权又出现了各种麻烦事。
  • 使用智能指针可以解决所有权和借用带来的复杂度,但带来其它的问题。
  • 最后介绍了Rust的Trait对象完成多态和函数重载的玩法。

Rust是一个比较严格的编程语言,它会严格检查你程序中的:

  • 变量是否是可变的
  • 变量的所有权是否被移走了
  • 引用的生命周期是否完整
  • 对象是否需要实现一些Trait

这些东西都会导致失去编译的灵活性,并在一些时候需要“去糖”,导致,你在使用Rust会有诸多的不适应,程序编译不过的挫败感也是令人沮丧的。在初学Rust的时候,我想自己写一个单向链接,结果,费尽心力,才得以完成。也就是说,如果你对Rust的概念认识的不完整,你完全写不出程序,那怕就是很简单的一段代码。我觉得,这种挺好的,逼着程序员必需了解所有的概念才能编码。但是,另一方面也表明了这门语言并不适合初学者。

没有银弹,任何语言都有些适合的地方和场景。

(全文完)


关注CoolShell微信公众账号和微信小程序

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——

陈皓 April 04, 2020 at 10:48PM
from 酷 壳 – CoolShell https://ift.tt/3dT197A

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 写在在家办公四周之时

几年前我曾经写过一点对于 “在家办公” 的思考,后来又写了一点,但是从来都没有想到过,长期的在家办公如今已经不是一个可选项,而是一个必选项了。

应该说,我从来都不是一个频繁在家办公的支持者,我是说,在家办公这样的互联网公司特有的 “福利” 当然是好的,但是 “频繁” 在家办公对于团队、项目,甚至个人职业成长等等各方面来说,都不是一件好事。我记得在刚加入亚马逊的时候,我听说亚马逊给了一位工程师这样一个 offer——允许一个月之内四分之三的时间远程办公。当时我觉得这件事情还是挺不可思议的,因为像曾经的 37signals 这样的小公司当然容易做到,但是长期和频繁地在家办公却不是大型互联网公司能玩得转的。

现在整个情况都发生变化了,由于新冠疫情,我们被迫在家办公,或者说,全公司绝大多数人都只能选择在家办公了,而且这件事情目前为止还似乎在漆黑的隧道里,还没有看到头。

在家办公的好处

虽然一般情况下,我更希望到公司去办公,而不是在家,但是不可否认在家办公是有很多好处的。

首先,在家办公会让自己更自由。开某些会的时候,可以躺在床上说话,一边说一边闭目休息(比如某些 1 on 1 沟通会);脖子酸了可以趴一会儿;家里有需要帮助和处理的事情也可以很方便地离开一会儿去处理。

其次,在家办公省掉了通勤的时间。不用考虑通勤的时间消耗,就意味着可以把闹铃设到一个更晚的时间,每天可以用于自己支配的时间更充裕。

最后,在家办公也能减少一些打扰。没有人来直接打扰你,这可以算一个原因,但这一条是有争议的,因为既然你在工作,你需要 “在线”,那么你的 Slack 很可能就不会消停……

在家办公的挑战

对于团队来说,面对面沟通和合作所带来的的凝聚力,是在家办公所无法带来的。想象一下,和你团队里的兄弟姐妹做一次 pair coding/review,或者是坐下来喝杯咖啡,再或者打局乒乓球,在 Happy Hour 时间聊一下。现在这些基本上都没有了,有的只有生硬和冷冰冰的一个又一个工作上的会议。

对于项目来说,地理位置上的密切合作,所带来的的沟通高效率,也是在家办公所无法带来的。现在大家似乎都慢慢习惯了对这些远程沟通工具的使用,比如 Zoom 电话会议,可是依然,很多会议还会面临着诸多远程沟通才会有的问题,比如会前调试设备,会中时不时会有杂七杂八的声音,会有人掉线。直接沟通无疑是最高效的,Zoom 这样的工具可以让沟通得以进行,但是看不到手势,看不到表情,连板书也不那么自然,还是损失了很多沟通的信息。

对个人职业发展来说,在家办公也失去了很多能力锻炼的机会。比方说,英语能力本来就不够强大的情况下,面对面的沟通可以化简掉很多的问题,可是电话沟通就会对听说能力要求直接上了一个很大的台阶,保证沟通中信息的传达变成了一件很有挑战性的事情。对我个人来说,已经在西雅图工作好几年了,因此这不算是一个大问题,但是我知道身边有很多初入职场的工程师,英文能力还较为生疏,沟通就更可能成为一个问题。

在家办公的一点技巧

接着聊一点我们可以做的,能够改善在家办公之弊端的措施。

硬件方面,显然,如今的在家办公不是一个 10 分钟的事情,也不是一个一两个钟头的事情,而是长时间,比方说,一天 7、8 个小时都需要持续发生的事情,是一个不能够轻易将就的事情。因此让自己在家办公时自己的身体尽量舒适就显得很有意义。对我来说,我不需要大的显示器,也不需要 laptop 有多高端的配置,但是,人体工学桌椅是很有帮助的,我可以坐一会,站一会。脖子不容易酸,也不容易疲劳。

环境方面,尽可能保证一个安静的房间,是一个很有助益的因素。除此以外,在家的诱惑太多,干扰太多,一个降噪耳机可能能够帮助排除干扰。我有时候也会捧着笔记本电脑,临时地挪到另外的一个更加安静的房间,去开完电话会议。

沟通的技巧方面,我觉得在重要的会议前,简单地罗列一些会议的安排和要点是非常有帮助的,这可能并非特定针对于在家办公的场景,但毫无疑问在家办公让其变得更为重要。开会的时候,有了这样的提纲,就可以专注于要解决的问题,而讨论的时候,也因为有了要点和上下文,效率更高。

最后,还是希望疫情快过去吧。在家呆得已经发霉了,以往生活中喜欢做的事情,比如旅行、打球,或者是看电影,似乎这些不管什么都无法正常进行了。Social distancing 已经让本来就在疏远的人际,越来越远了。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/2JqK1YQ

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【喵神】 使用 protocol 和 callAsFunction 改进 Delegate

2018 年 3 月的时候我写过一篇在 Swift 中如何改进 Delegate Pattern 的文章,主要思想是用遮蔽变量 (shadow variable) 声明的方式,来保证 self 变量可以被常时地标记为 weak。本文中,为了保证没有看过原文的读者能处在同一频道,我会先 (再次) 简单介绍一下这种方法。然后,结合 Swift 5.2 的新特性提出一些小的改进方式。

Delegate

简单说,为了避免繁琐老式的 protocol 定义和实现,我们可能更倾向于选择提供闭包的方式完成回调。比如在一个收集用户输入的自定义 view 中,提供一个外部可以设置的函数类型变量 onConfirmInput,并在合适的时候调用它:

class TextInputView: UIView {

    @IBOutlet weak var inputTextField: UITextField!
    var onConfirmInput: ((String?) -> Void)?

    @IBAction func confirmButtonPressed(_ sender: Any) {
        onConfirmInput?(inputTextField.text)
    }
}

TextInputView 的 controller 中,检测 input 确定事件就不需要一堆 textInputView.delegate = selftextInputView(_:didConfirmText:) 之类 的麻烦事了,可以直接设置 onConfirmInput

class ViewController: UIViewController {

    @IBOutlet weak var textLabel: UILabel!

    override func viewDidLoad() {
        super.viewDidLoad()
        let inputView = TextInputView(frame: /*...*/)
        inputView.onConfirmInput = { text in 
            self.textLabel.text = text
        }
        view.addSubview(inputView)
    }
}

但是这引入了一个 retain cycle!TextInputView.onConfirmInput 持有 self,而 self 通过 view 持有 TextInputView 这个 sub view,内存将会无法释放。

当然,解决方法也很简单,我们只需要在设置 onConfirmInput 的时候使用 [weak self] 来将闭包中的 self 换为弱引用即可:

inputView.onConfirmInput = { [weak self] text in
    self?.textLabel.text = text
}

这为使用 onConfirmInput 这样的闭包变量加上了一个前提:你大概率需要将 self 标记为 weak 以避免犯错,否则你将写出一个内存泄漏。这个泄漏无法在编译期间定位,运行时也不会有任何警告或者错误,这类问题也极易带到最终产品中。在开发界有一句话是真理:

如果一个问题可能发生,那么它必然会发生。

一个简单的 Delegate 类型可以解决这个问题:

class Delegate<Input, Output> {
    private var block: ((Input) -> Output?)?
    func delegate<T: AnyObject>(on target: T, block: ((T, Input) -> Output)?) {
        self.block = { [weak target] input in
            guard let target = target else { return nil }
            return block?(target, input)
        }
    }

    func call(_ input: Input) -> Output? {
        return block?(input)
    }
}

通过设置 block 时就将 target (通常是 self) 做 weak 化处理,并且在调用 block 时提供一个 weak 后的 target 的变量,就可以保证在调用侧不会意外地持有 target。举个例子,上面的 TextInputView 可以重写为:

class TextInputView: UIView {
    //...
    let onConfirmInput = Delegate<String?, Void>()
    
    @IBAction func confirmButtonPressed(_ sender: Any) {
        onConfirmInput.call(inputTextField.text)
    }
}

使用时,通过 delegate(on:) 完成订阅:

inputView.onConfirmInput.delegate(on: self) { (self, text) in
    self.textLabel.text = text
}

闭包的输入参数 (self, text) 和闭包 body self.textLabel.text 中的 self并不是原来的代表 controller 的 self,而是由 Delegateself 标为 weak 后的参数。因此,直接在闭包中使用这个遮蔽变量 self,也不会造成循环引用。

到这里为止的原始版本 Delegate 可以在这个 Gist 里找到,加上空行一共就 21 行代码。

问题和改进

上面的实现有三个小瑕疵,我们对它们进行一些分析和改进。

1. 更自然i的调用

现在,对 delegate 的调用时不如闭包变量那样自然,每次需要去使用 call(_:) 或者 call()。虽然不是什么大不了的事情,但是如果能直接使用类似 onConfirmInput(inputTextField.text) 的形式,会更简单。

Swift 5.2 中引入的 callAsFunction,它可以让我们直接以“调用实例”的方式 call 一个方法。使用起来很简单,只需要创建一个名称为 callAsFunction 的实例方法就可以了:

struct Adder {
    let value: Int
    func callAsFunction(_ input: Int) -> Int {
      return input + value
    }
}

let add2 = Adder(value: 2)
add2(1)
// 3

这个特性非常适合把 Delegate.call 简化,只需要加入对应的 callAsFunction 实现,并调用 block 就行了:

public class Delegate<Input, Output> {
    // ...
    
    func callAsFunction(_ input: Input) -> Output? {
        return block?(input)
    }
}

class TextInputView: UIView {
    @IBAction func confirmButtonPressed(_ sender: Any) {
        onConfirmInput(inputTextField.text)
    }
}

现在,onConfirmInput 的调用看起来就和一个闭包完全一样了。

类似于 callAsFunction 的直接在实例上调用方法的方式,在 Python 中有很多应用。在 Swift 语言中添加这个特性能让习惯于 Python 的开发者更容易地迁移到像是 Swift for TensorFlow 这样的项目。而这个提案的提出和审核相关人员,也基本是 Swift for TensorFlow 的成员。

2. 双层可选值

如果 Delegate<Input, Output> 中的 Output 是一个可选值的话,那么 call 之后的结果将会是双重可选的 Output??

let onReturnOptional = Delegate<Int, Int?>()
let value = onReturnOptional.call(1)
// value : Int??

这可以让我们区分出 block 没有被设置的情况和 Delegate 确实返回 nil 的情况:当 onReturnOptional.delegate(on:block:) 没有被调用过 (blocknil) 时,value 是简单的 nil。但如果 delegate 被设置了,但是闭包返回的是 nil 时,value 的值将为 .some(nil)。在实际使用上这很容易造成困惑,绝大多数情况下,我们希望把 .none.some(.none).some(.some(value)) 这样的返回值展平到单层 Optional.none.some(value)

要解决这个问题,可以对 Delegate 进行扩展,为那些 OutputOptional 情况提供重载的 call(_:) 实现。不过 Optional 是带有泛型参数的类型,所以我们没有办法写出像是
extension Delegate where Output == Optional 这样的条件扩展。一个“取巧”的方式是自定义一个新的 OptionalProtocol,让 extension 基于 where Output: OptionalProtocol 来做条件扩展:

public protocol OptionalProtocol {
    static var createNil: Self { get }
}

extension Optional : OptionalProtocol {
    public static var createNil: Optional<Wrapped> {
         return nil
    }
}

extension Delegate where Output: OptionalProtocol {
    public func call(_ input: Input) -> Output {
        if let result = block?(input) {
            return result
        } else {
            return .createNil
        }
    }
}

这样,即使 Output 为可选值,block?(input) 调用所得到的结果也可以经过 if let 解包,并返回单层的 result 或是 nil

3. 遮蔽失效

由于使用了遮蔽变量 self,在闭包中的 self 其实是这个遮蔽变量,而非原本的 self。这样要求我们比较小心,否则可能造成意外的循环引用。比如下面的例子:

inputView.onConfirmInput.delegate(on: self) { (_, text) in
    self.textLabel.text = text
}

上面的代码编译和使用都没有问题,但是由于我们把 (self, text) 换成了 (_, text),这导致闭包内部 self.textLabel.text 中的 self 直接参照了真正的 self,这是一个强引用,进而内存泄露。

这种错误和 [weak self] 声明一样,没有办法得到编译器的提示,所以也很难完全避免。也许一个可行方案是不要用 (self, text) 这样的隐式遮蔽,而是将参数名明确写成不一样的形式,比如 (weakSelf, text),然后在闭包中只使用 weakSelf。但这么做其实和 self 遮蔽差距不大,依然摆脱不了用“人为规定”来强制统一代码规则。当然,你也可以依靠使用 linter 和添加对应规则来提醒自己,但是这些方式也都不是非常理想。如果你有什么好的想法或者建议,十分欢迎交流和指教。

March 12, 2020 at 09:00AM via OneV’s Den https://ift.tt/2TGNAjC

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【酷壳】 与程序员相关的CPU缓存知识

好久没有写一些微观方面的文章了,今天写一篇关于CPU Cache相关的文章,这篇文章会讲述一些多核 CPU 的系统架构以及其原理,包括对程序性能上的影响,以及在进行并发编程的时候需要注意到的一些问题。这篇文章我会尽量地写简单和通俗易懂一些,主要是讲清楚相关的原理和问题,而对于一些细节和延伸阅读我会在文章最好给出相关的资源。

本文比较长,主要分成这么几个部分:基础知识、缓存的命中、缓存的一致性、相关的代码示例和延伸阅读。

因为无论你写什么样的代码都会交给CPU来执行,所以,如果你想写出性能比较高的代码,这篇文章中的技术还是应该认真学习的。

基础知识

首先,我们都知道现在的CPU多核技术,都会有几级缓存,老的CPU会有两级内存(L1和L2),新的CPU会有三级内存(L1,L2,L3 ),如下图所示:

其中:

  • L1缓分成两种,一种是指令缓存,一种是数据缓存。L2缓存和L3缓存不分指令和数据。
  • L1和L2缓存在第一个CPU核中,L3则是所有CPU核心共享的内存。
  • L1、L2、L3的越离CPU近就越小,速度也越快,越离CPU远,速度也越慢。

再往后面就是内存,内存的后面就是硬盘。我们来看一些他们的速度:

  • L1 的存取速度:
  • L2 的存取速度:
  • L3 的存取速度:
  • RAM内存的存取速度

我们可以看到,L1的速度是RAM的27倍,但是L1/L2的大小基本上也就是KB级别的,L3会是MB级别的。例如:Intel Core i7-8700K ,是一个6核的CPU,每核上的L1是64KB(数据和指令各32KB),L2 是 256K,L3有12MB(我的苹果电脑是 Intel Core i9-8950HK,和Core i7-8700K的Cache大小一样)。

于是我们的数据就从内存向上,先到L3,再到L2,再到L1,最后到寄存器进行CPU计算。为什么会设计成三层?这里有下面几个方面的考虑:

  • 一个方面是物理速度,如果你要更在的容量就需要更多的晶体管,除了芯片的体积会变大,更重要的是大量的晶体管会导致速度下降,因为访问速度和要访问的晶体管的位置成反比,也就是当信号路径变长时,通信速度会变慢。这部分是物理问题。
  • 另外一个问题是,多核技术中,数据的状态需要在多个CPU中进行同步,并且,我们可以看到,cache和RAM的速度差距太大,所以,多级不同尺寸的缓存有利于提高整体的性能。

这个世界永远是平衡的,一面变得有多光鲜,另一面也会变得有多黑暗。建立这么多级的缓存,一定就会引入其它的问题,这里有两个比较重要的问题,

  • 一个是比较简单的缓存的命中率的问题。
  • 另一个是比较复杂的缓存更新的一致性问题。

尤其是第二个问题,在多核技术下,这就很像分布式的系统了,要对多个地方进行更新。

缓存的命中

在说明这两个问题之前。我们需要要解一个术语 Cache Line。缓存基本上来说就是把后面的数据加载到离自己进的地方,对于CPU来说,它是不会一个字节一个字节的加载的,因为这非常没有效率,一般来说都是要一块一块的加载的,在CPU的缓存技术中,这个术语叫“Cache Line”(有的中文编译成“缓存线”),一般来说,一个主流的CPU的Cache Line 是 64 Bytes(也有的CPU用32Bytes和128Bytes),也就是16个32位的整型。也就是说,CPU从内存中捞数据上来的最小数据单位。

比如:Cache Line是最小单位(64Bytes),所以先把Cache分布多个Cache Line,比如:L1有32KB,那么,32KB/64B = 500 个 Cache Line。

一方面,缓存需要把内存里的数据放到放进来,英文叫 CPU Associativity。Cache的数据放置的策略决定了内存中的数据块会拷贝到CPU Cache中的哪个位置,因为Cache的大小远远小于内存,所以,需要有一种地址关联的算法,能够让内存中的数据可以被映射到cache中来。这个有点像内存管理的方法。

基本上来说,我们会有如下的一些方法。

  • 一种方法是,任何一个内存地址的数据可以被缓存在任何一个Cache Line里,这种方法是最灵活的,但是,如果我们要知道一个内存是否存在于Cache中,我们就需要进行O(n)复杂度的Cache遍历,这是很没有效率的。
  • 另一种方法,为了降低缓存搜索算法,我们需要使用像Hash Table这样的数据结构,最简单的hash table就是做“求模运算”,比如:我们的L1 Cache有500个Cache Line,那么,公式:`(内存地址 mod 500)x 64` 就可以直接找到所在的Cache地址的偏移了。但是,这样的方式需要我们的程序对内存地址的访问要非常地平均,这成了一种非常理想的情况了。
  • 为了避免上述的两种方案的问题,于是就要容忍一定的hash冲突,也就出现了 N-Way 关联。也就是把连续的N个Cache Line绑成一组,然后,先把找到相关的组,然后再在这个组内找到相关的Cache Line。

那么,Cache的命中率会成为程序运行性能非常关键的事,所以,了解上面的这些东西,会有利于我们知道在什么情况下有可以导致缓存的失效。

对于 N-Way 关联我们取个例子,并多说一些细节(因为后面会用到),Intel 大多数处理器的L1 Cache都是32KB,8-Way 组相联,Cache Line 是64 Bytes。于是,

  • 32KB的可以分成,32KB / 64 = 512 条 Cache Line。
  • 因为有8 Way,于是会每一Way 有 512 / 8 = 64 条 Cache Line。
  • 于是每一路就有 64 x 64 = 4096 Byts 的内存。

为了方便索引内存地址,

  • Tag:每条 Cache Line 前都会有一个独立分配的 24 bits来存的 tag,其就是内存地址的前24bits
  • Index:内存地址后续的6个bits则是在这一Way的是Cache Line 索引,2^6 = 64 刚好可以索引64条Cache Line
  • Offset:再往后的6bits用于表示在Cache Line 里的偏移量

如下图所示:(更多的细节可以读一下《Cache: a place for concealment and safekeeping》)

(图片来自《Cache: a place for concealment and safekeeping》)

这意味着:

  • L1 Cache 可映射 36bits 的内存地址,一共 2^36 = 64GB的内存
  • 因为只要头24bits相同就会被映射到同一个Way中,所以,每4096个地址会放在一Way中。
  • 当CPU要访问一个内存的时候,通过这个内存的前24bits 和中间的6bits可以直接定位相应的Cache Line。

此外,当有数据没有命中缓存的时候,CPU就会以最小为Cache Line的单元向内存更新数据。当然,CPU并不一定只是更新64Bytes,因为访问主存是在是太慢了,所以,一般都会多更新一些。好的CPU会有一些预测的技术,如果找到一种pattern的话,就会预先加载更多的内存,包括指令也可以预加载。这叫 Prefetching 技术 (参看,Wikipedia 的 Cache Prefetching纽约州立大学的 Memory Prefetching)。比如,你在for-loop访问一个连续的数组,你的步长是一个固定的数,内存就可以做到prefetching。(注:指令也是以预加载的方式执行,参看本站的《代码执行的效率》中的第三个示例)

缓存的一致性

对于主流的CPU来说,缓存的写操作基本上是两种策略(参看本站《缓存更新的套路》),

  • 一种是Write Back,写操作只要在cache上,然后再flush到内存上。
  • 一种是Write Through,写操作同时写到cache和内存上。

为了提高写的性能,一般来说,主流的CPU(如:Intel Core i7/i9)采用的是Write Back的策略,因为直接写内存实在是太慢了。

好了,现在问题来了,如果有一个数据 x 在 CPU 第0核的缓存上被更新了,那么其它CPU核上对于这个数据 x 的值也要被更新,这就是缓存一致性的问题。(当然,对于我们上层的程序我们不用关心CPU多个核的缓存是怎么同步的,这对上层都是透明的)

一般来说,在CPU硬件上,会有两种方法来解决这个问题。

  • Directory 协议。这种方法的典型实现是要设计一个集中式控制器,它是主存储器控制器的一部分。其中有一个目录存储在主存储器中,其中包含有关各种本地缓存内容的全局状态信息。当单个CPU Cache 发出读写请求时,这个集中式控制器会检查并发出必要的命令,以在主存和CPU Cache之间或在CPU Cache自身之间进行数据同步和传输。
  • Snoopy 协议。这种协议更像是一种数据通知的总线型的技术。CPU Cache通过这个协议可以识别其它Cache上的数据状态。如果有数据共享的话,可以通过广播机制将共享数据的状态通知给其它CPU Cache。这个协议要求每个CPU Cache 都可以“窥探”数据事件的通知并做出相应的反应。

因为Directory协议是一个中心式的,会有性能瓶颈,而且会增加整体设计的复杂度。而Snoopy协议更像是微服务+消息通讯,所以,现在基本都是使用Snoopy的总线的设计。

这里,我想多写一些细节,因为这种微观的东西,不自然就就会更分布式系统相关联,在分布式系统中我们一般用Paxos/Raft这样的分布式一致性的算法。而在CPU的微观世界里,则不必使用这样的算法,原因是因为CPU的多个核的硬件不必考虑网络会断会延迟的问题。所以,CPU的多核心缓存间的同步的核心就是要管理好数据的状态就好了。

这里介绍几个状态协议,先从最简单的开始,MESI协议,这个协议跟那个著名的足球运动员梅西没什么关系,其主要表示缓存数据有四个状态:Modified(已修改), Exclusive(独占的),Shared(共享的),Invalid(无效的)。

这些状态的状态机如下所示:

下面是个示例(如果你想看一下动画演示的话,这里有一个网页(MESI Interactive Animations),你可以进行交互操作,这个动画演示中使用的Write Through算法):

当前操作 CPU0 CPU1 Memory 说明
1) CPU0 read(x)  x=1 (E) x=1 只有一个CPU有 x 变量,
所以,状态是 Exclusive
2) CPU1 read(x)  x=1 (S) x=1(S) x=1 有两个CPU都读取 x 变量,
所以状态变成 Shared
3) CPU0 write(x,9)  x=9 (M) x=1(I) x=1 变量改变,在CPU0中状态
变成 Modified,在CPU1中
状态变成 Invalid
4) 变量 x 写回内存  x=9 (M) X=1(I) x=9 目前的状态不变
5) CPU1  read(x)  x=9 (S) x=9(S) x=9 变量同步到所有的Cache中,
状态回到Shared

 

MESI 这种协议在数据更新后,会标记其它共享的CPU缓存的数据拷贝为Invalid状态,然后当其它CPU再次read的时候,就会出现 cache misses 的问题,此时再从内存中更新数据。可见,从内存中更新数据意味着20倍速度的降低。我们能不直接从我隔壁的CPU缓存中更新?是的,这就可以增加很多速度了,但是状态控制也就变麻烦了。还需要多来一个状态:Owner(宿主),用于标记,我是更新数据的源。于是,现了 MOESI 协议

MOESI协议的状态机和演示我就不贴了,我们只需要理解MOESI协议允许 CPU Cache 间同步数据,于是也降低了对内存的操作,性能是非常大的提升,但是控制逻辑也非常复杂。

顺便说一下,与 MOESI 协议类似的一个协议是 MESIF,其中的 F 是 Forward,同样是把更新过的数据转发给别的 CPU Cache 但是,MOESI 中的 Owner 状态 和MESIF 中的 Forward 状态有一个非常大的不一样—— Owner状态下的数据是dirty的,还没有写回内存,Forward状态下的数据是clean的,可以丢弃而不用另行通知。

需要说明的是,AMD用MOESI,Intel用MESIF。所以,F 状态主要是针对 CPU L3 Cache 设计的(前面我们说过,L3是所有CPU核心共享的)。(相关的比较可以参看StackOverlow上这个问题的答案

程序性能

了解了我们上面的这些东西后,我们来看一下对于程序的影响。

示例一

首先,假设我们有一个64M长的数组,设想一下下面的两个循环:

const int LEN = 64*1024*1024;
int *arr = new int[LEN];

for (int i = 0; i < LEN; i += 2) arr[i] *= i;

for (int i = 0; i < LEN; i += 8) arr[i] *= i;

按我们的想法来看,第二个循环要比第一个循环少4倍的计算量,其应该也是要快4倍的。但实际跑下来并不是,在我的机器上,第一个循环需要127毫秒,第二个循环则需要121毫秒,相差无几。这里最主要的原因就是 Cache Line,因为CPU会以一个Cache Line 64Bytes最小时单位加载,也就是16个32bits的整型,所以,无论你步长是2还是8,都差不多。而后面的乘法其实是不耗CPU时间的。

示例二

我们再来看一个与缓存命中率有关的代码,我们以一定的步长increment 来访问一个连续的数组。

for (int i = 0; i < 10000000; i++) {
    for (int j = 0; j < size; j += increment) {
        memory[j] += j;
    }
}

我们测试一下,在下表中, 表头是步长,也就是每次跳多少个整数,而纵向是这个数组可以跳几次(你可以理解为要几条Cache Line),于是表中的任何一项代表了这个数组有多少,而且步长是多少。比如:横轴是 512,纵轴是4,意思是,这个数组有 4*512 = 2048 个长度,访问时按512步长访问,也就是访问其中的这几项:[0, 512, 1024, 1536] 这四项。

表中同的项是,是循环1000万次的时间,单位是“微秒”(除以1000后是毫秒)

| count |   1    |   16  |  512  | 1024  |
------------------------------------------
|     1 |  17539 | 16726 | 15143 | 14477 |
|     2 |  15420 | 14648 | 13552 | 13343 |
|     3 |  14716 | 14463 | 15086 | 17509 |
|     4 |  18976 | 18829 | 18961 | 21645 |
|     5 |  23693 | 23436 | 74349 | 29796 |
|     6 |  23264 | 23707 | 27005 | 44103 |
|     7 |  28574 | 28979 | 33169 | 58759 |
|     8 |  33155 | 34405 | 39339 | 65182 |
|     9 |  37088 | 37788 | 49863 |156745 |
|    10 |  41543 | 42103 | 58533 |215278 |
|    11 |  47638 | 50329 | 66620 |335603 |
|    12 |  49759 | 51228 | 75087 |305075 |
|    13 |  53938 | 53924 | 77790 |366879 |
|    14 |  58422 | 59565 | 90501 |466368 |
|    15 |  62161 | 64129 | 90814 |525780 |
|    16 |  67061 | 66663 | 98734 |440558 |
|    17 |  71132 | 69753 |171203 |506631 |
|    18 |  74102 | 73130 |293947 |550920 |

我们可以看到,从[9,1024] 以后,时间显注上升。包括[17,512] 和 [18,512] 也显注上升。这是因为,我机器的 L1 Cache 是 32KB, 8 Way 的,前面说过,8 Way的一个组有64个Cache Line,也就是4096个字节,而1024个整型正好是 4096 Bytes,所以,一旦过了这个界,每个步长都无法命中 L1 Cache,每次都是 Cache Miss,所以,导致访问时间一下子就上升了。而 [16, 512]也是一样的,其中的几步开始导致L1 Cache开始失效。

示例三

接下来,我们再来看个示例。下面是一个二维数组的两种遍历方式,一个逐行遍历,一个是逐列遍历,这两种方式在理论上来说,寻址和计算量都是一样的,执行时间应该也是一样的。

const int row = 1024;
const int col = 512
int matrix[row][col];

//逐行遍历
int sum_row=0;
for(int r=0; r<row; r++) {
    for(int c=0; c<col; c++){
        sum_row += matrix[r];
    }
}

//逐列遍历
int sum_col=0;
for(int c=0; c<col; c++) {
    for(int r=0; r<row; r++){
        sum_col += matrix[r];
    }
}

然而,并不是,在我的机器上,得到下面的结果。

  • 逐行遍历:0.081ms
  • 逐列遍历:1.069ms

执行时间有十几倍的差距。其中的原因,就是逐列遍历对于CPU Cache 的运作方式并不友好,所以,付出巨大的代价。

示例四

接下来,我们来看一下多核下的性能问题,参看如下的代码。两个线程在操作一个数组的两个不同的元素(无需加锁),线程循环1000万次,做加法操作。在下面的代码中,我高亮了一行,就是p2指针,要么是p[1],或是 p[18],理论上来说,无论访问哪两个数组元素,都应该是一样的执行时间。

void fn (int* data) {
    for(int i = 0; i < 10*1024*1024; ++i)
        *data += rand();
}

int p[32];

int *p1 = &p[0];
int *p2 = &p[1]; // int *p2 = &p[30];

thread t1(fn, p1);
thread t2(fn, p2);

然而,并不是,在我的机器上执行下来的结果是:

  • 对于 p[0]p[1] :560ms
  • 对于 p[0]p[30]:104ms

这是因为 p[0]p[1] 在同一条 Cache Line 上,而 p[0]p[30] 则不可能在同一条Cache Line 上 ,CPU的缓冲最小的更新单位是Cache Line,所以,这导致虽然两个线程在写不同的数据,但是因为这两个数据在同一条Cache Line上,就会导致缓存需要不断进在两个CPU的L1/L2中进行同步,从而导致了5倍的时间差异

示例五

接下来,我们再来看一下另外一段代码:我们想统计一下一个数组中的奇数个数,但是这个数组太大了,我们希望可以用多线程来完成,这个统计。下面的代码中,我们为每一个线程传入一个 id ,然后通过这个 id 来完成对应数组段的统计任务。这样可以加快整个处理速度。

int total_size = 16 * 1024 * 1024; //数组长度
int* test_data = new test_data[total_size]; //数组
int nthread = 6; //线程数(因为我的机器是6核的)
int result[nthread]; //收集结果的数组

void thread_func (int id) {
    result[id] = 0;
    int chunk_size = total_size / nthread + 1;
    int start = id * chunk_size;
    int end = min(start + chunk_size, total_size);

    for ( int i = start; i < end; ++i ) {
        if (test_data[i] % 2 != 0 ) ++result[id];
    }
}

然而,在执行过程中,你会发现,6个线程居然跑不过1个线程。因为根据上面的例子你知道 result[] 这个数组中的数据在一个Cache Line中,所以,所有的线程都会对这个 Cache Line 进行写操作,导致所有的线程都在不断地重新同步 result[] 所在的 Cache Line,所以,导致 6 个线程还跑不过一个线程的结果。这叫 False Sharing。

优化也很简单,使用一个线程内的变量。

void thread_func (int id) {
    result[id] = 0; 
    int chunk_size = total_size / nthread + 1;
    int start = id * chunk_size;
    int end = min(start + chunk_size, total_size);

    int c = 0; //使用临时变量,没有cache line的同步了
    for ( int i = start; i < end; ++i ) {
        if (test_data[i] % 2 != 0 ) ++c;
    }
    result[id] = c;
}

我们把两个程序分别在 1 到 32 个线程上跑一下,得出的结果画一张图如下所示:

上图中,我们可以看到,灰色的曲线就是第一种方法,橙色的就是第二种(用局部变量的)方法。当只有一个线程的时候,两个方法相当,而且第二种方法还略差一点,但是在线程数增加的时候的时候,你会发现,第二种方法的性能提高的非常快。直到到达6个线程的时候,开始变得稳定(前面说过,我的CPU是6核的)。而第一种方法无论加多少线程也没有办法超过第二种方法。因为第一种方法不是CPU Cache 友好的。

篇幅问题,示例就写到这里,相关的代码参看我的Github相关仓库

延伸阅读

(全文完)


关注CoolShell微信公众账号和微信小程序

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——

陈皓 March 02, 2020 at 03:43AM
from 酷 壳 – CoolShell https://ift.tt/2VAUecw

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月15日典范条目

1879S Morgan Dollar NGC MS67plus Reverse.png

摩根銀元美國鑄幣局於1878至1904年間生產的一種1美元硬幣,之後還在1921年再度投產。國會通過《1873年鑄幣法案》為自由鑄造銀幣運動劃上句點,坐姿自由女神銀元因此停產,摩根銀元則是此後美國發行的第一種標準銀元。硬幣由鑄幣局助理雕刻師喬治·T·摩根設計並以他命名,其正面刻有自由女神肖像,背面則刻有展開翅膀的老鷹,爪子上還抓有箭和橄欖枝。國會於1876年秋通過布蘭德-阿利森法,授權發行新銀元,並要求財政部每個月按市場價購買200至400萬美元白銀並打造成銀幣。1890年,國會又通過謝爾曼收購白銀法,其中把財政部每個月要購買的白銀量大幅提升到14萬公斤,但在銀元生產上則只要求鑄幣局再繼續一年。這一法案之後在1893年廢除。1898年,國會通過新法案,要求之前根據謝爾曼收購白銀法買下的所有銀錠都要打造成銀元,鑄幣局於是繼續生產到1904年才把庫存的銀錠用完,摩根銀元也暫時停產。1918年通過的皮特曼法案授權將數以百萬計的銀元熔解後再重新鑄造,摩根銀元於是又在1921年再次投產,同年末,新設計的和平銀元面世,摩根銀元的設計正式退出歷史舞台。

February 15, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2vx1vza

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月14日典范条目

Tropical Storm Edouard 2002.jpg

2002年热带风暴爱德华2002年大西洋飓风季的第五个热带风暴。爱德华于9月1日从佛罗里达州以东的一片对流区和冷锋发展成热带气旋,在弱转向气流的影响下,系统向北漂移并沿顺时针路径循环向西移动。虽然有中等到较强风切变的不利影响,风暴还是在9月3日达到风速每小时约100公里的最高强度,但又在接下来向西行进的过程中快速减弱。9月5日,爱德华在佛罗里达州东北部实现登陆,并在穿越该州后于9月6日消散,其残留被热带风暴费伊的环流吸收。热带风暴爱德华给佛罗里达州带去了中等程度降水,其中该州西部降雨量超过175毫米。虽然登陆时系统仍有热带风暴强度,但其在陆地上行进时的风速很小。此外虽有多条道路被雨水淹没,但此次风暴没有造成人员伤亡,总体破坏也很小。

February 14, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2vxnaXQ

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月13日典范条目

Florida counties map.png

美國佛羅里達州一共有67個,於1821年成為美國領土時只有兩個郡,即以薩瓦尼河(Suwanee River)為界,西部為艾斯康比亞郡,東部為聖約翰斯郡,後來成立的其它所有郡都曾是這兩個郡的一部分。佛羅里達於1845年成為美國的第27個,1925年由阿拉楚阿郡析置的吉爾克里斯特郡是全州最年輕的郡。佛羅里達州的郡是州政府的分支。1968年,各郡獲得了自行發放特許狀的權力。除了瓦古拉郡郡城克勞福德維爾外,佛羅里達州的其他所有郡城都是註冊成立的自治市

February 13, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2OLug1O

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

【四火】 技术面试中,什么样的问题才是好问题?

其实很久以前就想谈一谈这个话题了,但是最近才有了足够的动机。因为从最近参加的很多 debrief 来看,我认为身边大多数的软件工程师面试中,在通过技术问题来考察候选人这方面,很多都做得不够好。比方说,我看到对于一些经验丰富的软件工程师候选人的面试,一些面试官依然是草率地扔出一道算法题让做了事,并且认为能不能够比较清晰完整地将代码写出来,是工程师级别裁定的最重要的标准。而这样的做法我认为是非常不妥的。

首先,我要明确的是,这个问题,指的是技术面试中俗称的 “主要问题”,具体来说,就是面试官会拿出一个问题和候选人讨论,并通过由此开始双方的互相沟通和问题发散来达到考察的目的,因此,这个 “问题”,从某种角度说,更像一个 “话题”。这个过程通常在每轮面试中会持续几十分钟(如果你对这种面试方式感兴趣,你可以看一下这个简单的介绍)。下面的讨论,都是建立在这种面试风格和方式之上的。

其次,作为一个 disclaimer,我想说,以下内容来自于我的认识,并且是针对于技术面试这一个狭窄范围内的认识,自然带有主观的倾向性和认知的局限性,它并不是来自任何公司或组织的标准。

好,下面我就来尝试把这个问题讲清楚、讲透彻。我认为这并不是一件容易的事情,因此如果你对其有不同的看法,欢迎和我一起讨论。

典型案例

我先来举这样一个典型的例子,这里面包含了若干个值得商榷的方面,你可以看看是不是似曾相识:

在和候选人谈论完项目和经历以后,面试还有 40 分钟,于是面试官问:你能否实现一个 LRU 队列?

于是候选人想了一下,就开始做题了,也就是在白板上大写特写,于是面试官也就开始忙自己的事儿了。等到 40 分钟后,候选人写了一白板,但是显然,他在这过程中遇到了一些困难,最后虽然实现了,但是代码写得有些复杂,也遗漏了两、三个重要的 corner case。

于是面试之后,面试官在评语中写道,“候选人能力一般,算法题实现起来磕磕绊绊,最后的代码偏臃肿,而且有明显的 bug”。

在往下阅读以前,请你想一想,这样的面试形式有哪些值得商榷的地方?

技术面试的目的

好,我先卖个关子,先不回答上面的问题,而是先谈一谈,对于软件工程师候选人来说,我们为什么要进行这样的技术面试。事实上,有很多考察项,完全不需要技术面试这样麻烦的途径,就可以很容易、很高效地实现;而下面我说的这些方面,这些对于软件工程师来说至关重要的方面,技术面试却是合理考察的唯一可行途径。

技术能力方面

通常不同轮次的面试,会考察不同的技术点,这个对于不同的团队和职位,是不一样的。

举例来说,对于某业务平台团队的一个高级工程师的职位,五轮面试中,一轮考察项目和经验,一轮考察系统设计,两轮考察具体问题的解决,特别包括算法和数据结构,还有一轮考察面向对象设计等其它内容,这其中,后三轮都包括白板编码的考察。

对于一个有经验的工程师候选人来说,我认为这就是一个比较立体、综合,也是一种比较合理的技术考察点的划分方式。并且,这五轮中有四轮都会花费大量的时间,通过我今天将谈到的技术问题,来对候选人进行技术能力方面的评估。这里,有这样几个非常常见的技术方面的考察项:

  1. 分析问题,整理需求的能力。问题在一开始可能很模糊,但是优秀的且有经验的工程师可以识别出核心的诉求来,这个 “识别” 的能力,下文我还会详述。这里的诉求可能有多个,但是考虑到时间的关系,面试过程中往往只会从某个角度覆盖其中一两个。
  2. 根据需求来设计系统的能力。这里既包括功能性需求,又包括非功能性需求,前者是必须要涉及到的,但是后者也经常也放在一起考量。其实这一点可大可小,它未必一定指系统设计中,功能是否得到实现,并且这个过程中,可能会涉及到系统的扩展性、可用性、一致性等等方面。
  3. 将核心逻辑实现的能力。如今,考察比重容易被高估的算法和数据结构就大体上属于这一部分。它也有功能和非功能的两个角度——功能上算法能否实现需求,非功能上算法是否具备足够的性能,编码是否遵循最佳实践,代码是否具备良好的可扩展性等等。而编码能力,指的是在思路达成一致以后,核心逻辑能不能落到纸面(代码)上。毕竟,“空谈误国,实战兴邦”。
  4. 经验和其它工程能力。这部分相对更为灵活。比如对测试能力的考察,即可以做怎样的测试来实现对于功能需求和非功能需求正确性的保证。对于特定的团队和项目来说,有时候会特别专注于特定的技术能力,比如前端的团队,是需要考察前端的基础技能的。

考虑到时间和覆盖面、覆盖深度的权衡,上面这四点有时候不能在一轮面试中完全覆盖,往往也会包括三点。比如,系统设计的面试可以着重覆盖 1、2、4 点,而编码为主的面试可以着重覆盖 1、3、4 点。

非技术能力方面

和技术能力考察所不同的是,非技术能力考察在不同面试官中的特异性更大,换言之,每个人的角度和标准都可能不相同。但我觉得下面这几条是特别重要,因而必须要覆盖到的:

  1. 沟通合作的能力。如果不计时间成本,最理想的面试是什么?其实就是一起工作。工作中才会有足够多必要的沟通,无论是正面的品质还是负面的问题都会无所遁形。可是面试的时间有限,我们没有办法实现真正的工作氛围,但依然可以模拟工作中一起考察、分析和解决问题的过程,而这个过程,就是要通过 “沟通” 串起来的。沟通是一个大的话题,具体的考察项有很多,比如,能不能接受建议?能不能讨论想法?有些候选人一旦进入自己的思考模式就听不进别的话了,于是一个点要反复强调几遍;而有的则是缺少 backbone,稍微追问一下,也不思考,就立马改变主意。
  2. 热情和兴趣。热情和兴趣的影响是巨大的,都说兴趣是最好的老师,这部分是很难 “教出来” 的。对于初级工程师来说更是如此。热情和兴趣不但会影响到他/她自己的未来发展,也会影响到整个团队的氛围。
  3. 学习能力。学习能力很大程度决定了候选人在新的岗位上进步的潜力。同样的基础和基本的问题解决能力,有的候选人能够 “一点就透”,触类旁通,这在一定程度上就反映了学习的能力。毫无疑问,软件工程师每天都在面对新问题,入职以后就会发现,不止问题是新的,代码是新的,类库是新的,工具是新的,在成熟到能够有一定产出之前,这一步一定是学习。

技术能力和非技术能力,哪个更占主导?事实上,这二者都很重要,并且二者各自又具备不同的特点。当然相对来说,非技术能力更加难以提高,因而这方面的问题要更加引起重视。比方说,要让一个对于软件领域缺乏热情和兴趣的候选人,在入职以后改头换面,是几乎不可能的一件事情。

其它方面

上面说的是技术面试中对于 “能力” 的考察。其实,还有一些考察项,严格来说并不能算是 “能力”,因此我就没有归类在上面,也不是本文的重点,但这并不是说它们不重要。

比如,候选人是否具备正直的品格。在 OCI,debrief 的结果,通常有 hire 和 no hire 两种,但是有一种情况,可以归结到一个特殊的 “never hire” 里面去,这样的候选人没有面试冷冻期,不会有职位和级别的讨论,就是一个 “永不考虑” 聘用——这就是品格问题。品格问题会导致 never hire 的出现,比如候选人对当前的所在职位说谎了。

再比如,和团队的契合程度。不同的团队,接纳候选人的程度和要求都是不一样的。一个典型的例子是,有时候我们发现,有的候选人在投票的边界线上,即本身是具备相当的潜力的,但是由于相对缺乏领域经验,且某些方面显示出方法明显不得要领。如果团队中有成熟、有经验的工程师可以带着,且团队有一定的空间允许他花更长的时间学习和成长,那么最后的结论就是 hire,否则就是 no hire。你也可以看出,很多时候这样的决定都不是非黑即白的,影响的因素是多方面的。

再再比如,性格不兼容导致的风险。我遇到过一例,候选人在面试过程中,在多轮面试中都表现出高傲和自满的个性来。于是这成为了一个担心招聘进来以后,风险过高的重要方面。于是最后我们放弃了这个候选人,尽管这个候选人的技术方面是没有问题的。有人可能会说,聪明人都是有个性的。但其实 “有个性” 和 “难相处” 却有着微妙的差别,而且再包容的团队,也有自己的底线。我们当然不希望错过优秀的人才,但是这并不是不计代价的。

从这几个方面也能看出,这些 “非能力” 的考察项,往往具备着或 0 或 1 的 “red flag” 的特点。面试官一般不会花心思在这部分的考察上,但如果发现这方面的问题,且经过了明确。那结果往往就会是一个明确的否决票,而这个否决票是和级别、职位无关的。

回看那个案例

讲完了技术面试的目的,再来回看那个案例。那个案例中,所记叙的面试过程,对于技术面试的技术能力和非技术能力的考察,是否有覆盖呢?我们不妨一条一条看吧:

技术能力方面:

  1. 分析问题,整理需求的能力。这一条考察的程度明显是不够的,给出的问题,是一个明确的、具体的算法题,也就是要实现一个 LRU 队列。也许这其中存在着问题分析和需求整理的空间,但对于具体算法题来说,这个空间显然并不大,而且候选人闷头就写了,这方面无从考察。对于一个初级工程师的面试来说可能还好一些,我通常没有微词;可对于一个要去面试一个经验丰富的工程师,我是很不赞成纯算法题面试的,而这就是其中的一个重要原因。
  2. 根据需求来设计系统的能力。这一点的覆盖基本为 0。上来就写代码了,不清楚思考的过程,也更谈不上什么系统设计了。
  3. 将核心逻辑实现的能力。这条确实是这种面试方式能够覆盖的部分,因为整个过程,就是候选人思考并编码实现的过程,只不过,面试官能得到的只有一个 “结果”,而非整个 “过程”。这样的数据,能反映出来在核心逻辑实现方面的价值,就要大打折扣了。
  4. 经验和其它工程能力。也许能够从代码的实现上获知一部分,但这一条考察的程度也显然是很不够的。

再来看非技术能力方面:

  1. 沟通合作的能力。这是最大的问题,因为这方面是远远不足的,整个过程没有沟通,没有合作,只有默默地做题。
  2. 热情和兴趣。这个过程很难从这个角度获取足够的候选人在热情和兴趣方面展示出来的信息。
  3. 学习能力。同上。

也就是说,除了 “将核心逻辑实现的能力” 可能还勉强过得去,这样的面试方式,并无法全面、合理地考察候选人作为软件工程师的综合素质。

事实上,如果你联想实际工作。如果你的团队中有这样一个工程师,拿到一句简单的需求,不确认问题,不沟通设计,不讨论方案,直接就开始埋头苦干,就算能写出可以工作的代码来,这是不是依然是一件无比恐怖的事情?显然,我们的面试要尽可能避免这样的事情在真实世界中发生。我们要找的是软件工程师,不是只会刷题编码者。

这也是我把这个案例,放在开头,作为反面案例的原因之一。

等等,“之一”!难道还有别的原因?

是的,这还没完,这个案例还有着其它弊端,我想再卖个关子——而现在,你可以想一想,再往下看。

怎样的问题才是 “好” 问题?

终于要正面回答标题中的问题了,到底怎样的问题才能真正称得上 “好” 问题呢?下面是我认为最重要的几条衡量标准。

从模糊到清晰

首先,这个问题在一开始要足够模糊,以便让候选人可以逐层递进,逐步细化,寻根究底。这个过程,其实就是将 “具体问题” 经过分析、归纳、思考、抽象并将其映射成为一个 “软件问题” 的过程。在问题变得清晰的过程中,理想的情况是,候选人可以表现出主动性,即候选人可以在多数情况下引领讨论的思路,而不是面试官。面试官需要顺着候选人的思路,逐步框定下问题的讨论范畴,并明确到其核心实现是确实可以用软件的办法实现的。

在这样的状态下,候选人可以以自然的状态,具备相当自由度地发挥自己的能力。从这个过程中,可以观察得到太多候选人的不同角度的特质了。通过这种方式,也可以很大程度避免了已经知道 “标准答案” 的面试官,由于思路的局限性,而给面试施加的源自于主观偏好的影响。

这就好像是开放世界的 RPG 游戏,有多个不同的路径都可以完成任务,玩家可以决策并决定主角的走向,但是这一切始终还要在游戏设计者的掌控之内。这当然是说的理想状态,有时候会有偏差,但我们朝着这个方向努力。这也对面试官驾驭不同的状况有着很高的要求,毕竟,面试官要对这个问题前前后后足够的熟悉,以便应对各种不同的细化场景。有一个常见的方式,是可以从一个自己已经足够熟悉的问题开始,比如自己曾经多年工作涉及的某类系统。

我来举一个具体例子。比如,有这样一个问题:

怎样设计一个流量控制系统?

这就是一个模糊到没法再模糊的问题了。不知你会不会产生下面这样的问题:

  • 什么系统需要流量控制?
  • 现在的流量是多少?
  • 需要支持到什么时间精度?
  • 流量控制的规则怎么定义?
  • 超过流量的请求怎么处理?
  • ……

其实,这些都或多或少是需要面试官和候选人一起逐步思考、分析和明确的。在这个过程中,可以考察的内容太多太多了。

事实上,针对不同程度的候选人,上述这个问题给出的最原始的模糊程度是不一样的,问题越是模糊,这部分对于候选人的要求也就越高。对于一个工作十多年的,有着多年系统设计经验的工程师来说,上面这些问题大致都应该是他/她能够主动提问,或是主动引领明确的。

值得一提的是,理想的问题最好还有一些隐藏的 “坑”,能否把这些坑识别出来,也是对于工程能力方面,一个很好的小的考察点。比方说,优秀的候选人应该想到,流量控制可以基于绝对时间窗口,或是相对时间窗口来进行的,但是要真正保护系统,相对时间窗口才是最理想的。当然在实现难度上,相对时间窗口,往往会更难一些。

而对于一个没有工作经验,并将要研究生毕业的候选人来说,问这样一个模糊的问题,往往带来了过大的难度,不但不容易推进面试的进程,还可能给候选人带来沮丧的心理。我们不希望看到,候选人拿到问题以后就懵了,如果发现候选人推进有困难,面试官需要介入并帮助。

因此根据候选人的程度,这需要面试官主动回答这些问题,或是直接缩小或明确问题的范畴,当这个问题的范畴缩到最小时,这可以是一个直接存在多种解法的算法题。极端地说,这个问题可以一直缩小到这样的程度:

假定说有这样一个 API,名字叫做 isAllowed,这个 API 在系统每次收到请求的时候就调用,传入的是请求对象,传出 boolean 值表示是否允许这次调用——如果最近一分钟内调用次数小于 10000 次就允许,反之则不允许。你能否将这个 API 实现出来?

如果候选人还一脸迷茫,可以提供这样的参考 API:

class RateLimiter {
    public boolean isAllowed(Request req) {
        // TODO
    }
}

你看,这只是一个将问题明确、细化和分解的过程,并没有涉及到实际实现代码该用的算法。但是,上面提的那些问题,要么都通过这个例子明确了,要么都给出具体数字了,这本身,就将一个模糊的问题,降低难度明确为一个具体的算法问题了。

不止一个解

前面一步已经谈到了有不同的方式可将模糊的 “实际问题” 映射到了一个可解的 “软件问题”,那么现在,这个 “软件问题” 依然没有标准答案。可能有几个参考答案,它们互相比较起来各有优劣。大多数情况下,候选人的思路,都在这几个参考答案的思路之中,但有时也能看到特立独行的新奇思路。

如同前一步所说的那样,对于不同级别的软件工程师职位来说,需求分析、系统设计等等这些方面的要求可能有着很大的差别;但是在这一步,对于数据结构和算法这样的基础能力,却是接近的。

对于这里谈到的流量控的算法来说,实现方式是有很多种的,代码复杂程度,控制精度,时间复杂度和空间复杂度等等都有着非常大的区别。当然此时涉及到的,已经基本只是算法层面的话题了,就算法本身而言,我在极客时间专栏中对其中的几个典型方法做了一些介绍,感兴趣的话可以阅读。

我可以再举一个我曾经经常在面试中拿来使用的例子:

某社交网站有两百万的注册用户,每个用户都有积分属性,且积分根据用户在社交网站上的行为而不断有小幅度的频繁变更(比如登陆一次就+1 分,评论一次就+2 分等等),怎样设计一种算法,能够高效、准确地实时获取指定用户在所有用户中基于积分的排名?

上面的问题从模糊逐步落实到实现上的时候,异步、定时地排序,是最容易想到的方案,而题目表述中的 “高效” 和 “实时” 这两个修饰词让这个问题变得困难。这个过程中,我见到的不错的办法就至少有七、八种,比方说,下面这个推进问题解决的例子:

  1. 候选人:在需要的时候进行排序,方案是……
  2. 面试官:好,这样的方式下,时间、空间复杂度是多少?
  3. 候选人:……(说着说着自己意识到时间消耗可能巨大)
  4. 面试官:对,不仅时间、空间都消耗巨大,CPU 也是,你能否优化?
  5. 候选人:……(提出了一些优化思路,但是他自己对它们的实时性也不满意)
  6. 面试官:好,有换个角度更进一步优化的方式吗?
  7. 候选人:对了,可以让数据一直是排好序的!
  8. 面试官:好主意,那你怎么设计数据结构呢?
  9. 候选人:我可以使用一个 map 来保存用户 id 到积分的映射,再把积分从小到大按序放在数组中,这样二分查找就可以找到对应积分所处的排名。
  10. 面试官:听起来不错,那么这时候获取排名的复杂度是多少?
  11. 候选人:……
  12. 面试官:对,每当用户的积分小幅变化的时候,你怎么维持这个数组依然有序?
  13. 候选人:从数组中拿掉一个老的积分,再放入一个新的积分……
  14. 面试官:这个变更影响的数据量有多少,时间复杂度又是如何?
  15. 候选人:……
  16. 面试官:不错,可这个方法有什么问题吗?
  17. 候选人:(恍然大悟)如果新添加一个用户,新的积分会出现在数组头部,数组内的所有数据都要向后移动一个单位!
  18. 面试官:没错,那你打算怎么优化?
  19. 候选人:可以把数组内的积分从大到小排序,这样新添加的用户所对应的积分总在尾部。
  20. 面试官:很好,这个方法还有什么问题吗?
  21. 候选人:……(意识到在某些情况下,有很多用户拥有相同的积分,这时时间复杂度会退化)
  22. 面试官:那样的话,你怎么优化?
  23. 候选人:数组的元素除了记录当前积分,还记录有多少个用户具有这个积分,从而消除相同积分的重复元素……
  24. 面试官:很好,可这个方法会带来一个问题,你能想到吗?
  25. 候选人:对了,如果积分变化以后,新的积分是没有出现过的,那么添加到数组里,就是一个新元素,于是所有比它小的积分全部都要向后移动一个单位。
  26. 面试官:非常好,那么你怎么优化?
  27. 候选人:如果使用链表来代替数组就可以避免这个问题,(突然意识到)可是链表我就没法二分查找了……
  28. 面试官:没错,那什么样的数据结构和链表在这方面具有一定相似性,又能够具备二分查找相似的时间复杂度?
  29. 候选人:……(这一步能回答出来答案就很多了,很多都是很不错的思路,比如有用跳表的,有用二叉搜索树的等等)

这只是一个简化了的片段,实际的沟通的内容远比这部分内容多,但是从中也依然可以管中窥豹,看出问题解决的过程是怎样逐步推进的。

从这里也可以看出,无论是从实际问题细化到软件问题,还是求解这个软件问题,都存在着多条通往罗马的道路,看起来很美好,但这样的问题设计和面试把控并不容易。但既然大家都是软件工程师,是未来有可能一起工作的工程师,面试官的能力和可能就和候选人接近,于是,为了保证面试的效果,就一定要精心准备这样的问题,而不能指望随机和临场想出来一个 “好” 的问题提问。

围绕问题的解决要完整

这个问题的分析、讨论和解答过程要完整。对,其实这一点说的已经不是问题本身了,而是攻克这个问题的过程了。

这指的是整个过程要努力让候选人能够抵达 “踮踮脚能够到” 的难度,并且能够完成从确认、分析、讨论、编码、验证和改进等一个过程。这让整个面试显得完整,同时带来了这样两大好处:

  • 对于面试官来讲,这样一个完整的过程,可以更全面地考察候选人,避免陷入视角过窄和一叶障目的情境。同时,“踮踮脚能够到” 的难度,又可以给整个考察的进程具备较为合理的预期。
  • 对于候选人来讲,心态可以得到一定程度的平复,不沮丧,能够 “完整地” 面试完一轮,能够收获信心。别忘了,面试是双向的,给候选人一个良好的印象是很重要的。

前文我举的这个将问题从模糊到逐步清晰化的这个例子,就是一个需要面试官根据候选人情况动态调整的例子。在候选人能够经过思考而快速推进问题解决进展的时候,要让出主动权,以被动回答和鼓励为主;但在候选人卡壳的时候,要夺回主动权,及时给出提示和引导。

在落到数据结构和算法上面的时候,极少有候选人能够在叙述思路的时候直接给出最优解的。这时候,如果时间充裕,特别是在候选人进展非常顺利的时候,可以不断提示、追问以要求 “代码前优化”,一步一步优化到他/她的问题解决的能力边界,这就是其中的一个探寻其 “踮踮脚能够到” 的这个问题的解决能力的一个办法。但这个过程的前提,是一定要给编码留足时间。当然,如果候选人不能在限定时间内给出清晰的优化后思路,那不妨就退一步到原先那个算法角度不那么 “好”,但是思路清晰的解法上,并落实到代码。

比方说,对于前文所述的那个流量控制的问题,候选人在还有半个小时的时候就想到了使用一个时间复杂度为 O(N) 的解,而面试官认为时间还比较充裕,那就可以尝试挑战一下候选人 “能否再优化一下复杂度?”。

有些时候,由于前面的过程磕磕绊绊,时间剩下不多了,依然只有时间复杂度较高的 brute force 的解法,那么将这个解法实现了,其实也是一个不错的选择。有时候时间实在比较紧张,可以要求实现一部分核心代码,这些都比由于时间太短而代码写了一半匆匆收尾要好得多。我的经验是,在讨论充分,思路清晰的情况下,代码完成的时间,一般只需要 10 到 15 分钟,这样的代码量对于面试来说是比较合理的。

当然,相较而言,一种更为糟糕的结果是,一直到最后,讨论的深度依然离编码尚远,甚至依然停留在一个很高的泛泛而谈的层面。

如果在编码完成之后,尚有时间,优秀的候选人会拿实际的例子去验证代码的正确性。而面试官也可以和候选人讨论 “代码后优化”,比如以下的问题:

  • 你能否进一步优化算法以提高时间/空间复杂度?
  • 如果是工业级别的代码,你觉得代码还有哪些问题?
  • 你该怎样去设计测试,来保证这段代码的正确性 ?

对考察项的覆盖兼有深度和广度

这个问题要能够考察前文所述的技术能力和非技术能力。

这里说的覆盖,不一定要全部覆盖,但是要覆盖其中的大部分,并且对于每一个考察项要具备一定的考察深度。我见到过不少其它的面试风格,但我认为这样就着一个模糊的主要问题(话题)逐步展开的方式是最好的。因为它可以兼具广度和深度的平衡。具体来说:

面试很容易走向的一个极端就是考虑广度,但缺乏深度。比如一种风格是绝大部分的面试时间用来询问候选人的项目和经验,让候选人自己介绍,而面试官跟进追问。这原本是一种很好的方式,但是由于候选人对自己的项目通常远比面试官熟悉得多,除非明确的同一领域,否则面试官较难对于其中的内容挖掘到足够的深度,从而识别出候选人是真正做事的人,还是夸夸其谈的人。这也是这种方式理论可行,但实际开展难度较大的原因之一。

另一个极端,自然就是考虑深度,但缺乏广度。比如给出一个过于具体的问题,缺乏发挥和迂回的空间,对这个问题所涉及的很小一部分深度挖掘,甚至纠缠于某个特殊而单一的 case 很长时间,但是却只能覆盖很少的考察角度。

由于深度和广度都是可控的,那么这样的可以拿来问不同经验和不同技术背景的工程师候选人。这样对于面试官来说,可以获得足够的数据,便于在遇到新的候选人的时候,能够进行横向比较,做出更准确的评估。比方说,过去某级别的候选人能够在面对这个问题的时候,能够达到什么样的级别,而如今这个候选人有着类似表现,这就可以以过去的那个例子来作为参考比较了。

“不好” 的问题

现在,让我们再次回到文章开头那个例子问题,除了已经提到的考察项的覆盖不够,它还有哪些问题呢?参考上文已经提到了 “好” 问题的标准,我觉得其中的这样两条是违背的:

从模糊到清晰。显然,问题给出的时候就已经相对比较清晰了,这样的方式并不能模拟软件工程师日常面对的许多模糊而困难的实际问题。我已经提到,对于经验丰富的候选人来说,这样的问题无法重现将实际问题映射到软件问题这样的一个重要思考过程。

另一个是,围绕问题的解决要完整。示例问题的考察过程中,只有缺乏互动的编码环节,没有其它过程,没有编码前的分析、思考和优化,也没有编码后的测试、改进和优化。考虑到 LRU 完整算法是一个实现代码量偏大的问题,拿来放到面试中做一个完整实现,由于会消耗过多的时间,挤压其它时间,因此显得有些过了。

其它 “不好” 的问题

前面说了过于清晰的纯算法题的 “不好” 之处,也说了 “好” 问题的例子,最后我想再来说几类其它的且典型的 “不好” 的例子。

依赖于语言或框架

而这里说的依赖不好,是因为考虑到候选人不同的技术背景,如果没有特殊的需要,避免这样的依赖,以避免产生不应有的错误的衡量数据。

比方说,问一个关于 JVM 的问题,这个问题可以问,特别是在候选人强调其具备一定 Java 背景的前提下。但是这样的问题不能成为 “主菜”,尤其是候选人不一定具备很强的 Java 背景,这样的方式会导致考察的偏颇。

过于复杂的规则或背景知识

这主要是基于面试的有限时间考虑的,过于复杂的规则或背景知识,容易把时间消耗到澄清它们上面;另外,有些背景知识并非是所有人都熟知的,这就会引起考察标准的非预期。我给一个经典的反面例子:

设计一个算法,把一个小于一百万的正整数,使用罗马数字来表示。

这个问题描述简洁,但是拿来做技术面试中的主要问题,其中一个不妥之处就是,不是所有人都很清楚一百万内的罗马数字表示法的。对于不清楚的人来说,要搞清楚这个表示法的规则,就已经是一件有些复杂和耗时的事情了。显然,这个罗马数字表示法的知识点,不应该成为考察和衡量的标准。

当然,有时候有些问题的背景知识是冷门的,但是表述简洁,那么这样的话只要 面试官能够主动、迅速地说清楚,拿来使用是没问题的。

知识性问题

我想特别谈一谈,对于知识性问题的提问。在讨论问题的过程中,如果涉及到关联的具体知识,那么提问一些基础知识是一个不错的选择,这是考察候选人 CS 基础是否牢靠的方式。比如候选人提到使用 HashMap,而他/她最熟悉的编程语言是 C++,那么询问在 C++中 HashMap 是怎样实现的就是一个可行的问题。而且,由于这样的问题是嵌套在前述的这个大流量控制问题的解决过程中的,更显得自然而不突兀。

反之,如果这样的知识性问题较为冷门或浅表,和当前的讨论中的问题无关,或是不在候选人的知识体系内,这样的问题就值得商榷了。比如,仅仅因为自己的项目组使用 Spring,面试官就询问候选人 Spring 的 bean 的单例和多例分别是怎样配置的,而恰巧候选人又是 C++背景,对于这部分并不熟悉,这样的问题除了给候选人造成困扰以外,意义就不太大了。

如果把知识性问题作为主要问题来提问,我认为是不适合的。因为一方面它不具备普适性,另一方面它又具备太强的随机性。

这里不具备普适性这一条,指的是不同技术背景的软件工程师候选人都要能够适合参与这个问题的解答。举例来说,如果问 “Tomcat 的线程池的配置策略?”,这就是一个不具备普适性的问题,这是一个偏重 “知识性” 的问题,如果候选人没有使用过 Tomcat,或是只是略有了解,很可能就栽了。

而具备太强的随机性这一条,指的是一旦待考察的问题具体以后,这个问题就容易从对 “能力” 的考察变成了对 “知识” 的考察,而这个知识,又恰恰是比较容易随机的。也就是说,我们不希望候选人 “恰巧” 知道或不知道某一个细小的知识点,来决定他/她是否通过这项考察。

无论如何,知识性的问题作为考察的辅助方式可以,但不应成为主角。我还是觉得我们应当能把更多的时间,留给主要问题的解决过程本身。

关于 “技术面试中,什么样的问题才是好问题?”,我就说这么多吧。也欢迎你分享你的看法,我们一起讨论。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

via 四火的唠叨 https://ift.tt/38fQVuV

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月12日典范条目

PatNixon.jpg

塞尔玛·凯瑟琳·“帕特”·瑞安·尼克松第37任美国总统理查德·尼克松的妻子,于1969至1974年间担任第一夫人。帕特·尼克松生于内华达州伊利。1940年,她嫁给了当时还是律师的理查德·尼克松。在1968年美国总统选举成为第一夫人后,帕特·尼克松推动了包括志愿服务在内的多项慈善活动。她陪同丈夫一起出访中华人民共和国苏联,而独立出访非洲和南美洲更带来了“夫人大使”的声誉。她还是第一位进入过战斗区域的第一夫人。这些访问为她赢得了媒体和受访国的好评。她担任第一夫人直到丈夫因水门事件而于1974年辞职时为止。在之后的生活中,她与丈夫回到加利福尼亚州,之后搬到新泽西州。1976年和1983年,她出现了两次中风。1992年,她被诊断出患有肺癌,于1993年逝世,享年81岁。

February 12, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2UUL0Yz

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月11日典范条目

Governorates of Lebanon.svg

黎巴嫩的行政區劃共有三級,其中省屬於第一級行政區劃,而縣和市鎮則分別作為與第二級行政區劃與第三級行政區劃。黎巴嫩各省由總督管治,而各省總督由黎巴嫩部長會議任命。根據《2003年7月16日第522號法令》,阿卡省與巴勒貝克-希爾米勒省分別從北黎巴嫩省和貝卡省析出,使黎巴嫩管轄的省份的數目由6個增加至8個。在黎巴嫩的8個省中,除作為首都的貝魯特省不轄縣、阿卡省僅轄一個縣(阿卡縣)外,所有省均下轄多於一個縣,而下轄縣數量最多的省為北黎巴嫩省黎巴嫩山省,均轄6個縣。在黎巴嫩的8個省中,除貝魯特省不轄市鎮外,所有省均有下轄市鎮,而下轄市鎮數量最多的省為黎巴嫩山省,轄326個市鎮。在黎巴嫩的8個省中,人口最少的是阿卡省,人口僅有281,843人,而人口最多的是黎巴嫩山省,人口達1,101,817人;面積最小的是貝魯特省,面積僅19.8平方公里,而面積最大的是巴勒貝克-希爾米勒省,面積3,009平方公里;人口密度最低的是巴勒貝克-希爾米勒省,平均每一平方公里僅有人口121.473人,而人口密度最高的是貝魯特省,平均每一平方公里有人口36,947.879人。

February 11, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/38rLn0F

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月10日典范条目

1878 three-dollar piece obverse.jpg

3美元金币美国铸币局于1854至1889年间生产的一种金币,由该局首席雕刻师詹姆斯·B·朗埃克设计,1853年2月21日获得授权。硬币正面刻有头戴美洲原住民公主头饰的自由女神头像,背面的中间是面值和年份,周围有玉米小麦棉花烟草组成的花环。部分来源认为,这种金币是为了方便人们大量购买邮票。朗埃克在设计金币时想了多种办法确保新币和2.5美元金币有显著区别,不但采用的坯饼更薄,而且设计图案也是别具一格。金币投产后的第一年就出产了超过10万枚,但其流通程度非常有限。虽然美国西岸部分地区不接受纸币,只能使用金币和银币,但东部的情况截然不同,特别是在经济内战爆发而陷入动荡后,3美元金币基本上在东部的商品交易中难得一见,并且此后再也没有出现过大范围流通。3美元金币于1889年停产,国会再在次年中止其发行授权。这种硬币存在多种年份版本,其中许多的铸造量都很少,但最为罕见的品种还是旧金山铸币局1870年打造的1870-S版,确认存在的仅有一枚。

February 10, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/37bFFhT

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月9日典范条目

Tropical Cyclone 01B 2003.jpg

2003年5月,一场正式名称为“第一号特强气旋风暴鲍勃”的热带气旋斯里兰卡引发56年来最严重的洪涝灾害。系统于5月10日在孟加拉湾上空发展形成,是2003年北印度洋气旋季的首场风暴。由于外界环境有利,系统在向西北方向移动的过程中稳步加强。于5月13日达到持续风速每小时140公里的最高强度,气旋在孟加拉湾中部上空向北飘移,因风切变增多而逐渐减弱。风暴转向东进,于5月16日退化成强烈低气压,然后蜿蜒向东北方向移动并重新增强成气旋风暴。系统从缅甸西部登岸,于次日在陆地上空消散。气旋在孟加拉湾中部基本停止前进期间给斯里兰卡西南部带去倾盆大雨,引发的洪灾和山体滑坡导致2万4750户民宅被毁,另有3万2426套受到一定程度破坏,致使约80万人无家可归。风暴一共造成260人死亡,经济损失约1亿3500万美元。气旋还令印度的安达曼-尼科巴群岛及该国孟加拉湾沿岸地区降下小雨。除此以外,风暴把水分推离印度大陆,可能因此引发旷日持久的热浪,夺走1400人的生命,缅甸也出现暴雨。

February 09, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2Ssudcs

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月8日典范条目

源於公元一世紀或二世紀的安息帝國陶製人面噴水器

安息帝國古波斯地區主要的政治及文化勢力。由阿爾沙克一世建立。全盛時期的安息帝國疆域北達今土耳其東南的幼發拉底河,東抵伊朗。安息帝國座落在地中海羅馬帝國與中國漢朝之間的貿易路線絲綢之路之上,使帝國成為了商貿中心。法爾斯伊什塔克爾的統治者阿爾達希爾一世叛變,在公元224年殺害了安息帝國最後一位統治者阿爾達班五世。阿爾達希爾一世建立了薩珊王朝,不過安息帝國的分支阿薩息斯王朝則仍在亞美尼亞繼續其統治。安息帝國是一個由不同文化組成的國家,她在很大程度上吸納了包括波斯文化希臘文化及地區文化的藝術、建築、宗教信仰及皇室標記。

February 08, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/374Ilhj

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share

维基百科2020年2月7日典范条目

MMI Chapel.jpg

马里昂军事学院于1842年在美國阿拉巴马州马里昂市創校,在该国仅有的4所军事初级学院中历史最为悠久。马里昂军事学院是南方院校协会的成员之一,有“美国伊顿”之称,曾被评为卓越荣誉军事学校、最佳军事初级学院、阿拉巴马州校友收入最高的社区学院等。马里昂的军校学员团绰号猛虎营。自建校一百余年以来,包括一位美利坚联盟国准将在内的美军各个军种共有超过200名将军毕业于该校。1916年,马里昂军事学院成为了首批引进美国陆军陆军预备军官训练团的学校之一。大约在同一时期,又开设了联邦军校的预备课程。二战时期,学校从仅有的两栋建筑逐步扩建至今日之规模。1968年,美国陆军提前授衔计划进入了马里昂军事学院。2006年,马里昂转型为州立,并成为了阿拉巴马州法定的官方军校。马里昂军事学院的校园經相关机构认证为阿拉巴马州历史地标。校内有两处国家史迹名录,分别是军校礼拜堂和拉夫雷斯楼和校长官邸。此外,阿拉巴马军事名人堂也位于校内。马里昂军事学院每年都会以主要游行队伍的身份参加美国历史最悠久的老兵节庆祝活动——伯明翰老兵节游行。

February 07, 2020 at 08:00AM
from 维基百科典范条目供稿 https://ift.tt/2SnXULI

VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)
VN:F [1.9.22_1171]
Rating: 0 (from 0 votes)
Share