|
|
 |
|
|
Thread Tools | Display Modes |
Feb 6th, 2008, 5:03 PM
|
#1 |
|
Programming Guru
 
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 1,885
Rep Power: 5
  |
S&K Trees, Differences In Code And Speed
The problem statement where the solution comes from is not exactly important. But if you want to see where the code is coming from, here is the question:
http://cemc.math.uwaterloo.ca/ccc/2004/stage2/sk/sk.pdf I found a solution online that is very, very fast. C Syntax (Toggle Plain Text)
It takes a few milleseconds for the following input file: (((S((S((SK)K))(K(S((S(KS))K)))))(K(K((SK)K))))((((S((S((S(KS))K))(K((S((SK)K))((SK)K)))))((S((S(KS))K))(K((S((SK)K))((SK)K)))))((S(K(S((S((S((S((SK)K))(K(K(K((SK)K))))))(KK)))(K((S((S(KS))K))(K((SK)K))))))))((S(K(S((S(KS))K))))((S((S(KS))K))(K((S(K(S(K(S(K((S((SK)K))(K(K((SK)K))))))))))((S((S(KS))((S(K(S(KS))))((S(K(S(KK))))((S((S(KS))K))(K((S((S(KS))((S(K(S(K((S((S(KS))((S(KK))((S(KS))((S(K(S((SK)K))))K)))))(KK))))))((S((S(KS))K))(K((S((SK)K))(KK)))))))(K((S((SK)K))(KK))))))))))(K(K((S((S((S(KS))((S(KK))((S(KS))((S(K(S((SK)K))))K)))))(KK)))((SK)K)))))))))))((S((S(KS))K))((S((S(KS))K))((S((S(KS))K))(K((SK)K))))))) My solution was very similar: C Syntax (Toggle Plain Text)
However, there's one huge difference. Mine takes 30 seconds to arrive at the same answer, where his takes 0.01 seconds. What in the world is going on here? I can't wrap my head around the magic behind the "node" function in the first code. That is where the speed increase is occuring. It somehow limits the number of times it calls malloc. I set a counter to keep track of how many times malloc is called in their code: 65079. In my code, I call malloc 20525615 times. But, now for the weird part: Our functions "eval" are called the same number of times in both versions: 217237 times. The node function is the only difference between memory allocation. And the node function (which calls malloc) is used more often in his eval (5 times) than in my eval (1 time). According to that, his function is calling malloc more than mine. It doesn't make any sense. It must be his incref, decref, and assign, that effectively reduce the number of calls to malloc. It somehow makes it so he does not need to call "clonetree" as I have done. I have a feeling that's where my large number of mallocs come from. But I don't see how or why his approach works. Question: Could anyone explain to me how incref, decref, and assign all work, in context of the tree? |
|
|
|
Feb 6th, 2008, 11:48 PM
|
#2 |
|
Programming Guru
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 1,885
Rep Power: 5
|
Re: S&K Trees, Differences In Code And Speed
Update: So I set a counter on the clonetree function, and it turns out it accounts for 20521777 / 20525615 of the mallocs. In other words, it's taking up 99.98% of the run time. Therefore, the call to clonetree (in my eval) is the key difference between our two algorithms.
But if I address the memory, instead of copying it with clonetree, it does not work. It must be copied. But for some reason, the first implementation's use of incref and decref creates a way around needing to copy it. Can anyone decipher that code and figure out why he does not need to recursively copy the subtree? I know this must be a hassle for anyone to commit time to look at it closely. So I greatly appreciate anyone's attempts to help me understand this. It's been bugging me for a while now. |
|
|
|
|
Feb 7th, 2008, 12:53 AM
|
#3 |
|
Expert Programmer
Join Date: Jun 2005
Posts: 852
Rep Power: 4
|
Re: S&K Trees, Differences In Code And Speed
Because the subtrees are never modified directly (i.e. they are only used to create new subtrees, or they are 'decref'ed - their l and r nodes are never modified), it is safe to have two subtrees pointing to the same memory. The tricky part is that obviously you can't free something that is still in use. That is where the reference counting comes in. Whenever a node is moved from one location to another, the old location is decref'ed and the new location is incref'ed.
Note also that this implementation will return true for isLeaf(NULL), since NULL < 3 - it took me a while to spot that. That prevents NULL pointers from being increfed or decrefed. You could try this with your implementation - just change clonenode to just return the original value and remove the free call from freetree. Sure it will leak memory like a sieve, but you should end up with comparable speed, assuming 64000 allocations with no frees don't muck up your runtime. |
|
|
|
|
Feb 7th, 2008, 3:44 PM
|
#4 |
|
Programming Guru
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 1,885
Rep Power: 5
|
Re: S&K Trees, Differences In Code And Speed
Thanks for your reply. I tried your suggestion in the three following ways. None of them worked. They all blink, and then produce a 0kb output file.
Commented Clonetree and Freetree: #include <stdio.h>
#include <stdlib.h>
#include <string.h>
int debug = 0;
typedef struct self_node {
struct self_node *l;
struct self_node *r;
} t_node;
t_node t_s = { NULL };
t_node t_k = { NULL };
t_node *new_node(t_node *l, t_node *r) {
//debug++;
t_node (* node) = (t_node *)malloc(sizeof(t_node));
node->l = l;
node->r = r;
return node;
}
t_node *parse(char **s) {
t_node *node;
if (**s == '(') {
(*s)++;
node = parse(s);
node = new_node(node, parse(s));
}
else if (**s == 'S') node = &t_s;
else if (**s == 'K') node = &t_k;
(*s)++;
return node;
}
void print(t_node *node) {
if(!node)return;
if(node == &t_s) {
printf("S");
return;
}
if(node == &t_k) {
printf("K");
return;
}
printf("(");
print(node->l);
print(node->r);
printf(")");
}
int isleaf(t_node *node) {
return (node == &t_s) || (node == &t_k);
}
void freetree(t_node *node) {
//if (!node || isleaf(node)) return;
//freetree(node->l);
//freetree(node->r);
//free(node);
}
t_node *clonetree(t_node *node){
//if (!node || isleaf(node)) return node;
//debug++;
//return new_node(clonetree(node->l), clonetree(node->r));
return node;
}
t_node *eval(t_node *node) {
//debug++;
// Base Case
if(!node || isleaf(node)) return NULL;
t_node *temp;
// Rule 1
if(node->l &&
node->l->l == &t_k) {
temp = node->l->r;
freetree(node->r);
free(node->l);
node = temp;
return node;
}
// Rule 2
if(node->l &&
node->l->l &&
node->l->l->l == &t_s) {
temp = node->l->l->r;
free(node->l->l);
node->l->l = temp;
temp = node->l->r;
node->l->r = node->r;
node->r = new_node(temp, clonetree(node->l->r));
return node;
}
// Rule 3
temp = eval(node->l);
if(temp) {
node->l = temp;
return node;
}
// Rule 4
temp = eval(node->r);
if(temp) {
node->r = temp;
return node;
}
// Rule 5
return NULL;
}
int main() {
char buff[1024*64];
char *c;
t_node *tree = NULL;
t_node *temp;
freopen("d1_3.in", "rt", stdin);
freopen("d1_3.out", "wt", stdout);
gets(buff);
while(strlen(buff)) {
c = buff;
tree = parse(&c);
while (1) {
//print(tree);
//printf("\n");
temp = eval(tree);
if (temp == NULL) break;
tree = temp;
}
print(tree);
printf("\n\n%d\n", debug);
freetree(tree);
gets(buff);
}
return 0;
}Commented All Additional Frees: #include <stdio.h>
#include <stdlib.h>
#include <string.h>
int debug = 0;
typedef struct self_node {
struct self_node *l;
struct self_node *r;
} t_node;
t_node t_s = { NULL };
t_node t_k = { NULL };
t_node *new_node(t_node *l, t_node *r) {
//debug++;
t_node (* node) = (t_node *)malloc(sizeof(t_node));
node->l = l;
node->r = r;
return node;
}
t_node *parse(char **s) {
t_node *node;
if (**s == '(') {
(*s)++;
node = parse(s);
node = new_node(node, parse(s));
}
else if (**s == 'S') node = &t_s;
else if (**s == 'K') node = &t_k;
(*s)++;
return node;
}
void print(t_node *node) {
if(!node)return;
if(node == &t_s) {
printf("S");
return;
}
if(node == &t_k) {
printf("K");
return;
}
printf("(");
print(node->l);
print(node->r);
printf(")");
}
int isleaf(t_node *node) {
return (node == &t_s) || (node == &t_k);
}
void freetree(t_node *node) {
//if (!node || isleaf(node)) return;
//freetree(node->l);
//freetree(node->r);
//free(node);
}
t_node *clonetree(t_node *node){
//if (!node || isleaf(node)) return node;
//debug++;
//return new_node(clonetree(node->l), clonetree(node->r));
return node;
}
t_node *eval(t_node *node) {
//debug++;
// Base Case
if(!node || isleaf(node)) return NULL;
t_node *temp;
// Rule 1
if(node->l &&
node->l->l == &t_k) {
temp = node->l->r;
freetree(node->r);
//free(node->l);
node = temp;
return node;
}
// Rule 2
if(node->l &&
node->l->l &&
node->l->l->l == &t_s) {
temp = node->l->l->r;
//free(node->l->l);
node->l->l = temp;
temp = node->l->r;
node->l->r = node->r;
node->r = new_node(temp, clonetree(node->l->r));
return node;
}
// Rule 3
temp = eval(node->l);
if(temp) {
node->l = temp;
return node;
}
// Rule 4
temp = eval(node->r);
if(temp) {
node->r = temp;
return node;
}
// Rule 5
return NULL;
}
int main() {
char buff[1024*64];
char *c;
t_node *tree = NULL;
t_node *temp;
freopen("d1_3.in", "rt", stdin);
freopen("d1_3.out", "wt", stdout);
gets(buff);
while(strlen(buff)) {
c = buff;
tree = parse(&c);
while (1) {
//print(tree);
//printf("\n");
temp = eval(tree);
if (temp == NULL) break;
tree = temp;
}
print(tree);
printf("\n\n%d\n", debug);
freetree(tree);
gets(buff);
}
return 0;
}Always Make A New Node Instead Of Modifying Any Subtrees (Just Like The Very Fast Method): #include <stdio.h>
#include <stdlib.h>
#include <string.h>
int debug = 0;
typedef struct self_node {
struct self_node *l;
struct self_node *r;
} t_node;
t_node t_s = { NULL };
t_node t_k = { NULL };
t_node *new_node(t_node *l, t_node *r) {
//debug++;
t_node (* node) = (t_node *)malloc(sizeof(t_node));
node->l = l;
node->r = r;
return node;
}
t_node *parse(char **s) {
t_node *node;
if (**s == '(') {
(*s)++;
node = parse(s);
node = new_node(node, parse(s));
}
else if (**s == 'S') node = &t_s;
else if (**s == 'K') node = &t_k;
(*s)++;
return node;
}
void print(t_node *node) {
if(!node)return;
if(node == &t_s) {
printf("S");
return;
}
if(node == &t_k) {
printf("K");
return;
}
printf("(");
print(node->l);
print(node->r);
printf(")");
}
int isleaf(t_node *node) {
return (node == &t_s) || (node == &t_k);
}
void freetree(t_node *node) {
if (!node || isleaf(node)) return;
freetree(node->l);
freetree(node->r);
free(node);
}
t_node *clonetree(t_node *node){
if (!node || isleaf(node)) return node;
return new_node(clonetree(node->l), clonetree(node->r));
}
t_node *eval(t_node *node) {
//debug++;
// Base Case
if(!node || isleaf(node)) return NULL;
t_node *temp;
// Rule 1
if(node->l &&
node->l->l == &t_k) {
return node->l->r;
}
// Rule 2
if(node->l &&
node->l->l &&
node->l->l->l == &t_s) {
return new_node(new_node(node->l->l->r, node->r), new_node(node->l->r, node->r));
}
// Rule 3
temp = eval(node->l);
if(temp) {
return new_node(temp, node->r);
}
// Rule 4
temp = eval(node->r);
if(temp) {
return new_node(node->l, temp);
}
// Rule 5
return NULL;
}
int main() {
char buff[1024*64];
char *c;
t_node *tree = NULL;
t_node *temp;
freopen("d1_3.in", "rt", stdin);
freopen("d1_3.out", "wt", stdout);
gets(buff);
while(strlen(buff)) {
c = buff;
tree = parse(&c);
while (1) {
//print(tree);
//printf("\n");
temp = eval(tree);
if (temp == NULL) break;
tree = temp;
}
print(tree);
//printf("\n\n%d\n", debug);
freetree(tree);
gets(buff);
}
return 0;
}Last edited by Sane; Feb 7th, 2008 at 4:14 PM. |
|
|
|
|
Feb 7th, 2008, 4:33 PM
|
#5 |
|
Programming Guru
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 1,885
Rep Power: 5
|
Re: S&K Trees, Differences In Code And Speed
Damn the stupid time limit on the editing! No one's even read my last post, and it's exactly 30 minutes since I posted it. I should be able to simply edit my posts.
So it turns out the last method does work. It just leaks so much memory that it fails around the 6000th iteration or so. I understand now what you meant about the subtrees not being modified. We are allowed to reference the same subtree, in rule 2, instead of cloning it, if we never modify any subtrees. Since now any time we reach a node, we create new nodes. This, in a sense, clones the subtree. Now I just need to understand incref and decref. I think I get it: Does rc keep track of how many parents a node has? If it ever has zero parents, we can erase it. And if we assign the node to another parent, rc increases? If that's not the case, I'm a lost fool. That seems close, but not quite right. I will try my idea, and hopefully it will end up matching his code. Let's see how this goes. Last edited by Sane; Feb 7th, 2008 at 4:47 PM. |
|
|
|
|
Feb 7th, 2008, 6:39 PM
|
#6 |
|
Expert Programmer
Join Date: Jun 2005
Posts: 852
Rep Power: 4
|
Re: S&K Trees, Differences In Code And Speed
Thats right - in this case it is how many parents the node has, in the more general case, it is how many times the node is referenced. When the count falls down to zero, then nothing is referencing the node any more, so it can be freed.
Yes, the rules 3 and 4 changing the node would have mucked up the multiple referencer mechanism. Note: I can't get either of the original two programs to finish with the example SK string. I have been running the reference counting one now for 13 minutes and it is still going. Could you check that the string is the one you are using? |
|
|
|
|
Feb 7th, 2008, 6:51 PM
|
#7 |
|
Programming Guru
Join Date: Apr 2005
Location: Waterloo, Ontario
Posts: 1,885
Rep Power: 5
|
Re: S&K Trees, Differences In Code And Speed
You need to append a couple trailing newlines to the end of the data file. It only stops when it finds a blank line (part of the input specifications).
Edit: Do you have any reading material, or information I can look up online, that provides a detailed look at reference counting in trees? I can't find any good resources. I'd like a more general overview, including where it helps, when to use it, and why it works. With the small change, my code now runs in a few milleseconds, but I don't quite understand it all. For instance, I have to reference count the root node when I parse it. Why? I feel like there's something I don't quite get, and diagrams of the tree and reference counts, in a textbook format, might help immensely. Thanks for all your help too. Truly appreciate it.  Last edited by Sane; Feb 7th, 2008 at 7:09 PM. |
|
|
|
|
| Bookmarks |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
| Thread Tools | |
| Display Modes | |
|
|
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| I need speed increase | FireflyX | JavaScript and Client-Side Browser Scripting | 5 | Dec 22nd, 2007 9:55 AM |
| Pacman in Python Code | acwbrat | Python | 3 | Nov 18th, 2007 12:01 PM |
| Some Nifty Code | Sane | Python | 2 | May 10th, 2005 5:56 AM |
Linear Mode
