显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

KeepItSimple&&Stupid

Nothing But Orz - Jay(A_Code_Monkey)

 
 
 
 
 
 

博客搬家

2014-11-15 15:42:22 阅读37 评论2 152014/11 Nov15

博客新地址:http://blog.csdn.net/colorwaterer

作者  | 2014-11-15 15:42:22 | 阅读(37) |评论(2) | 阅读全文>>

还是排序算法

2014-11-15 14:37:34 阅读54 评论0 152014/11 Nov15

最近面试经常会碰到一些排序上的题目,所以回去之后一直在巩固这方面的知识。

对于排序算法,我们不能仅看他的效率有多高,还要观察他所占用空间大小和稳定性。

一、排序的关键因素

1、空间

In-place sort:插入排序、选择排序、冒泡排序、堆排序、快速排序。

Out-place sort:归并排序、计数排序、基数排序、桶排序。

这就说明,当数据量过大时,选择 In 排序的比较明智的,因为 Out 排序所占用的内存和空间都比较大,而 In 排序不需要。

2、稳定性

stable sort:插入排序、冒泡排序、归并排序、计数排序、基数排序、桶排序。

unstable sort:选择排序、快速排序、堆排序。

为什么稳定性这么重要?原因很简单,假如你的排序算法经常碰到一些让你耗费大量时间去排序的数据,这明显会影响整体代码运行效率。

二、九大排序算法总结

当然,下面所讲的排序算法都是未经过优化的原始方法。

1、插入排序

插入排序的最优时间数据是已排好序的时候,复杂度为O(n),最坏时间数据是倒叙的时候,负责度是O(n^2)。

而且插入排序比较适合适用少量数据的排序。

2、冒泡排序

冒泡排序的最坏时间是O(n^2),其未作处理的最优时间也是O(n^2),但是做过处理后的最优时间是O(n)。

3、选择排序

最优和最坏时间都是O(n^2),优化后最优时间是O(n)。

作者  | 2014-11-15 14:37:34 | 阅读(54) |评论(0) | 阅读全文>>

优化快速排序的几个方法

2014-11-7 19:25:20 阅读659 评论0 72014/11 Nov7

普通的快排方法对于随机数组来说是挺快的,但是当遇到已经排好序的数组,复杂度马上就降为O(n^2)了。

所以我们需要对其进行优化。首先产生这种情况的原因是什么?是基数,当一个已经排好序的数组,我们所选的基数要么最大,要么最小,这就使得在排序过程中耗费了大量时间,那么如何筛选基数?

方法一:随机数产生区间内的某个数。

方法二:在划分算法上进行优化。

我们将同时从两端进行遍历,将需要的值进行交换即可。

方法三:短区间进行选择排序。

考虑到选择算法的最优时间是O(n),也就是对于已经近似排序好的数组,耗费的时间接近于遍历一次的时间。

方法四:考虑到随机数耗费的时间比较多,所以更好的做法就是我们人工筛选基数。

将要排序的区间进行分段。

当区间长度小于 7 时,我们采用选择排序;

当区间长度小于 40 时,我们将区间分成两段,得到左端点、右端点和中点,我们对这三个点取中数作为基数;

当区间大于等于 40 时,我们将区间分成 8 段,得到左三点、中三点和右三点,分别再得到左三点中的中数、中三点中的中数和右三点中的中数,再将得到的三个中数取中数,然后将该值作为基数。

具体代码只是在上一份的代码中加个筛选中数函数即可。

作者  | 2014-11-7 19:25:20 | 阅读(659) |评论(0) | 阅读全文>>

Node.js 单线程事件驱动的异步式 I/O

2014-10-14 15:49:54 阅读178 评论0 142014/10 Oct14

Node.js 并没有采用传统的多线程阻塞式 I/O,原因是异步式 I/O 减少了多线程的开销。对于操作系统来说,创建一个线程的代价是十分昂贵的,需要给它分配内存、列入调度,同时在线程切换的时候还要执行内存分页。

异步式编程与以往的程序设计思维不同,它通过回调函数来实现,将请求发送给了操作系统,然后立即执行后面的语句,执行完以后进入事件循环监听事件。当接收到 I/O 请求完成的事件时,事件循环会主动调用回调函数以完成后续工作。

下面我们来看个例子:

var fs = require('fs');

fs.readFile('file.txt', 'utf-8', function(err, data) {

if (err) {

console.error(err);

} else {

console.log(data);

}

});

console.log('end.');

上述代码运行的结果是:

end.

Contents of the file.

接下来我们来看看同步式代码:

var fs = require('fs');

var data = fs.readTileSync('file.txt', 'utf-8');

console.log(data);

console.log('end.');

作者  | 2014-10-14 15:49:54 | 阅读(178) |评论(0) | 阅读全文>>

Node.js 初入门

2014-10-11 19:03:18 阅读63 评论7 112014/10 Oct11

官方下载地址:http://www.nodejs.org/download/

根据自己电脑的不同系统选取并下载,我的是 Windows 64-bit。

安装

双击刚刚下载的 msi 文件,依次完成要求即可。

安装完成后可以测试一下是否安装成功(进入 cmd 界面,然后输入 node -v 和 npm -v),显示如下:

出现以上提示就表示成功了(cmd 界面输入 “node” 可进入 node 开发模式下)。

hello world

创建一个 helloworld.js 文件,在文件内键入 console.log("Hello World");

保存后,我们来运行一下。

打开 cmd,然后输入命令 - node 文件

HTTP 服务器

新建一个项目目录,在里面创建一个 server.js 的文件,内容:

var http = require("http");

http.createServer(function(request, response) {

response.writeHead(200, {"Content-Type": "text/plain"});

response.write("Hello World");

response.end();

}).listen(8888);

使用 Node.js 运行,然后打开浏览器输入

作者  | 2014-10-11 19:03:18 | 阅读(63) |评论(7) | 阅读全文>>

Windows Service 与 WebService 开发

2014-10-11 1:43:15 阅读45 评论0 112014/10 Oct11

最近的一个小项目终于告一段落了,还是老规矩,整理一下吧。

因为紧接着还有一个项目要尽快完成,所以这里先粗写一下,以后有时间的时候补上完整的说明。

WebService:

在远程服务器上部署一个 WebService 供本地服务调用,将本地服务发送到 WebService 的数据保存或更新到远程服务器

数据库中并反馈结果给本地服务。

Windows Service:

在本地机器上开发一个 Windows 服务,每过一定时间向远程服务器的 WebService 发送更新过的数据。

期间如果断网(无法将数据发送到远程服务器上),则将发送失败的数据以文本形式保存到本地文本文件中。

保存时根据不同时间的数据,按照年——月——日的形式建立文件夹,以天为单位保存每一份文本文件。

当网络恢复时,则将本地文件中的数据优先发送到远程服务器上。

守护进程:

守护进程的主要功能就是实时监测 Windows Service 是否崩溃或停止,若崩溃则需要重新启动它。

作者  | 2014-10-11 1:43:15 | 阅读(45) |评论(0) | 阅读全文>>

留恋我的ACM

2014-9-18 14:07:36 阅读84 评论0 182014/09 Sept18

时间过的真快,转眼间已经大四了,马上就要告别ACM了,这个学期最后一次比赛,比完后我也就退役了。

本想早点退役的,只是学弟们不太争气,有的迷恋游戏,贪玩,离ACM越来越远。

所以为了今年比赛成绩不是很难看,我们还在继续,我们能做的也就这些了,就是希望新一届的新生能够努力,不要迷恋游戏,好好学习,发扬宁工ACM集训队,让宁工ACM集训队有朝一日也能出现在World Final的现场赛中。

真是怀念留在集训队的日子啊

2012年11月宁波市赛铜奖

2013年5月浙江省赛铜奖

2013年6月杭州邀请赛铜奖

2013年蓝桥杯浙江省一等奖

2013年蓝桥杯全国赛二等奖

2013年亚洲区域赛铜奖

2014年蓝桥杯浙江省一等奖

2014年浙江省赛银奖

2014年西安邀请赛铜奖

2014年蓝桥杯全国赛一等奖

2014年亚洲区域赛铜奖

2014年亚洲区域赛铜奖

2014年宁波市赛金奖

最后祝愿13届新生能在将来的比赛中有所突破,不断提升自身实力和团体实力。

作者  | 2014-9-18 14:07:36 | 阅读(84) |评论(0) | 阅读全文>>

在浏览器中输入一个网站后,都发生了什么

2014-8-28 18:35:22 阅读58 评论0 282014/08 Aug28

以下仅是我对此的个人理解,如有错误,请一定指出,立马修改。

当我们打开了一个浏览器,在地址栏输入一个网址时,例如:www.baidu.com。

此时,我们的电脑会发送一个请求数据包到百度。

但是,www.baidu.com仅仅是一个域名,我们并不知道它的服务器具体在哪,所以此时就需要将域名转换为IP地址。

利用DNS协议,已知DNS服务器为8.8.8.8,于是我们向这个地址发送一个DNS数据包(53端口)。

然后,DNS服务器做出响应,告诉我们www.baidu.com的IP地址是202.108.22.5。

其次,我们还需要知道百度服务器的MAC地址。

首先,我们根据自己的子网掩码和IP地址进行与运算,得到一个结果A,再将子网掩码和对方的IP地址与运算,得到结果B,如果A等于B,则我们的数据包里写入的接收方MAC地址则是对方服务器的MAC地址,否则写入的接收方MAC地址则是当前网关的MAC地址(MAC地址通过ARP协议获得)。

因为浏览网页用的是HTTP协议,他是基于TCP协议的,所以HTTP数据包里嵌有TCP数据包。

TCP协议里包含双方的端口信息,接收方HTTP默认端口为80,而发送方的HTTP端口是一个随机生成的整数。

并且TCP数据包里再嵌入IP数据包,IP数据包里包含了双方的IP地址。

最后,IP数据包嵌入以太网数据包,以太网数据包里包含了双方的MAC地址。

经过多个网关的转发,百度服务器接收到了你发送的数据包,然后做出回应,再用TCP协议发回来。

作者  | 2014-8-28 18:35:22 | 阅读(58) |评论(0) | 阅读全文>>

TCP/IP的5层模型

2014-8-28 17:15:14 阅读95 评论0 282014/08 Aug28

TCP/IP通信的三次握手、四次挥手

三次握手:

第一次握手:客户端发送syn包(syn=x)到服务器,并进入SYN_SEND状态,等待服务器确认;

第二次握手:服务器收到syn包,必须确认客户的SYN(ack=x+1),同时自己也发送一个SYN包(syn=y),即SYN+ACK包,此时服务器进入SYN_RECV状态;

第三次握手:客户端收到服务器的SYN+ACK包,向服务器发送确认包ACK(ack=y+1),此包发送完毕,客户端和服务器进入ESTABLISHED状态,完成三次握手。

握手过程中传送的包里不包含数据,三次握手完毕后,客户端与服务器才正式开始传送数据。理想状态下,TCP连接一旦建立,在通信双方中的任何一方主动关闭连接之前,TCP 连接都将被一直保持下去。

与建立连接的“三次握手”类似,断开一个TCP连接则需要“四次握手”。

第一次挥手:主动关闭方发送一个FIN,用来关闭主动方到被动关闭方的数据传送,也就是主动关闭方告诉被动关闭方:我已经不 会再给你发数据了(当然,在fin包之前发送出去的数据,如果没有收到对应的ack确认报文,主动关闭方依然会重发这些数据),但是,此时主动关闭方还可 以接受数据。

第二次挥手:被动关闭方收到FIN包后,发送一个ACK给对方,确认序号为收到序号+1(与SYN相同,一个FIN占用一个序号)。

第三次挥手:被动关闭方发送一个FIN,用来关闭被动关闭方到主动关闭方的数据传送,也就是告诉主动关闭方,我的数据也发送完了,不会再给你发数据了。

作者  | 2014-8-28 17:15:14 | 阅读(95) |评论(0) | 阅读全文>>

OSI参考模型

2014-8-28 17:04:39 阅读57 评论0 282014/08 Aug28

第7层 应用层(Application Layer)

应用层能与应用程序界面沟通,以达到展示给用户的目的。 在此常见的协议有: HTTP,HTTPS,FTP,TELNET,SSH,SMTP,POP3等。

第6层 表示层(Presentation Layer)

表示层能为不同的客户端提供数据和信息的语法转换内码,使系统能解读成正确的数据。同时,也能提供压缩解压、加密解密。

第5层 会话层(Session Layer)

会话层用于为通信双方制定通信方式,并创建、注销会话(双方通信)。

第4层 传输层(Transport Layer)

传输层用于控制数据流量,并且进行调试及错误处理,以确保通信顺利。而发送端的传输层会为分组加上序号,方便接收端把分组重组为有用的数据或文件。

第3层 网络层(Network Layer)

网络层的作用是决定如何将发送方的数据传到接收方。该层通过考虑网络拥塞程度、服务质量、发送优先权、每次路由的耗费来决定节点X到节点Y的最佳路径。我们熟知的路由器就工作在这一层,通过不断的接收与传送数据使得网络变得相互联通。

第2层 数据链路层(Data link Layer)

首先数据链路层的功能在于管理第一层的比特数据,并且将正确的数据发送到没有传输错误的路线中。创建还有

作者  | 2014-8-28 17:04:39 | 阅读(57) |评论(0) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 
 
 

浙江省 宁波市 双子座

 发消息  写留言

 
加油↖(^ω^)↗
 
近期心愿赶紧学算法
人生格言Nothing But Orz - Jay
交友目的 结交朋友
博客等级加载中...
今日访问加载中...
总访问量加载中...
最后登录加载中...
 
 
 
 
 
 
 
心情随笔列表加载中...
 
 
 
 
 
 
 
博友列表加载中...
 
 
 
 
 
 
 
列表加载中...
 
 
 
 
 
 我要留言
 
 
 
留言列表加载中...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018

注册 登录  
 加关注