Name: Anonymous 2011-07-08 16:18
Well, this is my first time posting in the text board, so...
I asked in /g/ already and I have some questions. My problem is as follows.
I'm building a tree structure in C. Each level has an array of pointers that point to the following node. The amount of pointers depends on the level too, so a lower level node will have less pointers than the father. An insertion in this structure has a O(lg lg n) complexity. However, building the node is using O(u) for u child nodes. And at times I need to build the node in the middle of the insertion function. This is slowing significantly the run time and adding a complexity time the function shouldn't have.
I was thinking of using a char variable initially set to zero, and if the amount of pointers to be allocated exceeds 8 I can resize the char variable with realloc. A zero in the i-th bit means the i-th node is not pointing to a node. I don't know how much time will this take and I don't know if it'll be too costly to search for a specific byte.
Then there's this function, memset. It seems awesome and all but I don't know how much time it takes.
I need this node building function to take O(1) or a really reasonable time so it doesn't make the whole function slower than it should be.
Wat do?
I asked in /g/ already and I have some questions. My problem is as follows.
I'm building a tree structure in C. Each level has an array of pointers that point to the following node. The amount of pointers depends on the level too, so a lower level node will have less pointers than the father. An insertion in this structure has a O(lg lg n) complexity. However, building the node is using O(u) for u child nodes. And at times I need to build the node in the middle of the insertion function. This is slowing significantly the run time and adding a complexity time the function shouldn't have.
I was thinking of using a char variable initially set to zero, and if the amount of pointers to be allocated exceeds 8 I can resize the char variable with realloc. A zero in the i-th bit means the i-th node is not pointing to a node. I don't know how much time will this take and I don't know if it'll be too costly to search for a specific byte.
Then there's this function, memset. It seems awesome and all but I don't know how much time it takes.
I need this node building function to take O(1) or a really reasonable time so it doesn't make the whole function slower than it should be.
Wat do?