Segmentation Fault

**Mercury_Linx** · 04-23-2003

Hm... I had a program that need to recurs pretty deep before. I realise that going too deep will cause a stack overflow (duh)

So... what I did is to segment out the data chunck, and run the recursion to work with small chunck of data each time.

For example, I have a array of 5000 element, instead of letting a single function to recurs and go into 5000 level deep, I devide out the recursion into 50 times, with each time it process 100 element, save up the result some where else, and continue with the remaining, in the end, the element I neeed to process is getting smaller and smaller... and at the end I get the cvalue I want.

Is is posible to implement such work areound for you?

**Lost__Soul** · 04-23-2003

i have no problem with recursion...i had one a few days ago, which was causing a stack overflow,but not now...only a infinite cycle with big files...try to read all the posts, the recursion problem has been solved long ago...

**Mercury_Linx** · 04-23-2003

Opps ;p ... Found out about that just now ... Hm... how do I remove post?

**Lost__Soul** · 04-23-2003

Anyone tried to run the debug...?Just getting a little worried...I spent one hour looking at all the sums in t6.in and saw no infinite cycle...It just closed...If the sums are different, if its working with small inputs,how can it enter an infinite cycle?!The only difference between the inputs is the size...

**Lost__Soul** · 04-23-2003

I´ve updated the code again(just small changes related to the machines where the programs are tested)...Still "the problem"...

**Lost__Soul** · 04-24-2003

why isnt anyone replying...Is anyone at least trying to run my code with t4 and t5 and try to see what´s wrong with it...?Or do i have to try elsewhere?i asked a lot of persons and the only thing they told me was "it should work...". That´s not a very nice thing to hear...

Just a few days left for the delivery of the project...And i cant find the error...

**Hammer** · 04-24-2003

I have an idea to help you debug it. Give me a bit of time, and I'll upload some stuff for you. I just gotta stop my PC from crashing all the time first (I hate XP, but that's another subject!)

**Hammer** · 04-24-2003

OK, here we go.

I amended the poe_na_fila() function to print the contents of the percurso array each time it gets called:

Code:

void poe_na_fila(int x)
{
  int i;

  percurso[coroa] = x;
  coroa++;
  for (i = 0; i < coroa; i++)
    printf ("%d ", percurso[i]);
  putchar('\n');
}

I then ran the program and directed the output to a file like so:
c:\>prog.exe t4.in >out.txt

I did this for both the t4.in file, and the short sample set of numbers in your first post on this thread. The output is in the attached zip file. For those who can't be bothered to download it, here's the output from the sample set of numbers:

Code:

This input:

7
9
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
6 7 6
1 3 4
3 5 8
5 7 12
1 7

Produced this output:
1 
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5 
1 2 3 4 5 6 
1 2 3 4 5 6 7 
1 2 3 4 5 
1 2 3 4 5 7 
1 2 3 
1 2 3 5 
1 2 3 5 6 
1 2 3 5 6 7 
1 2 3 5 
1 2 3 5 7 
1 
1 3 
1 3 4 
1 3 4 5 
1 3 4 5 6 
1 3 4 5 6 7 
1 3 4 5 
1 3 4 5 7 
1 3 
1 3 5 
1 3 5 6 
1 3 5 6 7 
1 3 5 
1 3 5 7 
24

You will notice that the output for t4.in is considerably larger, in fact the file I've provided is only a few MB, it actually went to over 100mb in amount 20-30 seconds the first time I ran it.

Unfortunately I have no answers for you, I can only suggest you review this output to see if you can see where you program is going "wrong". Also, consider these:

- maybe it is actually working, it's just so inefficient that it will take hours to work on a file the size of t4.in

- maybe a set sequence of numbers in t4.in have caused the loop. You might be able to replicate the problem with a smaller input file using the same numbers.

**Lost__Soul** · 04-24-2003

Well,thnks for trying to find the mistake.the second possible error you mentioned isnt happening,since with t5 and t6 i get the same "infinite cycle".Looking at the percurso array in each call didnt suprise me,since its suppossed to work that way.Also,looking at it in t4 shows that the paths are being correctly stored and the flows being correctly computed.The only thing i can do to see if its really that slow,is leave the program working during the night.Im saying this because i already left it working for 2 hours with t4.in and still no result.If the problem is the speed,i can talk to my teachers and say that the program is working perfectly,only the algorhitm i created is probably quite ineficient.If its not a speed problem,i really dont know what to do...

**Lost__Soul** · 04-25-2003

Ok,i guess today i have the proof that the problem inst the time the program takes to compute all the flows.I left it working during the night with t4 in.After 11 hours working still no result.I believe its impossible that the program would take so much time.For example, t4 has 44850 possible sums, and in debug it calculates at least one every second (much more of course).So the problem must be with another thing...But no one can see what...

**Lost__Soul** · 04-25-2003

I may have a clue about what going wrong.A friend of mine analized the program and said that probably memory is not enough to store all the elements of the lists. That would explain a lot of things:the debug closes at a random point because it avoids entering an infinite cycle, the program is in cycle because the leak of memory corrupts the lists...I have no idea if this is the problem with my program,there´s no way to see that with such large inputs,but its a possibilty...The alternative is write the linked lists in a temp file and read them from there....But i have no idea of how to to that...Anyone can help me?i dont want to modify all my program,just the way things are called.

**Lost__Soul** · 04-26-2003

So...No one has any idea if this might be my problem?Or any way of solving it with a temp file...?

**Lost__Soul** · 04-26-2003

Guess not...Daam, i have to delivery the project Monday and i still dont know what can i do...Someone could at least tell me if the problem is related to memory,like my friend said?too many elements in the lists?If thats the problem,is there anything i can do about it?...
Today i added a counter for the number of sums the program computes.In t4.in,after 10 seconds,it already calculated 1,5 milion different sums...Something is wrong...An since my algorhitm is ok,the problem must be with memory or something...HELP,PLEASE!

**Hammer** · 04-26-2003

Warning: Long post

Your problem lies within your algorythm. Here is why:

Assuming each node has direct access to all nodes with a higher value, the number of calculations to perform a check of 300 nodes is huge. For example, the following is a simple table of only 10 nodes:

Code:

10
45
1    2    1
1    3    1
1    4    1
1    5    1
1    6    1
1    7    1
1    8    1
1    9    1
1    10   1
2    3    1
2    4    1
2    5    1
2    6    1
2    7    1
2    8    1
2    9    1
2    10   1
3    4    1
3    5    1
3    6    1
3    7    1
3    8    1
3    9    1
3    10   1
4    5    1
4    6    1
4    7    1
4    8    1
4    9    1
4    10   1
5    6    1
5    7    1
5    8    1
5    9    1
5    10   1
6    7    1
6    8    1
6    9    1
6    10   1
7    8    1
7    9    1
7    10   1
8    9    1
8    10   1
9    10   1
1    10

For the purpose of the discussion, I have set all "peso" values (third number of each data line) to 1, as the point is to discuss the number of calculations required to traverse every route. Using your program, I simply added a counter in it to see how many complete paths it found. I did this by having a counter called CountOfPaths, and incremented its value every time "if (source == sink)" became true. For the above input (10 nodes), it told me there were 256 paths available. To prove it was doing its job correctly, I also made your program print out the paths as it found them, here's was it output:

Code:

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 10
1 2 3 4 5 6 7 9 10
1 2 3 4 5 6 7 10
1 2 3 4 5 6 8 9 10
1 2 3 4 5 6 8 10
1 2 3 4 5 6 9 10
1 2 3 4 5 6 10
1 2 3 4 5 7 8 9 10
1 2 3 4 5 7 8 10
1 2 3 4 5 7 9 10
1 2 3 4 5 7 10
1 2 3 4 5 8 9 10
1 2 3 4 5 8 10
1 2 3 4 5 9 10
1 2 3 4 5 10
1 2 3 4 6 7 8 9 10
1 2 3 4 6 7 8 10
1 2 3 4 6 7 9 10
1 2 3 4 6 7 10
1 2 3 4 6 8 9 10
1 2 3 4 6 8 10
1 2 3 4 6 9 10
1 2 3 4 6 10
1 2 3 4 7 8 9 10
1 2 3 4 7 8 10
1 2 3 4 7 9 10
1 2 3 4 7 10
1 2 3 4 8 9 10
1 2 3 4 8 10
1 2 3 4 9 10
1 2 3 4 10
1 2 3 5 6 7 8 9 10
1 2 3 5 6 7 8 10
1 2 3 5 6 7 9 10
1 2 3 5 6 7 10
1 2 3 5 6 8 9 10
1 2 3 5 6 8 10
1 2 3 5 6 9 10
1 2 3 5 6 10
1 2 3 5 7 8 9 10
1 2 3 5 7 8 10
1 2 3 5 7 9 10
1 2 3 5 7 10
1 2 3 5 8 9 10
1 2 3 5 8 10
1 2 3 5 9 10
1 2 3 5 10
1 2 3 6 7 8 9 10
1 2 3 6 7 8 10
1 2 3 6 7 9 10
1 2 3 6 7 10
1 2 3 6 8 9 10
1 2 3 6 8 10
1 2 3 6 9 10
1 2 3 6 10
1 2 3 7 8 9 10
1 2 3 7 8 10
1 2 3 7 9 10
1 2 3 7 10
1 2 3 8 9 10
1 2 3 8 10
1 2 3 9 10
1 2 3 10
1 2 4 5 6 7 8 9 10
1 2 4 5 6 7 8 10
1 2 4 5 6 7 9 10
1 2 4 5 6 7 10
1 2 4 5 6 8 9 10
1 2 4 5 6 8 10
1 2 4 5 6 9 10
1 2 4 5 6 10
1 2 4 5 7 8 9 10
1 2 4 5 7 8 10
1 2 4 5 7 9 10
1 2 4 5 7 10
1 2 4 5 8 9 10
1 2 4 5 8 10
1 2 4 5 9 10
1 2 4 5 10
1 2 4 6 7 8 9 10
1 2 4 6 7 8 10
1 2 4 6 7 9 10
1 2 4 6 7 10
1 2 4 6 8 9 10
1 2 4 6 8 10
1 2 4 6 9 10
1 2 4 6 10
1 2 4 7 8 9 10
1 2 4 7 8 10
1 2 4 7 9 10
1 2 4 7 10
1 2 4 8 9 10
1 2 4 8 10
1 2 4 9 10
1 2 4 10
1 2 5 6 7 8 9 10
1 2 5 6 7 8 10
1 2 5 6 7 9 10
1 2 5 6 7 10
1 2 5 6 8 9 10
1 2 5 6 8 10
1 2 5 6 9 10
1 2 5 6 10
1 2 5 7 8 9 10
1 2 5 7 8 10
1 2 5 7 9 10
1 2 5 7 10
1 2 5 8 9 10
1 2 5 8 10
1 2 5 9 10
1 2 5 10
1 2 6 7 8 9 10
1 2 6 7 8 10
1 2 6 7 9 10
1 2 6 7 10
1 2 6 8 9 10
1 2 6 8 10
1 2 6 9 10
1 2 6 10
1 2 7 8 9 10
1 2 7 8 10
1 2 7 9 10
1 2 7 10
1 2 8 9 10
1 2 8 10
1 2 9 10
1 2 10
1 3 4 5 6 7 8 9 10
1 3 4 5 6 7 8 10
1 3 4 5 6 7 9 10
1 3 4 5 6 7 10
1 3 4 5 6 8 9 10
1 3 4 5 6 8 10
1 3 4 5 6 9 10
1 3 4 5 6 10
1 3 4 5 7 8 9 10
1 3 4 5 7 8 10
1 3 4 5 7 9 10
1 3 4 5 7 10
1 3 4 5 8 9 10
1 3 4 5 8 10
1 3 4 5 9 10
1 3 4 5 10
1 3 4 6 7 8 9 10
1 3 4 6 7 8 10
1 3 4 6 7 9 10
1 3 4 6 7 10
1 3 4 6 8 9 10
1 3 4 6 8 10
1 3 4 6 9 10
1 3 4 6 10
1 3 4 7 8 9 10
1 3 4 7 8 10
1 3 4 7 9 10
1 3 4 7 10
1 3 4 8 9 10
1 3 4 8 10
1 3 4 9 10
1 3 4 10
1 3 5 6 7 8 9 10
1 3 5 6 7 8 10
1 3 5 6 7 9 10
1 3 5 6 7 10
1 3 5 6 8 9 10
1 3 5 6 8 10
1 3 5 6 9 10
1 3 5 6 10
1 3 5 7 8 9 10
1 3 5 7 8 10
1 3 5 7 9 10
1 3 5 7 10
1 3 5 8 9 10
1 3 5 8 10
1 3 5 9 10
1 3 5 10
1 3 6 7 8 9 10
1 3 6 7 8 10
1 3 6 7 9 10
1 3 6 7 10
1 3 6 8 9 10
1 3 6 8 10
1 3 6 9 10
1 3 6 10
1 3 7 8 9 10
1 3 7 8 10
1 3 7 9 10
1 3 7 10
1 3 8 9 10
1 3 8 10
1 3 9 10
1 3 10
1 4 5 6 7 8 9 10
1 4 5 6 7 8 10
1 4 5 6 7 9 10
1 4 5 6 7 10
1 4 5 6 8 9 10
1 4 5 6 8 10
1 4 5 6 9 10
1 4 5 6 10
1 4 5 7 8 9 10
1 4 5 7 8 10
1 4 5 7 9 10
1 4 5 7 10
1 4 5 8 9 10
1 4 5 8 10
1 4 5 9 10
1 4 5 10
1 4 6 7 8 9 10
1 4 6 7 8 10
1 4 6 7 9 10
1 4 6 7 10
1 4 6 8 9 10
1 4 6 8 10
1 4 6 9 10
1 4 6 10
1 4 7 8 9 10
1 4 7 8 10
1 4 7 9 10
1 4 7 10
1 4 8 9 10
1 4 8 10
1 4 9 10
1 4 10
1 5 6 7 8 9 10
1 5 6 7 8 10
1 5 6 7 9 10
1 5 6 7 10
1 5 6 8 9 10
1 5 6 8 10
1 5 6 9 10
1 5 6 10
1 5 7 8 9 10
1 5 7 8 10
1 5 7 9 10
1 5 7 10
1 5 8 9 10
1 5 8 10
1 5 9 10
1 5 10
1 6 7 8 9 10
1 6 7 8 10
1 6 7 9 10
1 6 7 10
1 6 8 9 10
1 6 8 10
1 6 9 10
1 6 10
1 7 8 9 10
1 7 8 10
1 7 9 10
1 7 10
1 8 9 10
1 8 10
1 9 10
1 10
256 complete paths

Now, changing the input slightly, I came up with the following figures for the number of possible routes based on the number of nodes:

Code:

Nodes   Total Routes
10      256
15      8192
20      262144
25      8388608
26      16777216
27      33554432
28      67108864
29      134217728
(do you see a pattern?)

With only 28 nodes, your program took 26 seconds to run, with 29 nodes it took 50 seconds. In short, add one node, and you double the paths, and therefore the execution time. Now, imagine the number of routes when you have 300 nodes to work through (I suggest you work that number out). That is why your program is struggling.

How to fix this? Find a better algorythm, or make this one smarter. How you do that is for you to find out... (it's your homework, afterall

).

To assist me with this work, I wrote small program to generate the input files, you might find it useful:

Code:

/*
 * This generates the input files
 */
#include <stdio.h>

#define MAX 29

int main(void)
{
  int i, j;
  
  printf ("%d\n", MAX);
  
  for (i = MAX-1, j = 0; i; i--)
    j += i;
  printf ("%d\n", j);
  
  for (i = 1; i < MAX; i++)
    for (j = i+1; j <= MAX; j++)
      printf ("%-4d %-4d 1\n", i, j);
  printf ("%-4d %-4d\n", 1, MAX);
  
  return 0;
}

One last thing, don't bump your threads on here. If and when people have answers to your questions, they will post them.

**Lost__Soul** · 04-27-2003

I see...I guess i have to search for another algorithm,since this one was created by me,i heard about something called the algorithm for the longuest paths that could be useful,dont know exactly how,because i dont want the longuest or shortest path,but i´ll give it a search.Thnks and sorry for all the threads,i was getting a little worried...

Thread: Segmentation Fault

Thread Tools

Search Thread

Display

Similar Threads

Segmentation fault problem

Segmentation fault

Segmentation fault

Locating A Segmentation Fault

Segmentation fault...