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

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-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!
Newer Posts
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 -