首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 合并数十万个vector<int>的高效方法？
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • chenjuan815
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    • 揭帖率：
    发表于：2008-04-15 10:12:59 楼主
    我用了个最最笨的压缩方法，在P4,3.0G,512M内存的机器上运行了一天，没有出结果，然后跟踪估计了下时间，大约需要9天时间才能完成数据压缩，太慢了！不知道各位有没有好的压缩方法？

    本人有近30万个vector <int>（每个vector <int>中的值为0~179），如：

    vector <vector <int>> a;

    a[0]={0,3,179}

    a[1]={}//该vector为空

    a[2]={2,6,8,56,119,36}

    a[3]={0，3，179}

    a[4]={1,2,3,4,5,6,7,8,9,10...,179}// “满”vector <int>,表示从0到179间的数均在该vector中

    ....

    a[310000]=...

    先要对上述31万个vector <int>进行压缩，压缩原则为
    1.空vector <int>删除，如a[1]
    2.“满”vector <int>删除，如a[4]
    3.相同vector <int>删除其中一个，如a[0]和a[3]相同，则删除其中任意一个
    4.互补vector <int>删除其中一个，互补的意思是两vector <int>不相交且其并集为“满”vector <int>
    100  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • baihacker
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 3
    发表于：2008-04-15 10:18:041楼 得分:0
    2.“满”vector <int>删除，如a[4] : 映射到一个180个数的数组, map[a[k][i]] = 1; map[i]中存在0则不满
    3.相同  映射到一个180个数的数组, map1[a[k][i]] = 1; map12[a[k][i]] = 1; map1[i] map2[i]中存在不同的则不同
    上面就把检查满和相同压缩到线性时间了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wuyu637
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:22:102楼 得分:0
    hash表。。。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • baihacker
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 3
    发表于：2008-04-15 10:23:063楼 得分:0
    在123done了以后

    for (int i = 0; i < ??; ++i)
        for (int j = i+1; j < ??; ++j)
        {
            if (i j 互补)
            {
                删除标志[i] = true;
                break;
            }
        }

    只是这些操作不一定都是在内存完成的...
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wuyu637
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:23:244楼 得分:0
    hash可以做千万级别的数据。。。而且速度很快。。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Supper_Jerry
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:23:415楼 得分:0
    1.利用vector的size，满的和空的删除
    2.分组，size互补的作为1组，分成89组
    组内遍历看是否互补。
    3.组内遍历的时候，由于是有序数组，也可以在查找的时候，减少计算量
    比如：0到179顺序在组内查找，有0的分成一组，没有0的分成一组，然后有1.2..3依次分组。
    上述能够减少一些计算量吧。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • babyvox1999
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:29:456楼 得分:0
    相同vector <int>删除其中一个，如a[0]和a[3]相同，则删除其中任意一个
    4.互补vector <int>删除其中一个，互补的意思是两vector <int>不相交且其并集为“满”vector
    ------------------------------------
    这2个比较耗时间阿。。。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • chenjuan815
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:30:087楼 得分:0
    因为帖子一天后才能加分，所以我只能暂时给出100分了，见谅，呵呵

    我的方法是：依次考察每个vector <int>，看它

    是否为空

    是否为“满”

    和之前的vector <int>比较是否形同
    是否互补

    如果满足上述任意一个条件，则用erase函数删除该vector <int>
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • icosagon
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:33:168楼 得分:0
    我觉得你用vector是一个错误
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • icosagon
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:37:329楼 得分:0
    自已写一个哈希算法，要求互补算出来的结果相等
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Supper_Jerry
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:37:5010楼 得分:0
    和之前的vector <int>比较是否形同
    是否互补
    怪不得速度慢了

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • baihacker
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 3
    发表于：2008-04-15 10:40:4611楼 得分:0
    C/C++ code
    //伪代码
//如果在内存中操作,这些数据在平均情况下会占用100M的内存,额外内存可以忽略不计
const int SIZE = 300000;
const int MAX = 179;
bool f[SIZE];
int mp1[MAX+1], mp2[MAX+1];

for (int i = 0; i < SIZE; ++i)
{
     f[i] = false;
     memset(mp1, 0, (mp1的大小));
     for (int j = 0; j < (a[i]的大小); ++j)
         mp1[a[i][j]] = 1;
     if (j == 0)
     {
         f[i] == true;
     }
     else
     {
        for (int j = 0; j <= MAX; ++j)
             if (mp1[j] == 0)
             {
                f[i] = true;
                break;
             }
     }        
}
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tjltail
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:41:3912楼 得分:0
    我的思路是建立hash表

    hash表的大小为 1 + 2 +......+179;
    每个vector的所有和做为他的hash值

    删除空:将hash值为零的删除
    删除满 将hash值为 1 + 2+ ...+179的删除

    在每个hash值相同的里面找相同的vector

    在hash值和为1+2+.......+179的俩个里面找互补的vector


    其实还可以优化
    通过俩层hash，速度会更快
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • icosagon
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:48:4013楼 得分:0
    每个vector的所有和做为他的hash值 ,这样会有很多相同的
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tjltail
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:51:2914楼 得分:0
    做hash主要是为了减少搜索的范围进行局部比较
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • sheenl
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:51:5115楼 得分:0
    估计是在含有大量元素的vector里面频繁删除元素导致速度太慢了. vector里面不适合频繁删除元素的.
    你不要找到一个删除一个, 批量删除可能会好一点, 比如说remove_if 再 erase
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • nuistbaker
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:53:3016楼 得分:0
    baihacker映射到一个180个数的数组，不错，
    Supper_Jerry 利用数组的SIZE也不错。
    2个办法一起用最好，先按SIZE分组，然后再在比较之前映射到180的数组。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • baihacker
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 3
    发表于：2008-04-15 10:55:1017楼 得分:0
    C/C++ code
    //伪代码
//如果在内存中操作,这些数据在平均情况下会占用100M的内存,额外内存可以忽略不计
const int SIZE = 300000;
const int MAX = 179;
bool f[SIZE];
int mp1[MAX+1], mp2[MAX+1];
int s[MAX+1], c[MAX+1];

for (int i = 0; i < SIZE; ++i)
{
     f[i] = false;
     memset(mp1, 0, (mp1的大小));
     for (int j = 0; j < (a[i]的大小); ++j)
         mp1[a[i][j]] = 1;
     if (j == 0)
     {
         f[i] = true;
     }
     else
     {
        f[i] = true;
        for (int j = 0; j <= MAX; ++j)
             if (mp1[j] == 0)
             {
                f[i] = false;
                break;
             }
     }        
} 

for (int i = 0; i < SIZE; ++i)
{
     if (f[i]) continue;
     for (int j = 0; j < SIZE; ++j)
     {
           if (f[j]) continue;
           memset(mp1, 0, (mp1的大小));
           memset(mp2, 0, (mp2的大小));
           for (int k = 0; k < (a[i]的大小); ++k)
               mp1[a[i][k]] = 1;
           for (int k = 0; k < (a[j]的大小); ++k)
               mp2[a[i][j]] = 1;
           bool sdel = true;
           bool cdel = true;
           for (int k = 0; k <= MAX; ++k)
           {
                if ( mp1[k] != mp2[k]) sdel = false;
                if ( mp1[k] + mp2[k] != 1) cdel = false;
                if ( sdel && cdel) break;
           }
           f[i] = sdel || cdel;
     }    
}

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • sheenl
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 10:55:4918楼 得分:0
    remove_if也要不停的搬动元素, 可能也不行. 还是要自己来
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • baihacker
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 3
    发表于：2008-04-15 10:59:4319楼 得分:0
    C/C++ code
    //伪代码
//如果在内存中操作,这些数据在平均情况下会占用100M的内存,额外内存可以忽略不计
const int SIZE = 300000;
const int MAX = 179;
bool f[SIZE];
int mp1[MAX+1], mp2[MAX+1];

for (int i = 0; i < SIZE; ++i)
{
     f[i] = false;
     memset(mp1, 0, (mp1的大小));
     for (int j = 0; j < (a[i]的大小); ++j)
         mp1[a[i][j]] = 1;
     if (j == 0)
     {
         f[i] = true;
     }
     else
     {
        f[i] = true;
        for (int j = 0; j <= MAX; ++j)
             if (mp1[j] == 0)
             {
                f[i] = false;
                break;
             }
     }        
} 

for (int i = 0; i < SIZE; ++i)
{
     if (f[i]) continue;
     for (int j = 0; j < SIZE; ++j)
     {
           if (f[j]) continue;
           memset(mp1, 0, (mp1的大小));
           memset(mp2, 0, (mp2的大小));
           for (int k = 0; k < (a[i]的大小); ++k)
               mp1[a[i][k]] = 1;
           for (int k = 0; k < (a[j]的大小); ++k)
               mp2[a[i][j]] = 1;
           bool sdel = true;
           bool cdel = true;
           for (int k = 0; k <= MAX; ++k)
           {
                if ( mp1[k] != mp2[k]) sdel = false;
                if ( mp1[k] + mp2[k] != 1) cdel = false;
                if ( !sdel && !cdel) break;
           }
           f[i] = sdel || cdel;
           if (f[i]) break;
     }    
} 
//现在的终于像了...应该还有很多没有做好的

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • baihacker
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 3
    发表于：2008-04-15 11:03:0220楼 得分:0
    C/C++ code
    //如果在内存中操作,这些数据在平均情况下会占用100M的内存,额外内存可以忽略不计
//算的是300000数据的,如果只有10万,就应该是33M内存,基本可以忍受
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Maxwell
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 11:11:0921楼 得分:0
    外面一层不要用一个vector存，用vector <int>中元素的和做key用std::multimap存，这样分类处理数量就少了。如果vector <int>内部没有重复的数字，还可以用size()再做一个索引。30多万个感觉几分钟就够了似的。楼主能给个测试用数据就更好了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • icosagon
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-04-15 11:25:1222楼 得分:0
    C/C++ code
    #include <vector>
#include <bitset>

using namespace std;


#define N 180

vector<vector<int> > v;

string hashResult(vector<int> & vints)
{
    bitset<N> bitInt;
    int nCounts = vints.size();

    for (int i=0; i<nCounts; ++i)
    {
        bitInt.set(i);
    }
    
    if (bitInt.test(0))
    {
        return bitInt.to_string();
    } 
    else
    {
        bitInt = ~bitInt;
        return bitInt.to_string();
    }
}


    没测试
    修改 删除 举报 引用 回复
    进入用户个人空间