在数组上使用链接列表。 [英] Using a link list over an array.
问题描述
我想知道两种数据结构中的哪一种（链接列表或
数组）在我的情况下会更好。我必须为我的光线追踪程序创建一个
光线列表。
ray的数据结构如下所示：
typedef struct
{
vector origin; / * vector是3个双精度数组* /
向量efield;
双t;
向量方向;
} ray;
我需要一个非常精细的光线网格，比如15-20百万美元这样的光线。很多时候我的程序失败并报告内存较少当
我使用数组因为还有数据结构存储。
带有数组的
例如。 raylist [some_size]当我追踪光线时，我按下
：
for（count = 0; count< numberofrays; count ++）
{
/ *跟踪光线列表[i] * /
}
我意识到一旦光线被跟踪，它就没有在
程序中进一步使用，因此不必要地占用了那些可以在其他地方使用的内存。
我以为使用链接列表可能会对我的情况有所帮助
在这里。
ray * p;
ray * q;
p = ray_list_head_ptr; / * ray_list_head_ptr指向第一个节点
在链接列表中* /
while（p！= NULL）
{
/ *跟踪由p * /
q = p指向的光线;
p = p-> next;
/ *现在q指向的光线是没有用的，因此内存和
使节点指向p作为光线列表的第一个节点* /
free（q）;
ray_list_head_ptr = p;
}
Hi, I am wondering which of the two data structures (link list or
array) would be better in my situation. I have to create a list of
rays for my ray tracing program.
the data structure of ray looks like this:
typedef struct
{
vector origin; /* vector is an array of 3 doubles */
vector efield;
double t;
vector direction;
}ray;
I need a very fine grid of rays i.e. something like 15-20 millions of
such rays. Many a times my program fails and reports less memory when
I use an array because there are data structures to be stored as well.
with an array eg. raylist[some_size] when i trace the rays, i do the
following :
for(count = 0; count < numberofrays; count++)
{
/* trace the ray raylist[i] */
}
I realized that once a ray was traced, it had no further use in the
program so it was unnecessarily occupying that memory which can be
utilized elsewhere.
I was thinking that using a link list may help my situation a little
bit here.
ray *p;
ray *q;
p = ray_list_head_ptr; /* ray_list_head_ptr points to the first node
in link list */
while( p != NULL)
{
/* trace the ray pointed by p */
q = p;
p = p->next;
/* Now the ray pointed by q is of no use so free that memory and
make the node pointed by p as the first node of the ray list */
free(q);
ray_list_head_ptr = p;
}
推荐答案
pereges< Br*****@gmail.comwrites：
pereges <Br*****@gmail.comwrites:
您好，我想知道这两个数据结构中的哪一个（链接列表或
在我的情况下会更好。我必须为我的光线追踪程序创建一个
光线列表。
ray的数据结构如下所示：
typedef struct
{
vector origin; / * vector是3个双精度数组* /
向量efield;
双t;
向量方向;
} ray;
我需要一个非常精细的光线网格，比如15-20百万美元这样的光线。很多时候我的程序失败并报告内存较少当
我使用数组因为还有数据结构存储。
带有数组的
例如。 raylist [some_size]当我追踪光线时，我按下
：
for（count = 0; count< numberofrays; count ++）
{
/ *跟踪光线列表[i] * /
}
Hi, I am wondering which of the two data structures (link list or
array) would be better in my situation. I have to create a list of
rays for my ray tracing program.
the data structure of ray looks like this:
typedef struct
{
vector origin; /* vector is an array of 3 doubles */
vector efield;
double t;
vector direction;
}ray;
I need a very fine grid of rays i.e. something like 15-20 millions of
such rays. Many a times my program fails and reports less memory when
I use an array because there are data structures to be stored as well.
with an array eg. raylist[some_size] when i trace the rays, i do the
following :
for(count = 0; count < numberofrays; count++)
{
/* trace the ray raylist[i] */
}
您可能根本不需要存储它们。在我看过的版本中，raylist [i]中的
数据似乎是由i确定的（实际上是固定网格中光线的
位置）。如果是这种情况，只需在使用点制作
光线。
如果计算一次性使用它们，您只需要存储它们
（或差不多一次）。例如，如果计算raylist [i]是
更容易知道ralylist [0] ... raylist [i-1]。
You may not need to store them at all. In once version I saw, the
data in raylist[i] seemed to be determined by i (in effect the
position of the ray in a fixed grid). If this is the case, just make
the ray at the point of use.
You only need to store them if the computation uses them all at once
(or in nearly at once). For example, if computing raylist[i] is
easier knowing ralylist[0] ... raylist[i-1].
我意识到，一旦光线被追踪，它在
程序中没有进一步的使用，所以它不必要地占用那些可以在其他地方使用的内存。
我以为使用链接列表可能会对我的情况有所帮助
位。
I realized that once a ray was traced, it had no further use in the
program so it was unnecessarily occupying that memory which can be
utilized elsewhere.
I was thinking that using a link list may help my situation a little
bit here.
这将允许你删除它们，是的，但链表总是
使用比裸阵列稍多的空间。如果访问模式
很复杂，那么列表也可能会变慢。
-
Ben。
It would allow you to delete them, yes, but a linked list will always
use slightly more space than a bare array. If the pattern of access
is complex then a list is likely to be slower as well.
--
Ben.
" pereges" < Br ***** @ gmail.com在留言中写道
新闻：f5 ************************* ********* @ z16g2000 prn.googlegroups.com ...
"pereges" <Br*****@gmail.comwrote in message
news:f5**********************************@z16g2000 prn.googlegroups.com...
您好，我想知道这两个数据结构中的哪一个（链接列表或
数组）在我的情况下会更好。我必须为我的光线追踪程序创建一个
光线列表。
Hi, I am wondering which of the two data structures (link list or
array) would be better in my situation. I have to create a list of
rays for my ray tracing program.
我需要一个非常精细的光线网格，例如15-20百万美元这样的光线。很多时候我的程序失败并报告更少的内存当
我使用数组因为还有数据结构存储。
I need a very fine grid of rays i.e. something like 15-20 millions of
such rays. Many a times my program fails and reports less memory when
I use an array because there are data structures to be stored as well.
我意识到一旦光线被跟踪，它就无法在
程序中进一步使用，因此它不必要地占用在其他地方使用的内存可以是b $ b。
I realized that once a ray was traced, it had no further use in the
program so it was unnecessarily occupying that memory which can be
utilized elsewhere.
甚至有必要一次创建2000万条光线吗？你能
一次创建，处理和处理它们吗？
-
bartc
Is it even necessary to create the 20million rays all at once? Could you
create, process, and dispose of them one at a time?
--
bartc
Ben Bacarisse< be ******** @ bsb.me.ukwrites：
Ben Bacarisse <be********@bsb.me.ukwrites:
pereges< Br*****@gmail.comwrites：
pereges <Br*****@gmail.comwrites:
>我想知道这两个数据结构中的哪一个（链接列表或
数组）在我的情况会更好。我必须为我的光线追踪程序创建一个
光线列表。
光线的数据结构如下所示：
typedef struct
{
矢量起源; / * vector是3个双精度数组* /
矢量efield;
双t;
向量方向;
} ray;
我需要一个非常精细的光线网格，例如15-20万个这样的光线。很多时候我的程序失败并且在使用数组时报告的内存较少，因为还有数据结构存储。
有一个数组，例如。 raylist [some_size]当我追踪光线时，我做了
以下：
for（count = 0; count< numberofrays; count ++）
/ *跟踪光线列表[i] * /
}
>Hi, I am wondering which of the two data structures (link list or
array) would be better in my situation. I have to create a list of
rays for my ray tracing program.
the data structure of ray looks like this:
typedef struct
{
vector origin; /* vector is an array of 3 doubles */
vector efield;
double t;
vector direction;
}ray;
I need a very fine grid of rays i.e. something like 15-20 millions of
such rays. Many a times my program fails and reports less memory when
I use an array because there are data structures to be stored as well.
with an array eg. raylist[some_size] when i trace the rays, i do the
following :
for(count = 0; count < numberofrays; count++)
{
/* trace the ray raylist[i] */
}
您可能根本不需要存储它们。在我看过的版本中，raylist [i]中的
数据似乎是由i确定的（实际上是固定网格中光线的
位置）。如果是这种情况，只需在使用点制作
光线。
如果计算一次性使用它们，您只需要存储它们
（或差不多一次）。例如，如果计算raylist [i]是
更容易知道ralylist [0] ... raylist [i-1]。
You may not need to store them at all. In once version I saw, the
data in raylist[i] seemed to be determined by i (in effect the
position of the ray in a fixed grid). If this is the case, just make
the ray at the point of use.
You only need to store them if the computation uses them all at once
(or in nearly at once). For example, if computing raylist[i] is
easier knowing ralylist[0] ... raylist[i-1].
>我意识到，一旦光线被追踪，它就没有在
程序中使用了，所以它不必要地占用了可以在其他地方使用的记忆。
我是以为使用链接列表可能会对我的情况有所帮助。
>I realized that once a ray was traced, it had no further use in the
program so it was unnecessarily occupying that memory which can be
utilized elsewhere.
I was thinking that using a link list may help my situation a little
bit here.
它允许你删除它们，是的，但链表总是
比裸阵列使用更多的空间。如果访问模式
很复杂，那么列表也可能会变慢。
It would allow you to delete them, yes, but a linked list will always
use slightly more space than a bare array. If the pattern of access
is complex then a list is likely to be slower as well.
即使访问模式较慢，链表也可能比较慢。不要忘记像虚拟内存这样的东西发挥作用
他在阅读新点的过程中遍历他的列表
并转移到下一个光线。
Even the pattern of access is slower the linked list is likely to be
slower as well. Dont forget things like virtual memory coming into play
as he traverses his list on top of the overhead of reading new points
and moving to the next ray.
这篇关于在数组上使用链接列表。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
