Alright /proglodites/, let's hear how all of you implement a sparse arrays that stores two-dimensional data.
Name:
Anonymous2011-12-23 0:10
I'm particularly interested in what FrhozenVoyd will say, considering I remember him saying he only ever uses arrays to store things because he doesn't know any other data structures
Name:
Anonymous2011-12-23 0:57
Like any INTEGER men I do vector<vector<BigInt>> and just buy more ram.
>>10
respect and appreciate your wonderful and elegant lua clone.
Name:
Anonymous2011-12-23 22:39
Have some kind of tree with the following data types
root node
;;majority value
;;index
;;value
data type:
;;index
;;value
When storing data to the array it is first checked against the majority value for that set, if the value is not equal to the majority value it is stored in the tree with its index number. otherwise it is discarded. Retrival works like a binary tree.
At least that's how I would do it. Keep in mind I have zero idea about how this *should* be done.
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.
>>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:
Anonymous2011-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.
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.
Everything but a map from index to pairs is retarded.
Name:
sage2011-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:
Anonymous2011-12-24 9:53
Judy arrays.
Name:
Anonymous2011-12-24 9:55
Sorry but I'm a Javascript coder, could you please explain? I don't understand the question.
Name:
Anonymous2011-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.
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.
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.