TCP 的 timewait 状态是什么？谁会有 timewait 状态？timewait 状态存在的作用是什么？如何避免大量的 timewait 状态占用系统资源？

timewait 状态是 TCP 链接的主动关闭方会有的状态，在发出最后一个 ACK 包之后，主动关闭方进入 timewait 状态，以确保 ACK 包到达对端，以及等待网络中之前迷路的数据包完全消失，防止在端口被复用的时候收到迷路包从而出现收包错误。

timewait 状态会持续 2MSL（max segment lifetime) 的时间，一般会有 1分钟到4分钟事件。这段事件内 端口不可被重分配使用。

timewait 并不会占用更多系统资源，但是可以通过修改内核参数 /etc/sysctl.conf 来达到 限制timewait 数量的功能。

##TIME_WAIT状态原理

通信双方建立TCP连接后，主动关闭连接的一方就会进入TIME_WAIT状态。客户端主动关闭连接时，会发送最后一个ack，然后会进入TIME_WAIT状态，再停留2个MSL时间(后有MSL的解释)，进入CLOSED状态。

上图是以客户端主动关闭连接为例，说明这一过程的。

##TIME_WAIT状态存在的理由

TCP/IP协议就是这样设计的，是不可避免的。主要有两个原因:

###可靠地实现TCP全双工连接的终止

TCP协议在关闭连接的四次握手过程中，最终的ACK是由主动关闭连接的一端（后面统称A端）发出的，如果这个ACK丢失，对方（后面统称B端）将重发出最终的FIN，因此A端必须维护状态信息（TIME_WAIT）允许它重发最终的ACK。如果A端不维持TIME_WAIT状态，而是处于CLOSED 状态，那么A端将响应RST分节，B端收到后将此分节解释成一个错误（在java中会抛出connection reset的SocketException)。
因而，要实现TCP全双工连接的正常终止，必须处理终止过程中四个分节任何一个分节的丢失情况，主动关闭连接的A端必须维持TIME_WAIT状态 。

###允许老的重复分节在网络中消逝
TCP分节可能由于路由器异常而“迷途”，在迷途期间，TCP发送端可能因确认超时而重发这个分节，迷途的分节在路由器修复后也会被送到最终目的地，这个迟到的迷途分节到达时可能会引起问题。在关闭“前一个连接”之后，马上又重新建立起一个相同的IP和端口之间的“新连接”，“前一个连接”的迷途重复分组在“前一个连接”终止后到达，而被“新连接”收到了。为了避免这个情况，TCP协议不允许处于TIME_WAIT状态的连接启动一个新的可用连接，因为TIME_WAIT状态持续2MSL，就可以保证当成功建立一个新TCP连接的时候，来自旧连接重复分组已经在网络中消逝。

MSL时间

MSL就是maximum segment lifetime(最大分节生命期），这是一个IP数据包能在互联网上生存的最长时间，超过这个时间IP数据包将在网络中消失 。MSL在RFC 1122上建议是2分钟，而源自berkeley的TCP实现传统上使用30秒。

TIME_WAIT状态维持时间

TIME_WAIT状态维持时间是两个MSL时间长度，也就是在1-4分钟。Windows操作系统就是4分钟。

##例程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<unistd.h>

int main()
{
    char buf[100];
    strcpy(buf, "hello\nworld");
    write(STDOUT_FILENO, buf, strlen(buf));
}

输出为

hello
world（光标在这里）

int main()
{
    char buf[100];
    strcpy(buf, "hel\0lo\nworld");
    write(STDOUT_FILENO, buf, strlen(buf));
}

输出为

hel（光标在这里）

int main()
{
    char buf[100];
    strcpy(buf, "hello\nworld");
    fputs(buf, stdout);
}

输出为：

hello
world

int main()
{
    char buf[100];
    strcpy(buf, "hel\0lo\nworld");
    fputs(buf, stdout);
}

输出为：

hel（光标在这里）

int main()
{
    char buf[100];
    strcpy(buf, "hello\nworld");
    write(STDOUT_FILENO, buf, strlen(buf));
}

输出：

hello
world(光标在这里)

##总结
其余socket的数据传输函数也是如此，只以\0作为字符串的结尾，而不是\n，\n将被认为是字符进行传输，并且后面的字符也会传输，直到遇到\0为止

如果只要打印某一部分字符，则在此字符串之后一定要加\0，因为\0才被认为是一个字符串的结束符

转载自这里

在TCP/IP中能够实现传输层功能的、具有代表性的协议是TCP和UDP。

##TCP：

TCP是面向连接的、可靠的流协议。流就是指不间断的数据结构，你可以把它想象成排水道中的水流。当应用程序采用TCP发送消息时，虽然可以保证发送的顺序，但还是犹如没有任何间隔的数据流发送给接收端。TCP充分地实现了数据传输时各种控制功能，可以进行丢包时的重发控制，还可以对次序乱掉的分包进行顺序控制。而这些在UDP中都没有。此外，TCP作为一种面向有连接的协议，只有在确认通信对端存在时才会发送数据，从而可以控制通信流量的浪费。根据TCP的这些机制，在IP这种无连接的网络上也能够实现高可靠性的通信。

TCP为提供可靠性传输，实行“顺序控制”或“重发控制”机制。此外还具备“流控制（流量控制）”、“拥塞控制”、提供网络利用率等众多功能。

TCP通过检验和、序列号、确认应答、重发控制、连接管理以及窗口控制等机制实现可靠性传输。

###通过序列号与确认应答提高可靠性
在TCP中，当发送端的数据到达接收主机时，接收端主机会返回一个已收到消息的通知。这个消息叫做确认应答（ACK）。

TCP通过肯定的确认应答（ACK）实现可靠的数据传输。当发送端将数据发出之后会等待对端的确认应答。如果有确认应答，说明数据已经成功到达对端。反之，则数据丢失的可能性很大。在一定时间内没有等到确认应答，发送端就可以认为数据已经丢失，并进行重发。由此，即使产生了丢包，仍然能够保证数据能够到达对端，实现可靠传输。未收到确认应答并不意味着数据一定丢失。也有可能是数据对方已经收到，只是返回的确认应答在途中丢失。这种情况也会导致发送端因没有收到确认应答，而认为数据没有到达目的地，从而进行重新发发送。

上述这些确认应答处理、重发控制以及重复控制等功能都可以通过序列号实现。序列号是按顺序给发送数据的每一个字节（8位字节）都标上号码的编号。接收端查询接收数据TCP首部中的序列号和数据的长度，将自己下一步应该接收的序号作为确认应答返送回去。就这样，通过序列号和确认应答号，TCP可以实现可靠传输。

###重发超时如何确定
重发超时是指在重发数据之前，等待确认应答到来的那个特定时间间隔。如果超过了这个时间仍未收到确认应答，发送端将进行数据重发。那么这个重发超时的具体时间长度又是如何确定的呢？

最理想的是，找到一个最小时间，它能保证“确认应答一定能在这个时间内返回”。然而这个时间长短随着数据包途径的网络环境的不同而有所变化。例如在高速的LAN中时间相对较短，而在长距离的通信当中应该比LAN要长一些。即使是在同一个网络中，根据不同时段的网络堵塞程度时间的长短也会发生变化。TCP要求不论处在何种网络环境下都要提供高性能通信，并且无论网络拥堵情况发生何种变化，都必须保持这一特性。为此，它在每次发包时都会计算往返时间及其偏差。将这个往返时间和偏差相加重发超时的时间，就是比这个总和要稍大一点的值。

在BSD的Unix以及Windows系统中，超时都以0.5秒为单位进行控制，因此重发超时都是0.5秒的整数倍。不过，由于最初的数据包还不知道往返时间，所以其重发超时一般设置为6秒左右。数据被重发之后若还是收不到确认应答，则进行再次发送。此时，等待确认应答的时间将会以2倍、4倍的指数函数延长。此外，数据也不会被无限、反复地重发。达到一定重发次数之后，如果仍没有任何确认应答返回，就会判断为网络或对端主机发生了异常，强制关闭连接。并且通知应用通信异常强行终止。

###连接管理
UDP是一种面向无连接的通信协议，因此不检查对端是否可以通信，直接将UDP包发送出去。TCP与此相反，它会在数据通信之前，通过TCP首部发送一个SYN包作为建立连接的请求等待确认应答。如果对端发来确认应答，则认为可以进行数据通信。如果对端的确认应答未能到达，就不会进行数据通信。此外，在通信结束时会进行断开连接的处理（FIN包）。

可以使用TCP首部用于控制的字段来管理TCP连接。一个连接的建立与断开，正常过程至少需要来回发送7个包才能完成。

###TCP以段为单位发送数据
在建立TCP连接的同时，也可以确认发送数据包的单位，我们也可以称其为“最大消息长度”（MSS：Maximum Segment Size）。最理想的情况是，最大消息长度正好是IP中不会被分片处理的最大数据长度。

TCP在传送大量数据时，是以MSS的大小将数据进行分割发送。进行重发时也是以MSS为单位。

MSS是在三次握手的时候，在两端主机之间被计算得出。两端的主机在发出建立连接的请求时，会在TCP首部中写入MSS选项，告诉对方自己的接口能够适应MSS的大小。然后会在两者之间选择一个较小的值投入使用。

###利用窗口控制提高速度
TCP以1个段为单位，每发一个段进行一次确认应答的处理，这样的传输方式有一个缺点，那就是，包的往返时间越长通信性能就越低。

为解决这个问题，TCP引入了窗口这个概念。即使在往返时间较长的情况下，它也能控制网络性能的下降。确认应答不再是以每个分段，而是以更大的单位进行确认时，转发时间将会大幅度的缩短。也就是说，发送端主机，在发送了一个段以后不必要一直等待确认应答，而是继续发送。

窗口大小就是无需等待确认应答而可以继续发送数据的最大值，如上，窗口大小为4个段。这个机制实现了使用大量的缓冲区，通过对多个段同时进行确认应答的功能。
收到确认应答的情况下，将窗口滑动到确认应答中的序列号的位置。这样可以顺序地将多个段同时发送提高通信性能。这种机制也被成为滑动窗口控制。

###流控制
发送端根据自己的实际情况发送数据。但是，接收端可能收到的是一个毫无关系的数据包又可能会在处理其他问题上花费一些时间。因此在为这个数据包做其他处理时会耗费一些时间，甚至在高负荷的情况下无法接收任何数据。如此一来，如果接收端将本应该接收的数据丢弃的话，就又会触发重发机制，从而导致网络流量的无端浪费。
为了防止这种现象的发生，TCP提供一种机制可以让发送端根据接收端的实际接收能力控制发送的数据量。这就是所谓的流控制。它的具体操作是，接收端主机向发送端主机通知自己可以接收数据的大小，于是发送端会发送不超过这个限度的数据。该大小限度就被称作窗口大小。

TCP首部中，专门有一个字段用来通知窗口大小。接收主机将自己可以接收的缓冲区大小放入这个字段中通知给发送端。这个字段的值越大，说明网络的吞吐量越高。
不过，接收端的这个缓冲区一旦面临数据溢出时，窗口大小的值也会随之被设置为一个更小的值通知给发送端，从而控制数据发送量。也就是说，发送端主机会根据接收端主机的指示，对发送数据的量进行控制。这也就形成了一个完整的TCP流控制（流量控制）。

###拥塞控制
有了TCP的窗口控制，收发主机之间即使不再以一个数据段为单位发送确认应答，也能够连续发送大量数据包。然而，如果在通信刚开始时就发送大量数据，也可能会引发其他问题。在网络出现堵塞时，如果突然发送一个较大量的数据，极有可能导致整个网络的瘫痪。TCP为了防止该问题的出现，在通信一开始时就会通过一个叫做慢启动的算法得出的数值，对发送数据量进行控制。

首先，为了在发送端调节所要发送数据的量，定义了一个叫做“拥塞窗口”的概念。于是在慢启动的时候，将这个拥塞窗口的大小设置为1个数据段（1MSS）发送数据，之后每收到一次确认应答（ACK），拥塞窗口的值就加1.在发送数据包时，将拥塞窗口的大小与接收端主机通知的窗口大小做比较，然后按照它们当中较小的那个值，发送比其还要小的数据量。

###提高网络利用率的规范
Nagle算法：
TCP中为了提高网络的利用率，经常使用一个叫做Nagle的算法。该算法是指发送端即使还有应该发送的数据，但如果这部分数据很少的话，则进行延迟发送的一种处理机制。具体来说，就是仅在下列任意一种条件下才能发送数据。如果两个条件都不满足，那么暂时等待一段时间以后再进行数据发送。

1. 已发送的数据都已经收到确认应答时
2. 可以发送最大段长度（MSS）的数据时

延迟确认应答：

当某个接收端收到这个小窗口的通知以后，会以它为上限发送数据，从而又降低了网络的利用率。为此，引入了一个方法，那就是收到数据以后并不立即返回确认应答，而是延迟一段时间的机制。

捎带应答：

捎带应答是指在同一个TCP包中既发送数据又发送确认应答的一种机制。由此，网络的利用率会提高，计算机的负荷也会减轻。不过，确认应答必须得等到应用处理完数据并将作为回执的数据返回为止，才能进行捎带应答。

##UDP：
UDP是User Datagram Protocol的缩写。UDP是不具有可靠性的数据报协议。细微的处理它会交给上层的应用去完成。在UDP的情况下，虽然可以确保发送消息的大小，却不能保证消息一定会到达。因此，应用有时会根据自己的需要进行重发处理。

UDP不提供复杂的控制机制，利用IP提供面向无连接的通信服务。并且它是将应用程序发来的数据在收到的那一刻，立即按照原样发送到网络上的一种机制。

即使是出现网络堵塞的情况下，UDP也无法进行流量控制等避免网络拥塞的行为。此外，传输途中即使出现丢包，UDP也不负责重发。甚至当出现包的到达顺序乱掉时也没有纠正的功能。如果需要这些细节控制，那么不得不交由采用UDP的应用程序去处理。UDP有点类似于用户说什么听什么的机制，但是需要用户充分考虑好上层协议类型并制作相应的应用程序。因此，也可以说，UDP按照“制造程序的那些用户的指示行事”。
由于UDP面向无连接，它可以随时发送数据。再加上UDP本身的处理既简单又高效，因此经常用于以下几个方面：

1. 包总量较少的通信（DNS、SNMP等）
2. 视频、音频等多媒体通信（即时通信）
3. 限定于LAN等特定网络中的应用通信
4. 广播通信（广播、多播）

可能有人会认为，鉴于TCP是可靠的传输协议，那么它一定优于UDP。其实不然。TCP与UDP的优缺点无法简单地、绝对地去做比较。那么，对这两种协议应该如何加以区分使用呢？下面，我就对此问题做一简单说明。

TCP用于在传输层有必要实现可靠的情况。由于它是面向有连接并具备顺序控制、重发控制等机制的，所以它可以为应用提供可靠传输。

而UDP主要用于那些对高速传输和实时性有较高要求的通信或广播通信。我们拿通过IP电话进行通话作为例子。如果使用TCP，数据在传送途中如果丢失会重发，但这样无法刘畅地传输通话人的声音，会导致无法进行正常交流。而采用UDP，它不会进行重发处理。从而也就不会有声音大幅度延迟到达的问题。即使有部分数据丢失，也只是会影响某一小部分的通话。此外，在多播与广播通信中也使用UDP而不是TCP。RIP、DHCP等基于广播的协议也要依赖于UDP。因此，TCP和UDP应该根据应用的目的按需使用。

转载自这里

##引言

对于任何使用 C 语言的人，如果问他们 C 语言的最大烦恼是什么，其中许多人可能会回答说是指针和内存泄漏。这些的确是消耗了开发人员大多数调试时间的事项。指针和内存泄漏对某些开发人员来说似乎令人畏惧，但是一旦您了解了指针及其关联内存操作的基础，它们就是您在 C 语言中拥有的最强大工具。

本文将与您分享开发人员在开始使用指针来编程前应该知道的秘密。本文内容包括：

• 导致内存破坏的指针操作类型
• 在使用动态内存分配时必须考虑的检查点
• 导致内存泄漏的场景

如果您预先知道什么地方可能出错，那么您就能够小心避免陷阱，并消除大多数与指针和内存相关的问题。

##什么地方可能出错？
有几种问题场景可能会出现，从而可能在完成生成后导致问题。在处理指针时，您可以使用本文中的信息来避免许多问题。

###未初始化的内存
在本例中，p 已被分配了 10 个字节。这 10 个字节可能包含垃圾数据，如图 1 所示。

char *p = malloc ( 10 );

如果在对这个 p 赋值前，某个代码段尝试访问它，则可能会获得垃圾值，您的程序可能具有不可预测的行为。p 可能具有您的程序从未曾预料到的值。

良好的实践是始终结合使用 memset 和 malloc，或者使用 calloc。

char *p = malloc (10);
memset(p,’’,10);

现在，即使同一个代码段尝试在对 p 赋值前访问它，该代码段也能正确处理 Null 值（在理想情况下应具有的值），然后将具有正确的行为。

###内存覆盖
由于 p 已被分配了 10 个字节，如果某个代码片段尝试向 p 写入一个 11 字节的值，则该操作将在不告诉您的情况下自动从其他某个位置“吃掉”一个字节。让我们假设指针 q 表示该内存。

结果，指针 q 将具有从未预料到的内容。即使您的模块编码得足够好，也可能由于某个共存模块执行某些内存操作而具有不正确的行为。下面的示例代码片段也可以说明这种场景。

char *name = (char *) malloc(11);
// Assign some value to name
memcpy ( p,name,11); // Problem begins here

在本例中，memcpy 操作尝试将 11 个字节写到 p，而后者仅被分配了 10 个字节。

作为良好的实践，每当向指针写入值时，都要确保对可用字节数和所写入的字节数进行交叉核对。一般情况下，memcpy 函数将是用于此目的的检查点。

###内存读取越界
内存读取越界 (overread) 是指所读取的字节数多于它们应有的字节数。这个问题并不太严重，在此就不再详述了。下面的代码提供了一个示例。

char *ptr = (char *)malloc(10);
char name[20] ;
memcpy ( name,ptr,20); // Problem begins here

在本例中，memcpy 操作尝试从 ptr 读取 20 个字节，但是后者仅被分配了 10 个字节。这还会导致不希望的输出。

###内存泄漏
内存泄漏可能真正令人讨厌。下面的列表描述了一些导致内存泄漏的场景。
重新赋值我将使用一个示例来说明重新赋值问题。

char *memoryArea = malloc(10);
char *newArea = malloc(10);

这向如下面的图 4 所示的内存位置赋值。

memoryArea 和 newArea 分别被分配了 10 个字节，它们各自的内容如图 4 所示。如果某人执行如下所示的语句（指针重新赋值）……

memoryArea = newArea;

则它肯定会在该模块开发的后续阶段给您带来麻烦。

在上面的代码语句中，开发人员将 memoryArea 指针赋值给 newArea 指针。结果，memoryArea 以前所指向的内存位置变成了孤立的，如下面的图 5 所示。它无法释放，因为没有指向该位置的引用。这会导致 10 个字节的内存泄漏。

在对指针赋值前，请确保内存位置不会变为孤立的。

• 首先释放父块

假设有一个指针 memoryArea，它指向一个 10 字节的内存位置。该内存位置的第三个字节又指向某个动态分配的 10 字节的内存位置，如图 6 所示。

free(memoryArea)

如果通过调用 free 来释放了 memoryArea，则 newArea 指针也会因此而变得无效。newArea 以前所指向的内存位置无法释放，因为已经没有指向该位置的指针。换句话说，newArea 所指向的内存位置变为了孤立的，从而导致了内存泄漏。

每当释放结构化的元素，而该元素又包含指向动态分配的内存位置的指针时，应首先遍历子内存位置（在此例中为 newArea），并从那里开始释放，然后再遍历回父节点。

这里的正确实现应该为：

free( memoryArea->newArea);
free(memoryArea);

• 返回值的不正确处理

有时，某些函数会返回对动态分配的内存的引用。跟踪该内存位置并正确地处理它就成为了 calling 函数的职责。

char *func ( )
{
 return malloc(20); // make sure to memset this location to ‘’…
}
void callingFunc ( )
{
 func ( ); // Problem lies here
}

在上面的示例中，callingFunc() 函数中对 func() 函数的调用未处理该内存位置的返回地址。结果，func() 函数所分配的 20 个字节的块就丢失了，并导致了内存泄漏。

###归还您所获得的
在开发组件时，可能存在大量的动态内存分配。您可能会忘了跟踪所有指针（指向这些内存位置），并且某些内存段没有释放，还保持分配给该程序。

始终要跟踪所有内存分配，并在任何适当的时候释放它们。事实上，可以开发某种机制来跟踪这些分配，比如在链表节点本身中保留一个计数器（但您还必须考虑该机制的额外开销）。

###访问空指针
访问空指针是非常危险的，因为它可能使您的程序崩溃。始终要确保您不是 在访问空指针。

##总结
本文讨论了几种在使用动态内存分配时可以避免的陷阱。要避免内存相关的问题，良好的实践是：

• 始终结合使用 memset 和 malloc，或始终使用 calloc。
• 每当向指针写入值时，都要确保对可用字节数和所写入的字节数进行交叉核对。
• 在对指针赋值前，要确保没有内存位置会变为孤立的。
• 每当释放结构化的元素（而该元素又包含指向动态分配的内存位置的指针）时，都应首先遍历子内存位置并从那里开始释放，然后再遍历回父节点。
• 始终正确处理返回动态分配的内存引用的函数返回值。
• 每个 malloc 都要有一个对应的 free。
• 确保您不是在访问空指针。

如果你的代码所在的进程中有多个线程在同时运行，而这些线程可能会同时运行这段代码。如果每次运行结果和单线程运行的结果是一样的，而且其他的变量的值也和预期的是一样的，就是线程安全的。

或者说:一个类或者程序所提供的接口对于线程来说是原子操作或者多个线程之间的切换不会导致该接口的执行结果存在二义性,也就是说我们不用考虑同步的问题。

线程安全问题都是由全局变量及静态变量引起的。

若每个线程中对全局变量、静态变量只有读操作，而无写操作，一般来说，这个全局变量是线程安全的；若有多个线程同时执行写操作，一般都需要考虑线程同步，否则的话就可能影响线程安全。

##举例
比如一个 ArrayList 类，在添加一个元素的时候，它可能会有两步来完成：

1. 在 Items[Size] 的位置存放此元素
2. 增大 Size 的值。

在单线程运行的情况下，如果 Size = 0，添加一个元素后，此元素在位置 0，而且 Size=1；

而如果是在多线程情况下，比如有两个线程，线程 A 先将元素存放在位置 0。但是此时 CPU 调度线程A暂停，线程 B 得到运行的机会。线程B也向此 ArrayList 添加元素，因为此时 Size 仍然等于 0 （注意哦，我们假设的是添加一个元素是要两个步骤哦，而线程A仅仅完成了步骤1），所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行，都增加 Size 的值。

那好，我们来看看 ArrayList 的情况，元素实际上只有一个，存放在位置 0，而 Size 却等于 2。这就是“线程不安全”了。

参考书籍是:《数据结构与算法分析-c语言描述，weiss著》

下图是排序算法时间复杂度等特性的一个总结：

下面详细总结一下各个算法，总结的方面包括：

1. 每个算法的思想是什么？
2. 每个算法的稳定性怎样？时间复杂度如何？
3. 在什么情况下，算法出现最好情况 or 最坏情况？
4. 每种算法的具体实现又是怎样的？

##各个排序算法的空间复杂度
大家往往只关心时间复杂度，而忽略了空间复杂度，所以这里讲空间复杂度提到前面来讲

冒泡排序，简单选择排序，堆排序，直接插入排序，希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置，(另外遍历序列时自然少不了用一个变量来做索引)

快速排序空间复杂度为log2n(因为递归调用了)；归并排序空间复杂是O(n)，需要一个大小为n的临时数组.

这里的一个问题是，归并排序也递归了，为什么时间复杂度不是log2n?

答：
归并排序每次递归都要用到一个辅助表，长度与待排序的表长度相同，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了，因而空间复杂度还是O（n）。

快速排序空间复杂度只是在通常情况下才为O(log2n)，如果是最坏情况的话，很显然就要O(n)的空间了。当然，可以通过随机化选择pivot来将空间复杂度降低到O(log2n)。

##冒泡排序

###基本思想
通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。

###时间复杂度

最好情况下：正序有序，则只需要比较n次。故，为O(n)

最坏情况下：逆序有序，则需要比较(n-1)+(n-2)+……+1，故为O(n*n)

###稳定性
排序过程中只交换相邻两个元素的位置。因此，当两个数相等时，是没必要交换两个数的位置的。所以，它们的相对位置并没有改变，冒泡排序算法是稳定的！

##代码

#define elementtype int
void bubble_sort(elementtype *array, int n) {
    elementtype tmp;
    int i = 0, j = 0;
    for(; i < n - 1; i++) {
        for(j = n -1; j > i; j--) {
            if(array[j] < array[j - 1]) {
                swap(array[j], array[j-1]);
            }
        }
    }
}

##选择排序

###思想
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。具体做法是：选择最小的元素与未排序部分的首部交换，使得序列的前面为有序。

选择排序是和冒泡排序差不多的一种排序。和冒泡排序交换相连数据不一样
的是，选择排序只有在确定了最小的数据之后，才会发生交换

###时间复杂度
最好情况：交换0次，但是每次都要找到最小的元素，因此大约必须遍历N*N次，因此为O(N*N)。减少了交换次数！

最坏情况：平均情况下：O(N*N)

###稳定性
由于每次都是选取未排序序列A中的最小元素x与A中的第一个元素交换，因此跨距离了，很可能破坏了元素间的相对位置，因此选择排序是不稳定的！

例如数组为5,5,3，第一次就会将第一个5和3交换

###代码

void select_sort(elementtype *array, int n) {
    elementtype tmp;
    int i, j, index;
    if(array == NULL && n < 0)
        exit(-1);

    for(i = 0; i < n - 1; i++) {
        index = i;
        for(j = i + 1; j < n; j ++) {
            if(array[j] < array[index])
                index = j;
        }

        if(index != i) {
            swap(array[i], array[index]);
        }
    }
}

##插入排序

###思想
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法—-插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

###时间复杂度
最好的情况：正序有序(从小到大)，这样只需要比较n次，不需要移动。因此时间复杂度为O(n)
最坏的情况：逆序有序,这样每一个元素就需要比较n次，共有n个元素，因此实际复杂度为O(n­2)
平均情况：O(n­2)

###稳定性
理解性记忆比死记硬背要好。因此，我们来分析下。稳定性，就是有两个相同的元素，排序先后的相对位置是否变化，主要用在排序时有多个排序规则的情况下。在插入排序中，K1是已排序部分中的元素，当K2和K1比较时，直接插到K1的后面(没有必要插到K1的前面，这样做还需要移动！！)，因此，插入排序是稳定的。

###代码

void insert_sort(elementtype *array, int n) {
    elementtype tmp;
    int p, j;
    for(p = 1; p < n; p++) {
        tmp = array[p];
        for(j = p; j > 0 && array[j - 1] > tmp; j--) {
            array[j]= array[j - 1];
        }
        array[j] = tmp;
    }
}

##shell排序

###思想
Shell排序是DL. Shell于1959年针对直接插入排序算法改进提出的，属于插入排序的范畴，是对直接插入排序算法的改进。直接插入排序在基本有序时效率较高，并且在序列规模不是很大时效率也很高，Shell排序就是针对这两点进行改进。核心思想是：待排序列有n个元素，先取一个小于n的整数h1作为第一个增量，把待排序列以间隔h1分成若干子序列，子序列内使用插入排序；然后取第二个增量h2(< h1)，重复上述的划分和排序，
直至所取的增量hl = 1 (h1 > h2 > … > hl)。

这样不管序列多么庞大，在先前较大步长分组下每个子序列规模都不是很大，用直接插入效率很高；后面步长变小，子序列变大，但由于整体有序性越来越明显，排序效率依然很高，大大提高了时间效率。

###时间复杂度

最好情况：由于希尔排序的好坏和步长d的选择有很多关系，因此，目前还没有得出最好的步长如何选择(现在有些比较好的选择了，但不确定是否是最好的)。所以，不知道最好的情况下的算法时间复杂度。

最坏情况：O(N*logN)，最坏的情况下和平均情况下差不多。

平均情况：O(N*logN)

###稳定性
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

有个猜测，方便记忆：一般来说，若存在不相邻元素间交换，则很可能是不稳定的排序。

###代码

void shell_sort(elementtype *array, int n) {
    elementtype tmp;
    int increment, i, j;
    for(increment = n/2; increment > 0; increment /= 2) {
        for(i = increment; i < n; i++) {
            tmp = array[i];
            for(j = i; j >= increment && array[j - increment] > tmp; j -= increment)
                    array[j] = array[j - increment];

            array[j] = tmp;
        }
    }
}

##堆排序

###思想
利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或者最小)的记录。也就是说，以最小堆为例，根节点为最小元素，较大的节点偏向于分布在堆底附近。

###时间复杂度
最坏情况下，接近于最差情况下：O(N*logN)，因此它是一种效果不错的排序算法

###稳定性
堆排序需要不断地调整堆，因此堆排序是一种不稳定的排序！

###代码

#define LeftChild(i) (2 * (i) + 1)
void perc_down(int *a, int i, int size)
{
    int child;

    int tmp = a[i];

    for(; LeftChild(i) < size ; i = child)
    {
        child = LeftChild(i);
        if(child != size - 1 && a[child] < a[child + 1])
                child ++;

        /***************************
         * 提升儿子到父结点，
         * 儿子结点的位置上存在空穴，
         * 需要继续比较
         **************************/
        if(a[child] > tmp)
                a[i] = a[child];
        else/*不需要提升*/
                break;
    }
    /*保存结点的位置找到*/
    a[i] = tmp;
}

void build_maxheap(int *a, int size)
{
    int step = 0;

    /***************************************
     * (size-1)/2实质是找到a[size-1]的父结点，
     * 也就是倒数第二层，堆的创建过程是一个
     * 由低层到高层逐渐创建的过程
     **************************************/
    for(step = (size - 1) / 2 ; step >= 0; -- step)
        perc_down(a, step, size);
}

void heap_sort(int *a, int size)
{
    int i = 0;
    /*创建堆*/
    build_maxheap(a,size);

    for(; i < size; i++)
        printf("%d ", a[i]);
    printf("\n");

    for(i = size - 1; i > 0; --i)
    {
        swap(a[i],a[0])；

        /*更新堆的结构*/
        perc_down(a,0,i);

    }

}

##归并排序

###思想
多次将两个或两个以上的有序表合并成一个新的有序表。

###时间复杂度

最好的情况：一趟归并需要n次，总共需要logN次，因此为O(N*logN)

最坏的情况： 接近于平均情况，为O(N*logN)

说明：对长度为n的文件，需进行logN 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

###稳定性
归并排序最大的特色就是它是一种稳定的排序算法。归并过程中是不会改变元素的相对位置的。

缺点是，它需要O(n)的额外空间。但是很适合于多链表排序。

###代码

/*left_start is the start of the left half, right_start is the start of the
  right half*/
void merge(int *array, int *tmp_array, int left_start, int right_start, int right_end)
{
    int left_end = right_start-1;
    int length = right_end-left_start+1;

    int tmp_pos = left_start;

    while(left_start <= left_end && right_start <= right_end) {
        if(array[left_start] <= array[right_start])
            tmp_array[tmp_pos++] = array[left_start++];
        else
            tmp_array[tmp_pos++] = array[right_start++];
    }

    /*main loop*/
    while(left_start <= left_end)
        tmp_array[tmp_pos++] = array[left_start++];
    while(right_start <= right_end)
        tmp_array[tmp_pos++] = array[right_start++];

    /*copy tmp_array back
      注意这里必须使用right_end作为数组下标，不能用tmp_pos，因为此时的
      tmp_pos已经越界了，上面多了一次++*/
    int i;
    for(i = 0; i < length; i++, right_end--)  
        array[right_end] = tmp_array[right_end];
}

void m_sort(int *array, int *tmp_array, int left, int right)
{
    int mid;

    if(left < right) {
        mid = (left + right)/2;
        m_sort(array, tmp_array, left, mid);
        m_sort(array, tmp_array, mid+1, right);
        merge(array, tmp_array, left, mid+1, right);
    }
}

void merge_sort(int *array, int n)
{
    if(array == NULL || n <= 0)
        exit(-1);

    int *tmp_array = (int *)malloc(n * sizeof(int));

    if(tmp_array != NULL) {
        m_sort(array, tmp_array, 0, n-1);
        free(tmp_array);
    }
    else
        exit(-1);
}

merge例程是精妙的。如果对merge的每个递归调用均局部声明一个临时数组，那么在任一时刻就可能有logN个临时数组处在活动期，这对于小内存的机器则是致命的。另一方面，如果merge例程动态分配并释放最小量临时内存，那么由malloc占用的时间会很多。严格测试指出，由于merge位于m_sort的最后一行，因此在任一时刻只需要一个临时数组活动，而且可以使用该临时数组的任意部分；我们将使用与输入数组array相同的部分。

#快速排序

###思想
它是由冒泡排序改进而来的。在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。

###时间复杂度
最好的情况：因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)，故为 O(N*logN)

最坏的情况：序列基本有序，选取的枢轴元素为最大值或最小值时，退化为冒泡排序，几乎要比较N*N/2次，故为O(N*N)

如何避免最坏情况：为改进快速排序算法，随机选取界点或最左、最右、中间三个元素中的值处于中间的作为界点，通常可以避免原始序列有序的最坏情况。

###稳定性
由于每次都需要和中轴元素交换，因此原来的顺序就可能被打乱。如序列为 5 3 3 4 3 8 9 10 11会将3的顺序打乱。所以说，快速排序是不稳定的！

###代码

/*数据交换*/
void swap(int *x,int *y)
{
   int temp;
   temp = *x;
   *x = *y;
   *y = temp;
}

int choose_pivot(int i,int j )
{
   return((i+j) /2);
}

/*递归和分治*/
void quick_sort(int list[],int left,int right)
{
   int key,i,j,k;
   if(left < right)
   {
      k = (left + right) / 2;
      swap(&list[left],&list[k]);
      key = list[left];
      i = left+1;
      j = right;
      while(1)
      {
         while((i < right) && (list[i] < key))
                i++;
         while((j > left) && (list[j] > key))
                j--;
         if( i < j) {
                swap(&list[i],&list[j]);
                //仅仅是为了防止死循环，见P183
                if(list[i] == list[j] && list[i] == key) {  
                    i++;  //j--;
                }
         }
         else
            break;
      }
     // 交换两个元素的位置
      swap(&list[left],&list[j]);
     // 递归地对较小的数据序列进行排序
      quick_sort(list,left,j-1);
      quick_sort(list,j+1,right);
   }
} 

快排在数据少的时候是不占优势的，所以一般是在数据少的时候用插入排序，数据多的时候用快排。上面的快排程序对书上的程序作了修改，防止了死循环，但并不是一个好程序。比较好的快排实现可以看这里

##df
对于磁盘存储方面，有很多命令行或基于GUI的工具，它可以告诉你关于当前磁盘空间的使用情况。这些工具用各种人们可读的格式展示磁盘利用率的详细信息，比如易于理解的总结，详细的统计信息或直观的可视化报告。如果你只想知道不同文件系统有多少空闲的磁盘空间，那么df命令可能是你所需要的。

[root@pc105 /]# df
Filesystem           1K-blocks     Used Available Use% Mounted on
/dev/mapper/VolGroup-lv_root
                      51475068 48090628    763000  99% /
tmpfs                  8135664       72   8135592   1% /dev/shm
/dev/sda1               487652    93128    368924  21% /boot
/dev/mapper/VolGroup-lv_home
                     901109008  4270596 851058036   1% /home
tmpfs                   102400        4    102396   1% /var/log/pearl2
tmpfs                  8135664        4   8135660   1% /var/run/pearl2

df命令可以展示任何“mounted”文件系统的磁盘利用率。该命令可以用不同的方式调用。

###用人们可读的方式展示
默认情况下，df命令用1K为块来展示磁盘空间，这看起来不是很直观。“-h”参数使df用更可读的方式打印磁盘空间（例如 100K，200M，3G）。

[root@pc105 /]# df -h
Filesystem            Size  Used Avail Use% Mounted on
/dev/mapper/VolGroup-lv_root
                       50G   46G  746M  99% /
tmpfs                 7.8G   72K  7.8G   1% /dev/shm
/dev/sda1             477M   91M  361M  21% /boot
/dev/mapper/VolGroup-lv_home
                      860G  4.1G  812G   1% /home
tmpfs                 100M  4.0K  100M   1% /var/log/pearl2
tmpfs                 7.8G  4.0K  7.8G   1% /var/run/pearl2

###展示Inode使用情况
当你监视磁盘使用情况时，你必须注意的不仅仅是磁盘空间还有“inode”的使用情况。在Linux中，inode是用来存储特定文件的元数据的一种数据结构，在创建一个文件系统时，inode的预先定义数量将被分配。这意味着，一个文件系统可能耗尽空间不只是因为大文件用完了所有可用空间，也可能是因为很多小文件用完了所有可能的inode。用“-i”选项展示inode使用情况。

[root@pc105 /]# df -i
Filesystem             Inodes  IUsed    IFree IUse% Mounted on
/dev/mapper/VolGroup-lv_root
                      3276800 635298  2641502   20% /
tmpfs                 2033916      3  2033913    1% /dev/shm
/dev/sda1              128016     53   127963    1% /boot
/dev/mapper/VolGroup-lv_home
                     57229312  35042 57194270    1% /home
tmpfs                 2033916      2  2033914    1% /var/log/pearl2
tmpfs                 2033916      2  2033914    1% /var/run/pearl2

###展示磁盘总利用率
默认情况下， df命令显示磁盘的单个文件系统的利用率。如果你想知道的所有文件系统的总磁盘使用量，增加“ –total ”选项（见最下面的汇总行）。

[root@pc105 /]# df -h --total
Filesystem            Size  Used Avail Use% Mounted on
/dev/mapper/VolGroup-lv_root
                       50G   46G  746M  99% /
tmpfs                 7.8G   72K  7.8G   1% /dev/shm
/dev/sda1             477M   91M  361M  21% /boot
/dev/mapper/VolGroup-lv_home
                      860G  4.1G  812G   1% /home
tmpfs                 100M  4.0K  100M   1% /var/log/pearl2
tmpfs                 7.8G  4.0K  7.8G   1% /var/run/pearl2
total                 925G   51G  829G   6%

##du
Linux du命令也是查看使用空间的，但是与df命令不同的是Linux du命令是对文件和目录磁盘使用的空间的查看，还是和df命令有一些区别的.

###显示目录或者文件所占空间

[root@localhost test]# du
608     ./test6
308     ./test4
4       ./scf/lib
4       ./scf/service/deploy/product
4       ./scf/service/deploy/info
12      ./scf/service/deploy
16      ./scf/service
4       ./scf/doc
4       ./scf/bin
32      ./scf
8       ./test3
1288    .
[root@localhost test]#

只显示当前目录下面的子目录的目录大小和当前目录的总的大小，最下面的1288为当前目录的总大小

###显示指定文件所占空间

[root@localhost test]# du log2012.log 
300     log2012.log
[root@localhost test]#

###查看指定目录的所占空间

[root@localhost test]# du scf
4       scf/lib
4       scf/service/deploy/product
4       scf/service/deploy/info
12      scf/service/deploy
16      scf/service
4       scf/doc
4       scf/bin
32      scf
[root@localhost test]#

###显示多个文件所占空间

[root@localhost test]# du log30.tar.gz log31.tar.gz 
4       log30.tar.gz
4       log31.tar.gz
[root@localhost test]#

###只显示总和的大小

[root@localhost test]# du -s
1288    .
[root@localhost test]# du -s scf
32      scf
[root@localhost test]# cd ..
[root@localhost soft]# du -s test
1288    test
[root@localhost soft]#

###方便阅读的格式显示

[root@localhost soft]# du -h test
608K    test/test6
308K    test/test4
4.0K    test/scf/lib
4.0K    test/scf/service/deploy/product
4.0K    test/scf/service/deploy/info
12K     test/scf/service/deploy
16K     test/scf/service
4.0K    test/scf/doc
4.0K    test/scf/bin
32K     test/scf
8.0K    test/test3
1.3M    test
[root@localhost soft]#

###文件和目录都显示

[root@localhost soft]# du -ah test
4.0K    test/log31.tar.gz
4.0K    test/test13.tar.gz
300K    test/test6/linklog.log
4.0K    test/test6/log2013.log
300K    test/test6/log2012.log
608K    test/test6
4.0K    test/test4/log2013.log
300K    test/test4/log2012.log
308K    test/test4
4.0K    test/scf/lib
4.0K    test/scf/service/deploy/product
4.0K    test/scf/service/deploy/info
12K     test/scf/service/deploy
16K     test/scf/service
4.0K    test/scf/doc
4.0K    test/scf/bin
32K     test/scf
4.0K    test/log2013.log
300K    test/log2012.log
4.0K    test/log30.tar.gz
4.0K    test/log.tar.bz2
4.0K    test/log.tar.gz
4.0K    test/test3/log2013.log
8.0K    test/test3
4.0K    test/scf.tar.gz
1.3M    test
[root@localhost soft]#

###显示几个文件或目录各自占用磁盘空间的大小，还统计它们的总和

[root@localhost test]# du -c log30.tar.gz log31.tar.gz 
4       log30.tar.gz
4       log31.tar.gz
8       总计
[root@localhost test]#

###按照空间大小排序

[root@localhost test]# du|sort -nr|more
1288    .
608     ./test6
308     ./test4
32      ./scf
16      ./scf/service
12      ./scf/service/deploy
8       ./test3
4       ./scf/service/deploy/product
4       ./scf/service/deploy/info
4       ./scf/lib
4       ./scf/doc
4       ./scf/bin
[root@localhost test]#

###输出当前目录下各个子目录所使用的空间

[root@localhost test]# du -h  --max-depth=1
608K    ./test6
308K    ./test4
32K     ./scf
8.0K    ./test3
1.3M    .
[root@localhost test]#

转载自这里

当你在浏览网站的时候，WEB 服务器会先送一小小资料放在你的计算机上，Cookie 会把你在网站上所打的文字或是一些选择都纪录下来。当下次你再光临同一个网站，WEB 服务器会先看看有没有它上次留下的 Cookie 资料，有的话，就会依据 Cookie
里的内容来判断使用者，送出特定的网页内容给你。 Cookie 的使用很普遍，许多提供个人化服务的网站，都是利用 Cookie来辨认使用者，以方便送出使用者量身定做的内容，像是 Web 接口的免费 email 网站，都要用到 Cookie。

具体来说cookie机制采用的是在客户端保持状态的方案，而session机制采用的是在服务器端保持状态的方案。

同时我们也看到，由于采用服务器端保持状态的方案在客户端也需要保存一个标识，所以session机制可能需要借助于cookie机制来达到保存标识的目的，但实际上它还有其他选择。

cookie机制。正统的cookie分发是通过扩展HTTP协议来实现的，服务器通过在HTTP的响应头中加上一行特殊的指示以提示浏览器按照指示生成相应的cookie。然而纯粹的客户端脚本如JavaScript或者VBScript也可以生成cookie。而cookie的使用是由浏览器按照一定的原则在后台自动发送给服务器的。浏览器检查所有存储的cookie，如果某个cookie所声明的作用范围大于等于将要请求的资源所在的位置，则把该cookie附在请求资源的HTTP请求头上发送给服务器。

cookie的内容主要包括：名字，值，过期时间，路径和域。路径与域一起构成cookie的作用范围。若不设置过期时间，则表示这个cookie的生命期为浏览器会话期间，关闭浏览器窗口，cookie就消失。这种生命期为浏览器会话期的cookie被称为会话cookie。

会话cookie一般不存储在硬盘上而是保存在内存里，当然这种行为并不是规范规定的。若设置了过期时间，浏览器就会把cookie保存到硬盘上，关闭后再次打开浏览器，这些cookie仍然有效直到超过设定的过期时间。存储在硬盘上的cookie可以在不同的浏览器进程间共享，比如两个IE窗口。而对于保存在内存里的cookie，不同的浏览器有不同的处理方式。

session机制。session机制是一种服务器端的机制，服务器使用一种类似于散列表的结构（也可能就是使用散列表）来保存信息。

当程序需要为某个客户端的请求创建一个session时，服务器首先检查这个客户端的请求里是否已包含了一个session标识（称为session id），如果已包含则说明以前已经为此客户端创建过session，服务器就按照session id把这个session检索出来
使用（检索不到，会新建一个），如果客户端请求不包含session id，则为此客户端创建一个session并且生成一个与此session相关联的session id，session id的值应该是一个既不会重复，又不容易被找到规律以仿造的字符串，这个session id将被在本次响应中返回给客户端保存。保存这个session id的方式可以采用cookie，这样在交互过程中浏览器可以自动的按照规则把这个标识发送给服务器。一般这个cookie的名字都是类似于SEEESIONID。但cookie可以被人为的禁止，则必须有其他机制以便在cookie被禁止时仍然能够把session id传递回服务器。

经常被使用的一种技术叫做URL重写，就是把session id直接附加在URL路径的后面。还有一种技术叫做表单隐藏字段。就是服务器会自动修改表单，添加一个隐藏字段，以便在表单提交时能够把session id传递回服务器。比如：

<form name="testform" action="/xxx"> 
<input type="hidden" name="jsessionid" value="ByOK3vjFD75aPnrF7C2HmdnV6QZcEbzWoWiBYEnLerjQ99zWpBng!-145788764"> 
<input type="text"> 
</form> 

实际上这种技术可以简单的用对action应用URL重写来代替。

cookie 和session 的区别：

1. cookie数据存放在客户的浏览器上，session数据放在服务器上。

2. cookie不是很安全，别人可以分析存放在本地的COOKIE并进行COOKIE欺骗
   考虑到安全应当使用session。

3. session会在一定时间内保存在服务器上。当访问增多，会比较占用你服务器的性能
   考虑到减轻服务器性能方面，应当使用COOKIE。

4. 单个cookie保存的数据不能超过4K，很多浏览器都限制一个站点最多保存20个cookie。

5. 所以个人建议：
   将登陆信息等重要信息存放为SESSION
   其他信息如果需要保留，可以放在COOKIE中

Python编程中常用的12种基础知识总结：遍历目录方法，列表按列排序、去重，字典排序，字典、列表、字符串互转，时间对象操作，命令行参数解析(getopt)，print 格式化输出，进制转换，Python调用系统命令或者脚本，Python 读写文件。

遍历目录方法

在某些时候，我们需要遍历某个目录找出特定的文件列表，可以通过os.walk方法来遍历，非常方便

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

import os
fileList = []
rootdir = "/data"
for root, subFolders, files in os.walk(rootdir):
    if '.svn' in subFolders: 
        subFolders.remove('.svn')  # 排除特定目录
    for file in files:
        if file.find(".t2t") != -1:# 查找特定扩展名的文件
            file_dir_path = os.path.join(root,file)
            fileList.append(file_dir_path)  
    
print fileList

列表按列排序(list sort)

如果列表的每个元素都是一个元组(tuple),我们要根据元组的某列来排序的话，可参考如下方法

下面例子我们是根据元组的第2列和第3列数据来排序的,而且是倒序(reverse=True)

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

>>> a = [('2011-03-17', '2.26', 6429600, '0.0'), ('2011-03-16', '2.26', 12036900, '-3.0'),
 ('2011-03-15', '2.33', 15615500,'-19.1')]
>>> print a[0][0]
2011-03-17
>>> b = sorted(a, key=lambda result: result[1],reverse=True)
>>> print b
[('2011-03-15', '2.33', 15615500, '-19.1'), ('2011-03-17', '2.26', 6429600, '0.0'),
('2011-03-16', '2.26', 12036900, '-3.0')]
>>> c = sorted(a, key=lambda result: result[2],reverse=True)
>>> print c
[('2011-03-15', '2.33', 15615500, '-19.1'), ('2011-03-16', '2.26', 12036900, '-3.0'),
('2011-03-17', '2.26', 6429600, '0.0')]

列表去重(list uniq)

有时候需要将list中重复的元素删除，就要使用如下方法

1
2
3
4
5
6
7

>>> lst= [(1,'sss'),(2,'fsdf'),(1,'sss'),(3,'fd')]
>>> set(lst)
set([(2, 'fsdf'), (3, 'fd'), (1, 'sss')])
>>>
>>> lst = [1, 1, 3, 4, 4, 5, 6, 7, 6]
>>> set(lst)
set([1, 3, 4, 5, 6, 7])

字典排序(dict sort)

一般来说，我们都是根据字典的key来进行排序，但是我们如果想根据字典的value值来排序，就使用如下方法

1
2
3
4
5
6
7

>>> from operator import itemgetter
>>> aa = {"a":"1","sss":"2","ffdf":'5',"ffff2":'3'}
>>> sort_aa = sorted(aa.items(),key=itemgetter(1))
>>> sort_aa
[('a', '1'), ('sss', '2'), ('ffff2', '3'), ('ffdf', '5')]
或者：
>>> sort_aa = sorted(aa.items(), key=lambda result: result[1])

字典,列表,字符串互转

以下是生成数据库连接字符串,从字典转换到字符串

1
2
3
4
5

>>> params = {"server":"mpilgrim", "database":"master", "uid":"sa", "pwd":"secret"}
>>> ["%s=%s" % (k, v) for k, v in params.items()]
['server=mpilgrim', 'uid=sa', 'database=master', 'pwd=secret']
>>> ";".join(["%s=%s" % (k, v) for k, v in params.items()])
'server=mpilgrim;uid=sa;database=master;pwd=secret'

下面的例子 是将字符串转化为字典

1
2
3
4
5
6

>>> a = 'server=mpilgrim;uid=sa;database=master;pwd=secret'
>>> aa = {}
>>> for i in a.split(';'):aa[i.split('=',1)[0]] = i.split('=',1)[1]  #split('=',1)表示按'='分割1次
...
>>> aa
{'pwd': 'secret', 'database': 'master', 'uid': 'sa', 'server': 'mpilgrim'}

时间对象操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

将时间对象转换成字符串
>>> import datetime
>>> datetime.datetime.now().strftime("%Y-%m-%d %H:%M")
  '2011-01-20 14:05'
 
时间大小比较
>>> import time
>>> t1 = time.strptime('2011-01-20 14:05',"%Y-%m-%d %H:%M")
>>> t2 = time.strptime('2011-01-20 16:05',"%Y-%m-%d %H:%M")
>>> t1 > t2
  False
>>> t1 < t2
  True
 
时间差值计算,计算8小时前的时间
>>> datetime.datetime.now().strftime("%Y-%m-%d %H:%M")
  '2011-01-20 15:02'
>>> (datetime.datetime.now() - datetime.timedelta(hours=8)).strftime("%Y-%m-%d %H:%M")
  '2011-01-20 07:03'
 
将字符串转换成时间对象
>>> endtime=datetime.datetime.strptime('20100701',"%Y%m%d")
>>> type(endtime)
  <type 'datetime.datetime'>
>>> print endtime
  2010-07-01 00:00:00
 
将从 1970-01-01 00:00:00 UTC 到现在的秒数，格式化输出   
 
>>> import time
>>> a = 1302153828
>>> time.strftime("%Y-%m-%d %H:%M:%S",time.localtime(a))
  '2011-04-07 13:23:48'

命令行参数解析(getopt)

通常在编写一些日运维脚本时，需要根据不同的条件，输入不同的命令行选项来实现不同的功能 在Python中提供了getopt模块很好的实现了命令行参数的解析,下面距离说明。请看如下程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys,os,getopt
def usage():
print '''''
Usage: analyse_stock.py [options...]
Options:
-e : Exchange Name
-c : User-Defined Category Name
-f : Read stock info from file and save to db
-d : delete from db by stock code
-n : stock name
-s : stock code
-h : this help info
test.py -s haha -n "HA Ha"
'''
 
try:
opts, args = getopt.getopt(sys.argv[1:],'he:c:f:d:n:s:')
except getopt.GetoptError:
usage()
sys.exit()
if len(opts) == 0:
usage()
sys.exit()  
 
for opt, arg in opts:
if opt in ('-h', '--help'):
  usage()
  sys.exit()
elif opt == '-d':
  print "del stock %s" % arg
elif opt == '-f':
  print "read file %s" % arg
elif opt == '-c':
  print "user-defined %s " % arg
elif opt == '-e':
  print "Exchange Name %s" % arg
elif opt == '-s':
  print "Stock code %s" % arg
elif opt == '-n':
  print "Stock name %s" % arg  
 
sys.exit()

print 格式化输出

截取字符串输出,下面例子将只输出字符串的前3个字母

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

>>> str="abcdefg"
>>> print "%.3s" % str
  abc
按固定宽度输出，不足使用空格补全,下面例子输出宽度为10
>>> str="abcdefg"
>>> print "%10s" % str
     abcdefg
截取字符串，按照固定宽度输出
>>> str="abcdefg"
>>> print "%10.3s" % str
         abc
浮点类型数据位数保留
>>> import fpformat
>>> a= 0.0030000000005
>>> b=fpformat.fix(a,6)
>>> print b
  0.003000
对浮点数四舍五入,主要使用到round函数
>>> from decimal import *
>>> a ="2.26"
>>> b ="2.29"
>>> c = Decimal(a) - Decimal(b)
>>> print c
  -0.03
>>> c / Decimal(a) * 100
  Decimal('-1.327433628318584070796460177')
>>> Decimal(str(round(c / Decimal(a) * 100, 2)))
  Decimal('-1.33')

进制转换

有些时候需要作不同进制转换，可以参考下面的例子(%x 十六进制,%d 十进制,%o 八进制)

1
2
3

>>> num = 10
>>> print "Hex = %x,Dec = %d,Oct = %o" %(num,num,num)
  Hex = a,Dec = 10,Oct = 12

Python调用系统命令或者脚本

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

使用 os.system() 调用系统命令 , 程序中无法获得到输出和返回值
>>> import os
>>> os.system('ls -l /proc/cpuinfo')
>>> os.system("ls -l /proc/cpuinfo")
  -r--r--r-- 1 root root 0  3月 29 16:53 /proc/cpuinfo
  0
 
使用 os.popen() 调用系统命令, 程序中可以获得命令输出，但是不能得到执行的返回值
>>> out = os.popen("ls -l /proc/cpuinfo")
>>> print out.read()
  -r--r--r-- 1 root root 0  3月 29 16:59 /proc/cpuinfo  
 
使用 commands.getstatusoutput() 调用系统命令, 程序中可以获得命令输出和执行的返回值
>>> import commands
>>> commands.getstatusoutput('ls /bin/ls')
  (0, '/bin/ls')

Python 读写文件

一次性读入文件到列表，速度较快，适用文件比较小的情况下
track_file = "track_stock.conf"
fd = open(track_file)
content_list = fd.readlines()
fd.close()
for line in content_list:
    print line  

逐行读入，速度较慢,适用没有足够内存读取整个文件(文件太大)
fd = open(file_path)
fd.seek(0)
title = fd.readline()
keyword = fd.readline()
uuid = fd.readline()
fd.close()  

写文件 write 与 writelines 的区别   

Fd.write(str) : 把str写到文件中，write()并不会在str后加上一个换行符
Fd.writelines(content) : 把content的内容全部写到文件中,原样写入，不会在每行后面加上任何东西

按F5刷新浏览器和在地址栏里输入网址然后回车。 这两个行为是不一样的。

按F5刷新浏览器， 浏览器会去Web服务器验证缓存。

如果是在地址栏输入网址然后回车，浏览器会”直接使用有效的缓存”, 而不会发http request 去服务器验证缓存，这种情况叫做缓存命中，如下图

实例： 比较第一次访问博客园主页和第二次博客园主页

1. 启动Fiddler, 用firefox打开博客园主页， 发现有50多个session。

2. 按CTRL+X将Fiddler中的所有session删除。 关闭firefox,重新打开一个firefox，打开博客园主页。 发现只有30多个session.

分析； 少了的session是因为firefox直接用了缓存，而没有发http request。