C++博客-宁静的天空

双向map简单讨论

heying — Thu, 15 Dec 2011 16:25:00 GMT

题目如下：

设计一双向map；

1，key可以找到value，value也可以找到key；

2，key和value的对应关系是多对多的关系；

3，key的值为1000万左右，最大为2000万；

4，value为char[128]，最多为1000万个；

5，尽量对设计进行优化；

1 class Data
2 {
3     public:
4       Data(char *);
5       ~Data();
6       Data &operator=(char *);
7       //比较两个对象是否相等，如果指针相同则相等，如果指针不同，内容相同，也是相等！！
8       bool operatoe==(const Data &tmpdata)const
9       {
10          if(tmpdata.m_lpdata == this->m_lpdata)
11             return true;
12          if(tmpdata.m_lpdata == NULL || this->m_lpdata == NULL)
13             return false;
14          if(memcmp(tmpdata.m_lpdata,this->m_lpdata,128)!=0)
15             return false;
16          return true;
17       };
18       bool operatoe<(const Data &tmpdata)const
19       {
20          if(tmpdata.m_lpdata == this->m_lpdata)
21             return false;
22          if(tmpdata.m_lpdata == NULL || this->m_lpdata == NULL)
23             return false;
24          if(memcmp(this->m_lpdata,tmpdata.m_lpdata,128)<0)
25             return true;
26          return false;
27       };
28    private:
29       char *m_lpdata;
30       Data();
31 };
32 //内存管理，管理所有存储数据；该处可以简单实现，也可复杂实现；看实际情况；
33 class MemManager
34 {
35 };
36 class DoubleLinkMap
37 {
38     public:
39       DoubleLinkMap();
40       ~DoubleLinkMap();
41    private:
42       //内存管理
43       MemManager m_memmanager;
44       //数据结构
45       #define MAXKEYVALUE 20000000
46       std::list<char *> m_KeyArray[MAXKEYVALUE];
47       std::multimap<Data,int> m_mulmap_value_key;
48 };
49

对以上数据结构说明：

1，由key获取value，直接访问m_KeyArray,其下标为key，那么得到的值为list，该list为指定key的所有value指针组成的list；可以由指针直接获取到数据；

2，由数据获取key，使用m_mulmap_value_key的lower_bound及upper_bound操作，直接可以获取到指定Data的所有key；主要实现了Data的==及<操作运算符，这两个运算符优先判断指针是否相等，后判断数据是否的大小；

3，当对数据进行删除操作时，比较麻烦些，如果删除指定key的所有value，那么需要通过m_KeyArray找到所有value的指针，然后再挨个删除所有指针在m_mulmap_value_key里的映射；注意，删除时需要判断key是否相等再删除；

4，对内存管理这里有了一个说明，可以对存储所有value的内存进行优化；暂时没有写关于内存管理的部分；

heying 2011-12-16 00:25 发表评论

证明某一数的平方根为无理数

heying — Mon, 23 Nov 2009 05:47:00 GMT

关注非完全平方数p
设整数 p 可分解为p1*p2*...*pz(pi为素数)
假设根号p 为有理数，可表示为n /m (n, m 互素)
有 n^2= p* m^2
p为非完全平方数，p的素因数至少有一个出现次数为单数，
设最小的这个数为 t
==> n^2| t
==> n| t
则 m^2| t, m| t
然而n| t
同假设n，m互素矛盾
即证

注：
1,a|b 表示a 可以被b 整除
2,p为非完全平方数，因为如果p为完全平方数，那么p的因子中不包含任何一个出现次数为单数的素因子;

heying 2009-11-23 13:47 发表评论

关于TCP的短链接和长链接

heying — Tue, 11 Mar 2008 15:59:00 GMT

今天我一个哥们让我帮他调试下程序，说一个普通网络通讯程序总丢包；我问他是TCP还是UDP，他说是TCP，我纳闷；经过我的了解，发现原来他的程序不是TCP丢包，而是，TCP链接出现问题，不能长时间保持长链接状态；
程序是这样的：
客户端为普通pc；服务器端为他们的嵌入式设备；
我问了他的需求，发现他传输速度要求不高，大概100B/s的样子；后来我就建议他使用短链接；发现短链接能够很好的工作，不过有些包需要发送两次；
出现以上情况的原因，我认为可能是以下两个方面：
1，网络不太稳定，硬件方面的问题；
2，他的嵌入式设备系统的网络驱动有问题，不能长时间保持长链接状态；

至于具体是什么原因，还有待于进一步研究；

heying 2008-03-11 23:59 发表评论

linux sys epool（转）

heying — Mon, 10 Mar 2008 15:11:00 GMT

Epoll为我们带来什么

　
Q：网络服务器的瓶颈在哪？
A：IO效率。

　　在大家苦苦的为在线人数的增长而导致的系统资源吃紧上的问题正在发愁的时候，Linux 2.6内核中提供的System Epoll为我们提供了一套完美的解决方案。传统的select以及poll的效率会因为在线人数的线形递增而导致呈二次乃至三次方的下降，这些直接导致了网络服务器可以支持的人数有了个比较明显的限制。

　　自从Linux提供了/dev/epoll的设备以及后来2.6内核中对/dev/epoll设备的访问的封装（System Epoll）之后，这种现象得到了大大的缓解，如果说几个月前，大家还对epoll不熟悉，那么现在来说的话，epoll的应用已经得到了大范围的普及。

　　那么究竟如何来使用epoll呢？其实非常简单。
　　通过在包含一个头文件#include 以及几个简单的API将可以大大的提高你的网络服务器的支持人数。

　　首先通过create_epoll(int maxfds)来创建一个epoll的句柄，其中maxfds为你epoll所支持的最大句柄数。这个函数会返回一个新的epoll句柄，之后的所有操作将通过这个句柄来进行操作。在用完之后，记得用close()来关闭这个创建出来的epoll句柄。

　　之后在你的网络主循环里面，每一帧的调用epoll_wait(int epfd, epoll_event events, int max events, int timeout)来查询所有的网络接口，看哪一个可以读，哪一个可以写了。基本的语法为：

　　nfds = epoll_wait(kdpfd, events, maxevents, -1);

　　其中kdpfd为用epoll_create创建之后的句柄，events是一个epoll_event*的指针，当epoll_wait这个函数操作成功之后，epoll_events里面将储存所有的读写事件。max_events是当前需要监听的所有socket句柄数。最后一个timeout 是epoll_wait的超时，为0的时候表示马上返回，为-1的时候表示一直等下去，直到有事件范围，为任意正整数的时候表示等这么长的时间，如果一直没有事件，则范围。一般如果网络主循环是单独的线程的话，可以用-1来等，这样可以保证一些效率，如果是和主逻辑在同一个线程的话，则可以用0来保证主循环的效率。

epoll_wait范围之后应该是一个循环，遍利所有的事件：

    for(n = 0; n < nfds; ++n) {
        if(events[n].data.fd == listener) { //如果是主socket的事件的话，则表示有新连接进入了，进行新连接的处理。
            client = accept(listener, (struct sockaddr *) &local, &addrlen);
        if(client < 0){
            perror("accept");
            continue;
    }
    setnonblocking(client); // 将新连接置于非阻塞模式
    ev.events = EPOLLIN | EPOLLET; // 并且将新连接也加入EPOLL的监听队列。

　　注意，这里的参数EPOLLIN | EPOLLET并没有设置对写socket的监听，如果有写操作的话，这个时候epoll是不会返回事件的，如果要对写操作也监听的话，应该是EPOLLIN | EPOLLOUT | EPOLLET

    ev.data.fd = client;
    if (epoll_ctl(kdpfd, EPOLL_CTL_ADD, client, &ev) < 0) {
        // 设置好event之后，将这个新的event通过epoll_ctl加入到epoll的监听队列里面，这里用EPOLL_CTL_ADD来加一个新的 epoll事件，通过EPOLL_CTL_DEL来减少一个epoll事件，通过EPOLL_CTL_MOD来改变一个事件的监听方式。
        fprintf(stderr, "epoll set insertion error: fd=%d0, client);
        return -1;
        }
    }
    else // 如果不是主socket的事件的话，则代表是一个用户socket的事件，则来处理这个用户socket的事情，比如说read(fd,xxx)之类的，或者一些其他的处理。
        do_use_fd(events[n].data.fd);
    }

　　对，epoll的操作就这么简单，总共不过4个API：epoll_create, epoll_ctl, epoll_wait和close。
　　如果您对epoll的效率还不太了解，请参考我之前关于网络游戏的网络编程等相关的文章。

　　世界变了，原来担心的问题，现在已经不是问题了。

heying 2008-03-10 23:11 发表评论

对于未确定数目参数的函数的实现方法

heying — Tue, 12 Dec 2006 01:33:00 GMT

摘要: 对于有些函数，我们没有办法确定其在各个调用中的具体参数个数和类型，声明这种函数的方法就是在函数参数序列结尾增加“...”；例如C语言中的控制台输出函数： int __cdecl printf (const char*, ...); 这些函数的实现一般和编译器的实现有很大关系。阅读全文

heying 2006-12-12 09:33 发表评论