关于数据结构的建议。 [英] A suggestion on data structures.
问题描述
我在这里遇到了一些困境。
我想在我的
项目中使用邻接矩阵来构建边缘列表。
东西是一个邻接矩阵，它有nv * nv个元素，其中nv
是顶点数。优点是它使我的项目中的事情变得非常快，只有一次通过三角形列表而不是两次。
但我对分配内存持怀疑态度对于nv * nv
元素。 nv也可以高达10,000,000。存储
10,000,000 * 10,000,000元素实际上可能是一个非常可靠的想法，甚至可能是不允许的。此外，在创建
矩阵时，也可能花费大量时间：
typedef int ** m;
matrix create_matrix（size_t cols，size_t rows）
{
size_t i;
matrix m;
m =（int **）malloc（rows * sizeof（int *））;
for（i = 0; i< rows; i ++）
{
m [i] =（int *）malloc（cols * sizeof（int））;
}
返回（m）;
}
您还需要在这里进行nv通行证。
然后我想使用memset进行一些初始化，即所有
值最初必须为零。我不知道
memset的内部运作情况，所以我再次担心它会减慢我的程序，甚至更多。有更简单的方法吗？
Hi, I''m in a bit of dilemma here.
I want to use an adjacency matrix for building edge lists in my
project.
The thing is an adjacency matrix will have nv * nv elements where nv
is number of vertices. Advantage is that it makes things very fast in
my project, only one pass over list of triangles as opposed to two.
But I''m a little skeptical about allocating memory for nv * nv
elements. nv can be very high up to 10,000,000 as well. Storing
10,000,000 * 10,000,000 elements might actually be an extremely
stupid idea which may not even be allowed. Also, while creating the
matrix also a lot of time may be spent :
typedef int **m;
matrix create_matrix(size_t cols, size_t rows)
{
size_t i;
matrix m;
m = (int **) malloc(rows * sizeof(int *));
for (i = 0; i < rows; i++)
{
m[i] = (int *) malloc(cols * sizeof(int));
}
return (m);
}
You still have to make nv passes here.
And then I want to do some initializations using memset i.e. all
values must be zero initially. I don''t know the internal workings of
memset so once again I''m fearing that it will slow my program even
more. Is there an easier way out of this ?
推荐答案
pereges< Br ***** @ gmail.comwrites：
pereges <Br*****@gmail.comwrites:
我想在我的
项目中使用邻接矩阵来构建边缘列表。
这是一个邻接矩阵将有nv * nv个元素，其中nv
是顶点数。优点是它使我的项目中的事情变得非常快，只有一次通过三角形列表而不是两次。
但我对分配内存持怀疑态度对于nv * nv
元素。 nv也可以高达10,000,000。存储
10,000,000 * 10,000,000元素实际上可能是一个非常可靠的想法，甚至可能是不允许的。此外，在创建
矩阵时，也可能花费大量时间：
typedef int ** m;
matrix create_matrix（size_t cols，size_t rows）
{
size_t i;
matrix m;
m =（int **）malloc（rows * sizeof（int *））;
for（i = 0; i< rows; i ++）
{
m [i] =（int *）malloc（cols * sizeof（int））;
}
返回（m）;
}
I want to use an adjacency matrix for building edge lists in my
project.
The thing is an adjacency matrix will have nv * nv elements where nv
is number of vertices. Advantage is that it makes things very fast in
my project, only one pass over list of triangles as opposed to two.
But I''m a little skeptical about allocating memory for nv * nv
elements. nv can be very high up to 10,000,000 as well. Storing
10,000,000 * 10,000,000 elements might actually be an extremely
stupid idea which may not even be allowed. Also, while creating the
matrix also a lot of time may be spent :
typedef int **m;
matrix create_matrix(size_t cols, size_t rows)
{
size_t i;
matrix m;
m = (int **) malloc(rows * sizeof(int *));
for (i = 0; i < rows; i++)
{
m[i] = (int *) malloc(cols * sizeof(int));
}
return (m);
}
你肯定不会这样做。首先，邻接矩阵中只有
0/1位，因此不需要一个整数数组。其次，
他们几乎总是稀疏的。你需要阅读稀疏布尔矩阵的表示
。最初，当然，这不是一个问题，但它会在以后变成一个问题！
-
Ben 。
You would not do this for sure. First, an adjacency matrix has only
0/1 bits in it, so there is no need to an array of ints. Secondly,
they are almost always sparse. You need to read up on representations
for sparse boolean matrices. Initially, of course, this is not a C
question but it will turn into one later!
--
Ben.
" pereges" < Br ***** @ gmail.com在留言中写道
新闻：1f ************************* ********* @ v1g2000p ra.googlegroups.com ...
"pereges" <Br*****@gmail.comwrote in message
news:1f**********************************@v1g2000p ra.googlegroups.com...
我在这里处于两难境地。 />
我想在我的
项目中使用邻接矩阵来构建边缘列表。
这是一个邻接矩阵将有nv * nv个元素，其中nv
是顶点数。优点是它使我的项目中的事情变得非常快，只有一次通过三角形列表而不是两次。
但我对分配内存持怀疑态度对于nv * nv
元素。 nv也可以高达10,000,000。存储
10,000,000 * 10,000,000元素实际上可能是一个非常可靠的想法，甚至可能是不允许的。此外，在创建
矩阵时，也可能花费大量时间：
typedef int ** m;
matrix create_matrix（size_t cols，size_t rows）
{
size_t i;
matrix m;
m =（int **）malloc（rows * sizeof（int *））;
for（i = 0; i< rows; i ++）
{
m [i] =（int *）malloc（cols * sizeof（int））;
}
返回（m）;
}
你还需要在这里进行nv传球。
Hi, I''m in a bit of dilemma here.
I want to use an adjacency matrix for building edge lists in my
project.
The thing is an adjacency matrix will have nv * nv elements where nv
is number of vertices. Advantage is that it makes things very fast in
my project, only one pass over list of triangles as opposed to two.
But I''m a little skeptical about allocating memory for nv * nv
elements. nv can be very high up to 10,000,000 as well. Storing
10,000,000 * 10,000,000 elements might actually be an extremely
stupid idea which may not even be allowed. Also, while creating the
matrix also a lot of time may be spent :
typedef int **m;
matrix create_matrix(size_t cols, size_t rows)
{
size_t i;
matrix m;
m = (int **) malloc(rows * sizeof(int *));
for (i = 0; i < rows; i++)
{
m[i] = (int *) malloc(cols * sizeof(int));
}
return (m);
}
You still have to make nv passes here.
至于这种情况下一个相当无用的建议（它会吃掉你所有的ram和
然后一些）：
因为所有行都是相同的大小，你实际上并不需要一个
锯齿状数组（除非算法以某种方式设法要求它），你可以
只是malloc（rows * cols * sizeof（int））
在这种情况下你不需要一个int - 而且正如其他人一样
指出稀疏的设置会好得多
As to a rather useless suggestion in this case (it will eat all your ram and
then some):
since all rows are going to be the same size, you don''t actually need a
jagged array (unless the algorithm somehow manages to require it), you could
just malloc(rows * cols * sizeof(int))
in this situation you wouldn''t need an int though - and as others have
pointed out, a sparse set would be much better
pereges < Br ***** @ gmail.com在留言中写道
新闻：1f ************************* ********* @ v1g2000p ra.googlegroups.com ...
"pereges" <Br*****@gmail.comwrote in message
news:1f**********************************@v1g2000p ra.googlegroups.com...
我在这里处于两难境地。 />
我想在我的
项目中使用邻接矩阵来构建边缘列表。
这是一个邻接矩阵将有nv * nv个元素，其中nv
是顶点数。优点是它使我的项目中的事情变得非常快，只有一次通过三角形列表而不是两次。
但我对分配内存持怀疑态度对于nv * nv
元素。 nv也可以高达10,000,000。存储
10,000,000 * 10,000,000元素实际上可能是一个非常可靠的想法，甚至可能是不允许的。此外，在创建
矩阵的同时也可能花费大量时间：
Hi, I''m in a bit of dilemma here.
I want to use an adjacency matrix for building edge lists in my
project.
The thing is an adjacency matrix will have nv * nv elements where nv
is number of vertices. Advantage is that it makes things very fast in
my project, only one pass over list of triangles as opposed to two.
But I''m a little skeptical about allocating memory for nv * nv
elements. nv can be very high up to 10,000,000 as well. Storing
10,000,000 * 10,000,000 elements might actually be an extremely
stupid idea which may not even be allowed. Also, while creating the
matrix also a lot of time may be spent :
不太可能有任何三角形相邻高达1000万人。
通常最多只有3人。除非它们将以不同寻常的方式连接。
每个三角形建议3个整数，包含其他三角形的索引。当
超过3时，有一些溢出方案（也许是分配列表中的3个点之一）
要测试两个A，B三角形是否相邻，需要测试B以查看
A是否在其列表中。
您可能会尝试哈希表：必须首先设置所有
邻接。设置完成后，从索引或地址创建哈希值
三角形A，B和查找;如果在表中，它们是相邻的。
（每个表条目包含A：B，但你也需要许多未使用的条目。）
-
Bartc
It''s unlikely any triangle could be adjacent to up to 10million others.
Usually up to just 3 others. Unless they are going to be connected in
unusual ways.
Suggest 3 ints per triangle, containing indices of other triangles. When
there are more than 3, have some overflow scheme (one of the 3 points to an
allocated list perhaps).
To test whether two A,B triangles are adjacent requires testing B to see if
A is in it''s list.
You might try also a hash table: this has to be set up first with all
adjacencies. Once set up, create a hash value from the indices or addresses
of triangles A,B, and lookup; if present in the table, they are adjacent.
(Each table entry contains A:B, but you need many unused entries too.)
--
Bartc
这篇关于关于数据结构的建议。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
