My note

本周，Facebook 将一个非常大的 pull request 合并到了 React 主分支。这个 PR 将 React 当前使用的构建工具替换成了 Rollup。这让许多人感到不解，纷纷在推特上提问：“为什么你们选择 Rollup 而不选择 Webpack 呢？”_{1 2 3}

有人问这个问题是很正常的。Webpack 是现在 JavaScript 社区中最伟大的成功传奇之一，它有着数百万/月的下载量，驱动了成千上万的网站与应用。它有着巨大的生态系统、众多的贡献者，并且它与一般的社区开源项目不同——它有着意义非凡的经济支持。

相比之下，Rollup 是那么的微不足道。但是，除了 React 之外，Vue、Ember、Preact、D3、Three.js、Moment 等众多知名项目都使用了 Rollup。为什么会这样呢？为什么这些项目不使用大家一致认可的 JavaScript 模块打包工具呢？

这两个打包工具的优缺点

Webpack 由 Tobias Koppers 在 2012 年创建，用于解决当时的工具不能处理的问题：构建复杂的单页应用（SPA）。尤其是它的两个特点改变了一切：

1. 代码分割可以将你的 app 分割成许多个容易管理的分块，这些分块能够在用户使用你的 app 时按需加载。这意味着你的用户可以有更快的交互体验。因为访问那些没有使用代码分割的应用时，必须要等待整个应用都被下载并解析完成。当然，你也可以自己手动去进行代码分割，但是……总之，祝你好运。
2. 静态资源的导入：图片、CSS 等静态资源可以直接导入到你的 app 中，就和其它的模块、节点一样能够进行依赖管理。因此，我们再也不用小心翼翼地将各个静态文件放在特定的文件夹中，然后再去用脚本给文件 URL 加上哈希串了。Webpack 已经帮你完成了这一切。

而 Rollup 的开发理念则不同：它利用 ES2015 模块的巧妙设计，尽可能高效地构建精简且易分发的 JavaScript 库。而其它的模块打包器（包括 Webpack在内）都是通过将模块分别封装进函数中，然将这些函数通过能在浏览器中实现的 require 方法打包，最后依次处理这些函数。在你需要实现按需加载的时候，这种做法非常的方便，但是这样做引入了很多无关代码，比较浪费资源。当你有很多模块要打包的时候，这种情况会变得更糟糕。

ES2015 模块则启用了一种不同的实现方法，Rollup 用的也就是这种方法。所有代码都将被放置在同一个地方，并且会在一起进行处理。因此得到的最终代码相较而言会更加的精简，运行起来自然也就更快。你可以点击这儿亲自试试 Rollup 交互式解释器（REPL）。

但这儿也存在一些需要权衡的点：代码分割是一个很棘手的问题，而 Rollup 并不能做到这一点。同样的，Rollup 也不支持模块热替换（HMR）。而且对于打算使用 Rollup 的人来说，还有一个最大的痛点：它通过插件处理大多数 CommonJS 文件的时候，一些代码将无法被翻译为 ES2015。而与之相反，你可以把这一切的事全部放心交给 Webpack 去处理。

那么我到底应该选用哪一个呢？

到目前为止，我们已经清晰地了解了这两个工具共存并且相互支撑的原因 — 它们应用于不同的场景。那么，现在这个问题的答案简单来说就是：

在开发应用时使用 Webpack，开发库时使用 Rollup

当然这不是什么严格的规定——有很多的网站和 app 一样是使用 Rollup 构建的，同时也有很多的库使用 Webpack。不过，这是个很值得参考的经验之谈。

如果你需要进行代码分割，或者你有很多的静态资源，再或者你做的东西深度依赖 CommonJS，毫无疑问 Webpack 是你的最佳选择。如果你的代码基于 ES2015 模块编写，并且你做的东西是准备给他人使用的，你或许可以考虑使用 Rollup。

对于包作者的建议：请使用 pkg.module！

在很长一段时间里，使用 JavaScript 库是一件有点风险的事，因为这意味着你必须和库的作者在模块系统上的意见保持一致。如果你使用 Browserify 而他更喜欢 AMD，你就不得不在 build 之前先强行将两者粘起来。通用模块定义（UMD）格式对这个问题进行了 部分 的修复，但是它没有强制要求在任何场景下都使用它，因此你无法预料你将会遇到什么坑。

ES2015 改变了这一切，因为 import 与 export 就是语言规范本身的一部分。在未来，不再会有现在这种模棱两可的情况，所有东西都将更加无缝地配合工作。不幸的是，由于大多数浏览器和 Node 还不支持 import 和 export，我们仍然需要依靠 UMD 规范（如果你只写 Node 的话也可以用 CommonJS）。

现在给你的库的 package.json 文件增加一个 "module": "dist/my-library.es.js" 入口，可以让你的库同时支持 UMD 与 ES2015。这很重要，因为 Webpack 和 Rollup 都使用了 pkg.module 来尽可能的生成效率更高的代码——在一些情况下，它们都能使用 tree-shake 来精简掉你的库中未使用的部分。

了解更多有关 pkg.module 的内容请访问 Rollup wiki 。

希望这篇文章能让你理清这两个开源项目之间的关系。如果你还有问题，可以在推特联系rich_harris、rollupjs、thelarkinn。祝你打包快乐！

感谢 Rich Harris 写了这篇文章。我们坚信开源协作是共同促进 web 技术前进的重要动力。

没有时间为开源项目做贡献？想要以其它方式回馈吗？欢迎通过 Open Collective 进行捐赠，成为 Webpack 的支持者或赞助商。Open Collective 不仅会资助核心团队，而且还会资助那些贡献出空闲时间帮助我们改进项目的贡献者们。

发布于掘金 https://juejin.im/post/58edb865570c350057f199a7

使用模块化系统设计原则来避免微服务的复杂性。

从单体式应用向微服务架构迁移已经是老生常谈的话题了。除了过过嘴瘾，似乎真的动手将单体式应用拆分成微服务也不是什么很困难的事。但是这种做法真的是你们团队的最佳选择吗？维护一个凌乱的单体式应用的确很伤脑筋，但是还有另一种优秀但常常被人忽视的替代方案：模块化应用开发。本文将探讨这种替代方案，并展现其与构建微服务的关系。

模块化微服务

“通过微服务，我们终于能够让团队独立工作了”或者“我们的单体式应用实在太复杂了，它降低了我们的工作效率”之类的话，只是让团队改用微服务架构的诸多原因中的一小部分；还有一种说法是需要可拓展性与弹性。所有开发人员似乎都渴望系统设计和开发的模块化。软件开发中的模块化可以总结为以下三个原则：

• 强大的封装性：隐藏了各个组件内部实现的细节，减少了不同组件之间的耦合性。团队可以在系统的各个非耦合部分中独立地工作。
• 定义良好的接口：你不可能隐藏组件内的所有东西（否则你的系统将毫无意义），因此有必要在组件之间定义良好且可靠的 API。任意一个组件都可以被符合接口规范的其它组件替换。
• 显式依赖：模块化系统意味着不同的组件需要在一起工作。因此你最好能有一种途径来表达（与验证）它们之间关系。

这些原则都可以用微服务架构来实现。只要做到对其它服务暴露定义明确的接口（通常是一个 REST API），就能以任意方式来实现一个微服务。它的实现细节是这个服务内部的事情，你可以改变这些实现细节而不影响整个系统。微服务之间的依赖关系通常在开发时是不明确的，这可能会导致在运行时服务编排失败。只能说在大多数微服务架构中，实现最后一条模块化原则还需要再接再厉。

因此，微服务架构实现了重要的模块化原则，并带来了以下三点实实在在的好处：

• 团队能够独立地工作与扩张。
• 微服务小巧、专一，降低了复杂度。
• 服务可以在不会影响全局的情况下内部进行更改或者替换。

那么微服务架构的缺点是什么呢？当你从一个单体式（虽然有点臃肿）应用切换成微服务分布式系统的时候，给表操作带来了巨大的复杂性。突然间，你发现你要不断地部署各种不同的（可能是由容器包装的）服务。这时，服务发现、分布式日志记录、跟踪等新的问题出现了。现在，你更加容易出现分布式计算的谬论造成的错误。接口的版本管理与配置管理成为你面对的主要问题。各种问题将数不胜数向你涌来。

事实证明，由于所有的微服务个体都需要联合起来实现业务逻辑，微服务之间的连接将变得无比复杂。看到这里，你应该意识到不能简单地将单体式应用拆分成微服务了。单体式应用中的“意大利面条式代码”问题重重，在其中再加上网络边界会将这些纠缠在一起的问题升级成彻头彻尾的痛苦。

• 译注：什么是意大利面式代码

模块化的替代方案

这是否意味着我们要么沉没在混乱的单体式应用中，要么淹没在令人抓狂的微服务复杂性中呢？其实，模块化也可以通过其它方式实现。在开发时最重要的是正确地规划项目边界并实施方案，我们也可以通过创建一个结构良好的单体式应用来实现这一点。当然，这意味着我们将尽可能利用编程语言与开发工具的协助来实现模块化原则。

例如在 Java 中，有几个可以帮助你构建应用的模块系统。OSGi 是其中最著名的一个，不过随着 Java 9 的发布，Java 平台将加入一个原生的模块系统。现在模块作为一等结构（first-class construct），成为了语言和平台的一部分。Java 模块可以表明对其它模块的依赖，以及在强封装实现类的时候公开暴露接口。甚至 Java 平台本身（一个庞大的代码库）已经使用了新的 Java 模块系统进行模块化。你可以在我即将出版的书Java 9 Modularity中了解有关 Java 9 模块化开发的更多信息。（现早期版本已经发布）

其它的语言也提供了类似的机制。例如，JavaScript 在 ES2015 规范中提供了一个模块系统。在此之前，Node.js 也为 JavaScript 后端提供了一个非标准的模块系统。然而 JavaScript 作为一种动态语言，对于强制接口（类型）与模块封装的支持还是较弱。你可以考虑在 JavaScript 的基础上使用 TypeScript 来重新获得这些优点。微软的 .Net 框架与 Java 一样都有着强类型，但就强封装以及程序集（Assemblies）间的显式依赖而言，它与 Java 即将推出的模块系统并不相同。尽管如此，你可以通过使用 .Net Core 中标准化的反转控制模式（IOC）以及创建逻辑相关的程序集来实现良好的模块化架构。即使是 C++ 也在以后的版本中考虑添加模块系统。许多语言都在向模块化靠近，这本身就是一个显著的进步。

当你有意识地使用你的开发平台的模块化特性时，你就可以实现之前提及的微服务的模块化优势。基本上模块系统越好，你在开发过程中获得的帮助就越多。只要在不同团队间的接触点定义好明确的接口，不同的团队也可以独立进行不同部分的工作。当然，在部署时还是要将模块在一个单独的部署单元中组合起来。这样可以防止过于复杂，以及减少迁移到微服务所需要的开发与管理成本。诚然，这也意味着你不能使用不同的技术栈来构建不同的模块，但你的团队应该不会真的这么做吧？

模块设计

创建好的模块和创建好的微服务一样，都需要严谨的设计。一个模块应该基于其域的有界上下文建模（DDD）。选择微服务的边界是架构上重要的决策，一旦出错就可能要付出沉重的代价。相较而言，模块化应用程序模块的边界更容易修改一些。模块间的重构通常由类型系统和编译器支持。微服务边界的重新划分则涉及大量的进程间通信（IPC），以确保运行时稳定性。老实说，你真的只用一次两次就能正确的划分好边界？

在许多方面，静态语言的模块为了定义明确的接口而提供了更好的结构。通过调用另一个模块暴露的接口提供的方法，比去调用另一个微服务的 REST 端点健壮性要强的多。REST+JSON 现在无处不在，但在没有编译器检查的情况下，它并没有”类型良好的互通性“这个特点。而事实上，通过网络序列化（或者反序列化）数据并不是无开销的，甚至这种传输方式更加逊色。此外，许多模块化系统允许你表明此模块对于其它模块的依赖关系，模块系统将不允许违背这些依赖关系的情况出现。而微服务之间的依赖关系只在运行时实现，导致系统难以调试。

模块也是代码所有权中的自然单位。一个团队可以负责系统中的一个或者多个模块，而只需要给其它团队提供模块的公共 API。在运行时，模块之间的隔离比微服务少，毕竟模块化单体式应用的所有模块都运行在同一个进程中。

• 译注：什么是代码所有权

毫无疑问，单体式应用的模块不可能像微服务一样有自己的数据。模块化应用内部的数据交流是通过定义良好的接口或者模块间的消息进行的，而不是通过共享数据存储进行。它与微服务最大的差别就是它的一切都发生在同一个进程中，因此同样不能低估最终的数据一致性问题。对于模块来说，最终的一致性问题可以是一个策略问题，或者你也可以仅将数据”逻辑地“分开存储在同一数据库内并仍然使用跨域事务。而对于微服务来说，这个问题别无选择：必须保证最终的一致性。

何时微服务才适用于你的团队？

那么何时迁移到微服务架构才合适呢？到目前为止，我们主要关注的是如何通过模块化来解决复杂性问题。对于这一点，微服务与模块化应用都可以做到，只不过各有所难。

当你的团队有如同 Google 或者 Netflix 般的规模的时候，拥抱微服务是毋庸置疑的。你有能力去建立你自己的平台与工具库，并且工程师的数量排除了任何使用单体式解决方案的可能。但是大多数的组织都达不到这个规模。即使你认为你的公司有朝一日将成为一个市值十亿美元的独角兽，在刚起步时使用模块化的单体式应用也无伤大雅。

另一个拆分微服务的理由是：不同的服务在实现上更适合使用不同的技术栈。那么，你必须有足够的规模来吸引人才以解决这些迥然不同的技术栈，并支持这些平台的运行。

微服务还可以做到独立部署系统的不同部分，这在大多数模块化平台中很难（甚至不可能）实现。隔离部署增加了系统的弹性与容错能力。此外，每个微服务的缩放特性可以是不同的，可以部署不同的微服务以匹配硬件。模块化的单体式应用可以进行水平缩放，但是只能将所有模块捆绑在一起同时进行拓展。虽然你可以通过这种方法得到很多好处，但这可能并不是最好的解决方案。

总结

总之，最好的方案就是找到一个折中的点。这两种方案都有可取之处，需要根据实际环境、组织和应用本身进行选择。既然你可以在之后迁移成微服务架构，那为什么最开始不直接使用模块化应用呢？如果你之前就已经划分好了模块边界，那也就不需要再去拆分你的单体式应用了。甚至你还可以在模块内部搭建微服务架构。那么问题就变成了：为什么微服务一定要是“微”的呢？

即使你的应用刚从模块化应用转成微服务架构，服务也不必非得很“微”才具备可维护性。在服务中应用模块化原则能让它们在复杂度的可扩展性上超越通常的微服务。现在这份蓝图中既有微服务也有模块，减少架构中的服务的数量可以节约成本；而其中的模块可以像构建单体式应用一样，构建和扩展服务。

如果你追求模块化的好处，请确保自己不要自嗨进入一种“非微服务不可”的心态。探索你喜爱的技术栈中的同进程模块化功能或框架，你将会得到支持去真正的执行模块化设计，而不是仅靠着约定来避免“意大利面条式代码”。最后，请深思熟虑后再选择：你是否愿意接受引入微服务造成的复杂度成本。有的时候你别无选择，但更多的时候其实你可以找到更好的解决方案。

发布于掘金 https://juejin.im/post/58eb2627da2f60005f0b2d60

如果你是一名 iOS 开发者，你应该听说过 React Native。它给出了简单而吸引人的承诺：一次编写，两处部署，同时搞定 iOS 与安卓版本的 app。我是一名资深的 iOS 开发者（还是一名更资深的 macOS 开发者），我想分享我应用这门神奇技术的经历。

去年，我们和一个客户进行过交谈。他们来找我们是因为他们想尽快完成他们的 iOS app。在讨论的过程中，他们提到了这个叫做 React Native 的东西。他们有个善于使用 Javascript 的 web 开发人员，那个人指出使用 RN 可以让开发速度快很多。这场谈判最终我们没有达成共识而是以失败告终，但这件事也让我开始思考是否应该将 RN 纳入我们的技术栈中

几周后一位老友来访，让我为他出版的一本书制作一个 app 作为补充参考资料。因为这个工作我找到了一线机会：这是一个很棒的时机来试一试 React Native。由于他的读者大多数使用安卓系统，因此「一次编写，两处部署」的理念在此深得我心。

我不会带你亲历一遍我的各种尝试和遇到的问题。但我要说的是，就这么一个简单的 app，并不能使用 RN 很好的进行开发。以下是原因。

首先，我必须说一下除开「一次编写，两处部署」的承诺，我喜欢 React Native 的地方。

• React.js，RN 由它而生。它是一种描述与更新 UI 的优雅方法。它的基本原理是组件使用一组传递给它的属性由上到下渲染其 UI。感谢 React 的虚拟 DOM，当属性变化时 UI 会立即更新，使得 model 与 view 能够自动且无缝地同步。我多么希望 iOS 的 UIKit 也这样设计啊！
• 更新 JSX 代码就可以在模拟器中更新 app 而不需要重新编译与重新运行，这点真的很棒。
• 蓬勃发展的 RN 社区提供了数以百计的预制组件，你可以在你的 app 中使用它们。（实际上我非常讨厌这种看似专业的「脚本小子」的编程方法。构建一个大部分都不是你自己写的，并且弄不明白的 app，将会导致之后的维护如同陷入泥潭一般困难）
• 我很担心 RN 的性能，但是在我的经历中它并没有出现问题。滚动和动画都很流畅。毕竟 RN app 大部分使用的是平台原生的 UI 控件，RN 的工程师们也对它们进行了很好的优化。

那么为什么我不喜欢它呢？老实说，我并不是 React Native 的目标用户。我熟悉 Javascript 但我并不精通它，我精通的是 Swift/Objective-C。我很快就意识到，如果我使用 RN 来完成这个 app，将会比我用 Swift 慢 10-20 倍。当然，安卓版本还要单独写，但是考虑到我学习 RN 的学习曲线，我还不如去学习 Java。

除此之外，我认为采用 RN 的解决方案还有一些严重的问题。

脆弱的依赖链

React Native 并不是一个一站式解决方案。我制作了一个粗略的必要组件依赖图：

React Native 的依赖链

如果你来自 web 开发的世界，这可能对你来说很正常；但是对我来说，这很不正常。我的世界中有 Xcode，任何创建 Swift/Obj-C/iOS/Mac/Apple TV 等 app 所需要的东西都已经封装好并由 Xcode 管理。依赖链和前面的图一样（甚至更长），但是依赖链中的东西都保证是同步且兼容的。

我现在肯定 RN 依赖链中的大多数组件都是互相兼容的。但我遇到了四五个需要在 StackOverflow 上花几小时寻求解决方案的问题。在我心中更重要的是之后会发生的事情。例如，升级 Nuclide（IDE 的 RN 拓展）可能需要新版的 Atom。我系统中的另一个工具需要新版的 winston，如果那个版本不兼容 RN 怎么办？后果可想而知。

被打破的承诺

事实证明「一次编写，两处部署」的承诺只有部分实现了。我遇到了必须要把我的 RN app 根据目标平台（iOS 或安卓）进行「分支」的问题。例如 tab bar，你可能认为像它这么随处可见的组件会被 RN 列为「一等公民」，但事实不是这样的。RN 为 iOS 收录了 TabBarIOS 组件，但是因为某些原因它在安卓上并不相同。相反，在 GitHub 上有一堆的教程和解决方案教你如何从头做起。又例如 nav bar，iOS 的 NavigatorIOS 与安卓的 Navigator 工作方式差别巨大。这些核心的导航功能结构在两个平台上的差异会导致要为每个平台分别编写大量的不同的文件与组件。我开始感觉到，尽管承诺很神奇，尽管我在用同一种语言，但其实我仍然在写两个不同的 app。

• 实际上，这个「承诺」其实是别人推断的，并不是官方宣称的（至少 Facebook/RN 的人没有这么宣称过）。官方宣传的是「一次学习，随处编写」。

令人惊讶的技术限制

我在做的这个项目其实是一个层级化的参考指南。书作者和我为目录与文章用我们设计的 UI 范式规划了一套挺合理的布局。根据我们的想法，我们可以通过链接或导航跳转到数百个使用静态内容的详情页中。我写好了代码，但奇怪的是我调用 require() 一直不成功。我经过一段时间的研究，了解到 RN 限制您无法从任意路径读取文件。显然你的 RN app 在编译时收集了所有可能用到的路径，任何编译器无法找到的路径都将不能读取。所以你可以用 require(‘../file1.json’) 但不能用 require(‘../file’ + ‘1’ + ‘.json’)。这个让人惊讶的限制使得我们的架构无法实现。

冒牌货般的 UI

你最终完成的 RN app 可能既不像原生的 iOS app 也不像原生的安卓 app。大多数用户可能不会察觉这个问题，但有些人会发现更大的问题。你有可能会丢失一些用户会注意到的平台特有的细节，例如不能从左侧右滑来返回。（当你用 NavigatorIOS 完成两个平台的导航时会出现这个问题）

总而言之，iOS 开发者不应该将 React Native 视为两个平台的跨平台解决方案。写一个原生的 iOS app 将会花费更少的时间并可能得到更棒的 UX。对于安卓 app 也一样，所以我认为大家应该更多的去专注于平台原生解决方案。

什么时候用 RN 才是正确的呢？如果你是一个专业的 Javascript 程序员或者你有这么一个员工，并且你不打算配置 iOS 开发或安卓开发人员，那么你可能会从中获益。还记得那个想要尽快做好跨平台 app 的那个客户吗？他们曾有一名 Javascript 工程师，他们 app 的 v1.0 版本最近才出现在应用商店中。此时，距他们联系我们已经过去了 8 个月。

发布于掘金 https://juejin.im/post/58df4c3fa0bb9f0069e2f2bd

由之前的学习笔记 使用python实现EM算法。

代码地址

EM algorithm

\[\text{Repeat until convergence}\{\\ \text{(E-step) For each i,set}\\ Q_i(z^{(i)}):=p(x^{(i)},z^{(i)};\theta)\\ \text{(M-step) set}\\ \theta:=\arg \max_\theta \sum^m_{i=1} \sum_{z^{(i)}} Q_i(z^{(i)}) \ln \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\}\]

准备数据

和上一篇k-means一样，从准备数据开始。EM算法可以用来对数据集中数据的分布参数进行极大似然估计。因此，为它准备两组一维高斯分布数据。

使用numpy的randn函数来生成正态分布数据，使用matplotlib来对其进行可视化。

1
2

import numpy as np
import matplotlib.pyplot as plt

参考numpy的文档，生成一个[latex]N(mu,sigma^2)[/latex]的正态分布，需要使用

mu + sigma * np.random.randn(..)

代码：

1
2
3
4
5
6
7
8
9

def generateDataAndShow():
    x1,x2 = mu1 + sigma * np.random.randn(500),mu2 + sigma * np.random.randn(500)
    x = np.append(x1,x2)
    plt.hist(x,50,normed=True)
    plt.show()
    return x

if __name__=='__main__':
    data = generateDataAndShow()

这样，就得到了两组分别以[latex]N(mu_1,sigma^{2)[/latex]与[latex]N(mu_2,sigma}2)[/latex]分布的数据集。通过matplotlib可以看到它们的分布概率图大致如下：

算法实现

算法的推导与分析在http://lsvih.com/?p=515 进行过了。总体来说是一个迭代渐进的过程。渐进的变量有两个，一个是实现分类的隐藏变量z，另一个是决定分布函数的参数[latex]theta[/latex]。

E-step

已知高斯函数的概率密度函数(PDF)为

\[f(x,\sigma,\mu)=\frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}\]

1
2
3
4

for i,X in enumerate(data):
    p1 = np.exp(-(X-mu1)**2/(2*sigma**2))/(sigma*(np.sqrt(2*np.pi)))
    p2 = np.exp(-(X-mu2)**2/(2*sigma**2))/(sigma*(np.sqrt(2*np.pi)))
    Z[i,0],Z[i,1] = p1/(p1+p2),p2/(p1+p2)

即实现\(Q_i(z^{(i)}):=p(x^{(i)},z^{(i)};\theta)\)

M-step

data为矩阵

\[\begin{bmatrix}x_1\\x_2\\...\\x_n\end{bmatrix}\]

而Z为矩阵

\[\begin{bmatrix}Z^{(1)}_1&Z^{(1)}_2\\Z^{(2)}_1&Z^{(2)}_2\\...\\Z^{(n)}_1&Z^{(n)}_2\end{bmatrix}\]

因此完成\(\theta:=\arg \max_\theta \sum^m_{i=1} \sum_{z^{(i)}} Q_i(z^{(i)}) \ln \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\)运算可以使用矩阵的点乘实现。

1

mu1,mu2 = np.dot(np.array(data),np.array(Z))/np.sum(Z,axis=0)

Result

在对于E-step与M-step不停的迭代优化后，达到一个期望精度值停止运算。因此main()可以写成

1
2
3
4
5
6
7
8

while True:
    o_mu1,o_mu2 = mu1,mu2
    Z = np.zeros([len(data),2])
    #E-Step
    #M-Step
    if abs(o_mu1-mu1)+abs(o_mu2-mu2) <= 0.001:
        print mu1,mu2
        break

在迭代至指定精度后，将得到的mu1与mu2与sigma决定的正态分步曲线画出来。

1
2
3
4
5
6
7
8

#Darw Gaussian function
import matplotlib.mlab as mlab
fig, ax = plt.subplots()
n,bins,p = ax.hist(data,50,normed=True)
y1,y2 = mlab.normpdf(bins, mu1, sigma), mlab.normpdf(bins, mu2, sigma)
ax.plot(bins, y1/2)
ax.plot(bins, y2/2)
plt.show()

可以看到，最初的generateData函数中画出的图形为

得到结果后画出的曲线为

基本能匹配之前生成的数据。

准备实现一些算法，顺带复习numpy，因此将比较简单的k-means算法用python实现一次。

k-means算法

准备数据集

首先，考虑数据集来源。懒得去找数据，因此直接用scikit的dataset模块随机生成一组聚类数据。既然要生成聚类数据，用make_blobs是再好不过了。sklearn.dataset.make_blobs文档

为了直观地展示数据，用matplotlib来进行数据可视化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import numpy as np
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

def generateDataAndShow():
    plt.figure(figsize=(8,5))
    plt.title("Dataset", fontsize='small')
    datas, class_info = make_blobs(n_samples=200 ,n_features=2, centers=3)
    plt.scatter(datas[:, 0], datas[:, 1], marker='o', c=class_info)
    plt.show()
    return datas

if __name__=='__main__':
    data = generateDataAndShow()

可以得到一个有三个聚类，共200个点的数据集。如图所示

且每次运行都会生成不同的数据。

此时，得到200对坐标数据以及相应的分类数据。仅将坐标数据拿出来进行计算。

算法实现

1、随机生成3个点，作为初始聚类中心。为了减少计算量，所以将3个点生成在所有点的值域中。此时data的数据结构是Float[][]，第一重数组为一个点，第二重数组为点的两个坐标。因此需要用到numpy的amax函数与amin函数：

1

[x_max, y_max], [x_min, y_min] = np.amax(data,axis=0),np.amin(data,axis=0)

使用numpy.random的rand生成一组点：

1
2
3

centers = np.random.rand(3,2)
centers[0:,0] = (x_max-x_min)*centers[0:,0]+x_min
centers[0:,1] = (y_max-y_min)*centers[0:,1]+y_min

这样就得到了在值域内的3个随机点。

2、计算距离。二维平面内两个点的距离公式为

\[d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\]

因此可以计算出每个点分别到三个聚类中心的距离：

1
2
3
4
5
6
7

def distance(data, dots):
    rs = []
    for d in data:
        rs.append([])
        for dot in dots:
            rs[-1].append(((d[0]-dot[0])**2+(d[1]-dot[1])**2)**0.5)
    return rs

3、分组。根据计算得到的各个点距离聚类中心的距离，可以判断这个点是属于哪一个聚类的。

1
2

def classify(dis):
    return [i.index(min(i)) for i in dis]

返回一个分类索引数组。这个时候也可以用plt将此时的分类打印出来，和最开始的正确聚类对比一下：

考虑一种特殊情况：只分出两个聚类。这时候将无法继续计算下去，应当重新随机生成中心。

4、移动聚类中心。根据随机得到的初始聚类，重新计算每个聚类的质心作为其新的聚类中心。

1
2
3
4
5

def calCenters(data, clazz):
    clz = [[] for i in range(3)]
    for index,dot in enumerate(data):
        clz[clazz[index]].append(dot)
    return [sum(x)/len(x) for x in clz]

得到了新的聚类中心

5、循环上述步骤，直到收敛。

1
2
3
4
5
6

while True:
    new_centers = calCenters(data, clazz)
    if equal(new_centers,centers):break
    else:
        centers = new_centers
        clazz = classify(distance(data,centers))

收敛条件是聚类中心点不再变化。

最终代码：https://github.com/lsvih/algorithm-practice/blob/master/k-means/k-means.py (_src=undefined)

结果

生成的聚类：

k-means运行后的聚类：

可以看到分类算法运行良好。

琴生不等式(Jensen's inequality)

最大似然函数应用到了琴生不等式。琴生不等式给出了积分的凸函数值和凸函数的积分值间的关系。它由以下两部分组成：

当\(f(x)\)是(a,b)区间上的凸函数时，则对任意的点\(x_1,x_2,...,x_n \in (a,b)\)有

\[f(\frac{x_1+x_2+...+x_n}{n}) \geq \frac{1}{n}[f(x_1)+f(x_2)+...+f(x_n)]\]

当\(x_1=x_2=...=x_n\)时取等号。

当\(f(x)\)是(a,b)区间上的凹函数时，则对任意的点\(x_1,x_2,...,x_n in (a,b)\)有

\[f(\frac{x_1+x_2+...+x_n}{n}) \leq \frac{1}{n}[f(x_1)+f(x_2)+...+f(x_n)]\]

当\(x_1=x_2=...=x_n\)时取等号。

将琴生不等式应用到概率论，有

当\(f(x)\)是凸函数时

\[E[f(X)]\geq f(EX)\]

当\(f(x)\)是凹函数时

\[E[f(X)]\leq f(EX)\]

如图所示：

最大似然算法(EM algorithm)的推导

似然函数(likelihood function)

当有一组数据\({ x^{(1)},...,x^{(m)} }\)，这一组数据是从更大的未知数据中抽样出来的，每一个x对抽样而言都是独立事件。因此，抽样出每个数据的概率为\(p(x)\)，抽样出这一组数据集的概率则为\(\prod^m_{i=1} p(x)\)。而所有的数据都满足某一个分布规律（求的正是这个规律），例如高斯分布等。这个分布规律含有一个分布参数\(\theta\)，这个参数决定了这个分布规律。此时抽样出数据集的概率为\(\prod^m_{i=1} p(x_i;\theta)\)，将这个式子记为\(L(\theta)\)，即

\[L(\theta)=\prod^m_{i=1} p(x_i;\theta)\]

当\(L(\theta)\)最大时，有最大的可能抽出这组数据，就能猜测\(\theta\)是分布概率的参数。这个式子被称为似然函数。

p(x;y)表示当参数为y时x的概率

为了让计算更方便，将乘法运算通过求ln值变化为加法运算

\[l(\theta)=\sum^m_{i=1} \ln p(x_i;\theta)\]

这个l称为loglikelihood function

最大似然函数

当有多组数据时，每组数据的分布规律都不同，对于每组数据来说都有一个隐藏的变量z将不同的组别分开。例如对于\(x^{(i)}\)来说，有\(p(z^{(1)})\)的可能是聚类1的，有\(p(z^{(2)})\)的可能是聚类2的。因此将所有的可能加起来，有

\[l(\theta)=\sum^m_{i=1} \ln p(x_i;\theta)=\sum^m_{i=1} ln\sum_{z^{(i)}}p(x^{(i)},z^{(i)};\theta)\]

为了求其最值，则需要对其进行求导。此时发现，\(\sum \ln \sum f(x,y,z)\)相当难进行求导，因此对其进行化简：

对于\(x^{(i)}\)，它的所有z概率之和记为\(\sum_{z^{(i)}} Q_i(z^{(i)})=1\)，对上式加入这个值，得到

\[l(\theta)=\sum^m_{i=1} \ln p(x_i;\theta)=\sum^m_{i=1} \ln\sum_{z^{(i)}} Q_i(z^{(i)}) \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\]

对于\(f(x)=\ln x\)来说，\(\frac{\mathrm{d}^2 f(x) }{\mathrm{d} x^2}=-\frac{1}{x^2}\leq0\)，因此它为凹函数。应用琴生不等式，\(E(f(x)) \leq f(EX)\)。同理，上式进行不等变换：

\[f(E_{z^{(i)~Q_i}}[\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}]) \geq E_{z^{(i)~Q_i}}[f(\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})})]\Rightarrow \\ \sum^m_{i=1} ln\sum_{z^{(i)}} Q_i(z^{(i)}) \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \\ \geq \sum^m_{i=1} \sum_{z^{(i)}} Q_i(z^{(i)}) \ln \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\]

此时得到的式子是一个不等式，确切的说是似然函数的下界。为了让似然函数达到最大，则需要得到合适的\(z,\theta\)让下界更高。

此时分两步来进行计算：第一步固定\(\theta\)调整\(Q_i(z^i)\)，让下界上升至最高(前式的不等式取到等号)，第二部固定\(Q_i(z^i)\)调整\(\theta\)，使似然函数的值升高，下界达到最高，再重复第一步。循环往复直到第二步收敛。

E-step

根据琴生不等式，当X为常数时，肯定有\(E[f(X)]= f(EX)\)，即

\[\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} = c\]

而\(\sum_{z^{(i)}} Q_i(z^{(i)})=1\)，因此

\[Q_i(z^{(i)})=\frac{p(x^{(i)},z^{(i)};\theta)}{\sum_z p(x^{(i)},z,\theta)}=p(x^{(i)},z^{(i)};\theta)\]

这就是第一步，让琴生不等式中的X为常数，取到f(x)的最大值。这一步记为E-step：

\[Q_i(z^{(i)}):=p(x^{(i)},z^{(i)};\theta)\]

M-step

固定\(\theta\)，下界为

\[\sum^m_{i=1} \sum_{z^{(i)}} Q_i(z^{(i)}) \ln \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\]

此时要调整\(Q_i(z^i)\)，让下界升到最高。记第t步为\(l(\theta^{t})\)，第t+1步为\(l(\theta^{t+1})\)。由于下界在升高，最大似然函数值也会升高，\(Q_i(z^i)\)随之升高，直到收敛。因此可以推导

\[l(\theta^{(t+1)})=\sum^m_{i=1} \sum_{z^{(i)}} Q_i^{(t+1)}(z^{(i)}) \ln \frac{p(x^{(i)},z^{(i)};\theta^{(t+1)})}{Q^{(t+1)}_i(z^{(i)})}\\ \geq \sum^m_{i=1} \sum_{z^{(i)}} Q_i^{t}(z^{(i)}) \ln \frac{p(x^{(i)},z^{(i)};\theta^{(t+1)})}{Q^{t}_i(z^{(i)})}\\ \geq \sum^m_{i=1} \sum_{z^{(i)}} Q_i^{t}(z^{(i)}) \ln \frac{p(x^{(i)},z^{(i)};\theta^{t})}{Q^{t}_i(z^{(i)})}=l(\theta^{t})\]

最终得到

\[l(\theta^{(t+1)}) \geq l(\theta^t)\]

因此可得知M-step中，\(Q_i(z^i)\)的值会不断增加直到收敛。

M-step记为

\[\theta:=\arg \max_\theta \sum^m_{i=1} \sum_{z^{(i)}} Q_i(z^{(i)}) \ln \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\]

最终得到最大似然算法：

\[ \text{Repeat until convergence}\{ \\ \text{(E-step) For each i,set}\\ Q_i(z^{(i)}):=p(x^{(i)},z^{(i)};\theta) \\ \text{(M-step) set}\\ \theta:=\arg \max_\theta \sum^m_{i=1} \sum_{z^{(i)}} Q_i(z^{(i)}) \ln \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\\ \} \]

Reference

Stanford CS229 http://cs229.stanford.edu/notes/cs229-notes8.pdf cs229-notes8-EM算法.pdf 从最大似然到EM算法浅解 http://blog.csdn.net/zouxy09/article/details/8537620/

做个简单的记事本,效果如下：

主要使用UserDefaults(以前是NSUserDefaults)实现数据的持久化,将Array数据存储在沙盒里。

直接使用

1
2
3
4

func syncStore(){
    UserDefaults.standard.set(objects, forKey: "history")
    UserDefaults.standard.synchronize()
}

存数据。

读取数据使用

1

objects = UserDefaults.standard.value(forKey: "history") as! Array<Any>

在第一次启动的时候读数据会出错，因此需要判断是否为第一次启动，如果是第一次启动则需要初始化存储结构。

1
2
3
4
5
6
7

let isFirstLaunch = UserDefaults.standard.string(forKey: "FirstLaunch") == nil
if(isFirstLaunch){
    UserDefaults.standard.set("false", forKey: "FirstLaunch")
    syncStore()
}else{
    objects = UserDefaults.standard.value(forKey: "history") as! Array<Any>
}

插入数据的function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func insertNewObject(_ sender: Any) {
    let alertController = UIAlertController(
    title: "添加备忘", 
    message: "请输入备忘内容", 
    preferredStyle: UIAlertControllerStyle.alert)
    let insertAction = UIAlertAction(
    title: "确认", 
    style: .default, 
    handler: {
    (action: UIAlertAction) -> Void in
        print(alertController.textFields![0].text!)
        self.objects.insert(alertController.textFields![0].text!, at: 0)
        let indexPath = IndexPath(row: 0, section: 0)
        self.tableView.insertRows(at: [indexPath], with: .automatic)
        self.syncStore()
    })
    let cancelAction = UIAlertAction(title: "取消", style: .cancel)
    alertController.addTextField { (textField:UITextField) in
        textField.placeholder = "请输入内容"
    }
    alertController.addAction(insertAction)
    alertController.addAction(cancelAction)
    self.present(alertController, animated: true, completion: nil)    
}

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,

Given n = 3,

You should return the following matrix:

[[ 1, 2, 3 ],

[ 8, 9, 4 ],

[ 7, 6, 5 ]]

与之前蛇形遍历一个思路，给定几个状态x,y,state(说明当前生成的方向)

在这个问题中，只有以下几种情况：向上生成到顶时，向右生成；向右生成到顶时，向下生成；向下生成到顶时，向左生成；向左生成到顶时，向上生成。最终的结束条件是生成了n^2个数字。

首先生成一个n*n的矩阵：

1
2
3
4
5

rs = []
for i in range(n):
    rs.append([])
    for j in range(n):
        rs[i].append(None)

这样就得到了一个n*n的空矩阵。

开始时尝试过

1

[[None]*n]*n

与

1

[[None for i in range(n)]]*n

的方式，发现均会出现问题。原因是以这种方式生成的二维数组的子项指向的是同一个对象。其后果是

1
2
3
4
5
6
7
8
9
10
11
12
13
14

>>> a = [[None]*5]*5
>>> a
[[None, None, None, None, None], 
[None, None, None, None, None], 
[None, None, None, None, None], 
[None, None, None, None, None], 
[None, None, None, None, None]]
>>> a[2][2] = 1
>>> a
[[None, None, 1, None, None], 
[None, None, 1, None, None], 
[None, None, 1, None, None], 
[None, None, 1, None, None], 
[None, None, 1, None, None]]

使用built-in查看它们的id发现：

1
2

>>> id(a[2]),id(a[3])
(4337281432, 4337281432)

因此放弃看上去简洁的写法。

更新：发现一个简洁有效的写法：

1

x = [[None for i in range(n)] for j in range(n)]

之后找出每个方向的条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

while step <= n**2:
# print x,y,state,step,layer,tmp
    rs[x][y] = step
    if state == 'up':
        if x == layer:
            y += 1
            state = 'right'
        else:x -= 1
    elif state == 'right':
        if y+1 == n-layer:
            x += 1
            state = 'down'
        else:y+=1
    elif state == 'down':
        if x+1 == n-layer:
            y -= 1
            state = 'left'
        else:x+=1
    elif state == 'left':
        if y == layer:
            x-=1
            state= 'up'
        else:y-=1
    step += 1

大意如此。其中layer为当前从外向内已生成完的层数，由

1

if step == n**2-(n-layer*2-2)**2:layer+=1

可以得到。

Input:

[[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ]]

Output: [1,2,4,7,5,3,6,8,9]

Explanation:

像蛇爬行一样沿着对角线来回遍历整个矩阵。

提供一种很容易实现的解题思路：

在遍历过程中有几种情况：向右遍历、向下遍历、向左下遍历、向右上遍历。

给定两个变量x,y(记做matrix[x][y])记录当前坐标，就能通过判断这几个方向决定下一个坐标位置。

例如，向左下遍历即x++,y--，如果x已经到矩阵下边界则转向右遍历；如果x未到矩阵下边界,y到矩阵左边界则向下遍历；如果xy都未到矩阵边界则继续向左下遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13

state,x,y,M,N = 'right_up',0,0,len(matrix),len(matrix[0])
if state == 'left_down':
    rs.append(matrix[x][y])
    if x == M-1 or y == 0:
        if x == M-1:
            y += 1
            state = 'right_after_left_down'
        else:
            x += 1
            state = 'down_after_left_down'
        else:
            x += 1
            y -= 1

依次类推，可以将所有情况与边界情况都列出来。

同时需要排除三种特殊情况：当矩阵为空时不存在遍历结果；当矩阵行或列为1时直接将矩阵从上至下遍历。

经简化可写出解法(result)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def findDiagonalOrder(matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[int]
    """
    if matrix == []:return []
    rs,state,x,y,M,N = [],0,0,0,len(matrix),len(matrix[0])
    if M == 1 or N == 1:return reduce(lambda x,y:x+y,matrix)
    while True:
        rs.append(matrix[x][y])
        if x == M-1 and y == N-1:return rs
        elif state == 0:
            if x == 0 or y == N-1:
                if y == N-1:x,state = x+1,2
                else:y,state = y+1,5
            else:x,y = x-1,y+1
        elif state == 1:
            if x == M-1 or y == 0:
                if x == M-1:y,state = y+1,4
                else:x,state = x+1,3
            else:x,y = x+1,y-1
        elif state == 3 or state == 4:x,y,state = x-1,y+1,0
        elif state == 2 or state == 5:x,y,state = x+1,y-1,1

其中每个元素都被处理过一遍，其时间复杂度为O(n)

除了内置(build-in)数据结构(dict,list,set,tuple)之外，python还提供了一些额外的数据结构。

1

import collections

collections提供了5种可选的数据结构:Counter,deque,OrderDict,defaultdict,namedtuple()

collections.Counter

1

from collections import Counter

简介

Counter是dict的一个子集，它可以用来计算dict中的可哈希对象。它是一个无排序集合，它的元素作为dict的key存储，对应的计数则以其value存储，例如Counter({'a':1,'b':2,'c':4})代表有1个a,2个b,4个c。Counter接受所有的整数作为其计数(包括0和负数在内)。

构造

构造一个空的Counter

1
2
3

c = Counter()
#此时c为
Counter()

从迭代器创建Counter

1
2
3

c = Counter("asdf")
#此时c为
Counter({'a':1,'s':1,'d':1,'f':1})

由字典mapping创建

1
2
3

c = Counter({'ss':1,'dd':2})
#此时c为
Counter({'dd':2,'ss':1})

由参数的keyword创建

1
2
3

c = Counter(hh = 2,ss = 6)
#此时c为
Counter({'ss':6,'hh':2}

特性

Counter有一些很有用的特性。例如，作为一个计数器，当读取Counter中不存在的key时，不会像通常dict那样返回错误，而是会返回0(意思是Counter里有0个这种key)

例如:

1
2
3

c = Counter(['a','a','c'])
#此时c为
Counter({'a':2,'c':1})

1
2
3
4

#使用dict
t = {'a':2,'c':1}
t['b']
#此时报错

1
2
3

#使用Counter
c['b']
#输出0

将Counter中的一个key的value设置为0(即将其计数清零)并不会删除这个元素，只有使用del才能将其中的元素删除。例如：

1
2
3
4
5
6
7
8
9

c = Counter(['a','a','c'])
#此时c为
Counter({'a':2,'c':1})
c['a'] = 0
#此时c为
Counter({'c':1,'a':0})
del c['c']
#此时c为
Counter({'a':0})

elements()

返回Counter()中计数大于1的所有元素。例如:

1
2
3
4

c = Counter({'a':2,'b':1,'d':0,'e':-2})
list(c.elements())
#输出
['a','a','b']

most_common([n])

返回Counter()中计数最多的n个元素。例如:

1
2
3
4

c = Counter("asdfaas")
c.most_common(2)
#输出
[('a',3),('b',2)]

subtract()

由一个Counter()减去另一个Counter()或迭代器或mapping。得到的数字可以为0或负数。例如：

1
2
3
4
5

c = Counter("addaw")
b = "adddf"
c.subtract(b)
#此时c为
Counter({'a':1,'w':1,'d':-1,'f':-1})

除此之外，Counter()还有一些dict本身有的特性。

比如

1
2
3
4
5

Counter("asdf") == Counter("fdsa") >>>> True

Counter("wwww") + Counter("ssss") >>>> Counter({'w':4,'s':4})

list(Counter("asdf")) >>>> ['a','s','d','f']

等等。

应用

Counter()计数器可以用在很多需要统计key出现字数的情景中。

例如求同素异构词（由相同的字母不同的顺序组成的词）:

1
2
3

from collections import Counter
def same(s,d):
    return Counter(s) == Counter(d)

求句子中出现次数最多的字母:

1
2
3

from collections import Counter
def count(d):
    return Counter(d).most_common(1)

等等