473,836 Members | 1,546 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Using a link list over an array.

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_p tr; /* ray_list_head_p tr 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_p tr = p;
}
Jun 27 '08 #1
36 2908
pereges <Br*****@gmail. comwrites:
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] */
}
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.

--
Ben.
Jun 27 '08 #2

"pereges" <Br*****@gmail. comwrote in message
news:f5******** *************** ***********@z16 g2000prn.google groups.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.
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.
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.
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
Jun 27 '08 #3
Ben Bacarisse <be********@bsb .me.ukwrites:
pereges <Br*****@gmail. comwrites:
>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] */
}

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.

Jun 27 '08 #4
On Jun 19, 5:00 pm, Ben Bacarisse <ben.use...@bsb .me.ukwrote:
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.
On Jun 19, 5:00 pm, "Bartc" <b...@freeuk.co mwrote:
Is it even necessary to create the 20million rays all at once? Could you
create, process, and dispose of them one at a time?

Good idea. I think I will create them on the fly, trace them and free
them as soon as their purpose is over.
Jun 27 '08 #5
pereges <Br*****@gmail. comwrites:
On Jun 19, 5:00 pm, Ben Bacarisse <ben.use...@bsb .me.ukwrote:
>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.
I also wrote (in the same message):

| 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.
On Jun 19, 5:00 pm, "Bartc" <b...@freeuk.co mwrote:
>Is it even necessary to create the 20million rays all at once? Could you
create, process, and dispose of them one at a time?

Good idea. I think I will create them on the fly, trace them and free
them as soon as their purpose is over.
I would have been nice if you had quoted the fact that I made the same
suggestion that you considered to be a good idea rather than the part
that is probably not of any use :-)

--
Ben.
Jun 27 '08 #6
On Thu, 19 Jun 2008 11:36:57 UTC, pereges <Br*****@gmail. comwrote:
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.
Arrays are fine when
- the nuber of elements needed is constant
- all memers are in use while the array exists
- no or at least rare resorting of the array is needed
- the number of elements is low
because sorting off array costs many moves of many members
as sorting by moving array member around is reall time exensive

lists are fine when
- you've no idea how many members the list may contain
its easy to shrink or increase the number of elements
- a unknown number of elements will go out of usage
while other lives in usage
- the number of elements in use changes heavely
during the time the list exists
- resorting is needed more ofen
moving pointers around is quick, at lest more quickly
as complete array members. Sorted insert/delete of a
a single member costs only changing a handful pointers
instead of moving up to O(n) array mebers up or down
- its more easy to split and join lists than whole arrays

At least there is no "what is better"? Sometimes arrays and sometimes
lists are better, strictly bounded on the usaga of the usage of the
data.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!
Jun 27 '08 #7
On Jun 20, 11:37 pm, "Herbert Rosenau" <os2...@pc-rosenau.dewrote :
On Thu, 19 Jun 2008 11:36:57 UTC, pereges <Brol...@gmail. comwrote:
Hi, I am wondering which of the two data structures (linklistor
array) would be better in my situation. I have to create alistof
rays for my ray tracing program.

Arrays are fine when
- the nuber of elements needed is constant
- all memers are in use while the array exists
- no or at least rare resorting of the array is needed
- the number of elements is low
becausesortingo ff array costs many moves of many members
assortingby moving array member around is reall time exensive

lists are fine when
- you've no idea how many members thelistmay contain
its easy to shrink or increase the number of elements
- a unknown number of elements will go out of usage
while other lives in usage
- the number of elements in use changes heavely
during the time thelistexists
- resorting is needed more ofen
moving pointers around is quick, at lest more quickly
as complete array members. Sorted insert/delete of a
a single member costs only changing a handful pointers
instead of moving up to O(n) array mebers up or down
- its more easy to split and join lists than whole arrays

At least there is no "what is better"? Sometimes arrays and sometimes
lists are better, strictly bounded on the usaga of the usage of the
data.
Is it easier to sort link lists as opposed to arrays ?? In one
implementation of quick sort applied on link lists, I saw that even
accessing a single Nth node required n-1 passes.
Jun 30 '08 #8
pereges wrote:
>
Is it easier to sort link lists as opposed to arrays ??
This isn't a C question, but it's easy to sort either
data structure.
In one
implementation of quick sort applied on link lists, I saw that even
accessing a single Nth node required n-1 passes.
That's nice. I've seen stupid things, too.

(If you want to learn about sorting and data structures and
other such language-independent topics, comp.programmin g would be
a better forum than a language-specific newsgroup. There's also
the revolutionary notion of consulting a book ...)

--
Er*********@sun .com
Jun 30 '08 #9
pereges wrote:
>
.... snip ...
>
Is it easier to sort link lists as opposed to arrays ?? In one
implementation of quick sort applied on link lists, I saw that
even accessing a single Nth node required n-1 passes.
Sorting lists is easy, and O(NlogN). See the following code:

/* List handling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* =============== === 30 April, 2001 =============== === */

#include "listops.h"

/* =============== =============== =============== ========== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* =============== =============== =============== ========== */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodep tr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;
} /* splitlist */

/* =============== =============== == */
/* Merge two ordered lists into one */
nodeptr mergelists(node ptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;
} /* mergelists */

/* =============== =============== =============== ===== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodep tr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root) ; /* alters list root */
root = mergelists(merg esort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */
/* end listops.c */

and the header file:

/* List handling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* =============== === 30 April, 2001 =============== === */

#ifndef listops_h_
#define listops_h_

#include <stddef.h/* NULL */
#include <iso646.h/* not, and */

/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* =============== =============== =============== ========== */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);

/* =============== =============== =============== ========== */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodep tr p);

/* =============== =============== == */
/* Merge two ordered lists into one */
nodeptr mergelists(node ptr p1, nodeptr p2,
int (*cmp)(void *, void*)); /* compare */

/* =============== =============== =============== ===== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodep tr root,
int (*cmp)(void *, void*)); /* compare */

#endif
/* end listops.h */

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.
Jul 1 '08 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
1393
by: Yang Lee | last post by:
Hi, I have a single link list. at the end of the program or in a loop i want to destroy this link list. so is it enough to free the pointer to this link list or do i have to traverse whole link list until last node where next field is null and free each node. please suggest. thanks lee
3
1784
by: Tom Timmermann | last post by:
In the process of building a link list, I noticed that successive calls to malloc() return a pointer address that keeps getting larger. Can I always count on this behavior and so do pointer comparisons like < or > ? Or is it possible for malloc to return a pointer address smaller than some previous call ? TomT
2
1619
by: siliconwafer | last post by:
Hi All, Q.1:Is a link list of characters terminated with '\0' equivalent to a string? Q.2:If so,can we do string operations in string.h on it?How? Q.3:What is better when it comes to creating arrays on heap - malloc or link list of individual elements?
4
4878
by: plmanikandan | last post by:
Hi, I am new to link list programming.I need to traverse from the end of link list.Is there any way to find the end of link list without traversing from start(i.e traversing from first to find the next for null).Is there any way to find the length of linked list in c.My need is to traverse from the end to 5th node Regards, Mani
10
9787
by: free2cric | last post by:
Hi, I have a single link list which is sorted. structure of which is like typedef struct mylist { int num; struct mylist *next;
103
16022
by: saraSS | last post by:
I'm trying to built and array of circular link list but when I read the input file Ijust get a long link list instead of different list and after trying to use Linked_list_Stack *obj; I'm getting this errors newcir.cpp:107: request for member `push' in `obj', which is of non-aggregate type `Linked_list_Stack*' newcir.cpp:110: request for member `print_list' in `obj', which is of non-aggregate type `Linked_list_Stack*'
9
4454
by: incredible | last post by:
how to sort link list of string
1
6570
by: ahoway | last post by:
I am having problems deleting a node from a link list. I need to delete the node which contains the number six. This is what I have so far..... Thank you in advance. #include <iostream> #include "stdafx.h" using namespace std; class IntNode
0
9825
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
10852
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
10596
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9382
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
6980
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5651
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
5829
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
4021
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3116
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.