Pointer or (allocatable) array list ?
in [Fortran]
|
Prev: An interesting new RNG.
Next: From Scripting to Scaling: Multi-core is challenging even the most battle-scared programmer
From: GianLuigi Piacentini on 1 Jul 2010 14:31 Dear Fortraneers, I am implementing some classic data structures like stack, queue, priority queue, list, binary search tree that will be used in some geometry-related code, and for which there are very few implementation around (at least what I am aware of...). I need to stay within current g95/gfortran capabilities (f95 with some f03). I plan to achieve some form of genericity using coco or some other preprocessor, because it is (for me) easier to understand than tricks to obtain genericity based on transfer and derived type memory layout. Several of these structures are classically implemented with pointers, but there are also pointerless implementations (like arraylist or binary search tree - see Sedgewick's Algorithms, old Pascal version, pg 184-185). Before starting to code, I would like you opinions about the array vs pointer choice on this specific topic. Many thanks in advance G.L. Piacentini
From: Ian Bush on 1 Jul 2010 17:21 On Jul 1, 7:31 pm, GianLuigi Piacentini <ggpi...(a)tin.it> wrote: > Dear Fortraneers, > > I am implementing some classic data structures like stack, queue, > priority queue, list, binary search tree that will be used in some > geometry-related code, and for which there are very few implementation > around (at least what I am aware of...). I need to stay within current > g95/gfortran capabilities (f95 with some f03). I plan to achieve some > form of genericity using coco or some other preprocessor, because it is > (for me) easier to understand than tricks to obtain genericity based on > transfer and derived type memory layout. > Several of these structures are classically implemented with pointers, > but there are also pointerless implementations (like arraylist or > binary search tree - see Sedgewick's Algorithms, old Pascal version, pg > 184-185). > Before starting to code, I would like you opinions about the array vs > pointer choice on this specific topic. > You've missed out what is about the most important piece of information - which are YOU happiest with? Unless there's a good reason, such as others having to maintain the code after you have written it, I would choose on that criterion, Ian
From: glen herrmannsfeldt on 1 Jul 2010 17:36 GianLuigi Piacentini <ggpiace(a)tin.it> wrote: > I am implementing some classic data structures like stack, queue, > priority queue, list, binary search tree that will be used in some > geometry-related code, and for which there are very few implementation > around (at least what I am aware of...). (snip) > Several of these structures are classically implemented with pointers, > but there are also pointerless implementations (like arraylist or > binary search tree - see Sedgewick's Algorithms, old Pascal version, pg > 184-185). > Before starting to code, I would like you opinions about the array vs > pointer choice on this specific topic. Others will have other opinions, but... Arraylist works well if you know in advance reasonably well what the size should be. Machines now add fast enough that computation speed shouldn't matter much. A pointer linked list has the advantage that you can allocate new elements one at a time very easily. With an array to increase the size you pretty much allocate a new, larger, one, copy the data over, then deallocate. (Twice if you don't have MOVE_ALLOC.) That means you must have about twice the memory you actually need. Even more if you want to increase the size exponentially, which saves time. If memory allocation isn't a problem, if a reasonable fixed size is likely to work well, arraylist is fine. -- glen
From: robin on 3 Jul 2010 04:24 "GianLuigi Piacentini" <ggpiace(a)tin.it> wrote in message news:4c2cdee8$0$31377$4fafbaef(a)reader1.news.tin.it... | Dear Fortraneers, | | I am implementing some classic data structures like stack, queue, | priority queue, list, binary search tree that will be used in some | geometry-related code, and for which there are very few implementation | around (at least what I am aware of...). I need to stay within current | g95/gfortran capabilities (f95 with some f03). I plan to achieve some | form of genericity using coco or some other preprocessor, because it is | (for me) easier to understand than tricks to obtain genericity based on | transfer and derived type memory layout. | Several of these structures are classically implemented with pointers, | but there are also pointerless implementations (like arraylist or | binary search tree - see Sedgewick's Algorithms, old Pascal version, pg | 184-185). | Before starting to code, I would like you opinions about the array vs | pointer choice on this specific topic. binary trees, queues, stacks, etc are best done as data structures and pointers. Especially trees, because the tree can be added to and deleted from simply. There are plenty of texts that illustrate these tasks.
From: robin on 3 Jul 2010 04:27
"glen herrmannsfeldt" <gah(a)ugcs.caltech.edu> wrote in message news:i0j1ok$h4q$1(a)speranza.aioe.org... | GianLuigi Piacentini <ggpiace(a)tin.it> wrote: | | > I am implementing some classic data structures like stack, queue, | > priority queue, list, binary search tree that will be used in some | > geometry-related code, and for which there are very few implementation | > around (at least what I am aware of...). | (snip) | | > Several of these structures are classically implemented with pointers, | > but there are also pointerless implementations (like arraylist or | > binary search tree - see Sedgewick's Algorithms, old Pascal version, pg | > 184-185). | > Before starting to code, I would like you opinions about the array vs | > pointer choice on this specific topic. | | Arraylist works well if you know in advance reasonably well what | the size should be. Machines now add fast enough that computation | speed shouldn't matter much. A pointer linked list has the advantage | that you can allocate new elements one at a time very easily. Data structures and pointers also have the advantage that elements can be added and removed with ease and almost ad-infinitum. | With an array to increase the size you pretty much allocate a new, | larger, one, copy the data over, then deallocate. (Twice if you | don't have MOVE_ALLOC.) That means you must have about twice the | memory you actually need. That comes with additional problems such as data compression, when the tree/stack/queue grows and contracts endlessly. |