我正在尝试创建一些代码以从大约 20 万到 100 万条记录的列表中找出记录。显然,我希望这个过程尽可能快。基本思想如下,大列表中的记录是数字的组合,要放在一起。例如:
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,400076,400097,800076,800097
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,200032,200078,500032,500078
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,300043,300083,600043,600083
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,600026,600077,900026,900077
0,0,0,0,0,0,0,0,0,0,0,0,0,0,100008,100028,400028,400056,600008,600056
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,400042,400098,500042,500098
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,15,86,500015,500086
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,400013,400076,800013,800076
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,700024,700083,900024,900083
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,100003,100047,800003,800047
记录的最大长度为 20,这就是附加零的原因。让我们暂时不要担心这些。所以,我想“捞出”一些记录,这样就不会观察到重复。如果有一个重复,我可以丢弃该记录,不再进一步查看。因此,我必须编制一个如下所示的列表:
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,400076,400097,800076,800097
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,200032,200078,500032,500078
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,300043,300083,600043,600083
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,600026,600077,900026,900077
0,0,0,0,0,0,0,0,0,0,0,0,0,0,100008,100028,400028,400056,600008,600056
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,400042,400098,500042,500098
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,15,86,500015,500086
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,700024,700083,900024,900083
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,100003,100047,800003,800047
请注意在上面的列表中,记录号。缺少 8,因为数字 400076 已经存在于先前的记录中。
我使用的代码如下:
void Make_List(ConfigList *pathgroups, ConfigList *configlist)
{
int i,j,k,l,flag,pg_num=0,len,p_num=0;
for(i = 0;i<configlist->num_total;i++)
{
flag = 0;
for(j = configlist->configsize-1;j>=0;j--)
{
if(configlist->pathid[i][j])
{
for(k = 0;k<pg_num;k++)
{
for(l = pathgroups->configsize-1;l>=0;l--)
{
if(pathgroups->pathid[k][l])
{
if(configlist->pathid[i][j]==pathgroups->pathid[k][l])
{
flag++;
break;
}
}
else
{
break;
}
}
if(flag)
{
break;
}
}
}
else
{
break;
}
if(flag)
{
break;
}
}
if(!flag)
{
len = 0;
for(j = configlist->configsize-1;j>=0;j--)
{
pathgroups->pathid[pg_num][j]=configlist->pathid[i][j];
if(configlist->pathid[i][j])
{
len++;
}
}
pg_num++;
p_num+=len;
if(p_num>=totpaths)
{
break;
}
}
}
Print_ConfigList(stderr,pathgroups);
}
ConfigList 结构主要存储二维数组以及程序不同部分使用的其他内容。
num_total
告诉我们数组中的行数,而 configsize
告诉我们数组中的列数。
totpaths
是一个断点,它在分配完全完成的情况下提前终止循环。
最佳答案
检查每个元素是否为每个分析的新元素重复具有 O(N^2)
的计算成本,考虑到您的大型输入集,这太多了。
基本上,您需要的是一个快速访问的数据结构,您可以在其中记录您的记录出现的次数或至少一个 bool 标志。
最简单的方法是使用一个数组,其中位置代表每个可能的值,数组值代表位置值出现的次数(或其存在的 bool 值)。但是,如果您的数据范围太大,您可以这样做,因为用于存储数组的内存与范围大小成正比。
避免这种情况的替代方法是使用哈希表或集合。
正如您在上面的评论中所确定的那样,您的整数范围是 [0,99999999]
因此,如果您想使用 vector 来跟踪每个单个值的存在与否,您可以需要大约 96 MB
才能将其存储在内存中。
这是一个使用字节数组的例子:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_IN_RANGE 99999999
int main()
{
char * isInInput = (char*)malloc(MAX_IN_RANGE+1);
memset(isInInput,0,MAX_IN_RANGE+1);
size_t i;
int inputExample[] = {1,3,5,2,1,5};
for(i = 0; i < 6; i++)
{
int value = inputExample[i];
printf("%d\n",value);
if(!isInInput[value])
{
printf("Add value %d to your collection\n", value);
isInInput[value] = 1;
}
else
{
printf("%d is repeated\n", value);
}
}
free(isInInput);
}
要改用哈希表,您可以依赖 Judy 等库为了避免实现您自己的哈希表。
关于c - 无重复创建二维数组的最佳方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23864443/