成为专业程序员路上用到的各种优秀资料、神器及框架
前言 成为一名专业程序员的道路上，需要坚持练习、学习与积累，技术方面既要有一定的广度，更要有自己的深度。 笔者作为一位tool mad，将工作以来用到的各种优秀资料、神器及框架整理在此，毕竟好记性不如烂键盘，此项目可以作为自己的不时之需。 本人喜欢折腾，记录的东西也比较杂，各方面都会有一些，内容按重要等级排序，大家各取所需。 这里的东西会持续积累下去，欢迎Star，也欢迎发PR给我。 Thonatos.Yang整理的GitBook版本，阅读体验更佳：https://thonatos.gitbooks.io/be-a-professional-programmer/ 目录 资料篇 技术站点 必看书籍 大牛博客 GitHub篇 工具篇 平台工具 常用工具 第三方服务 爬虫相关(好玩的工具) 安全相关 Web服务器性能/压力测试工具/负载均衡器 大数据处理/数据分析/分布式工具 Web前端 语言篇 Scala Java Python Swift .NET C & C++ 其他 游戏开发相关 日志聚合，分布式日志收集 RTP,实时传输协议与音视频 资料篇 技术站点 在线学习：Coursera、edX、Udacity、MIT公开课、MOOC学院、慕课网 Hacker News：非常棒的针对编程的链接聚合网站 Techmeme：美国知名科技新闻和博客聚集网站，类似的还有（Panda, Hacker & Designer News） Reddit - Programming板块：同上 Java牛人必备：Program Creek Stack Overflow：IT技术问答网站 SegmentFault：中文的技术问答社区 GitHub：全球最大的源代码管理平台，很多知名开源项目都在上面，如Linux内核，OpenStack等 码云：支持中文可免费创建私有项目的代码托管平台，可作为备选 LeetCode：来做做这些题吧，看看自己的算法水平如何？这可比什么面试宝典强多了。 LintCode：支持中文的编程题在线训练平台，可作为备选 Kaggle,Topcoder: 机器学习、大数据竞赛 掘金：高质量的技术社区 开发者头条 InfoQ：企业级应用，关注软件开发领域 V2EX: way to explore 国内老牌技术社区：OSChina、博客园、CSDN、51CTO 免费的it电子书：http://it-ebooks.info/ 在线学习：http://www.udemy.com/ 优质学习资源：http://plus.mojiax.com/ 代码练习：http://exercism.io/ and https://www.codingame.com DevStore:开发者服务商店 MSDN：微软相关的官方技术集中地，主要是文档类 谷歌开发者 码库 - 收录了实用的开源项目及资源 Coding 基于Git的国内代码托管平台，支持私有项目，有项目管理相关功能 必看书籍 SICP(Structure and Interpretation of Computer Programs) 深入理解计算机系统 代码大全2 人件 人月神话 软件随想录 算法导论（麻省理工学院出版社） 离散数学及其应用 设计模式 编程之美 黑客与画家 编程珠玑 The Little Schemer Simply Scheme_Introducing_Computer_Science C++ Prime Effective C++ TCP/IP详解 Unix 编程艺术 技术的本质 软件随想录 计算机程序设计艺术 程序员的自我修养：链接、装载与库 程序员修炼之道 高效能程序员的修炼 《精神分析引论》弗洛伊德 《失控》《科技想要什么》《技术元素》凯文凯利 程序开发心理学 天地一沙鸥 搞定：无压力工作的艺术 大牛博客 awesome-programmers - 各领域大牛，值得纪念的程序员们 云风（游戏界大牛）: http://blog.codingnow.com/ 王垠（不少文章喷到蛮有道理）：http://www.yinwang.org/ 冰河-伞哥(Lisp大牛)：http://tianchunbinghe.blog.163.com/ R大【干货满满】RednaxelaFX写的文章/回答的导航帖 陈皓-左耳朵耗子：http://coolshell.cn/ Jeff Atwood（国外知名博主）: https://blog.codinghorror.com/ 阮一峰（黑客与画家译者，Web）：http://www.ruanyifeng.com/ 廖雪峰（他的Python、Git教程不少人都看过）：http://www.liaoxuefeng.com/ 道哥的黑板报（安全）：https://zhuanlan.zhihu.com/taosay 国内GitHub上关注度较高的开发者 GitHub篇 Awesome Awesome: 这是个Awesome合集，常见的资料这里面都能找到 Awesome2: 类似第一个Awesome 杂七杂八、有用没用的Awesome合集 非常不错的语言类学习资料集合：Awesomeness awesome-ios-ui awesome-android-ui Awesome-MaterialDesign awesome-public-datasets awesome-AppSec(系统安全) awesome-datascience awesome-dataviz - 数据可视化库及资料 awesome-es awesome-comment - 神注释大全 awesome-hacking - 黑客工具箱 awesome-machine-learning - 机器学习资料 书籍资料 Every Programmer Should Know Latency Numbers Every Programmer Should Know system-design-primer: 系统设计入门 free-programming-books 中文版 免费的编程中文书籍索引 《程序员编程艺术 — 面试和算法心得》 GoBooks Papers we love 自然语言处理NLP推荐学习路线及参考资料 超级棒的机器学习资料（框架，库，软件）, 中文翻译版 机器学习(Machine Learning)&深入学习(Deep Learning)资料 Docker资料合集 学习使用Strom Hadoop Internals Spark Internals 大数据时代的数据分析与数据挖掘 – 基于Hadoop实现 如何制作操作系统 借助开源项目学习软件开发 几个不错的开源游戏引擎 一起写Python文章，一起看Python文章 R的极客理想系列文章 HTTP接口设计指南 分享自己长期关注的前端开发相关的优秀网站、博客、以及活跃开发者 Readings in Databases Data Science blogs 日志：每个软件工程师都应该知道的有关实时数据的统一概念 Android Code Path Android Learn Notes PHP 类库框架，资料集合 优秀项目 最值得关注的10个C语言开源项目 15款值得学习的小型开源项目 iOS-100个开源组件 十大Material Design开源项目 Android开源项目分类汇总 前端 & Node.js 前端资源 前端开发指南 前端技能汇总 前端资源大导航 收集前端方面的书籍 2014年最新前端开发面试题 简单清晰的JavaScript语言教程，代码示例 JavaScript编程规范 JavaScript必看视频 JavaScript标准参考教程（阮一峰的，整理的不错） JS必看 AngularJS Guide的中文分支 Angular2学习资料 AngularJS应用的最佳实践和风格指南 React-Native学习指南 七天学会NodeJS node.js中文资料导航 Nodejs学习路线图 如何学习nodejs 工作，工具 系统管理员工具集合 Pro Git Nginx开发从入门到精通 Google 全球 IP 地址库 收集整理远程工作相关的资料 Color schemes for hackers 游戏开发工具集，MagicTools 开发者工具箱， free-for-dev GitHub秘籍 Git风格指南 Bast-App 工具篇 平台工具 Swagger: RESTful API设计工具，前后端分离项目必备，顺便推荐下Easy Mock Phabricator: 软件开发平台，Facebook出品，现已开源，CodeReview神器（从这个往下一直到GitLab之间的工具统统可以忽略了） Redmine/Trac：项目管理平台 Jenkins/Jira(非开源)：持续集成系统（Apache Continuum，这个是Apache下的CI系统，还没来得及研究） git，svn：源代码版本控制系统 GitLab/Gitorious：构建自己的GitHub服务器 AppVeyor - 云端持续集成工具，可以与GitHub搭配使用 Postman:RESTful，api测试工具，HTTP接口开发必备神器；可替代工具：Insomnia Lottie: AE动画变原生代码，设计师必备 Sonar：代码质量管理平台 Nessus: 系统漏洞扫描器 gitbook：https://www.gitbook.io/写书的好东西，当然用来写文档也很不错的（发现不少产品的文档就是用的它） Travis-ci：开源项目持续集成必备，和GitHub相结合，https://travis-ci.org/ Trello：简单高效的项目管理平台，注重看板管理 日志聚合：graylog、ELK（推荐新一代的graylog，基本上算作是开源的Splunk了） 开源测试工具、社区（Selenium、OpenQA.org） Puppet:一个自动管理引擎，可以适用于Linux、Unix以及Windows平台。所谓配置管理系统，就是管理机器里面诸如文件、用户、进程、软件包这些资源。无论是管理1台，还是上万台机器Puppet都能轻松搞定。其他类似工具：CFEngine、SaltStack、Ansible Nagios：系统状态监控报警，还有个Icinga(完全兼容nagios所有的插件,工作原理,配置文件以及方法,几乎一模一样。配置简单,功能强大) Ganglia：分布式监控系统 fleet：分布式init系统 Ansible：能够大大简化Unix管理员的自动化配置管理与流程控制方式。 GeoLite免费数据库 jsHint:js代码验证工具 haproxy: 高可用负载均衡（此外类似的系统还有nginx，lvs） linux OS性能分析工具：dstat，iostat，iotop，nmon kimono：将网页信息转换为api接口的工具 集群管理工具：pdsh，ClusterSSH，mussh（可以用它快速管理Hadoop集群）ipa-server做统一的认证管理 influxdb: 分布式时序数据库，结合Grafana可以进行实时数据分析 dot: 程序员绘图利器（是种语言，也是个工具） Graph::Easy: （Ascii Art工具）字符流程图绘制，实乃程序员装逼神器。其他类似的工具Asciiflow, vi插件：drawit! spf13-vim: 让你的vim飞起来！ Kubernetes: 容器集群管理系统 Gatling: 服务器性能压力测试工具 systemtap: Linux内核探测工具、内核调试神器 Cygwin：Windows下的类UNIX模拟环境 MinGW：Windows下的GNU工具集 常用工具 EditorConfig: 让我们在各种不同IDE或编辑器下写代码保持风格一致 Mac下的神兵利器 asciinema: 终端录屏神器 Fiddler：非常好用的Web前端调试工具，当然是针对底层http协议的，一般情况使用Chrome等自带的调试工具也足够了，特殊情况还得用它去处理 Charles: Mac上的Web代理调试工具，类似Fiddler fir.im免费的移动App内测托管平台 wireshark：知名的网络数据包分析工具 PowerCmd:替代Windows Cmd的利器 RegexBuddy:强大的正则表达式测试工具 Soure Insight：源代码阅读神器 SublimeText：程序员最爱的编辑器 Database.NET：一个通用的关系型数据库客户端，基于.NET 4.0开发的，做简单的处理还是蛮方便的 Navicat Premium：支持MySql、PostgreSQL、Oracle、Sqlite和SQL Server的客户端，通用性上不如Database.NET，但性能方面比Database.NET好很多，自带备份功能也用于数据库定时备份。 Synergy : 局域网内一套键盘鼠标控制多台电脑 DameWare：远程协助工具集（我在公司主要控制大屏幕用） Radmin: 远程控制工具，用了一段时间的DameWare，还要破解，对Win7支持的不好，还是发现这个好用 Listary：能极大幅度提高你 Windows 文件浏览与搜索速度效率的「超级神器」 Clover：给资源管理器加上多标签，我平时工作的时候就用它，像Chrome一样使用资源管理器，甚是方便啊（这是Windows平台的） WinLaunch：模拟Mac OS的Launch工具 OllyDbg: OD大名鼎鼎的反汇编工具，Win平台 Fritzing：绘制电路图 LICEcap：gif教程制作 git，svn：版本控制系统 Enigma Virtual Box（将exe，dll等封装成一个可执行程序） Open DBDiff(针对SqlServer)数据库同步 SymmetricDS：数据库同步 BIEE,Infomatica，SPSS，weka，R语言：数据分析 CodeSmith，LightSwitch：代码生成 Pandoc：Markdown转换工具，出书用的。以前玩过docbook，不过现在还是Markdown盛行啊。 Window Magnet[Mac]：增强Mac窗口管理功能，想Win7一样具有窗口拖放到屏幕边缘自动调整的功能 log explorer：查看SqlServer日志 dependency walker：查询Windows应用程序dll依赖项 Shairport4w：将iPhone，iPad，iPod上的音频通过AirPlay协议传输到PC上 ngrok：内网穿透工具 Axure:快速原型制作工具，还有个在线作图的工具国内的一个创业团队做的，用着很不错http://www.processon.com/ Origami: 次世代交互设计神器 百度脑图：http://naotu.baidu.com/ tinyproxy:（Linux）小型的代理服务器支持http和https协议 EaseUS Partition Master：超级简单的分区调整工具，速度还是蛮快的，C盘不够用了就用它从D盘划点空间吧，不用重装系统这么折腾哦。 CheatEngine：玩游戏修改内存值必备神器（记得我在玩轩辕剑6的时候就用的它，超级方便呢） ApkIDE:Android反编译神器 翻、墙工具（自|由|门、天行浏览器，免费的VPN：http://www.mangovpn.com/）,发现最方便还属Lantern，免费用起来超级方便（更新于2015-08-22） 设计工具：Sketch、OmniGraffle MindManger：思维导图 MagicDraw:Uml图工具 innotop：MySql状态监测工具 墨刀：比Axure更为简单的原型工具，可以快速制作原型 Karabiner: Mac专用，修改键盘键位的神器，机械键盘必备 Timing：Mac专用，统计你的时间都花在哪了 f.lux: 护眼神器，过滤蓝光，程序员护眼必备良品 LaTeX: 基于ΤΕΧ的排版系统, 让写论文更方便 Antlr：开源的语法分析器，可以让你毫无压力的写个小parser 第三方服务 Let's Encrypt: 免费、自动化、开放的证书签发服务 DnsPod：一个不错的智能DNS服务解析提供商 DigitalOcean：海外的云主机提供商，价格便宜，磁盘是SSD的，用过一段时间整体上还可以，不过毕竟是海外的，网速比较慢。国内的就是阿里云了。还有个比较知名的是：Linode，据说速度上比DigitalOcean好很多 移动端推送服务：个推、JPush、云巴 LeanCloud：移动应用开发服务，包括:数据存储、用户管理、消息推送、应用统计、社交分享、实时聊天等服务 Color Hunt: 漂亮炫酷的配色网站，程序员的福音 Heroku: PaaS平台 爬虫相关(好玩的工具) Phantomjs(Web自动化测试，服务端渲染等) berserkJS(基于Phantomjs的改进版本) SlimerJS CasperJS selenium HtmlUnit（开源的java 页面分析工具，也是个Headless的浏览器） 安全相关 sql注入检测：sqlmap、haviji 端口扫描：nmap 渗透测试：BurpLoader sqltools: sql漏洞利用工具 snort: 入侵检测 Web服务器性能/压力测试工具/负载均衡器 ab: ab是apache自带的一款功能强大的测试工具 curl-loader: 真实模拟、测试Web负载 http_load: 程序非常小，解压后也不到100K webbench: 是Linux下的一个网站压力测试工具，最多可以模拟3万个并发连接去测试网站的负载能力。 Siege: 一款开源的压力测试工具，可以根据配置对一个WEB站点进行多用户的并发访问，记录每个用户所有请求过程的相应时间，并在一定数量的并发访问下重复进行。 squid（前端缓存），nginx（负载），nodejs（没错它也可以，自己写点代码就能实现高性能的负载均衡器）：常用的负载均衡器 Piwik：开源网站访问量统计系统 ClickHeat：开源的网站点击情况热力图 HAProxy：高性能TCP /HTTP负载均衡器 ElasticSearch：搜索引擎基于Lucene Page Speed SDK和YSLOW HAR Viewer: HAR分析工具 protractor：E2E（end to end）自动化测试工具 大数据处理/数据分析/分布式工具 Hadoop：分布式的文件系统，结合其MapReduce编程模型可以用来做海量数据的批处理（Hive，Pig，HBase啥的就不说了），值得介绍的是Cloudera的Hadoop分支CDH5，基于YARN MRv2集成了Spark可直接用于生产环境的Hadoop，对于企业快速构建数据仓库非常有用。 Spark：大规模数据处理框架（可以应付企业中常见的三种数据处理场景：复杂的批量数据处理（batch data processing）；基于历史数据的交互式查询（interactive query）；基于实时数据流的数据处理（streaming data processing）），CSND有篇文章介绍的不错 除了Spark，其他几个不错的计算框架还有：Kylin，Flink，Drill Ignite: In-Memory Data Fabric CarbonData: 华为的孵化项目，支持索引的列式存储 Ceph:Linux分布式文件系统（特点：无中心） Storm：实时流数据处理，可以看下IBM的一篇介绍 （还有个Yahoo的S4，也是做流数据处理的） Druid: 实时数据分析存储系统 Ambari: 大数据平台搭建、监控利器；类似的还有CDH Tachyon：分布式内存文件系统 Greenplum: 基于PostgreSQL的分布式MPP数据库 Mesos：计算框架一个集群管理器，提供了有效的、跨分布式应用或框架的资源隔离和共享 Impala：新一代开源大数据分析引擎，提供Sql语义，比Hive强在速度上 presto: facebook的开源工具，大数据分布式sql查询引擎 SNAPPY：快速的数据压缩系统，适用于Hadoop生态系统中 Kafka:高吞吐量的分布式消息队列系统 ActiveMQ:是Apache出品，最流行的，能力强劲的开源消息总线 MQTT:Message Queuing Telemetry Transport，消息队列遥测传输）是IBM开发的一个即时通讯协议，有可能成为物联网的重要组成部分 RabbitMQ：记得OpenStack就是用的这个东西吧 ZeroMQ：宣称是将分布式计算变得更简单，是个分布式消息队列，可以看下云风的一篇文章的介绍 开源的日志收集系统：scribe、chukwa、kafka、flume。这有一篇对比文章 Zookeeper：可靠的分布式协调的开源项目 Databus：LinkedIn 实时低延迟数据抓取系统 数据源获取：Flume、Google Refine、Needlebase、ScraperWiki、BloomReach 序列化技术：JSON、BSON、Thrift、Avro、Google Protocol Buffers NoSql：ScyllaDB（宣称是世界上最快的NoSql）、Apache Casandra、MongoDB、Apache CouchDB、Redis、BigTable、HBase、Hypertable、Voldemort、Neo4j MapReduce相关：Hive、Pig、Cascading、Cascalog、mrjob、Caffeine、S4、MapR、Acunu、Flume、Kafka、Azkaban、Oozie、Greenplum 数据处理：R、Yahoo! Pipes、Mechanical Turk、Solr/ Lucene、ElasticSearch、Datameer、Bigsheets、Tinkerpop NLP自然语言处理：Natural Language Toolkit、Apache OpenNLP、Boilerpipe、OpenCalais 机器学习：TensorFlow（Google出品），WEKA、Mahout、scikits.learn、SkyTree 可视化技术：GraphViz、Processing、Protovis、Google Fusion Tables、Tableau、Highcharts、EChats（百度的还不错）、Raphaël.js Kettle：开源的ETL工具 Pentaho：以工作流为核心的开源BI系统 Mondrian：开源的Rolap服务器 Oozie：开源hadoop的工作流调度引擎，类似的还有：Azkaban 开源的数据分析可视化工具：Weka、Orange、KNIME Cobar：阿里巴巴的MySql分布式中间件 数据清洗：data wrangler， Google Refine Web前端 Material Design: 谷歌出品，必属精品 Vue.js: 借鉴了Angular及React的JS框架，设计理念较为先进 GRUNT: js task runner Sea.js: js模块化 knockout.js：MVVM开发前台，绑定技术 Angular.js: 使用超动感HTML & JS开发WEB应用！ Highcharts.js, ECharts, Flot: 常用的数据可视化库 D3.js: 是一个基于JavaScript数据展示库（类似的还有P5.js） Vega: 基于D3的可视化语法 NVD3: 基于d3.js的图表库 Raw：非常不错的一款高级数据可视化工具 Rickshaw:时序图标库，可用于构建实时图表 JavaScript InfoVis Toolkit：另一款Web数据可视化插件 Pdf.js，在html中展现pdf ACE，CodeMirror：Html代码编辑器（ACE甚好啊） NProcess：绚丽的加载进度条 impress.js：让你制作出令人眩目的内容展示效果(类似的还有reveal) Threejs：3DWeb库 Hightopo：基于Html5的2D、3D可视化UI库 jQuery.dataTables.js:高度灵活的表格插件 Raphaël：js，canvas绘图库，后来发现百度指数的图形就是用它绘出来的 director.js：js路由模块，前端路由，Nodejs后端路由等，适合构造单页应用 pace.js：页面加载进度条 bower：Web包管理器 jsnice：有趣的js反编译工具，猜压缩后的变量名，http://www.jsnice.org/ Zepto.js：移动端替代jQuery的东东，当然也可以使用jquery-mobile. UI框架：Foundation，Boostrap，Pure，EasyUI，Polymer 前段UI设计师必去的几个网站：Dribbble，awwwards，unmatchedstyle，UIMaker Mozilla 开发者中心：https://developer.mozilla.org/en-US/ 图标资源：IcoMoon（我的最爱），Font Awesome, Themify Icons，FreePik，Glyphicons artDialog:非常漂亮的对话框 AdminLTE：github上的一个开源项目，基于Boostrap3的后台管理页面框架 Respond.js：让不懂爱的IE6-8支持响应式设计 require.js: js模块加载库 select2：比chosen具有更多特性的选择框替代库 AngularUI：集成angular.js的UI库 normalize.css: 采用了现代化标准让各浏览器渲染出的html保持一致的库 CreateJS：Html5游戏引擎 Less,Compass:简化CSS开发 emojify.js:用于自动识别网页上的Emoji文字并将其显示为图像 simditor:一个不错的开源的html编辑器，简洁高效 Sencha: 基于html5的移动端开发框架 SuperScrollorama+TweenMax+skrollr:打造超酷的视差滚动效果网页动画 jquery-smooth-scroll:同上，平滑滚动插件 Animate.css:实现了各种动画效果的css库 Emmet:前端工程师必备，前身为 Zen Coding React: facebook出品的js UI库 highlight.js：专门用来做语法高亮的库 GoJS: Html5交互式图表库，看demo更适合层次结构的图表。 10 Pure CSS (Mostly) Flat Mobile Devices: http://marvelapp.github.io/devices.css/ CodePen: http://codepen.io/ jsfiddle: http://jsfiddle.net/ 前端js，html，css测试利器 语言篇 折腾中：Scala、Python、Lua、JavaScript、Go 待折腾： Racket OCaml Rust Julia Scala Scala Standard Library API Scala School!: A Scala tutorial by Twitter A Tour of Scala: Tutorial introducing the main concepts of Scala Scala Overview on StackOverflow: A list of useful questions sorted by topic Programming in Scala，最新的第3版，还没有电子版，电子版是第一版 《Scala for the Impatient》 《Scala in Depth》 《Programming Scala》Dean Wampler and Alex Payne. O’Reilly 2009 Scala By Example Scala Cheatsheet学习模式匹配的好资料 Glossary of Scala and FP terms Metascala: A JVM written in Scala LMS: Program Generation and Embedded Compilers in Scala parboiled2: 性能很好的parser Java 常用的IDE：IntelliJ IDEA(强烈推荐)，Eclipse，Netbeans fastutil: 性能更好的Java集合框架 Guava: 谷歌的Java工具包，应用广泛 Lagom: 微服务框架，提供了Java、Scala API Curator：Netflix公司开源的一个Zookeeper client library，用于简化Zookeeper客户端编程，现在已经是apache下的一个独立项目了。Spark的HA也用的这货。 Rx(Reactive Extensions)框架：Vert.x, RxJava(Android中用的比较多), Quasar FindBugs: 代码静态分析工具，找出代码缺陷 Java反编译工具：Luyten，JD-Gui Drools: 规则引擎 Jersey: Java RESTful 框架 canal: 阿里巴巴出品，binlog增量订阅&消费组件 Web开发相关：Tomcat、Resin、Jetty、WebLogic等，常用的组件Struts，Spring，Hibernate Netty: 异步事件驱动网络应用编程框架，用于高并发网络编程比较好（NIO框架，spark 1.2.0就用netty替代了nio） MINA：简单地开发高性能和高可靠性的网络应用程序（也是个NIO框架），不少手游服务端是用它开发的 jOOQ：java Orm框架 Janino: 超级小又快的Java编译器，Spark的Tungsten引起用的它 Activiti:工作流引擎，类似的还有jBPM、Snaker Perfuse:是一个用户界面包用来把有结构与无结构数据以具有交互性的可视化图形展示出来. Gephi:复杂网络分析软件, 其主要用于各种网络和复杂系统，动态和分层图的交互可视化与探测开源工具 Nutch:知名的爬虫项目，hadoop就是从这个项目中发展出来的 web-harvest：Web数据提取工具 POM工具：Maven+Artifactory Akka:一款基于actor模型实现的 并发处理框架 EclEmma：覆盖测试工具 Shiro:安全框架 joda-time:简化时间处理 parboiled:表达式解析 dozer: 深拷贝神器 dubbo: 阿里巴巴出品的分布式服务框架 jackson databind: json序列化工具(fastjson,simplejson) Atomikos: 分布式事务管理 BoneCP：性能很赞的数据库连接池组件，据说比c3p0快好多 ProGuard: obconfuscation tool, 强大的混淆工具 S-99：Scala相关的99个问题 Python PyCharm：最佳Python IDE Eric,Eclipse+pydev,比较不错的Python IDE PyWin:Win32 api编程包 numpy:科学计算包，主要用来处理大型矩阵计算等，此外还有SciPy，Matplotlib GUI相关：PyQt，PyQwt supervisor:进程监控工具 PyGame: 基于Python的多媒体开发和游戏软件开发模块 Web框架: Django 开源web开发框架，它鼓励快速开发,并遵循MVC设计 Swift Swift精选资料 43个优秀的开源项目 客户端 糗事百科 Swift HackerNews Swift 知乎日报app Framework Twitter框架 Mac下简单HTTP Server Swifter 小工具 Swift Alarm Swift Note Swift RSS Reader Swift-PM2.5查询app 游戏 Flappy Swift FanFan Swift .NET Xilium.CefGlue:基于CEF框架的.NET封装，基于.NET开发Chrome内核浏览器 CefSharp：同上，有一款WebKit的封装，C#和Js交互会更简单 netz:免费的 .NET 可执行文件压缩工具 SmartAssembly:变态的.net代码优化混淆工具 NETDeob0：.net反混淆工具，真是魔高一尺道高一丈啊(还有个de4dot，在GitHub上，都是开源的) ILMerge：将所有引用的DLL和exe文件打成一个exe文件 ILSpy:开源.net程序反编译工具 Javascript.NET：很不错的js执行引擎，对v8做了封装 NPOI: Excel操作 DotRAS:远程访问服务的模块 WinHtmlEditor: Winform下的html编辑器 SmartThreadPool:使用C#实现的，带高级特性的线程池 Snoop: WPF Spy Utility Autofac: 轻量级IoC框架 HtmlAgilityPack：Html解析利器 Quartz.NET：Job调度 HttpLib：@CodePlex，简化http请求 SuperSocket：简化Socket操作，基于他的还有个SuperWebSocket，可以开发独立的WebSocket服务器了 DocX：未安装Office的情况下操作Word文件 Dapper：轻量级的ORM类，性能不错 HubbleDotNet：支持接入数据库的全文搜索系统 fastJSON：@CodeProject，高性能的json序列化类 ZXing.NET：@CodePlex，QR，条形码相关 Nancy：轻量级Http服务器，做个小型的Web应用可以摆脱IIS喽(Nancy.Viewengines.Razor,可以加入Razor引擎) AntiXSS：微软的XSS防御库Microsoft Web Protection Library Jint：JavaScript解释器 CS-Script：将C#代码文件作为脚本执行 Jexus：Linux下 高性能、易用、免费的ASP.NET服务器 Clay：将dynamic发挥的更加灵活，像写js一样写C# DynamicJSON：不必定义数据模型获取json数据 SharpPcap：C#版的WinPcap调用端，牛逼的网络包分析库（自带PacketNotNet用于包协议分析） Roslyn：C#，VB编译器 ImageResizer: 服务端自由控制图片大小，真乃神器也，对手机端传小图，PC端传大图，CMS用它很方便 UI相关：DevExpress, Fluent(Office 07风格), mui（Modern UI for WPF） NetSparkle：应用自动更新组件 ConfuserEx: 开源.net混淆工具 ServiceStack: 开源高性能Web服务框架，可用于构建高性能的REST服务 Expression Evaluator：Eval for C#,处理字符串表达式 http://nugetmusthaves.com/ Reactive Extensions (Rx):异步，事件驱动编程包， Rx = Observables + LINQ + Schedulers C & C++ Thrift:用来进行可扩展且跨语言的服务的开发(类似的还有个Avro，Google protobuf)。 libevent:是一个事件触发的网络库，适用于windows、linux、bsd等多种平台，内部使用select、epoll、kqueue等系统调用管理事件机制。（对了还有个libev呢） Boost:不多说了，准C++标准库 Valgrind\Ptmalloc\Purify: 调试工具 NetworkServer架构：acceptor->dispatcher->worker(这个不算工具哦) POCO - 开源的C++类库及应用程序框架的集合,它主要提供简单的、快速的网络和可移植应用程序 breakpad:崩溃转储和分析模块，很多crashreport会用到 UI界面相关：MFC、BCG和QT这类的就不说了，高端一点的还有Html和DirectUI技术：libcef（基于chrome内核的，想想使用html5开发页面，还真有点小激动呢）、HtmlLayout、Duilib、Bolt，非C++的，还有node-webkit也不错，集成了node和webkit内核。 其他 游戏开发相关 MINA：使用Java开发手游和页游服务器(对了还有Netty，也很猛的，都是基于NIO的) HP-Socket：见有有些页游服务器使用这个构建的 Unreal: 虚幻引擎，C++，基于这个引擎的游戏很多 OGRE：大名鼎鼎的3D图形渲染引擎，天龙八部OL、火炬之光等不少游戏都用了这个引擎 OpenVDB：梦工厂C++的特效库，开源的 cocos2d：跨平台2D游戏引擎 unity3d：跨平台3D游戏引擎，很火的哦 Nodejs：也有不少使用它来开发手游和页游服务器（网易的Pomelo） 日志聚合，分布式日志收集 Scribe：Facebook的（nodejs + scribe + inotify 同步日志） logstash:强大的日志收集系统，可以基于logstash+kibana+elasticsearch+redis开发强大的日志分析平台 log.io: nodejs开发的实时日志收集系统 Graylog: 易用、功能丰富的日志管理系统， 部署、维护、搜索比ELK简单 RTP,实时传输协议与音视频 RTP，RTCP，RTSP-> librtp，JRTPLIB(遵循了RFC1889标准) 环形缓冲区，实时数据传输用 SDL,ffmpeg,live555,Speex Red5:用Java开发开源的Flash流媒体服务器。它支持：把音频（MP3）和视频（FLV）转换成播放流； 录制客户端播放流（只支持FLV）；共享对象；现场直播流发布；远程调用。 转自:stanzhai
数据仓库 数据仓库，英文名称为Data Warehouse，可简写为DW或DWH。是一种资讯系统的资料储存理论，此理论强调利用某些特殊资料储存方式，让所包含的资料，特别有利于分析处理，以产生有价值的资讯并依此作决策。 利用数据仓库方式所存放的资料，具有一但存入，便不随时间而更动的特性，同时存入的资料必定包含时间属性，通常一个数据仓库皆会含有大量的历史性资料，并利用特定分析方式，自其中发掘出特定资讯。 数据仓库的特性 主题导向（Subject-Oriented） 有别于一般OLTP系统，数据仓库的资料模型设计，着重将资料按其意义归类至相同的主题区（subject area），因此称为主题导向。举例如Party、Arrangement、Event、Product等。 集成性（Integrated） 资料来自企业各OLTP系统，在数据仓库中是集成过且一致的。 时间差异性（Time-Variant） 资料的变动，在数据仓库中是能够被纪录以及追踪变化的，有助于能反映出能随着时间变化的资料轨迹。 不变动性（Nonvolatile） 资料一旦确认写入后是不会被取代或删除的，即使资料是错误的亦同。（i.e.错误的后续修正，便可因上述时间差异性的特性而被追踪） ETL ETL，是英文 Extract-Transform-Load 的缩写，用来描述将数据从来源端经过抽取（extract）、转换（transform）、加载（load）至目的端的过程。ETL一词较常用在数据仓库，但其对象并不限于数据仓库。 ETL是构建数据仓库的重要一环，用户从数据源抽取出所需的数据，经过数据清洗,最终按照预先定义好的数据仓库模型，将数据加载到数据仓库中去。 BI BI（Business Intelligence）即商务智能 广义上讲，BI包括ETL, DW和相应的Reporting System. 因为现在一般的公司动不动说上个BI系统，都是要从DW建模开始做，然后做ETL，最后做对应的Reporting System. 虽然最终领导们只看到了他们想要的报表，但是这一套系统是需要DW和ETL的支持的。 狭义的BI就仅仅指Reporting System, 就是基于DW设计的报表系统，是领导们想要看的报表的展现。通过DW中的维度表和事实表，来从不同的维度看领导想要的数据。比如大中华区销售了多少，每个省的KPI怎么样等等。常用的工具有OBIEE，BO，Cognos等等。 OLTP 联机事务处理OLTP（on-line transaction processing） 主要是执行基本日常的事务处理，比如数据库记录的增删查改。比如在银行的一笔交易记录，就是一个典型的事务。 OLTP的特点一般有： 实时性要求高。我记得之前上大学的时候，银行异地汇款，要隔天才能到账，而现在是分分钟到账的节奏，说明现在银行的实时处理能力大大增强。 数据量不是很大，生产库上的数据量一般不会太大，而且会及时做相应的数据处理与转移。 交易一般是确定的，比如银行存取款的金额肯定是确定的，所以OLTP是对确定性的数据进行存取 高并发，并且要求满足ACID原则。比如两人同时操作一个银行卡账户，比如大型的购物网站秒杀活动时上万的QPS请求。 OLAP 联机分析处理OLAP（On-Line Analytical Processing） 是数据仓库系统的主要应用，支持复杂的分析操作，侧重决策支持，并且提供直观易懂的查询结果。典型的应用就是复杂的动态的报表系统。 OLAP的特点一般有： 实时性要求不是很高，比如最常见的应用就是天级更新数据，然后出对应的数据报表。 数据量大，因为OLAP支持的是动态查询，所以用户也许要通过将很多数据的统计后才能得到想要知道的信息，例如时间序列分析等等，所以处理的数据量很大; OLAP系统的重点是通过数据提供决策支持，所以查询一般都是动态，自定义的。所以在OLAP中，维度的概念特别重要。一般会将用户所有关心的维度数据，存入对应数据平台。 总结： OLTP即联机事务处理，就是我们经常说的关系数据库，增删查改就是我们经常应用的东西，这是数据库的基础；TPCC(Transaction Processing Performance Council)属于此类。 OLAP即联机分析处理，是数据仓库的核心部心，所谓数据仓库是对于大量已经由OLTP形成的数据的一种分析型的数据库，用于处理商业智能、决策支持等重要的决策信息；数据仓库是在数据库应用到一定程序之后而对历史数据的加工与分析，读取较多，更新较少，TPCH属于此类。 随着大数据时代的到来，对于OLAP，列存储模式或者说nosql模式比传统意义的行存储模式可能更具优势。 ACID ACID，指数据库事务正确执行的四个基本要素的缩写。包含：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）。一个支持事务（Transaction）的数据库，必需要具有这四种特性，否则在事务过程（Transaction processing）当中无法保证数据的正确性，交易过程极可能达不到交易方的要求。 原子性 整个事务中的所有操作，要么全部完成，要么全部不完成，不可能停滞在中间某个环节。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。 一致性 一个事务可以封装状态改变（除非它是一个只读的）。事务必须始终保持系统处于一致的状态，不管在任何给定的时间并发事务有多少。 也就是说：如果事务是并发多个，系统也必须如同串行事务一样操作。其主要特征是保护性和不变性(Preserving an Invariant)，以转账案例为例，假设有五个账户，每个账户余额是100元，那么五个账户总额是500元，如果在这个5个账户之间同时发生多个转账，无论并发多少个，比如在A与B账户之间转账5元，在C与D账户之间转账10元，在B与E之间转账15元，五个账户总额也应该还是500元，这就是保护性和不变性 隔离性 隔离状态执行事务，使它们好像是系统在给定时间内执行的唯一操作。如果有两个事务，运行在相同的时间内，执行相同的功能，事务的隔离性将确保每一事务在系统中认为只有该事务在使用系统。这种属性有时称为串行化，为了防止事务操作间的混淆，必须串行化或序列化请求，使得在同一时间仅有一个请求用于同一数据。 持久性 在事务完成以后，该事务对数据库所作的更改便持久的保存在数据库之中，并不会被回滚。 由于一项操作通常会包含许多子操作，而这些子操作可能会因为硬件的损坏或其他因素产生问题，要正确实现ACID并不容易。ACID建议数据库将所有需要更新以及修改的资料一次操作完毕，但实际上并不可行。 目前主要有两种方式实现ACID：第一种是Write ahead logging，也就是日志式的方式(现代数据库均基于这种方式)。第二种是Shadow paging。 相对于WAL（write ahead logging）技术，shadow paging技术实现起来比较简单，消除了写日志记录的开销恢复的速度也快(不需要redo和undo)。shadow paging的缺点就是事务提交时要输出多个块，这使得提交的开销很大，而且以块为单位，很难应用到允许多个事务并发执行的情况——这是它致命的缺点。 WAL 的中心思想是对数据文件 的修改（它们是表和索引的载体）必须是只能发生在这些修改已经 记录了日志之后 -- 也就是说，在日志记录冲刷到永久存储器之后． 如果我们遵循这个过程，那么我们就不需要在每次事务提交的时候 都把数据页冲刷到磁盘，因为我们知道在出现崩溃的情况下， 我们可以用日志来恢复数据库：任何尚未附加到数据页的记录 都将先从日志记录中重做（这叫向前滚动恢复，也叫做 REDO） 然后那些未提交的事务做的修改将被从数据页中删除 （这叫向后滚动恢复 - UNDO）。 QPS 每秒查询率(Query Per Second)是对一个特定的查询服务器在规定时间内所处理流量多少的衡量标准。 临界区 临界区指的是一个访问共用资源（例如：共用设备或是共用存储器）的程序片段，而这些共用资源又无法同时被多个线程访问的特性。当有线程进入临界区段时，其他线程或是进程必须等待（例如：bounded waiting 等待法），有一些同步的机制必须在临界区段的进入点与离开点实现，以确保这些共用资源是被互斥获得使用，例如：semaphore。只能被单一线程访问的设备，例如：打印机。 javaCC 一个能生成语法和词法分析器的生成程序 ast Abstract Syntax Trees
Problem : 费解的开关 题目来源:06年NOIp模拟赛（一） by Matrix67 第四题 问题描述 你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态 10111 01101 10111 10000 11011 在改变了最左上角的灯的状态后将变成： 01111 11101 10111 10000 11011 再改变它正中间的灯后状态将变成： 01111 11001 11001 10100 11011 给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。 输入格式 第一行有一个正整数n，代表数据中共有n个待解决的游戏初始状态。 以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。 对于30%的数据，n<=5； 对于100%的数据，n<=500。 输出格式 输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。 对于某一个游戏初始状态，若6步以内无法使所有灯变亮，请输出“-1”。 样例输入 3 00111 01011 10001 11010 11100 11101 11101 11110 11111 11111 01111 11111 11111 11111 11111 样例输出 3 2 -1 程序代码 const BigPrime=3214567; MaxStep=6; type pointer=^rec; rec=record v:longint; step:integer; next:pointer; end; var total:longint; hash:array[0..BigPrime-1]of pointer; q:array[1..400000]of rec; function update(a:longint;p:integer):longint; begin a:=a xor (1 shl p); if p mod 5<>0 then a:=a xor (1 shl (p-1)); if (p+1) mod 5<>0 then a:=a xor (1 shl (p+1)); if p<20 then a:=a xor (1 shl (p+5)); if p>4 then a:=a xor (1 shl (p-5)); exit(a); end; function find(a:longint;step:integer):boolean; var now:pointer; begin now:=hash[a mod BigPrime]; while now<>nil do begin if now^.v=a then exit(true); now:=now^.next; end; new(now); now^.v:=a; now^.step:=step; now^.next:=hash[a mod BigPrime]; hash[a mod BigPrime]:=now; total:=total+1; exit(false); end; procedure solve; var p:integer; close:longint=0; open:longint=1; begin find(1 shl 25-1,0); q[1].v:=1 shl 25-1; q[1].step:=0; repeat inc(close); for p:=0 to 24 do if not find(update(q[close].v,p),q[close].step+1) and (q[close].step+1<MaxStep) then begin open:=open+1; q[open].v:=update(q[close].v,p); q[open].step:=q[close].step+1; end; until close>=open; end; procedure print(a:longint); var now:pointer; begin now:=hash[a mod BigPrime]; while now<>nil do begin if now^.v=a then begin writeln(now^.step); exit; end; now:=now^.next; end; writeln(-1); end; procedure main; var ch:char; i,j,n:integer; t:longint; begin readln(n); for i:=1 to n do begin t:=0; for j:=1 to 25 do begin read(ch); t:=t*2+ord(ch)-48; if j mod 5=0 then readln; end; print(t); if i<n then readln; end; end; begin solve; main; end. Problem : garden / 和MM逛花园 题目来源:07年Matrix67生日邀请赛第四题 问题描述 花园设计强调，简单就是美。Matrix67常去的花园有着非常简单的布局：花园的所有景点的位置都是“对齐”了的，这些景点可以看作是平面坐标上的格点。相邻的景点之间有小路相连，这些小路全部平行于坐标轴。景点和小路组成了一个“不完整的网格”。 一个典型的花园布局如左图所示。花园布局在6行4列的网格上，花园的16个景点的位置用红色标注在了图中。黑色线条表示景点间的小路，其余灰色部分实际并不存在。 Matrix67 的生日那天，他要带着他的MM在花园里游玩。Matrix67不会带MM两次经过同一个景点，因此每个景点最多被游览一次。他和他的MM边走边聊，他们是如此的投入以致于他们从不会“主动地拐弯”。也就是说，除非前方已没有景点或是前方的景点已经访问过，否则他们会一直往前走下去。当前方景点不存在或已游览过时，Matrix67会带MM另选一个方向继续前进。由于景点个数有限，访问过的景点将越来越多，迟早会出现不能再走的情况（即四个方向上的相邻景点都访问过了），此时他们将结束花园的游览。Matrix67希望知道以这种方式游览花园是否有可能遍历所有的景点。Matrix67可以选择从任意一个景点开始游览，以任意一个景点结束。 在上图所示的花园布局中，一种可能的游览方式如右图所示。这种浏览方式从(1,2)出发，以(2,4)结束，经过每个景点恰好一次。 输入格式 第一行输入两个用空格隔开的正整数m和n，表示花园被布局在m行n列的网格上。 以下m行每行n个字符，字符“0”表示该位置没有景点，字符“1”表示对应位置有景点。这些数字之间没有空格。 输出格式 你的程序需要寻找满足“不主动拐弯”性质且遍历所有景点的游览路线。 如果没有这样的游览路线，请输出一行“Impossible”（不带引号，注意大小写）。 如果存在游览路线，请依次输出你的方案中访问的景点的坐标，每行输出一个。坐标的表示格式为“(x,y)”，代表第x行第y列。 如果有多种方案，你只需要输出其中一种即可。评测系统可以判断你的方案的正确性。 样例输入 6 4 1100 1001 1111 1100 1110 1110 样例输出 (1,2) (1,1) (2,1) (3,1) (4,1) (5,1) (6,1) (6,2) (6,3) (5,3) (5,2) (4,2) (3,2) (3,3) (3,4) (2,4) 数据规模 对于30%的数据，n,m<=5； 对于100%的数据，n,m<=10。 程序代码： program garden; const dir:array[1..4,1..2]of integer= ((1,0),(0,1),(-1,0),(0,-1)); type arr=array[1..10]of integer; rec=record x,y:integer;end; var map:array[0..11,0..11]of boolean; ans:array[1..100]of rec; n,m,max:integer; step:integer=1; state:arr; procedure readp; var i,j:integer; ch:char; begin readln(m,n); for i:=1 to n do begin for j:=1 to m do begin read(ch); map[i,j]:=(ch='1'); inc(max,ord( map[i,j] )) end; readln; end; end; procedure writep; var i:integer; begin for i:=1 to step do writeln( '(' , ans[i].x , ',' , ans[i].y , ')' ); end; procedure solve(x,y:integer); var tx,ty,d:integer; step_cache:integer; state_cache:arr; begin step_cache:=step; state_cache:=state; if step=max then begin writep; exit; end; for d:=1 to 4 do begin tx:=x+dir[d,1]; ty:=y+dir[d,2]; while map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do begin inc(step); ans[step].x:=tx; ans[step].y:=ty; state[tx]:=state[tx] or ( 1 shl (ty-1) ); tx:=tx+dir[d,1]; ty:=ty+dir[d,2]; end; tx:=tx-dir[d,1]; ty:=ty-dir[d,2]; if (tx<>x) or (ty<>y) then solve(tx,ty); state:=state_cache; step:=step_cache; end; end; {====main====} var i,j:integer; begin assign(input,'garden.in'); reset(input); assign(output,'garden.out'); rewrite(output); readp; for i:=1 to n do for j:=1 to m do if map[i,j] then begin ans[1].x:=i; ans[1].y:=j; state[i]:=1 shl (j-1); solve(i,j); state[i]:=0; end; close(input); close(output); end. Problem : cowfood / 玉米地 题目来源:USACO月赛 问题描述 农夫约翰购买了一处肥沃的矩形牧场，分成M*N(1<=M<=12; 1<=N<=12)个格子。他想在那里的一些格子中种植美味的玉米。遗憾的是，有些格子区域的土地是贫瘠的，不能耕种。 精明的约翰知道奶牛们进食时不喜欢和别的牛相邻，所以一旦在一个格子中种植玉米，那么他就不会在相邻的格子中种植，即没有两个被选中的格子拥有公共边。他还没有最终确定哪些格子要选择种植玉米。 作为一个思想开明的人，农夫约翰希望考虑所有可行的选择格子种植方案。由于太开明，他还考虑一个格子都不选择的种植方案！请帮助农夫约翰确定种植方案总数。 输入格式: 第一行：两个用空格分隔的整数M和N 第二行到第M+1行：第i+1行描述牧场第i行每个格子的情况，N个用空格分隔的整数，表示这个格子是否可以种植（1表示肥沃的、适合种植，0表示贫瘠的、不可种植） 输出格式 一个整数，农夫约翰可选择的方案总数除以 100,000,000 的余数 样例输入 2 3 1 1 1 0 1 0 样例输出 9 样例说明 给可以种植玉米的格子编号： 1 2 3 4 只种一个格子的方案有四种(1,2,3或4)，种植两个格子的方案有三种(13,14或34)，种植三个格子的方案有一种(134)，还有一种什么格子都不种。 4+3+1+1=9。 数据规模 对于30%的数据，N,M<=4； 对于100%的数据，N,M<=12。 程序代码： program cowfood; const d=100000000; MaxN=12; var f:array[0..MaxN,1..2000]of longint; w:array[1..2000,1..2000]of boolean; st:array[0..2000]of integer; map:array[0..MaxN]of integer; m,n:integer; function Impossible(a:integer):boolean; var i:integer; flag:boolean=false; begin for i:=1 to MaxN do begin if flag and (a and 1=1) then exit(true); flag:=(a and 1=1); a:=a shr 1; end; exit(false); end; function Conflict(a,b:integer):boolean; var i:integer; begin for i:=1 to MaxN do begin if (a and 1=1) and (b and 1=1) then exit(true); a:=a shr 1; b:=b shr 1; end; exit(false); end; function CanPlace(a,b:integer):boolean; begin exit(a or b=b); end; procedure FindSt; var i:integer; begin for i:=0 to 1 shl MaxN-1 do if not Impossible(i) then begin inc(st[0]); st[st[0]]:=i; end; end; procedure Init; var i,j:integer; begin for i:=1 to st[0] do for j:=i to st[0] do if not Conflict(st[i],st[j]) then begin w[i,j]:=true; w[j,i]:=true; end; end; procedure Readp; var i,j,t,v:integer; begin readln(m,n); for i:=1 to m do begin v:=0; for j:=1 to n do begin read(t); v:=v*2+t; end; map[i]:=v; readln; end; end; procedure Solve; var i,j,k:integer; begin f[0,1]:=1; map[0]:=1 shl n-1; for i:=1 to m do for j:=1 to st[0] do if not CanPlace(st[j],map[i]) then f[i,j]:=-1 else for k:=1 to st[0] do if (f[i-1,k]<>-1) and w[j,k] then f[i,j]:=(f[i,j]+f[i-1,k]) mod d; end; procedure Writep; var j:integer; ans:longint=0; begin for j:=1 to st[0] do if f[m,j]<>-1 then ans:=(ans+f[m,j]) mod d; writeln(ans); end; begin assign(input,'cowfood.in'); reset(input); assign(output,'cowfood.out'); rewrite(output); FindSt; Init; Readp; Solve; Writep; close(input); close(output); end.
n皇后问题位运算版 n皇后问题是啥我就不说了吧，学编程的肯定都见过。下面的十多行代码是n皇后问题的一个高效位运算程序，看到过的人都夸它牛。初始时，upperlim:=(1 shl n)-1。主程序调用test(0,0,0)后sum的值就是n皇后总的解数。拿这个去交USACO，0.3s，暴爽。 procedure test(row,ld,rd:longint); var pos,p:longint; begin { 1} if row<>upperlim then { 2} begin { 3} pos:=upperlim and not (row or ld or rd); { 4} while pos<>0 do { 5} begin { 6} p:=pos and -pos; { 7} pos:=pos-p; { 8} test(row+p,(ld+p)shl 1,(rd+p)shr 1); { 9} end; {10} end {11} else inc(sum); end; 乍一看似乎完全摸不着头脑，实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟，实在没研究出来再看下面的解说。 和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6×6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。前面说过-a相当于not a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。 Gray码 假如我有4个潜在的GF，我需要决定最终到底和谁在一起。一个简单的办法就是，依次和每个MM交往一段时间，最后选择给我带来的“满意度”最大的MM。但看了dd牛的理论后，事情开始变得复杂了：我可以选择和多个MM在一起。这样，需要考核的状态变成了2^4=16种（当然包括0000这一状态，因为我有可能是玻璃）。现在的问题就是，我应该用什么顺序来遍历这16种状态呢？ 传统的做法是，用二进制数的顺序来遍历所有可能的组合。也就是说，我需要以0000->0001->0010->0011->0100->…->1111这样的顺序对每种状态进行测试。这个顺序很不科学，很多时候状态的转移都很耗时。比如从0111到1000时我需要暂时甩掉当前所有的3个MM，然后去把第4个MM。同时改变所有MM与我的关系是一件何等巨大的工程啊。因此，我希望知道，是否有一种方法可以使得，从没有MM这一状态出发，每次只改变我和一个MM的关系（追或者甩），15次操作后恰好遍历完所有可能的组合（最终状态不一定是1111）。大家自己先试一试看行不行。 解决这个问题的方法很巧妙。我们来说明，假如我们已经知道了n=2时的合法遍历顺序，我们如何得到n=3的遍历顺序。显然，n=2的遍历顺序如下： 00 01 11 10 你可能已经想到了如何把上面的遍历顺序扩展到n=3的情况。n=3时一共有8种状态，其中前面4个把n=2的遍历顺序照搬下来，然后把它们对称翻折下去并在最前面加上1作为后面4个状态： 000 001 011 010 ↑ ——– 110 ↓ 111 101 100 用这种方法得到的遍历顺序显然符合要求。首先，上面8个状态恰好是n=3时的所有8种组合，因为它们是在n=2的全部四种组合的基础上考虑选不选第3个元素所得到的。然后我们看到，后面一半的状态应该和前面一半一样满足“相邻状态间仅一位不同”的限制，而“镜面”处则是最前面那一位数不同。再次翻折三阶遍历顺序，我们就得到了刚才的问题的答案： 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 这种遍历顺序作为一种编码方式存在，叫做Gray码（写个中文让蜘蛛来抓：格雷码）。它的应用范围很广。比如，n阶的Gray码相当于在n维立方体上的Hamilton回路，因为沿着立方体上的边走一步，n维坐标中只会有一个值改变。再比如，Gray码和Hanoi塔问题等价。Gray码改变的是第几个数，Hanoi塔就该移动哪个盘子。比如，3阶的Gray码每次改变的元素所在位置依次为1-2-1-3-1-2-1，这正好是3阶Hanoi塔每次移动盘子编号。如果我们可以快速求出Gray码的第n个数是多少，我们就可以输出任意步数后Hanoi塔的移动步骤。现在我告诉你，Gray码的第n个数（从0算起）是n xor (n shr 1)，你能想出来这是为什么吗？先自己想想吧。 下面我们把二进制数和Gray码都写在下面，可以看到左边的数异或自身右移的结果就等于右边的数。 二进制数 Gray码 000 000 001 001 010 011 011 010 100 110 101 111 110 101 111 100 从二进制数的角度看，“镜像”位置上的数即是对原数进行not运算后的结果。比如，第3个数010和倒数第3个数101的每一位都正好相反。假设这两个数分别为x和y，那么x xor (x shr 1)和y xor (y shr 1)的结果只有一点不同：后者的首位是1，前者的首位是0。而这正好是Gray码的生成方法。这就说明了，Gray码的第n个数确实是n xor (n shr 1)。 今年四月份mashuo给我看了这道题，是二维意义上的Gray码。题目大意是说，把0到2^(n+m)-1的数写成2^n * 2^m的矩阵，使得位置相邻两数的二进制表示只有一位之差。答案其实很简单，所有数都是由m位的Gray码和n位Gray码拼接而成，需要用左移操作和or运算完成。完整的代码如下： var x,y,m,n,u:longint; begin readln(m,n); for x:=0 to 1 shl m-1 do begin u:=(x xor (x shr 1)) shl n; //输出数的左边是一个m位的Gray码 for y:=0 to 1 shl n-1 do write(u or (y xor (y shr 1)),' '); //并上一个n位Gray码 writeln; end; end.
二进制中的1有奇数个还是偶数个 我们可以用下面的代码来计算一个32位整数的二进制中1的个数的奇偶性，当输入数据的二进制表示里有偶数个数字1时程序输出0，有奇数个则输出1。例如，1314520的二进制101000000111011011000中有9个1，则x=1314520时程序输出1。 var i,x,c:longint; begin readln(x); c:=0; for i:=1 to 32 do begin c:=c + x and 1; x:=x shr 1; end; writeln( c and 1 ); end. 但这样的效率并不高，位运算的神奇之处还没有体现出来。 同样是判断二进制中1的个数的奇偶性，下面这段代码就强了。你能看出这个代码的原理吗？ var x:longint; begin readln(x); x:=x xor (x shr 1); x:=x xor (x shr 2); x:=x xor (x shr 4); x:=x xor (x shr 8); x:=x xor (x shr 16); writeln(x and 1); end. 为了说明上面这段代码的原理，我们还是拿1314520出来说事。1314520的二进制为101000000111011011000，第一次异或操作的结果如下： 00000000000101000000111011011000 XOR 0000000000010100000011101101100 --------------------------------------- 00000000000111100000100110110100 得到的结果是一个新的二进制数，其中右起第i位上的数表示原数中第i和i+1位上有奇数个1还是偶数个1。比如，最右边那个0表示原数末两位有偶数个1，右起第3位上的1就表示原数的这个位置和前一个位置中有奇数个1。对这个数进行第二次异或的结果如下： 00000000000111100000100110110100 XOR 000000000001111000001001101101 --------------------------------------- 00000000000110011000101111011001 结果里的每个1表示原数的该位置及其前面三个位置中共有奇数个1，每个0就表示原数对应的四个位置上共偶数个1。一直做到第五次异或结束后，得到的二进制数的最末位就表示整个32位数里有多少个1，这就是我们最终想要的答案。 计算二进制中的1的个数 同样假设x是一个32位整数。经过下面五次赋值后，x的值就是原数的二进制表示中数字1的个数。比如，初始时x为1314520（网友抓狂：能不能换一个数啊），那么最后x就变成了9，它表示1314520的二进制中有9个1。 x := (x and $55555555) + ((x shr 1) and $55555555); x := (x and $33333333) + ((x shr 2) and $33333333); x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F); x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF); x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF); 为了便于解说，我们下面仅说明这个程序是如何对一个8位整数进行处理的。我们拿数字211（我们班某MM的生日）来开刀。211的二进制为11010011。 +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原数 +---+---+---+---+---+---+---+---+ | 1 0 | 0 1 | 0 0 | 1 0 | <---第一次运算后 +-------+-------+-------+-------+ | 0 0 1 1 | 0 0 1 0 | <---第二次运算后 +---------------+---------------+ | 0 0 0 0 0 1 0 1 | <---第三次运算后，得数为5 +-------------------------------+ 整个程序是一个分治的思想。第一次我们把每相邻的两位加起来，得到每两位里1的个数，比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加，10+01=11，00+10=10，得到的结果是00110010，它表示原数前4位有3个1，末4位有2个1。最后一次我们把0011和0010加起来，得到的就是整个二进制中1的个数。程序中巧妙地使用取位和右移，比如第二行中$33333333的二进制为00110011001100....，用它和x做and运算就相当于以2为单位间隔取数。shr的作用就是让加法运算的相同数位对齐。 二分查找32位整数的前导0个数 这里用的C语言，我直接Copy的Hacker's Delight上的代码。这段代码写成C要好看些，写成Pascal的话会出现很多begin和end，搞得代码很难看。程序思想是二分查找，应该很简单，我就不细说了。 int nlz(unsigned x) { int n; if (x == 0) return(32); n = 1; if ((x >> 16) == 0) {n = n +16; x = x <<16;} if ((x >> 24) == 0) {n = n + 8; x = x << 8;} if ((x >> 28) == 0) {n = n + 4; x = x << 4;} if ((x >> 30) == 0) {n = n + 2; x = x << 2;} n = n - (x >> 31); return n; } 只用位运算来取绝对值 这是一个非常有趣的问题。 答案：假设x为32位整数，则x xor (not (x shr 31) + 1) + x shr 31的结果是x的绝对值，x shr 31是二进制的最高位，它用来表示x的符号。如果它为0（x为正），则not (x shr 31) + 1等于$00000000，异或任何数结果都不变；如果最高位为1（x为负），则not (x shr 31) + 1等于$FFFFFFFF，x异或它相当于所有数位取反，异或完后再加一。 高低位交换 这个题实际上是我出的，做为学校内部NOIp模拟赛的第一题。题目是这样： 给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示（不足32位用0补足）。我们称这个二进制数的前16位为“高位”，后16位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。 例如，数1314520用二进制表示为0000 0000 0001 0100 0000 1110 1101 1000（添加了11个前导0补足为32位），其中前16位为高位，即0000 0000 0001 0100；后16位为低位，即0000 1110 1101 1000。将它的高低位进行交换，我们得到了一个新的二进制数0000 1110 1101 1000 0000 0000 0001 0100。它即是十进制的249036820。 当时几乎没有人想到用一句位操作来代替冗长的程序。使用位运算的话两句话就完了。 var n:dword; begin readln( n ); writeln( (n shr 16) or (n shl 16) ); end. 而事实上，Pascal有一个系统函数swap直接就可以用。 二进制逆序 下面的程序读入一个32位整数并输出它的二进制倒序后所表示的数。 输入： 1314520 （二进制为00000000000101000000111011011000） 输出： 460335104 （二进制为00011011011100000010100000000000） var x:dword; begin readln(x); x := (x and $55555555) shl 1 or (x and $AAAAAAAA) shr 1; x := (x and $33333333) shl 2 or (x and $CCCCCCCC) shr 2; x := (x and $0F0F0F0F) shl 4 or (x and $F0F0F0F0) shr 4; x := (x and $00FF00FF) shl 8 or (x and $FF00FF00) shr 8; x := (x and $0000FFFF) shl 16 or (x and $FFFF0000) shr 16; writeln(x); end. 它的原理和刚才求二进制中1的个数那个例题是大致相同的。程序首先交换每相邻两位上的数，以后把互相交换过的数看成一个整体，继续进行以2位为单位、以4位为单位的左右对换操作。我们再次用8位整数211来演示程序执行过程： +---+---+---+---+---+---+---+---+ | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原数 +---+---+---+---+---+---+---+---+ | 1 1 | 1 0 | 0 0 | 1 1 | <---第一次运算后 +-------+-------+-------+-------+ | 1 0 1 1 | 1 1 0 0 | <---第二次运算后 +---------------+---------------+ | 1 1 0 0 1 0 1 1 | <---第三次运算后 +-------------------------------+
什么是位运算？ 程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果。由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。 各种位运算的使用 1. 与运算(&) 与运算通常用于二进制取位操作，例如一个数 & 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的最末位为0表示该数为偶数，最末位为1表示该数为奇数. 2. 或运算(|) 或运算通常用于二进制特定位上的无条件赋值，例如一个数 | 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数 | 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。 3. 异或运算(^) 异或运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。 异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(a ^ b) ^ b = a。所以异或运算可以用于简单的加密。 下面我们看另外一个东西。定义两个符号#和@，这两个符号互为逆运算，也就是说(x # y) @ y = x。现在依次执行下面三条命令，结果是什么？ x <- x # y y <- x @ y x <- x @ y 执行了第一句后x变成了x # y。那么第二句实质就是y <- x # y @ y，由于#和@互为逆运算，那么此时的y变成了原来的x。第三句中x实际上被赋值为(x # y) @ x，如果#运算具有交换律，那么赋值后x就变成最初的y了。这三句话的结果是，x和y的位置互换了。 加法和减法互为逆运算，并且加法满足交换律。把#换成+，把@换成-，我们可以写出一个不需要临时变量的swap过程： a = a + b; b = a - b; a = a - b; 好了，刚才不是说^的逆运算是它本身吗？于是我们就有了一个看起来非常诡异的swap过程： a = a ^ b; b = a ^ b; a = a ^ b; 4. 非运算(~) 非运算的定义是把内存中的0和1全部取反。使用~运算时要格外小心，你需要注意整数类型有没有符号。如果!的对象是无符号整数（不能表示负数），那么得到的值就是它与该类型上界的差，因为无符号类型的数是用0x0000到0xFFFF依次表示的。下面的程序返回65435。 #include <stdio.h> int main() { unsigned short a=100; a = ~a; printf( "%dn", a ); return 0; } 5. 左移运算(<<) a << b就表示把a转为二进制后左移b位（在后面添b个0）。例如100的二进制为1100100，而110010000转成十进制是400，那么100 << 2 = 400。可以看出，a << b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2。 通常认为a << 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。 定义一些常量可能会用到shl运算。你可以方便地用1 << 16 – 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，此时可以用shl来定义Max_N等常量。 6. 右移运算(>>) 和左移相似，a >> b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。我们也经常用>> 1来代替除2，比如二分查找、堆的插入操作等等。想办法用右移代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代替慢得出奇的取余运算，效率可以提高60%。 位运算的简单应用 有时我们的程序需要一个规模不大的Hash表来记录状态。比如，做数独时我们需要27个Hash表来统计每一行、每一列和每一个小九宫格里已经有哪些数了。此时，我们可以用27个小于2^9的整数进行记录。例如，一个只填了2和5的小九宫格就用数字18表示（二进制为000010010），而某一行的状态为511则表示这一行已经填满。需要改变状态时我们不需要把这个数转成二进制修改后再转回去，而是直接进行位操作。在搜索时，把状态表示成整数可以更好地进行判重等操作。 下面列举了一些常见的二进制位的变换操作。 功能 | 示例 | 位运算 去掉最后一位 | (101101->10110) | x >> 1 在最后加一个0 | (101101->1011010) | x << 1 在最后加一个1 | (101101->1011011) | x << 1+1 把最后一位变成1 | (101100->101101) | x | 1 把最后一位变成0 | (101101->101100) | x | 1-1 最后一位取反 | (101101->101100) | x ^ 1 把右数第k位变成1 | (101001->101101,k=3) | x | (1 << (k-1)) 把右数第k位变成0 | (101101->101001,k=3) | x & ~ (1 << (k-1)) 右数第k位取反 | (101001->101101,k=3) | x ^ (1 << (k-1)) 取末三位 | (1101101->101) | x & 7 取末k位 | (1101101->1101,k=5) | x & (1 << k-1) 取右数第k位 | (1101101->1,k=4) | x >> (k-1) & 1 把末k位变成1 | (101001->101111,k=4) | x | (1 << k-1) 末k位取反 | (101001->100110,k=4) | x ^ (1 << k-1) 把右边连续的1变成0 | (100101111->100100000) | x & (x+1) 把右起第一个0变成1 | (100101111->100111111) | x | (x+1) 把右边连续的0变成1 | (11011000->11011111) | x | (x-1) 取右边连续的1 | (100101111->1111) | (x ^ (x+1)) >> 1 去掉右起第一个1的左边 | (100101000->1000) | x & (x ^ (x-1)) 整数类型的储存 我们前面所说的位运算都没有涉及负数，都假设这些运算是在unsigned/word类型（只能表示正数的整型）上进行操作。但计算机如何处理有正负符号的整数类型呢？下面这个程序是考察16位整数的储存方式。 #include <stdio.h> int main() { short int a, b; a = 0x0000; b = 0x0001; printf( "%d %d ", a, b ); a = 0xFFFE; b = 0xFFFF; printf( "%d %d ", a, b ); a = 0x7FFF; b = 0x8000; printf( "%d %dn", a, b ); return 0; } 这个程序的输出为0 1 -2 -1 32767 -32768。其中前两个数是内存值最小的时候，中间两个数则是内存值最大的时候，最后输出的两个数是正数与负数的分界处。由此你可以清楚地看到计算机是如何储存一个整数的：计算机用0x0000到0x7FFF依次表示0到32767的数，剩下的0x8000到0xFFFF依次表示-32768到-1的数。32位有符号整数的储存方式也是类似的。稍加注意你会发现，二进制的第一位是用来表示正负号的，0表示正，1表示负。这里有一个问题：0本来既不是正数，也不是负数，但它占用了0x0000的位置，因此有符号的整数类型范围中正数个数比负数少一个。对一个有符号的数进行~运算后，最高位的变化将导致正负颠倒，并且数的绝对值会差1。也就是说，~ a实际上等于-a-1。这种整数储存方式叫做“补码”。
一. 机器数和真值 1、机器数 一个数在计算机中的二进制表示形式, 叫做这个数的机器数。机器数是带符号的，在计算机用一个数的最高位存放符号, 正数为0, 负数为1. 比如，十进制中的数 +3 , 计算机字长为8位, 转换成二进制就是00000011。如果是 -3 , 就是 10000011 。 那么，这里的 00000011 和 10000011 就是机器数。 2、真值 因为第一位是符号位，所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000011，其最高位1代表负，其真正数值是 -3 而不是形式值131（10000011转换成十进制等于131）。所以，为区别起见，将带符号位的机器数对应的真正数值称为机器数的真值。 例：0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = –000 0001 = –1 二. 原码, 反码, 补码的基础概念和计算方法 在探求为何机器要使用补码之前, 让我们先了解原码, 反码和补码的概念.对于一个数, 计算机要使用一定的编码方式进行存储. 原码, 反码, 补码是机器存储一个具体数字的编码方式. 1. 原码 原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制: [+1]原 = 0000 0001 [-1]原 = 1000 0001 第一位是符号位. 因为第一位是符号位, 所以8位二进制数的取值范围就是: [1111 1111 , 0111 1111] 即 [-127 , 127] 原码是人脑最容易理解和计算的表示方式. 2. 反码 反码的表示方法是: 正数的反码是其本身 负数的反码是在其原码的基础上, 符号位不变，其余各个位取反. [+1] = [00000001]原 = [00000001]反 [-1] = [10000001]原 = [11111110]反 可见如果一个反码表示的是负数, 人脑无法直观的看出来它的数值. 通常要将其转换成原码再计算. 3. 补码 补码的表示方法是: 正数的补码就是其本身 负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1) [+1] = [00000001]原 = [00000001]反 = [00000001]补 [-1] = [10000001]原 = [11111110]反 = [11111111]补 对于负数, 补码表示方式也是人脑无法直观看出其数值的. 通常也需要转换成原码在计算其数值. 三. 为何要使用原码, 反码和补码 现在我们知道了计算机可以有三种编码方式表示一个数. 对于正数因为三种编码方式的结果都相同: [+1] = [00000001]原 = [00000001]反 = [00000001]补 所以不需要过多解释. 但是对于负数: [-1] = [10000001]原 = [11111110]反 = [11111111]补 可见原码, 反码和补码是完全不同的. 既然原码才是被人脑直接识别并用于计算表示方式, 为何还会有反码和补码呢? 首先, 因为人脑可以知道第一位是符号位, 在计算的时候我们会根据符号位, 选择对真值区域的加减. (真值的概念在本文最开头). 但是对于计算机, 加减乘数已经是最基础的运算, 要设计的尽量简单. 计算机辨别"符号位"显然会让计算机的基础电路设计变得十分复杂! 于是人们想出了将符号位也参与运算的方法. 我们知道, 根据运算法则减去一个正数等于加上一个负数, 即: 1-1 = 1 + (-1) = 0 , 所以机器可以只有加法而没有减法, 这样计算机运算的设计就更简单了. 于是人们开始探索 将符号位参与运算, 并且只保留加法的方法. 首先来看原码: 计算十进制的表达式: 1-1=0 1 - 1 = 1 + (-1) = [00000001]原 + [10000001]原 = [10000010]原 = -2 如果用原码表示, 让符号位也参与计算, 显然对于减法来说, 结果是不正确的.这也就是为何计算机内部不使用原码表示一个数. 为了解决原码做减法的问题, 出现了反码: 计算十进制的表达式: 1-1=0 1 - 1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原= [0000 0001]反 + [1111 1110]反 = [1111 1111]反 = [1000 0000]原 = -0 发现用反码计算减法, 结果的真值部分是正确的. 而唯一的问题其实就出现在"0"这个特殊的数值上. 虽然人们理解上+0和-0是一样的, 但是0带符号是没有任何意义的. 而且会有[0000 0000]原和[1000 0000]原两个编码表示0. 于是补码的出现, 解决了0的符号以及两个编码的问题: 1-1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原 = [0000 0001]补 + [1111 1111]补 = [0000 0000]补=[0000 0000]原 这样0用[0000 0000]表示, 而以前出现问题的-0则不存在了.而且可以用[1000 0000]表示-128: (-1) + (-127) = [1000 0001]原 + [1111 1111]原 = [1111 1111]补 + [1000 0001]补 = [1000 0000]补 -1-127的结果应该是-128, 在用补码运算的结果中, [1000 0000]补 就是-128. 但是注意因为实际上是使用以前的-0的补码来表示-128, 所以-128并没有原码和反码表示.(对-128的补码表示[1000 0000]补算出来的原码是[0000 0000]原, 这是不正确的) 使用补码, 不仅仅修复了0的符号以及存在两个编码的问题, 而且还能够多表示一个最低数. 这就是为什么8位二进制, 使用原码或反码表示的范围为[-127, +127], 而使用补码表示的范围为[-128, 127]. 因为机器使用补码, 所以对于编程中常用到的32位int类型, 可以表示范围是: [-2^31, (2^31)-1] 因为第一位表示的是符号位.而使用补码表示时又可以多保存一个最小值. 四 原码, 反码, 补码 再深入 计算机巧妙地把符号位参与运算, 并且将减法变成了加法, 背后蕴含了怎样的数学原理呢? 将钟表想象成是一个1位的12进制数. 如果当前时间是6点, 我希望将时间设置成4点, 需要怎么做呢?我们可以: 往回拨2个小时: 6 - 2 = 4 往前拨10个小时: (6 + 10) mod 12 = 4 往前拨10+12=22个小时: (6+22) mod 12 =4 2,3方法中的mod是指取模操作, 16 mod 12 =4 即用16除以12后的余数是4. 所以钟表往回拨(减法)的结果可以用往前拨(加法)替代! 现在的焦点就落在了如何用一个正数, 来替代一个负数. 上面的例子我们能感觉出来一些端倪, 发现一些规律. 但是数学是严谨的. 不能靠感觉. 首先介绍一个数学中相关的概念: 同余 同余的概念 两个整数a，b，若它们除以整数m所得的余数相等，则称a，b对于模m同余 记作 a ≡ b (mod m) 读作 a 与 b 关于模 m 同余。 举例说明: 4 mod 12 = 4 16 mod 12 = 4 28 mod 12 = 4 所以4, 16, 28关于模 12 同余. 负数取模 正数进行mod运算是很简单的. 但是负数呢? 下面是关于mod运算的数学定义: x mod y = x - y⌊x/y⌋ 上面公式的意思是: x mod y等于 x 减去 y 乘上 x与y的商的下界. 以 -3 mod 2 举例: -3 mod 2 = -3 - 2x⌊-3/2⌋ = -3 - 2x⌊-1.5⌋ = -3 - 2x(-2) = -3 + 4 = 1 所以: (-2) mod 12 = 12-2=10 (-4) mod 12 = 12-4 = 8 (-5) mod 12 = 12 - 5 = 7 开始证明 再回到时钟的问题上: 回拨2小时 = 前拨10小时 回拨4小时 = 前拨8小时 回拨5小时= 前拨7小时 注意, 这里发现的规律! 结合上面学到的同余的概念.实际上: (-2) mod 12 = 10 10 mod 12 = 10 -2与10是同余的. (-4) mod 12 = 8 8 mod 12 = 8 -4与8是同余的. 距离成功越来越近了. 要实现用正数替代负数, 只需要运用同余数的两个定理: 反身性: a ≡ a (mod m) 这个定理是很显而易见的. 线性运算定理: 如果a ≡ b (mod m)，c ≡ d (mod m) 那么: (1)a ± c ≡ b ± d (mod m) (2)a c ≡ b d (mod m) 如果想看这个定理的证明, 请看:http://baike.baidu.com/view/79282.htm 所以: 7 ≡ 7 (mod 12) (-2) ≡ 10 (mod 12) 7 -2 ≡ 7 + 10 (mod 12) 现在我们为一个负数, 找到了它的正数同余数. 但是并不是7-2 = 7+10, 而是 7 -2 ≡ 7 + 10 (mod 12) , 即计算结果的余数相等. 接下来回到二进制的问题上, 看一下: 2-1=1的问题. 2-1=2+(-1) = [0000 0010]原 + [1000 0001]原= [0000 0010]反 + [1111 1110]反 先到这一步, -1的反码表示是1111 1110. 如果这里将[1111 1110]认为是原码, 则[1111 1110]原 = -126, 这里将符号位除去, 即认为是126. 发现有如下规律: (-1) mod 127 = 126 126 mod 127 = 126 即: (-1) ≡ 126 (mod 127) 2-1 ≡ 2+126 (mod 127) 2-1 与 2+126的余数结果是相同的! 而这个余数, 正式我们的期望的计算结果: 2-1=1 所以说一个数的反码, 实际上是这个数对于一个膜的同余数. 而这个膜并不是我们的二进制, 而是所能表示的最大值! 这就和钟表一样, 转了一圈后总能找到在可表示范围内的一个正确的数值! 而2+126很显然相当于钟表转过了一轮, 而因为符号位是参与计算的, 正好和溢出的最高位形成正确的运算结果. 既然反码可以将减法变成加法, 那么现在计算机使用的补码呢? 为什么在反码的基础上加1, 还能得到正确的结果? 2-1=2+(-1) = [0000 0010]原 + [1000 0001]原 = [0000 0010]补 + [1111 1111]补 如果把[1111 1111]当成原码, 去除符号位, 则: [0111 1111]原 = 127 其实, 在反码的基础上+1, 只是相当于增加了膜的值: (-1) mod 128 = 127 127 mod 128 = 127 2-1 ≡ 2+127 (mod 128) 此时, 表盘相当于每128个刻度转一轮. 所以用补码表示的运算结果最小值和最大值应该是[-128, 128]. 但是由于0的特殊情况, 没有办法表示128, 所以补码的取值范围是[-128, 127]
一．RAID定义 RAID(Redundant Array of Independent Disk 独立冗余磁盘阵列)技术是加州大学伯克利分校1987年提出，最初是为了组合小的廉价磁盘来代替大的昂贵磁盘，同时希望磁盘失效时不会使对数据的访问受损 失而开发出一定水平的数据保护技术。RAID就是一种由多块廉价磁盘构成的冗余阵列，在操作系统下是作为一个独立的大型存储设备出现。RAID可以充分发 挥出多块硬盘的优势，可以提升硬盘速度，增大容量，提供容错功能够确保数据安全性，易于管理的优点，在任何一块硬盘出现问题的情况下都可以继续工作，不会 受到损坏硬盘的影响。 二、 RAID的几种工作模式（仅讨论 RAID0，RAID1，RAID5，RAID10这四种，这四种比较典型） 1、RAID0 （又称为Stripe或Striping－－分条） 即Data Stripping数据分条技术。RAID 0可以把多块硬盘连成一个容量更大的硬盘群，可以提高磁 盘的性能和吞吐量。RAID 0没有冗余或错误修复能力，成本低，要求至少两个磁盘，一般只是在那些对数 据安全性要求不高的情况下才被使用。 2、RAID 1 （又称为Mirror或Mirroring－－镜像） RAID 1称为磁盘镜像：把一个磁盘的数据镜像到另一个磁盘上，在不影响性能情况下最大限度的保证系统的可靠性和可修复性上，具有很高的数据冗余能力，但磁盘利用 率为50%，故成本最高，多用在保存关键性的重要数据的场合。RAID 1的操作方式是把用户写入硬盘的数据百分之百地自动复制到另外一个硬盘上。 3、RAID 5 （可以理解为是RAID 0和RAID 1的折衷方案，但没有完全使用RAID 1镜像理念，而是使用了“奇偶校验信息”来作为数据恢复的方式，与下面的RAID10不同。） RAID 5 是一种存储性能、数据安全和存储成本兼顾的存储解决方案。 以四个硬盘组成的RAID 5为例，其数据存储方式如图4所示：图中，Ap为A1，A2和A3的奇偶校验信息，其它以此类推。由图中可以看出，RAID 5不对存储的数据进行备份，而是把数据和相对应的奇偶校验信息存储到组成RAID5的各个磁盘上，并且奇偶校验信息和相对应的数据分别存储于不同的磁盘 上。当RAID5的一个磁盘数据发生损坏后，利用剩下的数据和相应的奇偶校验信息去恢复被损坏的数据。 RAID 5可以理解为是RAID 0和RAID 1的折衷方案。RAID 5可以为系统提供数据安全保障，但保障程度要比Mirror低而磁盘空间利用率要比Mirror高。RAID 5具有和RAID 0相近似的数据读取速度，只是多了一个奇偶校验信息，写入数据的速度比对单个磁盘进行写入操作稍慢。同时由于多个数据对应一个奇偶校验信息，RAID 5的磁盘空间利用率要比RAID 1高，存储成本相对较低。 4、 RAID 10 （是RAID 0和RAID 1的组合方案） RAID10也被称为镜象阵列条带。象RAID0一样，数据跨磁盘抽取；象RAID1一样，每个磁盘都有一个镜象磁盘, 所以RAID 10的另一种会说法是 RAID 0+1。RAID10提供100%的数据冗余，支持更大的卷尺寸，但价格也相对较高。对大多数只要求具有冗余度而不必考虑价格的应用来说，RAID10提 供最好的性能。使用RAID10，可以获得更好的可靠性，因为即使两个物理驱动器发生故障（每个阵列中一个），数据仍然可以得到保护。RAID10需要4 + 2*N 个磁盘驱动器（N >=0)， 而且只能使用其中一半(或更小, 如果磁盘大小不一)的磁盘用量, 例如 4 个 250G 的硬盘使用RAID10 阵列， 实际容量是 500G。
第一章 创建和销毁对象 1.1 考虑用静态工厂方法替换构造器 1.2 用私有构造器或者枚举类型强化Singleton属性 1.3 避免创建不必要的对象 1.4 消除过期的对象引用 import java.util.Arrays; import java.util.EmptyStackException; public class Stack { private Object[] elements; private int size = 0; private static final int DEFAULT_INITIAL_CAPACITY = 16; public Stack() { elements = new Object[DEFAULT_INITIAL_CAPACITY]; } public void push(Object e){ ensureCapaciy(); elements[size++] = e; } public Object pop(){ if(size == 0){ throw new EmptyStackException(); } return elements[--size]; } private void ensureCapaciy(){ if(elements.length == size){ elements = Arrays.copyOf(elements, 2 * size + 1); } } } 在本例中,凡是数组下标小于size的那些元素都是过期引用 在支持垃圾回收的语言中,内存泄露是很隐蔽的 这类问题的修复方法很简单:一旦对象引用以及过期,只需要清空这些引用即可 public Object pop(){ if(size == 0){ throw new EmptyStackException(); } Object result = elements[--size]; elements[size] = null; return result; } 一般而言,只要类是自己管理内存,程序员就应该警惕内存泄露的问题 内存泄露的另一个常见的来源是缓存 内存泄露的第三个常见来源是监听器和其他回调.如果你实现了一个API,客户端在这个API中注册回调,却没有显式地取消注册,那么除非你采取某些动作,否则他们就会积聚.确保回调立即被当成垃圾回收的最佳方法是只保存它们的弱引用（weak reference）,例如，只将它们保存成WeakHashMap中的键. 第二章 对于所有对象都通用的方法 2.1 覆盖equals时总要覆盖hashCode 2.2 始终覆盖toString 2.3 考虑实现Compareable接口 第三章 类和接口 3.1 使类和成员的可访问行最小化 3.2 使可变性最小化 3.3 组合、继承 组 合 关 系 继 承 关 系 优点：不破坏封装，整体类与局部类之间松耦合，彼此相对独立 缺点：破坏封装，子类与父类之间紧密耦合，子类依赖于父类的实现，子类缺乏独立性 优点：具有较好的可扩展性 缺点：支持扩展，但是往往以增加系统结构的复杂度为代价 优点：支持动态组合。在运行时，整体对象可以选择不同类型的局部对象 缺点：不支持动态继承。在运行时，子类无法选择不同的父类 优点：整体类可以对局部类进行包装，封装局部类的接口，提供新的接口 缺点：子类不能改变父类的接口 缺点：整体类不能自动获得和局部类同样的接口 优点：子类能自动继承父类的接口 缺点：创建整体类的对象时，需要创建所有局部类的对象 优点：创建子类的对象时，无须创建父类的对象 请记住下面两句话： 继承要慎用，其使用场合仅限于你确信使用该技术有效的情况。一个判断方法是，问一问自己是否需要从新类向基类进行向上转型。如果是必须的，则继承是必要的。反之则应该好好考虑是否需要继承。《Java编程思想》 只有当子类真正是超类的子类型时，才适合用继承。换句话说，对于两个类A和B，只有当两者之间确实存在is-a关系的时候，类B才应该继续类A。《Effective Java》 3.4.接口只用于定义类型。 3.5 常量接口不值得效仿，接口应该只被用来定义类型，不应该被用来导出常量。 3.6 对于常量的使用我们应该遵循如下规则：如果常量与某个现有的类或者接口紧密相关，就应该把这些常量添加到这个类或者接口中；如果常量最好被看做枚举类型的成员，则应该用枚举类型来导出这些常量；否则应该使用不可实例化的工具类来导出这些常量。 第四章 泛型 推荐使用泛型，虽然他在运行时会被擦除。 尽可能地消除每一个非受检警告。如果无法消除警告，同时可以证明引起警告的代码是类型安全的，则可以使用@SuppressWarnings("unchecked")注解来禁止这条警告，同时我们必须要竟可能小的范围使用该注解，禁止在整个类上使用该注解。 第五章 枚举和注解 5.1 使用enum代替int常量 5.2 坚持使用Override注解 使用Override注解IDE会自动检查是否真的覆盖了超类的方法 第六章 方法 6.1 必要时，对不可变对象的构造器和访问方法进行检查性保护 6.2 慎用重载 方法重载是在编译时做出决定的。 永远都不要导出两个具有相同参数数目的重载方法，这是一个安全保守的方法。 任何一组给定的实际参数将应用于那个重载方法上 同一组参数只需要经过类型转换就可以被传递给不同的重载方法，如果不能避免这种情况，就应该保证：当传递同样的参数是，所有重载方法的行为必须一致 6.3 慎用可变参数 可变参数接受0个或者多个指定类型的参数。其机制是先创建一个数组，数组的大小为在调用位置所传递参数的数量，然后将参数值传递给数组，最后将数组传递给方法。 6.4 返回零长度的数组或者集合，而不应该是null。不重要但是值得注意 第七章 通用程序设计 7.1 局部变量作用域最小化 将局部变量的作用域最小化，可以增强代码的可读性和可维护性，并降低出错的可能性。 要是局部变量的作用域最小化，最有力的方法就是在第一次使用它的地方声明。一般来说每个局部变量都应该有一个初始化，如果没有足够的信息来对该变量进行有意义的初始化，则需要推迟该变量的声明，直到可以被初始化为止。 对于方法而言，应该尽可能地使方法小而集中，这样就可以将局部变量的作用域尽可能地小化。 7.2 优先使用for-each循环 for循环相比于while循环它可以使局部变量更小化，同时程序更加简短增强了可读性。 for-each循环在简洁性和预防bug方面有着传统for循环无法比拟的优势，并且没有性能损失，所以我们应该尽可能使用for-each循环，但是在以下三种情况是否无法使用for-each循环的： 过滤：如果需要遍历某个集合，删除特定的元素，则需要使用显示的迭代器。 转换：如果需要遍历列表或者数组，并取代它部分或者全部元素值，这时就需要迭代器来进行设置元素的值。 平行迭代 8.3 优先使用基本类型 基本类型相当于其引用类型有如下几个区别： 基本类型只有值，而引用类型则具有他们值不同的同一性，也就说new Integer(1) != new Integer(1)； 基本类型具有功能完备的值，而引用还有一个null值 3).基本类型通常比引用类型更加节省空间和时间。 当在一项操作中混合使用基本类型和其引用类型时，其引用类型会自动进行拆箱动作。 在进行迭代时需要格外注意拆箱装箱机制，因为频繁的拆箱装箱会导致性能的下降。 其他 8.4 如果需要精确的答案，请使用BigDecimal而不是double和float。 8.5 如果有合适的接口类型存在，那么对于参数、返回值、变量和域来说，就都应该使用接口类型进行声明。 第八章 异常 异常应该只用于异常的情况下，他们永远不应该用于正常的控制流。 异常机制设计是用于不正常的情况，所以很少会有JVM会对他进行优化，所以异常一般运行都比较慢。 我们应该尽量让异常代码块小，因为try..catch会阻碍JVM实现本来可能要执行的某些特定的优化。 第九章 并发 9.1 同步访问共享的可变数据 9.2 避免过度同步 9.3 executor和task优先于线程 9.4 并发工具优先于wait和notify 9.5 慎用延迟初始化 第十章 序列化 10.1 谨慎地实现Serializable接口 实现Serializable接口付出的最大代价是,一实现旦一个类被发布就大大降低了"改变这个类的实现"的灵活性 实现Serializable的第二个代价是,它增加了出现bug和安全漏洞的可能性(反序列化创建对象) 为了继承而设计的类应该尽可能少的去实现Serializable