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

Sparse Arrays

Name: Anonymous 2011-12-23 0:08

Alright /proglodites/, let's hear how all of you implement a sparse arrays that stores two-dimensional data.

Name: Anonymous 2011-12-23 23:13

struct sparsearray {
     long x;
     struct sparsearray *next;
     struct sparsepoint *points;
}

struct sparsepoint {
     long y;
     struct sparsepoint *next;
     void *data;
}
I would have the nodes sorted in ascending order and then traverse the linked list until the coordinates are greater than or equal to the desired value.

Name: Anonymous 2011-12-23 23:25

I made an array of my sexual encounters...

It was sparse

Name: Anonymous 2011-12-24 0:26

>>12
This is a pretty good answer. Most places give some sort of list as an answer, but as I said before, linear lookups.

Name: Anonymous 2011-12-24 1:40

Create a virtual address mapping (using mmap and the like) and then treat the memory like a contiguous two-dimensional array. If there's a page fault (or the SIGSEGV or other signal/exception that it corresponds to), catch it, and map in new memory at those addresses.

Name: Anonymous 2011-12-24 1:47

>>15

If you want faster look ups, you could define the matrix to be a hasmap, where keys are the i,j coordinates of the entry in the matrix, and the values are numbers, or whatever it is that resides in your matrix. You can get a perfect hash function with h(i,j) = i*width + j.

>>13-san's implementation is likely the best.

Name: Anonymous 2011-12-24 3:55


#include "void.h"
typedef struct sparsearray {
  u2 n;
  u2 size;
  u2 *nn;
  void **array;
}fagarray;

fagarray *new_faga(u2 n) {
  fagarray *f = malloc(sizeof(faga));
  f->n = n;
  f->size = 0;
  f->nn = calloc(0,sizeof(int)*n);
  f->array = calloc(NULL,sizeof(void *));
  return f;
}

void addnode(fagarray *f,u2 n,u2 c){
  f->nn[size] = n;
  f->array[size] = malloc(sizeof(n*c));
  size++;
}

void remnode(fagarray *f,u1 f){
  if(f) for i to f->n forb
          free(f->array[size][i]);
        fore
  free(f->array[size]);
  f->nn[size] = 0;
  size--;
}



amidoinitrite?

Name: Anonymous 2011-12-24 5:57

>>18
U2

Name: Anonymous 2011-12-24 6:46

Everything but a map from index to pairs is retarded.

Name: sage 2011-12-24 9:51

This is the first thing they teach when you learn about graphs.

Sparse graph -> Adjacency list
Dense graph -> Adjacency matrix

It is not rocket science.

Name: Anonymous 2011-12-24 9:53

Judy arrays.

Name: Anonymous 2011-12-24 9:55

Sorry but I'm a Javascript coder, could you please explain? I don't understand the question.

Name: Anonymous 2011-12-24 13:47

>>21
That's acceptable for most graphs; however, you can do better if you need a large two-dimensional grid with fast lookups. Lists will only get you linear searches.

Name: Anonymous 2011-12-24 13:53

>>19
I was trying to be like frozen void.

maybe i should have used more macros

Name: Anonymous 2011-12-24 13:57

Radix trees are a good way to do this.

Assuming you want each cell in the grid to be indexable by two integers denoting the x and y positions, you can concatenate the bitstrings of the x and y locations and use that as the lookup key in a big radix tree. Each node in the radix tree holds an array of 2n pointers, where n is the number of bits to use as a lookup at each node. Anytime you come across a null pointer, you return the default value. This would allow dynamic use of memory and logarithmic lookups as opposed to linear ones.

Name: Anonymous 2011-12-24 13:58

>>26
Sorry, radix trie.

Name: Anonymous 2011-12-24 14:07

>>25
You should start with less indentation and one letter (and possibly a number) variable names.

Name: Anonymous 2011-12-24 15:46

def (SparseMatrix = Hash.dup).new(h); h.default = 0; h; end

# example:
sm = SparseMatrix.new( [1, 2] => 4.14, [-1, 0] => 6.23 )
p sm[[1, 2]], sm[[3, 5]]

Name: Anonymous 2011-12-25 0:56

>>3

What? There's only about 12~24 bytes overhead for each vector when compared to a standard array. Not really a need to buy new RAM.

Name: Anonymous 2011-12-25 1:55

>>30

ey was probably referring to the cost of storing all dem zeros in the sparse matrix.

Name: Anonymous 2011-12-25 4:20

>>30
You're retarded.

Name: Anonymous 2011-12-25 4:22

The whole point of sparse vectors is to save space and speed up lookups to non-zero elements, iterators should be implemented as generators.

Name: Anonymous 2011-12-25 5:09

MEIN ANDERES CAR IST EIN CDR

Name: Anonymous 2011-12-25 9:54

>>25
And NO [code] tags.

Name: Anonymous 2011-12-25 12:31

>>29
FLOW AS SUCK

Name: Anonymous 2011-12-25 20:11

A balanced binary tree of ranges, each containing slots for the range. The interface for this is super trivial in C, but an ENTERPRISE QUALITY mess of awful horseshit in Java.

Name: Anonymous 2011-12-25 20:54

>>37

nested classes in java can help.
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 -