Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-4041-

Linked vs Dynamic Array

Name: Anonymous 2011-12-12 20:01

In consideration of modern architectures and memory layout, are linked data structures ever worth it?
It feels like an dynamic array is a lot better in every sense.

Name: Anonymous 2011-12-12 20:18

Good thread

Name: Anonymous 2011-12-12 20:33

>>1
Dat asymptote. Baby got back.

Name: Anonymous 2011-12-12 21:00

Use arrays from <32 elems lists, then switch to tree. Also, everything should be immutable - that way `take` and `drop` could reuse parts of old list.

Name: Anonymous 2011-12-12 21:19

Inserting/removing in the middle/begining?
Once might be okay, but what if you need to do it constantly?
Shit's gonna reallocate like mad.

Name: Anonymous 2011-12-12 21:27

>>1
Queues /thread

Name: Anonymous 2011-12-12 21:32

inb4 FV invents SilverBullet data structure which has O(1) on everypossible usage

Name: Anonymous 2011-12-12 21:34

>>7
inb4 the self-proclaimed `expert self taught programmer' trys to act smart and just ends up showing how he doesn't know programming even more

Name: Anonymous 2011-12-12 22:11

if it's mutable it's shit

Name: Anonymous 2011-12-12 22:27

>>7
hush-hush, we have him contained in these optimization for autist threads these days. please don't break a system that works.

Name: Anonymous 2011-12-12 22:53

>>9
fuck off and die, haskell fagstorm

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 0:19

>>7
Arrays and Multi-Dimensional arrays. If you want to know how i do something in O(1) time just ask. I never had problems with array speed since i started and i never had the need to use or invent something faster.

Name: Anonymous 2011-12-13 0:21

>>12
KEKEKEKEKEKEKEKEKEKEKEKEKEKEKEKEKE

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 0:27

Deleting Array elements:I just put NULL values for the datatype  O(1) here
Adding array space: realloc or making array with some MAX_SIZE which should be enough for most things. O(1)
Indexing: accessing the element[number] O(1)
Modifying Array Cells:one instant operation array[element]=value: O(1)
Anything else?

Name: Anonymous 2011-12-13 0:45

>>14
Deleting Array elements:I just put NULL values for the datatype  O(1) here
that's not how a delete function in a dynamic array works. You do know what a dynamic array is, right?
Adding array space: realloc or making array with some MAX_SIZE which should be enough for most things. O(1)
wasting space, why am i not surprised you bloat your own programs.
realloc O(1)
more proof you're retarded

Name: Anonymous 2011-12-13 0:51

>>14
How's that O(1) search function coming along with your shitty arrays?

Or the O(1) INSERT

Name: Anonymous 2011-12-13 0:56

>>14

taking the boring, lazy, and easy way out.

Name: Anonymous 2011-12-13 1:04

>>17
It's not boring—it doesn't even work! How can it be boring if it's broken‽ Laziness is a virtue in programming, but no worries, this kind of code will provide you with plenty of mop-up work to do.

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 2:10

>>16
I use binary search on sorted arrays if its required, and i don't insert stuff inside the array, i find empty slots first(since the MAX_SIZE array has empty slots at the end)

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 2:15

Insert into array is 2 stage operation:
1.find first empty/deleted slot(fileld with NULL values)
2.overwrite it with your value
the #1 is stored for convenience as extra variable describing where to get storage without searching empty slots each time.
the #2 is O(1) operation
=======================
Search for some value is not often needed: i usually prefer to store such "key values" in their own variables.
In case you need fast search:
1.sort the array. Should be pre-sorted if you want maximum speed.
2.binary search the array. O(Log N) at worst case O(1) at best

Name: Anonymous 2011-12-13 2:36

>> 20
1.find first empty/deleted slot(fileld with NULL values)
O(n)

the #1 is stored for convenience as extra variable describing where to get storage without searching empty slots each time.
Two successive deletions would need more than one variable.

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 2:50

>>21
If you use the insert that much you will maintain arrays of EmptySlots filled with N indexes to free array elements.
If you use Insert rarely you will maintain one variable and update it after each insert.

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 2:58

I don't normally need any empty slots, since i design the program such that i append new values at end of last non-empty element(the real_size of array not allocated_size) which is less then MAX_SIZE(allocated_size),and when array is too fragmented i compactify the empty slots and array first empty element become a lower index with.

Name: Anonymous 2011-12-13 3:07

>>22
Isn't an excuse for this poorly designed “algorithm”.

>>23
when array is too fragmented i compactify the empty slots
How often do you scan the array to know this?

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 3:08

>>24
When Real_size reaches around 10-20 elements below allocated_size.

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 3:09

I do not "scan the array" the real_size isincremented by one with each new element, and when the array is compacted i updated the real_size.

Name: Anonymous 2011-12-13 3:19

I always lazily delete from my data structures, it gives me that refreshing Java feel when I waste memory.

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 3:23

>>27
Wasting a couple of kilobytes or even megabytes is not that criticial.
You waste far more in CPU time if you keep the array compacted all time.

Name: Anonymous 2011-12-13 3:23

>>6
Queues do very well as dynamic arrays, what is your point?

Name: Anonymous 2011-12-13 3:24

>>28
Wasting a couple of kilobytes or even megabytes is not that criticial.
I'd say that depends on the situation and the application.

Name: Anonymous 2011-12-13 3:25

>>25
I won't ask nothing more, and just hope you know when to use hash tables and linked lists.

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 3:26

>>30
In that case, i would start using EmptySlots helper array aggressively as outlined in >>22

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 3:29

>>31
I use Arrays exclusively for my code, only when the API/Library/External code is requesting a struct of another format i switch to it.

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 3:33

Here is example of Bitmap struct as array:
bitmap[0]='B';
bitmap[1]='M';
u4*crfilesize=bitmap+2;
*crfilesize=FILESIZE;//skip 4+4
u4* bitmapoffset=bitmap+10;
*bitmapoffset=STDOFFSET;
u4* bhsize=bitmap+14;
*bhsize=HEADERINFOSIZE;
u4* w=bitmap+18;
*w=DEFWRES;
u4* h=bitmap+22;
*h=DEFHRES;
u2* bitplanes=bitmap+26;
*bitplanes=1;
u2* bitsperpixel=bitmap+28;
*bitsperpixel=BITSPERPIXEL;
u4* compression=bitmap+30;
*compression=0;
u4* imagesize=bitmap+34;
*imagesize=SIZE;
u4* xppm=bitmap+38;
u4* yppm=bitmap+42;
*xppm=STDPPM;
*yppm=STDPPM;
u4* numcolors=bitmap+46;
*numcolors=256;
u4* impcolors=bitmap+50;
*impcolors=256;//54 bytes
f8 off=0;
u4 currframe=0;
u4 i,c,m;
u4 x,y,height=*h,width=*w;
s4* colors=bitmap+54;
s4* pixels=bitmap+STDOFFSET;

Name: Anonymous 2011-12-13 5:40

if you don't care about the ordering of your array, you can delete arbitrary elements from the array by copying the last element of the array to the deletion index, and then decrementing the array size by one. You can reallocate the array to save space if it shrinks too small.

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 5:43

The point is you don't delete elements, you NULL them and continue using the array, until you need fresh slots (which are usually from end to allocated_size).

Name: Anonymous 2011-12-13 5:53

>>36
How are you certain that NULL isn't a valid value for an element in the array?

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 5:54

>>37
the ARRAY_NULL is defined as value which is invalid for any element.

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 5:54

#define ARRAY_NULL 2147483647

Name: Anonymous 2011-12-13 6:04

Just use std::vector for everything.

Name: Anonymous 2011-12-13 8:06

>>39
How are you certain that 2147483647 isn't a valid value for an element in the array?

Name: Anonymous 2011-12-13 8:10

>>41
Because you make it so.

Name: F r o z e n V o i d !!mJCwdV5J0Xy2A21 2011-12-13 8:23

>>41
because its defined to treat any integer which is ARRAY_NULL as invalid value which would trigger an error(actually just add debug message to console, i don't intend to interrupt it unless data is being corrupted)

Name: Anonymous 2011-12-13 9:00

>>43
kekekekekekekekekekekekekeke

Name: Anonymous 2011-12-13 9:23

>>44
I though FV was a slav...

Name: Anonymous 2011-12-13 9:23

>>45
*t

Name: Anonymous 2011-12-13 11:20

>>34
C/C++ looks like shit. Thank you, but I'll stick with Lisp.

Name: Anonymous 2011-12-13 11:38

i dont believe op understands the differences between linked lists and dynamic arrays properly
or he is a troll...

Name: Anonymous 2011-12-13 12:32

>>20'
>In case you need fast search:
>1.sort the array. Should be pre-sorted if you want maximum speed.
>2.binary search the array. O(Log N) at worst case O(1) at best

1) Not O(1) at best O(n*log(n))
2) I can bet you your binary search will average over more towards O(log(n)) than O(1) since O(1) requires you to pick something right in the middle
3) Overall you're looking at O(n*log(n)*log(n)) worst case when you need to search for something or O(n*log(n)) at best case



'Insert into array is 2 stage operation:
1.find first empty/deleted slot(fileld with NULL values)
2.overwrite it with your value

1) Not O(1)


You truly are retarded, may i suggest going back to your self-proclaimed expert programmers reddit page and never coming back. I'm sure you can keep yourself company there.

Name: Anonymous 2011-12-13 12:34

>>29
Queues do very well as dynamic arrays, what is your point?
You enjoy O(n) pop/poll everytime?

Name: Anonymous 2011-12-13 12:37

>>50
and O(n) push

Name: Anonymous 2011-12-13 14:04

>>50,51
Except that you can just treat the array as a circular buffer and only need to reallocate when you run out of allocated space, everything else is O(1) and the reallocation stages are amortized O(1).

Just because you're too retarded to do something as simple as use an array for a queue doesn't mean everybody else is, arrays severely outperform linked structures when it comes to things like deques, stacks and queues.

Name: Anonymous 2011-12-13 16:18

>arrays severely outperform linked structures when it comes to things like deques,stacks and queues

[citation required]

Name: Anonymous 2011-12-13 18:07

>>53
They're both O(1) at end-point push, enqueue and pop, but on modern architectures dynamic arrays are more cache efficient and have better locality of reference, so the constant is lower.

Name: Anonymous 2011-12-13 19:25

I wrote a small test, everything is one giant file so FrozenVoid should be happy. I wrote it so that the structures are easily extensible with O(1) peek and size operations and O(n) contains.

#include <stdlib.h>
#include <stddef.h>

typedef int data_type;

#define DATA_TYPE_NULL ((data_type) -1)
#define DATA_TYPE_DEALLOCATOR(data)

/* array_stack */

#define REALLOC_SIZE(oldsize) (2*(oldsize) + 1)

typedef struct {
  data_type * base;
  data_type * read;
  data_type * end;
} array_stack;

static inline array_stack *
array_stack_init (array_stack * self)
{
  self->base = NULL;
  self->read = self->base;
  self->end  = self->base + 0;

  return self;
}

static inline array_stack *
array_stack_clear (array_stack * self)
{
  while (self->base < self->read--)
    DATA_TYPE_DEALLOCATOR(*self->read);

  free(self->base);

  return array_stack_init(self);
}

static inline data_type
array_stack_push (array_stack * self, data_type elem)
{
  if (self->read == self->end) {
    ptrdiff_t read_offset = (self->read - self->base);
    ptrdiff_t size = (self->end - self->base);

    self->base = realloc(self->base, REALLOC_SIZE(size) * sizeof(data_type));
    self->read = self->base + read_offset;
    self->end  = self->base + REALLOC_SIZE(size);

    if (self->base == NULL)
      return DATA_TYPE_NULL;
  }

  return *self->read++ = elem;
}

static inline data_type
array_stack_pop (array_stack * self)
{
  if (self->read == self->base)
    return DATA_TYPE_NULL;

  return *--self->read;
}

/* linked stack */

typedef struct {
  struct linked_stack_node {
    struct linked_stack_node * prev;
    data_type elem;
  } * head;

  int size;
} linked_stack;

static inline struct linked_stack_node *
__linked_stack_node_init (struct linked_stack_node * self, data_type elem)
{
  self->prev = NULL;
  self->elem = elem;

  return self;
}

static inline struct linked_stack_node *
__linked_stack_node_alloc (data_type elem)
{
  struct linked_stack_node * node;

  node = malloc(sizeof(node));

  if (node == NULL)
    return NULL;

  return __linked_stack_node_init(node, elem);
}

static inline void
__linked_stack_node_destroy (struct linked_stack_node * self)
{
  DATA_TYPE_DEALLOCATOR(self->elem);
  free(self);
}

static inline linked_stack *
linked_stack_init (linked_stack * self)
{
  self->head = NULL;
  self->size = 0;

  return self;
}

static inline linked_stack *
linked_stack_clear (linked_stack * self)
{
  struct linked_stack_node * node;

  while (self->head != NULL) {
    node = self->head;
    self->head = self->head->prev;
    __linked_stack_node_destroy(node);
  }

  return linked_stack_init(self);
}

static inline data_type
linked_stack_push (linked_stack * self, data_type elem)
{
  struct linked_stack_node * node;

  node = __linked_stack_node_alloc(elem);

  if (node == NULL)
    return DATA_TYPE_NULL;

  node->prev = self->head;
  self->head = node;

  self->size += 1;

  return elem;
}

static inline data_type
linked_stack_pop (linked_stack * self)
{
  struct linked_stack_node * node;
  data_type elem;

  if (self->head == NULL)
    return DATA_TYPE_NULL;

  elem = self->head->elem;
  node = self->head;
  self->head = self->head->prev;

  __linked_stack_node_destroy(node);

  self->size -= 1;

  return elem;
}

/* testing */

#include <stdio.h>
#include <time.h>
#include <sys/time.h>

#define NUMBER_OF_OPERATIONS 100000000

static struct timeval time_buffer_start;
static struct timeval time_buffer_end;
static struct timeval time_buffer_res;
static time_t seed = 0;

static void
array_stack_test (void)
{
  int i;
  array_stack s;

  array_stack_init(&s);
  srand(seed);

  for (i = 0; i < NUMBER_OF_OPERATIONS; i++)
    rand() & 1 ? array_stack_push(&s, i) : array_stack_pop(&s);

  array_stack_clear(&s);
}

static void
linked_stack_test (void)
{
  int i;
  linked_stack s;

  linked_stack_init(&s);
  srand(seed);

  for (i = 0; i < NUMBER_OF_OPERATIONS; i++)
    rand() & 1 ? linked_stack_push(&s, i) : linked_stack_pop(&s);

  linked_stack_clear(&s);
}

#define test(implementation)                        \
  do {                                              \
    gettimeofday(&time_buffer_start, NULL);         \
    implementation##_test();                        \
    gettimeofday(&time_buffer_end, NULL);           \
                                                    \
    timersub(&time_buffer_end,                      \
             &time_buffer_start,                    \
             &time_buffer_res);                     \
                                                    \
    printf(#implementation ": %lu.%06lu seconds\n", \
           time_buffer_res.tv_sec,                  \
           time_buffer_res.tv_usec);                \
  } while (0)

int main (void)
{
  seed = time(NULL);

  test(array_stack);
  test(linked_stack);

  return 0;
}

Name: Anonymous 2011-12-13 20:48

>>34
Here is example of Bitmap struct as array:
Here is example of a Bitmap "struct array" as a struct:
struct Bitmap {
     char magic[2];
     uint32_t crfilesize, dummy, bitmapoffset, bhsize, w, h;
     uint16_t bitplanes, bitsperpixel;
     uint32_t compression, imagesize, xppm, yppm, numcolors, impcolors;
     int32_t colors;
     char padding[n]; //pad until STDOFFSET
     int32_t pixels;
};

Now if you have a compiler that isn't crap, you can do this:
bitmap = (struct Bitmap){
     .magic = "BM",
     .crfilesize = FILESIZE,
     .bitmapoffset = STDOFFSET,
     .bhsize = HEADERINFOSIZE,
     .w = DEFWRES,
     .h = DEFHRES,
     .bitplanes = 1,
     .bitsperpixel = BITSPERPIXEL,
     .compression = 0,
     .imagesize = SIZE,
     .xppm = STDPPM,
     .yppm = STDPPM,
     .numcolors = 256,
     .impcolors = 256
};
double off = 0;
uint32_t currframe = 0;
uint32_t i,c,m;
uint32_t x,y,height = bitmap.h, width = bitmap.w;

Name: Anonymous 2011-12-14 5:41

>>56
char magic[2];
.magic = "BM",
.magic = {'B', 'M', '\0'},

What?

Name: Anonymous 2011-12-14 7:09

>>57
You are a moron.

Name: Anonymous 2011-12-14 8:57

>>58
Sorry, I don't know why but I think it's wrong.

Name: Anonymous 2011-12-14 9:33

>>57
Please optimize your quotes in the future, your post is full of whitespace bloat. That might be cool if you're Guido but it doesn't fly here.

Thank you for your cooperation.

Name: Anonymous 2011-12-14 9:40

>>57
Have you read your C99 section 6.7.8 point 14 and example 8 today?

Name: Anonymous 2011-12-14 11:36

>>55
array_stack: 9.260464 seconds
linked_stack: 17.577262 seconds

Stay mad linkedfags.

Name: Anonymous 2011-12-14 11:43

>>61
Speaking of which, is char t[3] = "abcd"; legal and defined?

Name: Anonymous 2011-12-14 13:00

>>63
According to 6.7.8 paragraph 2, no.

Name: F r o z e n V o i d ® 2011-12-14 21:32

>>60 OPTIMIZED
struct Bitmap { char magic[2]; /* ... */ }; bitmap = (struct Bitmap){ .magic = "BM", /* does this equal .magic = {'B','M','\0'},? */ /* ... */ };

Name: Anonymous 2011-12-14 22:25

>>62
Why didn't you just allocate 100000000 elements for the array from the start?

Name: Anonymous 2011-12-14 22:39

I just came by to see what our /prog/ looked like out of curiosity. It's nice to see even our text boards can't escape from hilariously bad tripfags.

Name: Anonymous 2011-12-14 23:39

>>64
No initializer shall attempt to provide a value for an object not contained within the entity being initialized.
The language here is awful. "contained"? Really?

Name: Anonymous 2011-12-14 23:50

>>65
FV: making readable code since never

Name: Anonymous 2011-12-15 1:24

>>66
Because the total number of elements is unknown, and it would make the proponents of linked data structures even more mad if the array stack got even faster.

But yes, that's possible.

Name: Anonymous 2012-03-23 0:00

Bump,  linkedlists are shit

Name: Anonymous 2012-03-23 0:04

>>71
timestamp quads holy shit you're a pro

Name: Anonymous 2012-03-23 1:05

My little Ｆｒｏｚｅｎ　Ｖｏｉｄ can't be this cute!
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -