豪翔天下

Change My World by Program

0%

OK,昨晚熬夜到两点都没解决这个问题,不过还好昨晚至少知道了问题没有出现在配置上,而是IP有问题。今天写了一张工单给ustack的客服,终于知道答案了。

现象:ustack的云服务器中的mysql数据库无法实现远程登录。

环境:Ubuntu14.04(server) + ustack服务器

解决

1.修改默认安全组

阿里云没有安全组功能,默认不对端口进行限制

ustack的安全组是云主机虚拟网卡上行和下行流量的防火墙,就相当与其NAT的防火墙,而DigitalOcean没有这个东西,不信你可以试试ifconfi g,该命令在ustack可以看到两张网卡,但是却没有外网ip的网卡,而DigitalOcean则可以直接看到外网ip的网卡切没有内网的ip。以下是usta
ck的默认安全组:

可以看到其上行流量是完全开放的,但是下行却只开放了几个端口,可以在这里面添加安全规则,也可以自己另外建立安全组,然后在虚拟网卡里面绑定到相应的虚拟网卡就可以
生效了,然后重启一下服务器(没尝试过不重启会不会生效,反正我是重启了的)。

2.MySQL授权root用户远程登录

需要注意的是,最好不要用root用户远程登录,可自己新建一个用户用于远程登录,并限制一些权限,由于我这只是测试用的服务器,所以无所谓。首先在服务器中执行如下
命令:

mysql -u root -p   # 登录MySQL
mysql> use mysql;
mysql> select host, user from user;   # 查看是否已经分配了权限
+-----------+------------------+
| host      | user             |
+-----------+------------------+
| 127.0.0.1 | root             |
| ::1       | root             |
| localhost | debian-sys-maint |
| localhost | root             |
| tech      | root             |
+-----------+------------------+
6 rows in set (0.00 sec)
mysql> grant all privileges on 星__.星__ to 'root'@'\%' identified by 'password' with grant option;
mysql> select host, user from user;    # 结果中的\%就表示所有IP都可以用root用户登录
+-----------+------------------+
| host      | user             |
+-----------+------------------+
| \%         | root             |
| 127.0.0.1 | root             |
| ::1       | root             |
| localhost | debian-sys-maint |
| localhost | root             |
| tech      | root             |
+-----------+------------------+
6 rows in set (0.00 sec)

3.修改MySQL侦听端口

修改MySQL配置文件/etc/mysql/my.cnf,将bind-address后的值localhost修改为ustack服务器的内网IP(
注意这里修改成的是内网ip,因为ustack是用的NAT方式转发过去的,它本身根本无法识别外网IP)

阿里云需要将bind-address设置为服务器的外网IP

DigitalOcean也要设置为外网IP(DO貌似没有内网IP)

4.测试

在另一台电脑上执行mysql -h 外网IP -uroot -p,这里的IP是外网IP,如果能访问就表示设置成功了。

参考:http://www.111cn.net/database/mysql/46646.htm

近日老板给了我一个数据库,让我学学人家是怎么设计的,之前从来没有导入过别人的数据库,期间遇到一些问题,特记录如下:

1.批量导入问题

首先老板给我的文件不是一个单独的sql文件而是一张一张单独的表对应的sql文件,加起来好几十个,我可不想一个一个的导入,所以到网上找到了一个比较方便的方法:

首先,要知道有一种sql文件是这样的:

source file1.sql;
source file2.sql;
srouce file3.sql;
...

如果再用source命令执行这个文件的话就可以实现批量导入功能,但是怎么能直接获取全部文件名呢(由于source命令是在mysql shell里执行的,所以
要用绝对路径),这是可以用管道了(linux下用ls,windows下用dir)。首先可以把所有sql文件放到一个文件夹内(如果同名就重命名,没有关系的)。
然后在cmd里执行

dir foldername /b/od/s > all.sql

这条命令会列出foldername文件夹内的所有子文件的绝对路径并将结果输出到all.sql文件内。然后用文本编辑器打开该sql文件,用替换工具,将每一行替
换为

source 绝对路径;

的形式并保存。然后在MySQL里执行

source all.sql的绝对路径

这样就能完全导入了。

2.导入乱码的问题

出现乱码肯定是中文乱码,但是,虽然你把MySQL默认编码设置为utf8并且把数据库设置为utf8但依然无法避免人家导出时不用utf8的情况,我应该就是碰到这
么一个问题了,所以下次自己用命令导出的时候一定要设置编码:

mysqldump -uroot -pmysql --default-character-set=utf8 database > xxxx.sql

而如果遇到别人的数据库导入乱码的时候就需要把所有东西全部设置为utf8就可以彻底解决问题了:

SET character_set_client = utf8;
SET character_set_connection = utf8;
SET character_set_database = utf8;
SET character_set_results = utf8;
SET character_set_server = utf8;
SET collation_connection = utf8_bin;
SET collation_database = utf8_bin;
SET collation_server = utf8_bin;




# 然后再导入




source all.sql

每个学计算机的同学都会有这么一个困扰:身边的人会问你各种各样的电脑问题,但事实上自己所学的内容和他们的理解根本就不一样。我们学计算机,学的是计算机的原理,不
是学如何看哪个硬件好不好,我们学的是软件,但不是PS这种软件,我们可以做一个手机APP,但那不是一两天就能做好的。每次跟你们解释的时候由于你们也不理解,所以
我们也很困扰。所以特写这么一篇科普文章,希望你们能够看看我对电脑的一些常用的知识。(文中有些观点肯定会被懂电脑的人喷,但请理解)

1.关于购机

好吧,这是我们最薄弱的一块儿,实话实说,我们真的对硬件不了解,无论是手机或者是电脑。如果非要让我们提供建议,那么很简单,有钱就买苹果,MacBook也有60
00多的,我就很喜欢。但我肯定买不起,我目前的这台宏碁笔记本3600元买来,加了一根140块钱4G的金士顿DDR3内存条(2012年买的,当时内存条可没如今
这么贵,而且我是买电脑那里买的,都是水货),今年又加了一个120G的三星固态硬盘(SSD),貌似是400多,反正别人送的,我也不知道多少钱。我的电脑嘛,还是
可以应付很多大型游戏的,显卡是NVIDIA GeForce GT
630M,在大型游戏方面,极品飞车18之前都能流畅运行。PS:不要说哪款网络游戏能称得上大型游戏,真正的大型游戏都是单机。

在品牌的选择方面,只要不买神舟都行,其实我也不讨厌国产的,但自从看了神舟的官网后,我对神舟就绝望了。在价钱方面,一句话,如果要玩大型游戏或者用专业的软件比如
视频制作等,一定要4000以上,显卡一定要独立,如果不玩大型游戏,那么3500以上都行,如果不玩游戏,平时只是上上网聊聊天,3000以上都行。在显卡选择方面
,除非用ADM最顶端的几个型号,不然就买英伟达的。在CPU方面不要追求主频,它并不能代表什么,但一定要用Intel的。硬盘方面,如果不存太多片(你懂得),3
00G以上真的够了,最好选择有固态硬盘的,以后装什么软件就不用犹豫装不装在C盘了,一样的神速。内存方面,最好4G及以上。系统方面,不要去纠结预装的什么系统,
也不要被老板忽悠他装的是正版系统,无论预装的什么,都可以直接叫老板装一个你喜欢的系统,而且是正版的,零成本,跟他说几句,绝对不收钱。windows还有正盗版
之分,linux绝对是正版且免费的,别被老板忽悠。还有,如果电脑不是触屏的,最好别用win8。

手机嘛,我觉得都差不多,反正我799买来的红米用了一年多了,感觉不错。我买电子产品都有一个预计的使用时间,我预计799的手机用一年就可以了,不过目前看来应该
可以再多用一年左右的。

另外,关于水货的问题,水货为什么那么便宜,就因为他们不是通过正规渠道获得的,不用上税,电子产品的税率一般在15%-20%之间吧,也就是说5000的电脑大概税
收都是850,你知道为什么那么便宜了吧,如果你想要买的连正常价格的80%都没有那么就应该多长个心眼,很有可能是盗版或是劣质产品。

PS:我现在的装备:宏碁E1-471G笔记本(3600) + 4G金士顿内存条(140) + 台电x98 Air II平板(949) + 红米手机(799)

  • 三星22英寸显示器(别人送的) + 三星120G的SSD(别人送的) + 凯酷机械键盘(499) +

说不出名字的鼠标&耳机&游戏手柄(90) =
![](http://7xnc86.com1.z0.glb.clouddn.com/the-computer-acknowlodge-i-
know_1.jpg)

2.软件方面

正如上面所说,如果想重装系统,这个就可以找计算机专业的了,分分钟给你重装个正版稳定的系统,别到电脑城里去跳坑。盗版系统激活了照样是正版,而且没任何区别。当然
,学计算机的不会装系统也很正常,学校又没教过。另外,像做图、做视频、做CAD神马的,我们真的没那么多时间去学,而且这些软件根本没必要去学,要使用什么功能,去
百度一下立马学会。还有,在使用电脑过程中,如果遇到什么问题,比如什么软件打不开安装不上什么的,首先请重启一下,如果还有问题,请把电脑具体的提示截屏过来,不要
光说遇到个问题。在是否安装电脑管理软件方面,我建议还是装一个比较好,方便管理电脑,比如清理垃圾、关闭开机自启动的软件、安装软件等都很方便的,我个人用的是36
0,不要喷360,至少在我眼里现在唯一不流氓的软件就是360了(那些说安装完360卸载不干净的,请不要用360软件管家来卸载360安全卫士!)。是否安装补丁
方面,这个其实安不安装无所谓,只要你平时不拍什么艳照。是否安装杀毒软件方面,凭个人爱好,如果总是感觉电脑有毒,那么安装一下杀一下毒就行了,反正不用的时候你不
打开就行了。

3.购物方面

请尽量用360安全浏览器购物,千万别用IE,360浏览器至少能分辨大量的钓鱼网站。再科普一下如何简单的识别钓鱼网站,一般,如果你的电脑没有木马病毒,是可以直
接通过浏览器的地址栏看出是不是合法网站的。就比如淘宝嘛,域名是[www.taobao.com,对于任何网址,前面加不加http://都一样,当然这只是淘宝网
的首页,如果点击了其他页面那么就会有www.taobao.com/XXX,这样的也都是对的,无论XXX是什么...](http://www.taobao.c
om,对于任何网址,前面加不加http://都一样,当然这只是淘宝网的首页,如果点击了其他页面那么就会有www.taobao.com/XXX,这样的也都是对
的,无论XXX是什么内容,有斜杠也无所谓,因为最重要的就是”taobao.com”。如果有其他情况就要注意了,比如www.123taobao.com,www
.tacbao.com,www.taobao.hehe.com,等绝对是钓鱼网站。还有就是天猫\\(tmall.com\\)虽然和淘宝是一家的,但是域名不一样
“Link: http://www.taobao.com,对于任何网址,前面加不加http://都一样,当然这只是淘宝网的首页,如果点击了其他页面那么就会有
www.taobao.com/XXX,这样的也都是对的,无论XXX是什么内容,有斜杠也无所谓,因为最重要的就是"taobao.com”。如果有其他情况就要注
意了,比如www.123taobao.com,www.tacbao.com,www.taobao.hehe.com,等绝对是钓鱼网站。还有就是天猫\\(tma
ll.com\)虽然和淘宝是一家的,但是域名不一样” )。

还有一种钓鱼网站是盗号的网站(请不要太在意QQ号被盗这件事,没什么的,盗你的号一般是改不到你密码的,顶多转发些黄色的盗号网站罢了),当然如果你QQ号黄钻、红
钻什么杂七杂八的都是满级或者你在QQ里面有大量的Q币就要注意了。盗号网站也很好识别,一般他们是这样的网站:你打开后会要求你输入QQ帐号和密码,因为他们无法拿
到腾讯的API,所以必须你手动输入,这种网站一般模仿得像正常的网站,但字体一般都不大对劲,有经验的人一样就能看出来,而且也能通过网址结构判断的。这些网址一般
非常奇葩,你根本无法从网址看出来和主题有什么关系。

4.个人方面

请珍惜你身边的程序员。以下是我从网上整理的一些事实: 1.要嫁就嫁程序员,钱多话少死得早(人好话少壕得早) 2.程序员都很专一,除了计算机就是你
3.不喝酒不抽烟不发脾气 4.一套衣服穿半年 5.经常加班,而且同事清一色的男人,绝对不会搞外遇
6.经常加班,所以周末一定会怀着一颗愧疚的心在家陪老婆逛街、看电视、聊天、做家务
7.只认识0和1,基本没理财能力,一定会主动把所有的钱都交给老婆管,还会千恩万谢地 8.知道既然世界上不存在没有Bug的程序,就更加不会有没有缺点的人,所以
绝不会老婆太过苛求;知道系统若不经常维护就无法保持稳定运行,所以一定会每天都对老婆精心呵护
9.嫁给瘦弱的程序员,也许永远无法目睹他像李连杰那样以一敌十的英姿,却也会听到他吼道:“哪个孙子又在QQ上骂你呐?看我不盗了她的号……”
10.除了每个月买一本书,就没有其它需要花钱的地方,剩下的钱只能变着法的给老婆买各种首饰和衣服 11.每天都读书到深夜,是孩子的好榜样
12.程序猿都很单纯,虽然 13.程序员很热心。论坛上兄弟们有困难,他们会出手相助。生活中,朋友有电脑问题,他们会帮助解决
14.程序员很细心。写代码是个细活,不细心就会有bug,真写了bug,还得耐心细心的去找出来。在生活中
15.程序猿很浪漫,别以为他们每天面对代码就不懂风花雪夜了,没准你们每个第一次他都早已经清清楚地存进了程序里,就等给你一个惊喜呢

Nginx用起来比Apache方便简介,也有很多超过Apache的地方。Nginx不仅可以作为http服务器来用,更重要的,它还可以用来做负载均衡和反向代理。Nginx官方文档

  • 正向代理:类似fq,服务器代替我们去访问其他的服务
  • 反向代理:外部访问内部服务,例如外部用户访问公司内部的各个服务,通过一个nginx进行代理

安装nginx

安装方法见: nginx安装方法

如果要安装最新稳定版nginx,可以添加这个源:

1
2
3
4
5
[nginx]
name=nginx repo
baseurl=https://nginx.org/packages/centos/7/$basearch/
gpgcheck=0
enabled=1

Web项目目录的常用权限

1
2
find /A -type d -exec chmod 0755 {} \;
find /A -type f -exec chmod 0644 {} \;

配置文件详解

阅读全文 »

MySQL的逻辑备份是使用mysqldump命令(文本备份,而非二进制备份)来从数据库中提取数据,并将结果写到一个纯文本上,就是我们平常用mysqldmin到处的.sql格式的文件,里面是SQL语句。正是如此,逻辑备份可以在MySQL正在运行时执行,并且可以做到不锁表备份(也可以声明锁定),一般用于数据迁移或者数据量很小时。

备份

下面的命令是直接在linux的cmd里执行,而不是mysql的shell

1
2
3
4
5
mysqldump -q --single-transaction -A -u root -p > all.sql # 导出所有数据库到all.sql
mysqldump -q --single-transaction -u root -p user > user.sql # 导出user数据库
mysqldump -q --single-transaction -u root -p user admin > admin.sql # 导出user数据库里名为admin的表
mysqldump -q -d --skip-triggers user admin-u root -p > admin.sql # 导出user数据库里名为admin的表的结构
mysqldump -q -d --skip-triggers user -u root -p > jiego.sql # 导出user数据库的结构

其中mysqldump的常用参数如下:

1
2
3
4
5
6
7
8
9
-B:导出多个数据库
-E:把事件events一起导出
-R:把存储过程routines一并导出
-q:快速模式,不把查询结果显示在终端
--default-character-set=utf8:这点很重要,因为大量的数据库默认都会是utf8
--flush-logs:生成新的二进制日志文件,主要用于增量备份,恢复数据,增量备份必须加此选项,否则会丢失 数据
--lock-all-tables:锁住全局表,会出现写操作等待
--single-transaction:设置本次会话隔离级别为REPEATABLE READ,确保本次会话时,不会看到其他会话已提交了的数据
--triggers:把触发器一并导出,默认开启了此选项的

:需要注意的是,在5.5之后,mysqldump默认无法备份performance_schema这个数据库,但是可以通过—databases指定名字和--skip-lock-tables的方式来备份,但是不知道为什么,虽然能备份但是还是会给出错误信息。performance_schema是新增的mysql的性能监视引擎,所以我认为不备份也行,本来默认也是关闭的,因为数据库迁移或者恢复的时候可以不用看之前的这些的,有什么问题看系统日志就行了,具体的请参见官方手册

在slave里备份

MySQL5.5之后mysqldump增加了一个参数--dump-slave,可以在slave端dump数据,并且可以建立新的slave,可大大降低主服务器的压力。

恢复

假设有一个数据库结构的备份文件user.sql,那么可以 在mysql的shell里面执行如下命令

1
2
3
4
create database User;     # 首先得创建一个数据库
use User; # 选择该数据库
source /root/User.sql; # 导入sql文件
show tables; # 查看是否创建成功

也可以在创建相应数据后后在linux的shell里执行(在外面创建数据库我没找到方法)

1
mysql -u root -p user < user.sql

额,这是最简单的备份方式,只需要把mysql的数据文件打包并压缩即可,要恢复的时候再把相应的文件拷过去覆盖就行了。

冷备份实际上是最简单的备份方式(好吧,第一次我就差点把数据库搞崩溃了),但由于要求停止MySQL服务来进行备份和恢复,并且只能完整备份,所以实用性并不高。

备份

首先,进入数据库并找出数据文件存放目录:

mysql> show variables like '\%dir\%';
+-----------------------------------------+----------------------------+
| Variable_name                           | Value                      |
+-----------------------------------------+----------------------------+
| basedir                                 | /usr                       |
| binlog_direct_non_transactional_updates | OFF                        |
| character_sets_dir                      | /usr/share/mysql/charsets/ |
| datadir                                 | /var/lib/mysql/            |
| innodb_data_home_dir                    |                            |
| innodb_log_group_home_dir               | ./                         |
| innodb_max_dirty_pages_pct              | 75                         |
| lc_messages_dir                         | /usr/share/mysql/          |
| plugin_dir                              | /usr/lib/mysql/plugin/     |
| slave_load_tmpdir                       | /tmp                       |
| tmpdir                                  | /tmp                       |
+-----------------------------------------+----------------------------+
11 rows in set (0.00 sec)

数据目录就是datadir的所在位置,即/var/lib/mysql/

然后执行:

cd /var/lib/                          # 进入其上级目录
service mysql stop                    # 关闭mysql服务,这里我其实并没有关闭,但我没有在高                                         数据量下测试过
tar jcvf ~/backup.tar.bz2 mysql/      # 打包压缩该目录到根目录

恢复

执行如下命令即可:

cd ~/                           # 进入备份文件的保存目录
tar jxvf backup.tar.bz2 mysql/  # 解压
gunzip -r mysql/                # 递归解压
service mysql stop              # 必须先关闭服务
rm -r /var/lib/mysql/           # 删除原目录
mv ~/mysql/ /var/lib/           # 把备份的文件移动到/var/lib/里面去替代原来的mysql
service mysql start             # 重启mysql服务

需要注意的是恢复过后,就和原来数据库一模一样了,包括所有的修改和帐号密码等信息。

参考:《MySQL管理之道》

简介

Sysbench是一个模块化、跨平台、多线程基准测试工具,主要用于评估测试各种不同系统参数下的数据库负载情况。

安装

sudo apt-get install sysbench

参数列表

General options:

--num-threads=N          线程数,默认为1
--max-requests=N         并发请求限制,默认为10000
--max-time=N             最大执行时间,默认为0
--forced-shutdown=STRING 最大执行时间后多久强制关闭
--thread-stack-size=SIZE 每个线程的栈大小,默认32K
--init-rng=[on|off]      初始化随机数生成器,默认off
--test=STRING            test to run
--debug=[on|off]         打印更多的调试信息,默认off
--validate=[on|off]      尽可能执行验证检查,默认off
--help=[on|off]          查看帮助
--version=[on|off]       查看版本

Compiled-in tests:

fileio    磁盘I/O性能测试
cpu       CPU性能测试
memory    内存分配及传输速度测试
threads   POSIX线程性能测试
mutex     调度程序性能测试
oltp      数据库性能测试(OLTP基准测试)

使用举例

测试Mysql的InnoDB存储引擎,其中16个并发连接,最大请求1万个,表记录有9百万条:

sysbench --test=oltp -MySQL-table-engine=innodb \\
--oltp-table-size=9000000 \\
--max-requests=10000 \\
--num-threads=16 \\
--MySQL-host = 127.0.0.1 \\
--MySQL-port = 3306 \\
--MySQL-user = root \\
--MySQL-password = 123456 \\
--MySQL-db = test \\
--MySQL-socket=/tmp/MySQL.sock prepare

参考:http://www.oschina.net/question/17_4248

MySQL在5.5X开始,默认的存储引擎改为了InnoDB
Plugin引擎,而我正是在5.5开始使用MySQL的,对两个引擎的区别还不甚了解,所以特别查阅了大量的资料,整理如下:

有何区别:

最简单的,一条语句即可看到:

更具体的看下面:

Innodb

  • 索引聚集表,存储结构采用BTREE
  • 数据存储是有顺序的,默认以主键排序,主键就是数据本身,所以对于insert比较多的情况,最好建一个自增主键,以方便保持其顺序性

MyISAM

如何选择

我认为两个引擎没有孰优孰劣之分,具体怎么选择完全看业务需要。

InnoDB适合: 1.数据量巨大时,提高CPU效率,这一点上其他引擎都比不上InnoDB 2.使用事务 3.可靠性好、性能高 4.更新查询都相当频繁
5.表锁定几率较大 6.大量的主键查询 7.并发量大的update语句 8.高压力、高并发

MyISAM适合: 1.磁盘空间较小 2.大量count计算(MyISAM用一个值来记录,而InnoDB每次都扫描全表) 3.插入不频繁,查询频繁
4.不使用实务 5.大量的insert语句

作者:贺春旸

先介绍介绍作者,作者是51CTO技术博客之星,曾任职于中国移动飞信、国内某知名电商,致力于MySQL、Linux等开源技术的研究,现任职于机锋安卓市场,负责MySQL性能调优和架构设计。

其实这本书并不是讲什么非常前沿的技术,但是我看过很多的技术书籍以及网上的技术教程,大部分的技术都是上个世纪的,完全不能用,有些甚至连基本原理都改变了,但国内的书市几乎都被这种书填满了,直到这两年,随着开源社区的快速发展,微软、诺基亚的没落,人们(特别是国内的程序员)开始关注起最新的技术,开始向国外吸取精华,哪怕是看英文原版,也比等几年后出的中文翻译版要好。并且现在已经有大量的人涌入开源社区,义务进行翻译工作,如果GFVV不加阻挠,相信中国在计算机科学方面一定能快速成长到国际先进水平。

本书记述了作者多年以来在MySQL数据库维护上的一些见解以及处理问题的一些方法。当我拿到书本翻开目录的那一霎,顿时感觉买此书绝对值,因为作者完全是按照MySQL5.5来进行讲解的,虽然最新的稳定版5.6已经出来了一两年了,但是目前介绍MySQL的书籍有几本是5.0以上的?很难找到。人们一味地认为,即使软件版本怎么发展,很多内部的东西是不会变的,真的不会变吗?或许吧,但随着技术的快速发展,很多编程语言、系统架构都会吸收一些其他软件的优良之处以使自己的性能得到提升,这样就难免会有很多使用上必须更改的地方,即使只介绍以前的知识,但那些书籍至少也应该在后续的版本中介绍一下新版本的一些新的功能,哪些地方有改变。在看这本书之前的我,一直看的是那些所谓的计算机经典书籍,当然,我必须承认他们确实经典,无论再过多少年,他们依然是经典,但是他们中有很多东西于现在看来确实有些过时了。从本书开始,我对技术书籍有了更新的了解,也对如何选择书籍有了更深的领悟。

我一直使用MySQL,虽然没用过Oracle,不好对其发表评论,但就像现在大公司流行去IOE一样,我也深深地觉得他们三家确实太垄断了。现在我也在管理两个服务器,因为上次一气之下把服务器重装了系统,导致一些数据没有备份(还好都不重要),所以现在也开始关注服务器的管理了。本书并不是讲SQL的基本知识,所以适合的读者群应该是有一定基础知识并真正管理过MySQL数据库的人。另外,书中提到的大量的实践的知识,就不在这里详述了,已经将其整理到我的MySQL的其他几篇文章中去了。

PS:华章的图书虽然纸质上不大好,但整体触觉还是挺爽的。

《编程珠玑》

第一部分 基础

第1章 开篇

问题抽象描述:对10^7个正整数进行排序,只能使用1MB左右的内存空间

解决方案:使用位图,每个比特位代表一个整数,如果出现该整数则将该位置为1.

应用:该方法适合输入数据限制在相对较小的范围内;数据没有重复;而且对于每条记录而言,除了单一的整数外,没有任何其他关联数据。位图的数据结构,描述了一个有限定义域内的稠密集合。

第2章 啊哈!算法

问题抽象描述:
A.找出一个不在40亿个随机排列的32位整数的顺序文件中的数,仅有几百字节的内存
B.将一个n元一维向量向左选装i个位置,仅有数十个额外字节的存储空间,在正比于n的时间内完成向量的旋转
C.找出一个英语字典所有变位词集合。(pots,ptos, stop这种变位词)

解决方法:
A.二分搜索:采用已知包含至少一个缺失元素的一系列整数作为范围,并使用包含所有这些整数在内的文件表示这个范围。通过统计中间点之上和之下的元素来探测范围;或者上面或者下面的范围具有至多全部范围的一般元素。由于整个范围中有一个缺失元素,因此我们所需的那一半范围中必须也包含缺失的元素。
B.其中以前在很多地方都看到过这个方法,从ab开始,首先对a求逆得到c,然后对b求逆得到d,最后整体求逆,就得到ba了,然后各段的逆又可以在内部再次求逆,以此递归。
C.标识字典中的每一个词,使得在相同变位词类中的单词具有相同的标识。

第3章 数据决定程序结构

对数据结构所带来的方便进行了一些简述,这些在当今高级语言中都有所体现。

第4章 编写正确的程序

本章通过一些证明方法来证明了一个算法的正确性,由于我已经在《算法导论》里面饱受了数学的折磨了,这张直接跳过了,完全看不懂。

本章还介绍了一种用于检验程序正确性的方法,断言(assertion)或者叫不变式(invariant)。由于输入、程序变量和输出之间的关系勾勒出了程序的“状态”,断言使得程序猿可以准确阐述这些关系。

第5章 编程小事

本章写了一些测试的方法,不过都是手动进行测试。毋庸置疑,测试在编程中绝不是小事,特别是大型项目的开发,作者以小见大,说明了测试对于系统的稳定性和优化所带来的重大影响。

第二部分 性能

第6章 程序性能分析

从设计层面将程序性分为了几个方面:问题定义、系统结构、算法和数据结构、代码调优、系统软件、硬件。也有一个简单的分析方法就是看算法的复杂度,用O来表示那种。

第7章 粗略估算

本章使用生活中大量的例子来描述如何进行粗略估算,最近正好在看《蝎子网络》,发现我的数学功底越来越差,实际生活中有大量的使用估算的地方,比如,验证一些生活常识、验证一些新闻的正确性等。日常生活中的速算。

粗略估算的一些基本技巧:快速检验、经验法则(72法则)。还有一些估算定律:Little定律(队列中物体的平均数量为进入速率与平均停留时间的乘积。)

第8章 算法设计的技术

本章主要讲述了分治算法,这一算法我曾在算法导论上看过。

本章还介绍了几个重要的算法设计技术:保存状态,避免重复计算;将信息预处理至数据结构中;分治算法;扫描算法;累计;下界。

第9章 代码调优

本章介绍了优化代码的一些简单的思想和方法。例如将最常见类型的空闲记录缓存在一个链表中。然后,就可以通过对该链表的快速访问来处理常见的请求,而不必调用通用的内存分配程序。恰当使用函数、宏和内联代码。

”代码调优的最重要的原理就是尽量少用它.“

第十章 节省空间

Unix操作系统发明者(Dennis Ritchie和Ken Thompson)在论文中说道:“在系统及其软件方面,总是存在着相当严重的空间约束。如果同时对合理的效率和强大的能力提出要求,那么空间约束不仅具有经济上的意义,还会使设计更优雅一些。”

其实节省空间在所有地方都可以看到,比如在最初定义一个整数位数的时候,我一直使用的是int,但是如果要节约空间就使用其他的一些分配方法。

hash(散列表)特别适合某些稀疏场合。

如果一定要消耗时间来节省空间,在有些变量的计算上选择不存储,重新计算的方法更有效。在给变量分配内存时就使用动态分配。

第三部分 应用

第11章 排序

作者通过自己对快速排序的几种方法的改进超越了库函数。就像其他任何强大的工具一样,我们经常会在不该使用排序的时候使用排序,而在应该使用排序的时候却不使用排序。

第12章 取样问题

研究的一个问题就是输出随机数,虽然很多语言都提供了类似的随机函数,但是感觉目前大多数语言,特别是传统语言的随机几乎都无法做到真随机,必须自己在假随机上进行修改。

第13章:搜索

线性结构;二分搜索数。并提到了库的作用,C++标准模库提供了一个实现起来很容易,并且维护和扩展也比较简单的通用解决方案。当遇到涉及数据结构的问题时,我们的第一反应应该是寻求解决问题的通用工具。当然,有些时候针对特定的问题,使用专用的算法可能会大大提高运行速度。我们还要使用代码调优方法,比如将递归函数重写为迭代版本可以使链表的速度提升为原来的3倍,对大多数结构来说,引入哨兵可以获得清晰、简单的代码,并缩短运行时间。

第14章:堆

堆其实也是一种二叉树,但其有两个不同的性质:一是顺序性,任何结点的值都小于或等于其子结点的值。第二个性质就是形状,不是完整的三角形,右下角可以缺一点。

第15章:字符串

通过单词、短语和文本几个方面来处理字符串

《编程珠玑》(续)

第一部分 编程技术

第1章 性能监视工具

通过一些常用的代码性能监视工具,如行计数性能监视、过程时间性能监视等可以查看到一个程序里面各条语句的执行情况,以查找代码中执行最慢的地方,因为“一个程序中不到4%的语句通常占用了一半以上的运行时间”。我们最应该优化的就是这个地方。

第2章 关联数组

貌似本书很多章都是使用的Awk来讲解,但是Awk中的关联数组,我感觉就很像其他脚本语言中的字典,十分方便,但awk对字符串的处理可能更加方便,不过我是不喜欢其编码风格的。

第3章 程序猿的忏悔

再次提到调试脚手架的重要性,这一点上,Awk语言确实能起到很大的帮助,“Awk是一种构造算法原型的很好的语言,其内联数组使你模拟许多常用的数组结构,它的字段、隐式循环、模式-动作对等设计极大地简化了输入输出过程,隐式的变量声明和初始化也使得程序更加简洁。”。正如Fred Brooks认为“一个软件产品中应该有一半的代码都是脚手架”。

第4章 自描述数据

作者是使用的文档生成器来描述,其实本章所说的自描述数据在某种意义上类似于其他语言的一种模版,比如留下%s等占位符,让其他变量来填充。

第二部分 实用技巧

第5章 劈开戈尔迪之结

背景:在古希腊神话中,能解开戈尔迪之结者就可以当亚细亚之王,几百年后亚历山大大帝来了。他没有重蹈覆辙,而是拔出剑来,将结直接劈开,随即征服了亚洲。从那时起,“劈开戈尔迪之结”意味着为复杂问题找出聪明的解法。

我们在寻找解决问题的方法的需要考虑如下几个问题:什么是用户真正的需求(用户要求可预测性甚于要求速度);考虑成本与收益的平衡;别把问题弄得太复杂也别太简单;用正确的方法使用正确的工具;对员工的奖赏。。。

简单的方法谁都想要,但并不是每个人都能找得到,我们还应该考虑时间成本,别花过多时间去思考简单的方法,没准一个你目前觉得复杂的方法可以很快完成项目。

第6章 计算机科学箴言集

居然把一些计算机的箴言单独列为一章,我也是醉了。

第7章 粗略估算

在原书已经有了几乎一样的内容…

第8章 人员备忘录

大神,这是你自己的日记吗?

第三部分 人性化I/O

第9章 小语言

作者以Pic为例子讲解了一种小的语言是如何运行起来的,相信看过编译原理的同学都能理解。

第10章 文档设计

原以为是要教我们关于PRD这样的文档的写法,不过只是教了我们一些写Word文档的基本的规则,不过我觉得一个有基本审美观的人无论怎么写也不会写得很差的。

第11章 图形化输出

合理使用图形工具。

第12章 对调查的研究

也是借调查这一事件来强调模版的好处。

第四部分 算法

第13章 绝妙的取样

好吧,就是随机数的一些个问题。

第14章 编写数值计算程序

牛顿迭代,这个我倒是完全理解。本章学到重要的一点就是“在特殊的上下文环境中针对特殊目的设计的代码比通用的程序更有效”。

第15章 选择

使用分治算法来进行选择,太聪明了。