2010年5月19日
1. merge sort
2.线程安全
3.冒泡,快排,堆,插入 排序
4.时间复杂度
5.二叉树
6.java=>继承,protected 父子...
7.Linux 基础
2010年5月2日
早期的TCP实现,本来是为了 提高传输效率&&控制传输速率 而存在的滑动窗口[Sliding window] 机制,在发送方和接收方 生产和消耗数据的速率差异较大时,会产生一种比较犯傻的传输状态:发送方发送的数据报文[Segment] 具有一个大大的头部,附带的数据却少得可怜.
犯傻症的产生
考虑以下两种情况:
1.接收方的应用程序读取数据老慢老慢,一次只1byte.
可以想见,很快,接收方的缓存被填满,于是回发窗口通告[window advtisement]说:已满,勿发.
接下来,应用程序慢吞吞的读入1byte,缓存空余出来一字节,兴高采烈的再次回发窗口通告说:一字节可用,快来填满我.
发送方接到通告,生成并传送数据部分只一字节的报文.
然后,如此重复.
很明显,这样不好,效率太低. 一般TCP报文头部大小最少也是20字节,结果只拖这么点数据过去,头部的处理(校验和的计算,流的序列号的读取,数据的提取),到IP数据报的封装及相应的解封 又要照行不误,实在效率忒也底下了.
2.相应的是发送方的应用程序,产出数据慢,一次一字节,一字节一个报文,也会导致效率问题.
犯傻症的防治
1.接收方
a.对每一个到达的TCP报文回送ACK,但在窗口的空余增大到指定大小之前,我都不会报告窗口的大小,免得回送一个1byte,你就想也不想就发个报文过来.
b.或者,延迟ACK的发送.并不一定对每个TCP报文都回送ACK,而是每个报文到达后,稍等片刻.
Adventage:
1.减少交通流量.一个ACK可能对多个报文做出确认回复,不用一一回复啦.
2.Piggyback. 当接收方收到数据后需要回送数据时,可以在回送数据的TCP报文中捎带[piggyback] ACK确认,同样减少了网络流量.
3. 窗口通告[window advertizement]是在数据于缓冲区被读取后才发出的,这和对应的报文的到达时间有一定延后,而ACK的延迟发送就可能等待到窗口大小的改变，两者一起回发（又是piggyback?）,同样减少了数据流量.
Disadventage:
1.报文重传时间是根据报文来回时间推测而来的.ACK延迟策略影响了对合理重传时间的判断,本来一秒钟就到了的,结果延迟设定的时间太夸张,用了十秒,这边的传送方就说那好吧,就15秒吧,15秒还不到我就算你报文丢失了,直接结果就是反应迟钝,正常的5秒钟就可以判定丢失的,偏要等到15秒,好难等啊...
2.另外,延迟时间太夸张了,最直接的结果就是发送方等啊等,没等到,干脆重传了(其实那报文早到了,没回送确认而已),这样添加了无谓的重传,增加网络负担.
Solve:
相应的解决方法简单得很,既然都是延迟时间太夸张导致的,我就把延迟时间设个上限呗,现在的建议是0.5秒.
2.发送方
想象一下,为了避免传输小数据报,可以让TCP稍等一会儿,待到数据聚集多后,一起发送,嗯,想法不错,不过等多少时间呢?
0.5秒?50秒?
关键是TCP应对的对象是多种多样滴,可以是人,是打字快的人,是半小时打一个字的打字慢的人,是5M/S的文件传输.....
对人,0.5秒太短,对文件传输,时间又太长.故时间的选择是一个问题.
想一种自适应的策略出来.
1.对打字慢的人来讲,不应该强行奢望说每个报文都携带大量数据,不然应用程序延迟太大,聊QQ我打一行字不一定有20byte呢,结果你强行说100byte我再给你发,我不是很郁闷.所以这种情况理想下应该及时发送,相比人的慢速,网络的ACK是到的快的,所以但凡ACK到达,我就发送下一数据报,而不理睬是否报文数据达到一定大小(这样就没有提高传输效率一说了,不过程序嘛,当然用户体验第一啦,小牺牲一下效率也是值得滴).
2.对传输大户比如文件传输呢?
还发一个报文,乖乖等ACK然后再发下一个就太慢了吧,乖乖,我可是10M/S的速度写入啊,这时就应该藐视ACK,只要缓冲区数据写入填满了最大报文,就立刻发送,毫不等待(当然了,还是得遵循滑动窗口的限制吧,猜测,待确认).
而兼容以上两种情况的策略就诞生了:
1 . 对从应用程序收到的第一块数据,发送端的TCP直接将它发送出去，哪怕只有一个字节。
2 .此后，发送端的TCP就在输出缓存中积累数据，并等待：或者接收端的TCP发送出一个确认，或者数据已积累到可以装成一个最大的报文段。二者满足其一，发送端的TCP就可以发送这个报文段。
3.对剩下的传输，重复步骤2。这就是：如果收到了对报文段x的确认，或者数据已积累到可以装成一个最大的报文段，那么就发送下一个报文段(x + 1)。
(我看的《Intenetworking with TCP/IP》中，作者评价这个策略是Surpring and Elegant.赞赏之情溢于言表.
不同的网络层对应不同的传输单元,自上而下:
TCP (Transport layer 传输层) ==> Segment [报文]
IP (Network layer 网际层) ==> Datagram [数据报]
Ethernet (Link layer 链路层) ==> Frame [帧]
另外,存在一个泛称,通指所有层的基本传输单元:
Packet [分组]
更多可以参考 这里.
2010年4月21日
感觉义无反顾的再次在边界问题上纠结良久:
到底两边夹击的i和j 相遇之后返回pivot的操作如何处理?
两个极限情况的考虑:
1. i一路高歌到底,与j碰头
2.j顺流直下,直接到i
闲话不多说,上代码:
#include<stdlib.h>
#include <stdio.h>
/*
* Demo of how to quick sort an array
*
* Author: mmLiu
* Date : 2010_4_21
*/
void main(){
int getRandom();
void qSort(int a[],int low,int high);
//generate random array and print it
int a[20];
for(int i=0;i<20;i++){
a[i]=getRandom();
}
printf("befor sort\n");
for(int i=0;i<20;i++){
printf("%d\n",a[i]);
}
//sort the array and print the result
qSort(a,0,19);
printf("befor sort\n");
for(int i=0;i<20;i++){
printf("%d\n",a[i]);
}
getchar();
}
//quick sort
void qSort(int a[],int low,int high){
int partition(int a[],int low,int high);
if(low<high){
int pivot=partition(a,low,high);
//iterate
qSort(a,low,pivot-1);
qSort(a,pivot+1,high);
}
}
//seperate the array into 2 parts,smaller part and bigger part,return the pivot
int partition(int a[],int low,int high){
void swap(int a[],int i,int j);
int i=low+1;
int j=high;
while(i<j){
while(a[i]<a[low] && i<j){
i++;
}
while(a[j]>a[low] && i<j){
j--;
}
if(i<j){
swap(a,i,j);
}else if(i==j){
if(a[i]>=a[low]){
swap(a,i-1,low);
return i-1;
}else if(a[i]<a[low]){
swap(a,i,low);
return i;
}
}
}
}
//swap position in arrray
void swap(int a[],int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
//get random number
int getRandom(){
return 1+(int)(100.0*rand()/(RAND_MAX+1.0));
}
2010年4月20日
利用反射,根据文件配置,进行对象的实例化操作.
如下是做Migrate CSV data to DB2 时使用到得spring.xml 配置文件:
 <?xml version="1.0" encoding="gb2312"?>
<!DOCTYPE beans PUBLIC "-//SPRING//DTD BEAN//EN"
"http://www.springframework.org/dtd/spring-beans.dtd" >
<!--Configure CSVMigrationManager-->
<bean id="csvMigrationManager" class="com.ibm.pw.pps.CSVMigrationManager">
<!--This is for filtering csv files in a directory. This is required-->
<property name="fileFilter">
<bean class="com.ibm.pw.pps.filefilter.CSVFileFilter"/>
</property>
<!--If this is true, the table definition file for each csv file will be generated. The name of the definition file is the csv file's name appended by ".def.xml". This is optional, default to false-->
<property name="generateTableDefinitionFile" value="true"/>
<!--The path of the input csv file. This is required-->
<property name="inputPath" value="test_files/in.csv"/>
<!--The name of the Migrator instance to use to perform migration. The command line can use "-migrator" option to override this property. This is required-->
<property name="selectedMigratorName" value="xml"/>
<!--The parameters that are passed into the selected Migrator instance's migrate() method.
Some migrator might need this. For example, CSVToXMLMigrator needs the output path. This is optional, default to an empty map.-->
<property name="migratorParameters">
<map>
<entry key="outputPath" value="test_files/in.csv.xml"/>
</map>
</property>
<!--This is a map of one or more Migrator instances configured to be used.
Only one of them(named by selectedMigratorName) is used for a call on the no-arg migrate().
But caller can specify other Migrator without changing selectedMigratorName by calling the overloaded migrate() method. This is required-->
<property name="migrators">
<!--The key of the map is the unique identifier of a Migrator. Both 'selectedMigratorName' and the '-migrator' option of the command line should use this key to refer to Migrator instances.-->
<map>
<entry key="db2">
<!--This bean must be configured if migration to a database needs to be supported-->
<bean class="com.ibm.pw.pps.migratorimpl.CSVToDB2Migrator">
<!--This must be configured so that CSVToDB2Migrator can get the selected data source. This is required-->
<property name="dataSourceFactory" ref="dataSoutceFactory"/>
<!--A map of Converter instances can be configured, which are used for converting the string field in the csv file into other types. This is optional because ConvertUtils has some default converters. However if there is date value in a csv file, we must configure a DateLocaleConverter to convert string into java.util.Date-->
<property name="converters">
<map>
<entry key="java.util.Date">
<!--This is used for convert string into java.util.Date. Please refer to Apache Commons BeanUtils's doc(http://commons.apache.org/beanutils/commons-beanutils-1.7.0/docs/api/org/apache/commons/beanutils/locale/converters/DateLocaleConverter.html) for its ctor parameters-->
<bean class="org.apache.commons.beanutils.locale.converters.DateLocaleConverter">
<constructor-arg index="0">
<bean class="java.util.Locale">
<constructor-arg index="0" value="en"/>
</bean>
</constructor-arg>
<constructor-arg index="1" value="yyyy-MM-dd"/>
<constructor-arg index="2" value="true"/>
</bean>
</entry>
</map>
</property>
</bean>
</entry>
<entry key="xml">
<!--This bean must be configured if migration to a XML file needs to be supported-->
<bean class="com.ibm.pw.pps.migratorimpl.CSVToXMLMigrator"/>
</entry>
</map>
</property>
<!--The CSVParser instance for parsing a csv file. This is required-->
<property name="parser">
<bean class="com.ibm.pw.pps.csvparser.CSVParserImpl"/>
</property>
<!--The TableDefinitionFactory instance for creating a TableDefinition from the first row of a csv file. This is required-->
<property name="tableDefinitionFactory">
<bean class="com.ibm.pw.pps.tabledefinitionfactoryimpl.TableDefinitionFactoryImpl">
<!--This must be configured so that TableDefinitionFactoryImpl can get the selected data source. This is required-->
<property name="dataSourceFactory" ref="dataSoutceFactory"/>
</bean>
</property>
<!--The TableDefinitionWriter used for writing a table definition file for a csv file. This is required-->
<property name="tableDefinitionWriter">
<bean class="com.ibm.pw.pps.tabledefinitionwriter.XMLTableDefinitionWriter"/>
</property>
</bean>
</beans>
重点关注Manager 类的实例化,<bean> csvMigrationManager 下配置了com.ibm.pw.pps.CSVMigrationManager一系列字段的属性.
源码未曾研究过,猜想应该是利用反射直接设置字段,即使它是private的.
至于使用,如下:
 // Create an ApplicationContext
ApplicationContext context = new FileSystemXmlApplicationContext("test_files"
+ System.getProperty("file.separator") + "spring.xml");
// Get the Spring-configured CSVMigrationManager
CSVMigrationManager manager = (CSVMigrationManager) context.getBean("csvMigrationManager");
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 29 | 30 | 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 | 1 | 2 | | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
留言簿
随笔分类
文章分类
文章档案
搜索
最新评论
|
|