Using a link list over an array.

[pereges]

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;
}

[Ben Bacarisse]

Re: Using a link list over an array.

pereges <Broli00@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.

[Bartc]

Re: Using a link list over an array.


"pereges" <Broli00@gmail. comwrote in message
news:f5201209-e3ca-4719-a19b-6d1e3db81ae2@z1 6g2000prn.googl egroups.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

[Richard]

Re: Using a link list over an array.

Ben Bacarisse <ben.usenet@bsb .me.ukwrites:

pereges <Broli00@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.

[pereges]

Re: Using a link list over an array.

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.

[Ben Bacarisse]

Re: Using a link list over an array.

pereges <Broli00@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.

[Herbert Rosenau]

Re: Using a link list over an array.

On Thu, 19 Jun 2008 11:36:57 UTC, pereges <Broli00@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!

[pereges]

Re: Using a link list over an array.

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.

[Eric Sosman]

Re: Using a link list over an array.

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 ...)

--
Eric.Sosman@sun .com

[CBFalconer]

Re: Using a link list over an array.

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.

[pereges]

Re: Using a link list over an array.

On Jul 1, 8:03 am, CBFalconer <cbfalco...@yah oo.comwrote:

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 */

Hello, I tried to use your program to sort a list a vectors based on
their x coordinate but it seems only a part of the list was sorted.

This is vector data structure:

typedef struct
{
double coord[3]; /* 0 - x 1 - y 2 -z */

}vector;

Then I try to create the link list of nvert vertices stored in
array vert[0..nvert-1] using the node structure defined in listops.h:

node *p, *head = NULL;
node *prev;
int i;
for(i = 0; i < nvert; i++)
{
p = malloc(sizeof(n ode));
p->next = NULL;
p->data = &vert[i]; /* Store the address of the vector in p-

>data */

if(head == NULL)
{
head = p;
prev = head;
}
else
{
prev->next = p;
prev = p;
}
}

Now, each node contains a data pointer which points to a vector in
vert[]. Here's the comp function I used to sort
on basis of x coordinate i.e. coord[0] member :

int comp(void *vpa, void *vpb)
{
node *a = (node *) vpa;
node *b = (node *)vpb;

vector *va = (vector *) (a->data);
vector *vb = (vector *) (b->data);

return (va->coord[0] < vb->coord[0] ? -1 : va->coord[0] vb-

>coord[0]);

}

then I applied the mergesort:

mergesort(head, comp);

I check the result using:

p = head;
while (p != NULL)
{
printf("%f %f %f\n", p->data->coord[0], p->data->coord[1], p->data-

>coord[2]);

p = p->next;
}

and I discovered that almost 2000 vectors from the original list of
7778 were missing although the other vectors were sorted.

[CBFalconer]

Re: Using a link list over an array.

pereges wrote:

>

.... snip ...

>
then I applied the mergesort:
>
mergesort(head, comp);
>
I check the result using:
>
p = head;
while (p != NULL)
{
printf("%f %f %f\n", p->data->coord[0], p->data->coord[1], p->data-

coord[2]);++

p = p->next;
}
>
and I discovered that almost 2000 vectors from the original list of
7778 were missing although the other vectors were sorted.

I didn't read your code in detail, but simply noted the above.
mergesort is a function, and it returns a pointer to the head of
the sorted list. You discarded the result.

The simplest way to build the list is by adding items at the head

nodeptr listhead = NULL;
nodeptr temp;
...
while (another item to store) {
temp = malloc(sizeof *temp);
temp->next = listhead;
temp->datum = newitem;
listhead = temp;
}

after which listhead points to the unsorted list. After:

listhead = mergesort(listh ead, cmpfunction());

that list is sorted. You have to supply the proper cmpfunction for
your data.

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

[pereges]

Re: Using a link list over an array.

On Jul 1, 4:49 pm, CBFalconer <cbfalco...@yah oo.comwrote:

pereges wrote:
>
... snip ...
>

then I applied the mergesort:

>

mergesort(head, comp);

>

I check the result using:

>

p = head;
while (p != NULL)
{
printf("%f %f %f\n", p->data->coord[0], p->data->coord[1], p->data-

>coord[2]);++

p = p->next;
}

>

and I discovered that almost 2000 vectors from the original list of
7778 were missing although the other vectors were sorted.

>
I didn't read your code in detail, but simply noted the above.
mergesort is a function, and it returns a pointer to the head of
the sorted list. You discarded the result.
>
The simplest way to build the list is by adding items at the head
>
nodeptr listhead = NULL;
nodeptr temp;
...
while (another item to store) {
temp = malloc(sizeof *temp);
temp->next = listhead;
temp->datum = newitem;
listhead = temp;
}
>
after which listhead points to the unsorted list. After:
>
listhead = mergesort(listh ead, cmpfunction());
>
that list is sorted. You have to supply the proper cmpfunction for
your data.
>

Sorry I missed that bit of information. I checked again and it works
perfectly. Btw, I'm a little confused between qsort on array and merge
sort on link list. Which in your opinion is better ? From my project's
point of view, there seems to be some very obvious advantages.

[Ben Bacarisse]

Re: Using a link list over an array.

pereges <Broli00@gmail. comwrites:

On Jul 1, 8:03 am, CBFalconer <cbfalco...@yah oo.comwrote:

>pereges wrote:

<snip>

Is it easier to sort link lists as opposed to arrays ??

<snip>

>Sorting lists is easy, and O(NlogN). See the following code:

<snip>

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

<snip>

Hello, I tried to use your program to sort a list a vectors based on
their x coordinate but it seems only a part of the list was sorted.

<snip>

then I applied the mergesort:
>
mergesort(head, comp);
>
I check the result using:
>
p = head;
while (p != NULL)
{
printf("%f %f %f\n", p->data->coord[0], p->data->coord[1], p->data-

>>coord[2]);

p = p->next;
}

With CBFalconer's definition of a node, the code above will not
compile (p->data is a void *) so you have not shown us some key code.
Maybe the problem is in that part not shown.

and I discovered that almost 2000 vectors from the original list of
7778 were missing although the other vectors were sorted.

--
Ben.

[pereges]

Re: Using a link list over an array.

On Jul 1, 6:35 pm, Ben Bacarisse <ben.use...@bsb .me.ukwrote:

>
With CBFalconer's definition of a node, the code above will not
compile (p->data is a void *) so you have not shown us some key code.
Maybe the problem is in that part not shown.
>

Now, its working after I made some changes. Some changes

/* creating the link list */

node *p, *head = NULL;
int i = 0;

while (i < m->nvert)
{
p = malloc(sizeof *p);
p->next = head;
p->data = &m->vert[i];
head = p;
i++;
}

/* Sorting link list */

head = mergesort(head, cmp);
p = head;

/* Printing the vectors using soreted link list */
while (p != NULL)
{
vector_print(p->data);
p = p->next;
}

/* cmp function */

int cmp(const void *vpa, constvoid *vpb)
{
node *va = ( node *)vpa;
node *vb = ( node *)vpb;

vector *a = (vector *) (va->data);
vector *b = (vector *) (vb->data);

if (a->coord[1] < b->coord[1])
return -1;
if (a->coord[1] >b->coord[1])
return 1;
else
return 0;
}

The above cmp function sorts w.r.t the coord[1] member. Similarly, I
will write functions for coord[0] or coord[2].