Unix网络编程 第11章 Name and Address Conversions 笔记

# gethostbyname 和 gethostbyaddr 用来在 IPv4 地址和 hostname 之间转换. getservbyport 和 getservbyname 则是与服务相关。gethostbyname出错时不设errno而是设h_errno,并有hstrerror()函数。

# FQDN的全称是: Fully Qualified domain name. 技术上说必须以点号(period)终止.

# AAAA 被称为 "quad A" rcord, 给出了从hostname到Ipv6地址的映射。 PTR用来把IP地址到hostname.

# Entries in the DNS are known as Resource Records(RRs).

# 一个点分十进制(dotted-decimal)IPv4的地址前加 0::ffff:就是 IPv6的字符串形式。

# 与getpeername对应的函数不是gethostname而是getsockname.

# getaddrinfo函数的host参数指定为dotted-decimal IPv4或 IPv6 hex string,会使得只有IPv4或IPv6的addrinfo返回。

# 不给UDP套接字设置SO_REUSEADDR选项。We do not set the SO_REUSEADDR socket option for the UDP socket because this socket option can allow multiple sockets to bind the same UDP port on hosts that support multicasting. Since there is nothing like TCP's TIME_WAIT state for a UDP socket, there is no need to set this socket option when the server is started.

# 一般情况下,同端口的不同协议对应同样的服务。但也有例外。对于端口514,which is the rsh service with TCP, but the syslog service with UDP.

# gethostbyaddr的第一个参数是char* addr,而其实它并非指向一个char* 事实上指向in_addr结构体。

# getaddrinfo好复杂呀!hint的ai_flags设置了AI_CONONNAME成员得到host的canonical name.

# port 53 是domain service的端口号.

# 如果设置了IPV6_V6ONLY.那么一个来自ipv4 client的连接会被拒绝。

# POSIX says that specifying AF_UNSPEC will return addresses that can be used with any protocol family that can be used with the hostname and service name.

# POSIX specification also implies that if the AI_PASSIVE flag is specified without a hostname, then the IPv6 wildcard address(IN6ADDR_ANY_INIT or 0::0) should be returned as a sockaddr_in6 structure, along with the IPv4 wildcard address(INADDR_ANY or 0.0.0.0), which is returned as a sockaddr_in structure.

# An ipv6 server socket can handle both ipv4 and ipv6 on a dual-stack host. Refer to page319 in UNP for details.

Prof. Zixiang Xiong讲座 脏纸编码

作为主要兴趣在Linux方面的偏应用硕士,听了一个电信传输方面的学术讲座。所谓Dirty Paper Coding,我的理解是如果已知信道干扰,在发射机对发射信号预先减去该干扰,则发射信号经信道传输被接收机接收后,则信道干扰被自动抵消。很简单的Idea,但实际实施起来应该非常困难吧。Prof. Zixiang Xiong先介绍了他所工作的学校。呵。然后从Dirty-paper Coding的历史发展讲起。Instances of dirty paper coding include Costa precoding(1983) ,Tomlinson-Harashima precoding (1971) and the vector perturbation technique of Hochwald et al. (2005)。两位科学家GelfandPinsker开创了这个领域,到信息理论的实际设计准则如何应用到实践之中。Prof. Zixiang Xiong提出了两种有效的编码设计方法。理论回到实路,再介绍这两种编码设计方法在图形图象的数据隐藏,MIMO广播,抗噪预编码,无线网络传输协调方面的实际应用。Gaussian arbitrarily varying channel with a known interference signal at the encoder.

好复杂好深奥的数学变换。想起本科阶段的傅丽叶级数变换,卷积分就已经让我伤透脑筋。本次讲座的收获也就是让我一定程度上开拓了视野,接触到N多电信方面的术语。小波变换,脏纸编码,数字水印之类。术业有专功,我要专功我的Linux去嘞。。。

Sicily 1031 Campus 解题报告.

 

1 原题中文大意;
 
Sicily 1031 Campus实际上就是求一个图中给出两点的最短路径的问题。
 
2 算法思想及解题用到的主要数据结构;
 
用 dijkstra 算法求给定两点的最短路径.
 
按路径长度递增次序产生最短路径算法:   把V分成两组:   (1)S:已求出最短路径的顶点的集合   (2)V-S=T:尚未确定最短路径的顶点集合   将T中顶点按最短路径递增的次序加入到S中,   保证:(1)从源点V0到S中各顶点的最短路径长度都不大于   从V0到T中任何顶点的最短路径长度   (2)每个顶点对应一个距离值   S中顶点:从V0到此顶点的最短路径长度   T中顶点:从V0到此顶点的只包括S中顶点作中间   顶点的最短路径长度   依据:可以证明V0到T中顶点Vk的最短路径,或是从V0到Vk的   直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和。
 
3  逐步求精算法描述
 
用邻接矩阵存放图.1. 初使时令 S={V0},T={其余顶点},T中顶点对应的距离值   若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值   若不存在<V0,Vi>,d(V0,Vi)为∝   2. 从T中选取一个其距离值为最小的顶点W且不在S中,加入S   3. 对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的   距离值比不加W的路径要短,则修改此距离值   重复上述步骤2、3,直到S中包含所有顶点,即S=T为止
 
3 程序注释清单 // 这份代码通不过sicily。有case错误。我实在找不到原因。
 
#include <map>

#include <vector>

#include <string>

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <cassert>



#define INFINITE 0x0FFFFFFF



// 这个类的函数几乎不做参数有效性的检查. 

class graph_t

{

public:

// 构建一个 num x num 的邻接矩阵

graph_t(int num)

{

m_matrix = new int[num*num];

m_sunit = new bool[num];

m_spath_table = new int[num];

// memset(m_matrix, INFINITE, num*num);  // INFINITE 表示无穷远. 

for ( int i = 0; i < num*num; i++ )

{

m_matrix[i] = INFINITE;

}

m_num = num;

}



// row,column 取 [0, m_num)

int& operator()(int row, int column)

{

return m_matrix[row * m_num + column];

}



// vtx_start, vtx_end 取 [vtx_start, vtx_end)

int shortestpath_dij(int vtx_start, int vtx_end)

{

init_dij(vtx_start);  // 初始化dijkstra算法需要的一些数据. 



if ( vtx_end == vtx_start )

{

return this->operator()(vtx_start, vtx_end);

}



// 还剩 m_num - 1 个点. 

for ( int i = 1; i < m_num; i++ )

{

// 找下一个最近的点. 

int vtx = -1, min = INFINITE;

for ( int j = 0; j < m_num; j++ )

{

if ( m_sunit[j] )  // 这个点已经在已经求得最短路径的点的集合中了. 

continue;



if ( m_spath_table[j] < min )

{

vtx = j;

min = m_spath_table[j];

}

}

// 已经没有连通的顶点了. 

if ( vtx == -1 )

{

return -1;

}

m_sunit[vtx] = true;  // 把这个点加入集合中. 



// 这个点是终点.  http://blog.ykyi.net

if ( vtx == vtx_end )

{

return min;

}



// 因为找到了一个新的点加入了集合,更新最短路径表. 

for ( int k = 0; k < m_num; k++ )

{

if ( m_sunit[k] )

continue;



if (  min + this->operator()(vtx, k) < m_spath_table[k] )

{

m_spath_table[k] = min + this->operator()(vtx, k);

}

}

}



assert(0); // it's not suppossed to reach here.

return -1;

}



~graph_t()

{

delete m_matrix;

delete m_sunit;

delete m_spath_table;

}



private:

void init_dij(int vtx_start)

{

memset(m_sunit, 0, m_num);   // 初始化为没有点加入这个已求得最短路径的终点集合.

for ( int i = 0; i < m_num; i++ )

{

m_spath_table[i] = this->operator()(vtx_start, i);

}

assert( 0 == m_spath_table[vtx_start] );

m_sunit[vtx_start] = true;

}



private:

int   m_num;

int*  m_matrix;  // 存邻接矩阵

bool* m_sunit;   // 在dijkstra计算过程中用来存某点是否已经是最短路径中的点.

int*  m_spath_table;  // 在dijkstra计算过程中存到某点是的最短路径是多少.

};





int main(int argc, char* argv[])

{

int case_count, path_count, weight, next_ava_vtx;

int vtx_start, vtx_end;

std::map<std::string, int> loc2vtx;  // 存地点字符串到图的顶点号的映射. 

std::vector<int> spirit;

std::string line;



std::cin >> case_count;

for ( int i = 0; i < case_count; i++ )

{

loc2vtx.clear();

spirit.clear();

next_ava_vtx = 0;



std::cin >> path_count;

for ( int j = 0; j < path_count; j++ )

{

// 得到起点地址字符串. 

std::cin >> line;

std::map<std::string, int>::iterator ite = loc2vtx.find(line);

if ( loc2vtx.end() != ite )

{

vtx_start = ite->second;

}

else

{

vtx_start = next_ava_vtx;

loc2vtx[line] = vtx_start;

next_ava_vtx++;

}

spirit.push_back(vtx_start);



// 得到终点地址字符串. 

std::cin >> line;

ite = loc2vtx.find(line);

if ( loc2vtx.end() != ite )

{

vtx_end = ite->second;

}

else

{

vtx_end = next_ava_vtx;

loc2vtx[line] = vtx_end;

next_ava_vtx++;

}

spirit.push_back(vtx_end);



// 得到权重

std::cin >> weight;

spirit.push_back(weight);

}



// 至此 next_ava_vtx 中存放的实际上是邻接方阵的阶. 

graph_t graph(next_ava_vtx);

for ( int i = 0; i < spirit.size()/3; i++ )

{

int x = spirit[3*i];

int y = spirit[3*i+1];

int w = spirit[3*i+2];

graph(x, y) = w;

graph(y, x) = w;

}

for ( int i = 0; i < next_ava_vtx; i++ )

{

graph(i, i) = 0;

}



std::cin >> line;

std::map<std::string, int>::iterator ite = loc2vtx.find(line);

if ( ite == loc2vtx.end() )

{

std::cout << "-1\n";

continue;

}

vtx_start = loc2vtx[line];



std::cin >> line;

ite = loc2vtx.find(line);

if ( ite == loc2vtx.end() )

{

std::cout << "-1\n";

continue;

}

vtx_end = loc2vtx[line];



if ( vtx_start == vtx_end )

{

std::cout << "0\n";

continue;

}



std::cout << graph.shortestpath_dij(vtx_start, vtx_end) << std::endl;

}



return 0;

}

 

 
4 对时间复杂度,空间复杂度方面的分析、估算。
 
时间复杂度和空间复杂度都是O(n*n).   http://blog.ykyi.net
 
///////////// 原题
 
 
 
 
 
1031. Campus
 
 
 
 
 
Description
 
At present, Zhongshan University has 4 campuses with a total area of 6.17 square kilometers sitting respectively on both sides of the Pearl River or facing the South China Sea. The Guangzhou South Campus covers an area of 1.17 square kilometers, the North Campus covers an area of 0.39 square kilometers, the Guangzhou East Campus has an area of 1.13 square kilometers and the Zhuhai Campus covers an area of 3.48 square kilometers. All campuses have exuberance of green trees, abundance of lawns and beautiful sceneries, and are ideal for molding the temperaments, studying and doing research.
 
 
 
 
       Sometime, the professors and students have to go from one place to another place in one campus or between campuses. They want to find the shortest path between their source place S and target place T. Can you help them?
 
 
Input
 
The first line of the input is a positive integer C. C is the number of test cases followed. In each test case, the first line is a positive integer N (0<N<=100) that represents the number of roads. After that, N lines follow. The i-th(1<=i<=N) line contains two strings Si, Ti and one integer Di (0<=Di<=100). It means that there is a road whose length is Di between Si and Ti. Finally, there are two strings S and T, you have to find the shortest path between S and T. S, T, Si(1<=i<=N) and Ti(1<=i<=N) are all given in the following format: str_Campus.str_Place. str_Campus represents the name of the campus, and str_Place represents the place in str_Campus. str_Campus is "North", "South", "East" or "Zhuhai". str_Place is a string which has less than one hundred lowercase characters from "a-z". You can assume that there is at most one road directly between any two places.
 
Output
 
The output of the program should consist of C lines, one line for each test case. For each test case, the output is a single line containing one integer. If there is a path between S and T, output the length of the shortest path between them. Otherwise just output "-1" (without quotation mark). No redundant spaces are needed.
 
 

 

我看过的unix/linux世界的好书

"Advanced Programming in the Unix Environment" Volum I 2nd Edition 大名鼎鼎的  apue 作者是享誉 unix 世界的大牛 Richard Stevens.全书分两卷。第一卷我看了两遍, 第二卷翻了翻目录,不想看。

"Linux Device Drivers" 3rd Edition 简称LDD.这本书的中文版翻译的奇烂无比。果断读影印版的,要么就别看了。

"Managing Projects with GNU make" 讲GNU make的书. make这个古老的build工具。怎么 说呢。至少我觉得语法设计的非常不友好。无奈的历史问题。

"Version Control with Git" 讲git的书.混了个眼熟。一个人单独做小规模开发用不到那 么多特性咯。

<Linux内核设计与实现> 很薄的一本讲linux kernel的书。这本书看的中文版。陈莉君翻 译的还不错。只有很少错误。

<Unix编程艺术> 这本书我有中文版和英文版。先买了英文版看看不懂,于是买了中文版看 。除非你的英文水平接近有native speaker的水平并且词汇量超大,至少在一万以上吧。 否则还是看中文版吧。中文版译得很不错。英文版哥看得非常吃力。5。哥的词汇量接近一万 对自己的英文水平看技术类书还是很自信的,但是写这本书的作者是一位极具个性,极具 争议的unix hacker,行文风格尽显不羁个性。同样这本书也是争议颇多。支持的奉为圣经 ,反对的嘲笑作者见识短浅。

"Advanced Bash programming Guide"  讲编写bash脚本的。看的网上的电子版。太多内容了,基本上bash的特性面面惧到。很多内容看了就忘了。

<鸟哥的私房菜 基础篇>据说是中文书里算入门的好书了。网上的口啤不错。个人感觉讲的 内容非常之浅,不过确实是本入门的好书。但不觉得有收藏价值。这套书还有服务器部分,没有看过。没兴趣也不需要看. 

正在看 Richard Stevens 的另一本bible,“Unix network Programming” Volumn I 3 rd Edition。 看完了一半。一定要在寒假结束前看完。和apue一样,虽然最新版都是由新 的作者在原来的基础上更改的,但仍然保持了Richard Stevens的行文风格用语简练不花哨 ,详细细致易懂的风格。 明年争取啃下 "Understanding Linux Kernel". 计划选择性看部分"Essential Linux Device Drivers". 顺便提一下Richard Steven写的另一套久负盛名的书Tcp/ip详解,共三卷。简单的过了一下第一卷。没有认真看。

copyright blog.ykyi.net

听了林学民教授的一个学术报告

                  Graph-based Structure Search

林学民教授是数据库理论方面的专家。今天的学术报告,林教授给我们简单介绍了他的研究团队在海量数据检索方面的研究成果。

在快带发展的互联网社会,越来越多的应用需要检索快速地检索基于图结构的海量数据。比如近两三年兴起的,我们非常熟悉的社交网络。对于图的结构化检索是一个NPC问题。海量的数据规模使得问题变得非常的棘手。我搜索了一些资料也没搞清楚什么叫NPC问题。我简单地理解,是当问题的规模变得越来越大时,就不能确定是否能在确定的时间内求出解。

林教授先简单地提到对图的研究方向大致分Mining Graphs,Quering GraphsMining Graphs方面有Frequent Patterns, structure Similarityies, clustering, Ranking, classificationProf. Lin的团队主要做了Structure Similarities方面的一些研究。对于Querying Graphs,又大致分为Readibility, Connectivity between two nodes, substructure search, shortest paths, stringsProf. Lin话:对于shortest path,理论上求解很simple,但是应用到大量数据的时候,就要做很多工作。比如要做非常高效的索引。对于strings,一个很长的text可以看成一个长string。比于现在的internet搜索引擎,要解决区分互联网上太多冗余数据的问题,就属于这方面的研究。我知道搜索引擎是鼓励原创的,会给原创的页面比较高的page rank。针对这点,black hat SEO就会搞伪原创,怎样让搜索引擎快速区分出真正的原创内容呢?应该也属于这方面的课题吧。

林教授开始讲他的科研团队的第一个贡献。这个contribution是解决了关于图与图之间包含的问题。问题描述为:给出一个Data Graph和一个Query Graph,要在一个规模非常大的Data Graph里面找到这个Query Graph。林教授介绍了这个过程中的FilteringVerification算法简要思路。对于不懂学术的我,这部分真是相当地难以理解啊!!!设D是要处理的图。First index a set F of features from D。对于任意f属于F, f的超图。索引的算法思路是。如果q是一个frequent subgraph,则 1. 如果q已经被索引,则返回q的超图。2.如果q是一个超图,次q被索引了,不需要给次q的超图做verification。如果q不是一个frequent subgraph的情况下,验证受制于sigmal|D|。林教授认为这个求解过程的主要开销在verification阶段。他们的团队就是把这个cost显著降了一下,而且思路非常地clearsimple。他总结了三条经验: 1. Access infrequent labels as early as possible. 2. Retain connectivity。 3. Effectively use degree information.

The second contribution of Prof. Lin is to put the the theoretic algorithm into practice.有两个问题,一个是query graphdata graph包含(contained),另一个是query graph包含了data graph.林教授的团队的最结成果比已经发表了论文的另一个科研团队的成果的速度要快了一个数量级。Prof. Lin的语气显得有些遗憾,他们的思路是正确的,实现的效率也很高,但是时间上慢了小小。

http://blog.ykyi.net zausiu's blog

发言队段,研究这个方向的甘同学问了非常专业的问题,我不懂啊!还有一位信科院的研一同学问到了留学的问题,Prof. Lin说他要最top的学生,非常地talented,非常地diligent, 非常地good at algorithm,还要有非常好的practical ability。朝红阳教授向林教授打听有没有做图象search方面的大牛。

学术报告好难啊!我想听工程类的报告。但都是academic report啊!

//////////////////

Topic:

Graph-based Structure Search

 

Speaker:

Prof. Xuemin Lin

School of Computer Science and Enmgineering,University of New South Wales

and

School of Software ,Eastern China Normal University

 

Abstract:

Recent years have witnessed an emergence of graph-based applications that strongly demand efficient processing of graph-based queries and searches.

In many real applications such as chem- and  bio-informatics, road neworks, social networks, etc.,  efficiently and effectively conducting structure search on graphs is a key.

The problem of structure search on graphs and its variants are NP-complete. The presence of a large number of graphs makes the problem computationally more intractable.

In this talk, I will introduce recent techniques in graph structure search with the focus on our recent work published in SIGMOD, VLDB, ICDE, etc. My talk will cover the problems of substructure search, superstructure search, and substructure similarity search.

 

Brief Bio:

林学民,新南威尔士大学大学计算机科学及工程学院教授,数据库研究实验室主任。自2009年4月起,在华东师范大学担任兼职教授,2010年入选国家第四批千人计划学者,2011年6月起受聘于华东师范大学软件学院千人学者。生于上海市,1984年毕业于复旦大学数学系,1992年在昆士兰大学获得博士学位。长期从事数据库理论、算法与技术研究,包括空间数据、不确定数据、流数据、图数据等领域。近年来在数据库领域顶级国际学术会议及顶级杂志上共发表了70余篇学术论文;累计在数据库和算法领域重要的国际学术会议和国际学术期刊发表并录用了170余篇论文,其中10篇国际会议优秀论文,包括ICDE'07上的优秀学生论文奖 (best student paper award) ICDE'10上的优秀论文(one of the best papers) , 及SIGMOD'11 上的优秀论文(one of the best papers)。他目前的研究兴趣是海量数据的处理,包括图数据、时空数据、字符串数据、不确定数据等。学民先后在4th Australasian Theory Symposium (CATS'98), 6th International Computing and Combintorics Conference (COCOON2000), 6th Asia Pacific Web Conference (APweb04), the joint conference of 9th Asia Web Conference and 8th Web-Age Information Management Conference (APweb/WAIM2007), 和 19th and 20th Australasian Database Conference (ADC08, ADC09) 担任会议程序委员会主席,在14th International Conference on Database Systems for Advanced Applications (DASFAA09) 上担任大会主席。目前他是ACM TODS的编委。

 

Presided by 

Prof. Jianlin Feng

 

Date and Venue

Dec 21, 2011(Wed.) 14:00-15:00

Lecture Theater A101, School of Software, Sun Yat-sen University

冬大过年!无痛终结2011年.展望2012

写在冬至日,总结2011展望2012。冬大过年是广东的俗语。无痛终结是因为人心态早已看得化(开)。
首先:在无比苦逼的11年里,最大的贡献就是返校读书了。基本上确定可以了结本科毕业时被取消学位的心愿。
其次工作上没有什么好说的。在东莞光大集团工作了半年,不能说辛苦也不算闲。工作上没学到什么东东,没明显地进步。在此谢谢赵经理了,如果我有赵经理的硬件水平我就笑哈哈哈哈。以识了几位有意思的同事。
感情上则一如既往地Fail, Fail, Fail 。。。完全木有信心了。哥爱无力了。到了年尾心态竟变得更无所谓,该怎样就怎样吧。只是让家人操心了,对不起啊,尽力了啊。奶奶,对不起啊。也想让你开心的。哎!想起过年回家要去那么多亲戚拜年,555,拜托你们不要问不要问吖。
最后讲讲返校后的生活。在中大的生活第一学期课程非常多,非常忙。我还有我的plan要投入很多时间。时间无论如何不够用!同学关系远没本科时紧密。可能我的心态跟刚毕业的后生仔们相差甚远吧。写到这里,想起今年国庆时去了其它地方没有参加强强和敏的婚礼。唉!什么时候去江苏再给我机会补偿好吗。我做人是越来越失败了,完全是不分好坏敌我的混乱!
2012年是世界的最后一年。可恶的地球人,觉悟吧!
以前每年年尾都会许好多愿望。结果第二年能实现的却渺渺无几。反正都2012了,哥的愿望就务实一点好吧。维护世界和平的任务还是不要勉强啦!
明年必须在寒假结束前看完Unix网络编程.
通过六月的BEC高级考试。
全年选择性的读完Essential Linux Device Drivers和Understanding linux Kernel.
上半年看paper,形成写论文的思路。下半年动手写论文。
下半年拿到offer。银行?民航?其它国企?还是互联网公司抑或其它什么公司?…
感情的事务不设定目标。苦逼的技术宅男果断必然无解!