C++

Forum

 
Faster way?

MiquelH (2)
Hello there

For my course physical programming I need to simulate building-up of a neighbourhood. I need to simulate 100.000 houses in one minute. My code is working but way too slow. Is there a way to speed up my code? Thanks already for the response!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
#ifndef NEIGHBOUR_HDR
#define NEIGHBOUR_HDR

#include <iostream>

int n {100000};
int f = sqrt(n);

#endif

#include <iostream>
#include <valarray>
#include <cmath>
#include <random>
#include <chrono>
#include "neighbour.h"


//defining grid
class Grid{
  private:
    int nr_rows_;
    int nr_cols_;
    std::valarray<int> matrix_;
    
  public:
    Grid(const int nr_rows, const int nr_cols):
      nr_rows_{nr_rows},
      nr_cols_{nr_cols},
      matrix_(1, nr_rows*nr_cols) {}
    int& operator()(const int row, const int col){ return matrix_[nr_cols_*row+col];}
    int nr_rows() const { return nr_rows_;}
    int nr_cols() const { return nr_cols_;}
};
void predictMatrix(Grid& grid,
            int range0a,
            int range0b,
            Grid& grid2)
{
int c = 0;
int t = 1;

while (t<n){
  for (int i = 1 ; i <(2*f+1) -1 ; i++) {
    for (int j = 1 ; j <(2*f+1) -1 ; j++) {
      
      c = 0;

      // Het tellen van de buren met een 0
      if (i > 0 && grid(i + 1, j) == 0)
        c++;
      if (j > 0 && grid(i, j - 1) == 0)
        c++;
      if (i < (2*f+1) - 1 && grid(i - 1, j) == 0)
        c++;
      if (j < (2*f+1) - 1 && grid(i , j + 1) == 0)
        c++;

      //random number generator

      std::random_device rd;
      unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
      std::ranlux48 generator (seed);

      double g = generator();
      double m = generator.max();
      double p = g/m;

      // Het opstellen van de kans op een huis ivm het aantal buren

      if (t<n && grid(i,j) == 1 && c >= range0a && c <= range0b) {
        if (c==1 && p<=0.25) {grid2(i,j)=0 && t++;}

        if (c==2 && p<=0.5) {grid2(i,j)=0 && t++;}
        
        if (c==3 && p<=0.75) {grid2(i,j)=0 && t++;}
        
        if (c==4) {grid2(i,j) = 0 && t++;}

      }
      t=0;
      for (int i = 1 ; i <(2*f+1) -1 ; i++) {
        for (int j = 1 ; j <(2*f+1) -1 ; j++) {
          if (grid2(i,j)==0)
            t++;
        }
      }
    }
  }
  // De veranderingen overbrengen naar de matrix

  for (int k = 0; k < 2*f+1; k++)
    for (int m = 0; m < 2*f+1; m++)
      grid(k, m) = grid2(k,m);

  }
}

int main()
{
  Grid grid(2*f+1,2*f+1);
  // Grootte van het grid werd bepaald zodat deze in de meeste situaties groot genoeg zou zijn zonder te veel opslag in beslag te nemen
  grid (f,f)=0;

  int range0a = 1;
  int range0b = 4;
  Grid grid2(2*f+1,2*f+1);
  grid2 (f,f)=0;
  
    // Function call to calculate the resultant matrix after 'n' iterations.
  predictMatrix(grid, range0a, range0b, grid2);
  
  
     //Printing Result
  for (int i=0; i< (2*f+1); i++) {
    std::cout << std::endl;
    for (int j=0; j<(2*f+1); j++)
      std::cout << grid2(i,j) << " ";
    }
    return 0;
}
Last edited on
Ganado (6812)
What part is taking up the most time? predictMatrix, or printing it?
I assume it's predictMatrix, since that's where you have all the nested loops acting on large numbers.

1
2
3
4
5
6
7
8
9
10
11
 
      if (t<n && grid(i,j) == 1 && c >= range0a && c <= range0b) {
        if (c==1 && p<=0.25) {grid2(i,j)=0 && t++;}

        if (c==2 && p<=0.5) {grid2(i,j)=0 && t++;}
        
        if (c==3 && p<=0.75) {grid2(i,j)=0 && t++;}
        
        if (c==4) {grid2(i,j) = 0 && t++;}

      }
      t=0;

This part seems funny to me. Why are you using && here? Why are you incrementing t, just to set it back to 0?
It seems your logic is equivalent to:
1
2
3
4
5
6
7
 
      if (t<n && grid(i,j) == 1 && c >= range0a && c <= range0b) {
        if (c==1 && p<=0.25) {grid2(i,j)=0;}
        else if (c==2 && p<=0.5) {grid2(i,j)=0;}
        else if (c==3 && p<=0.75) {grid2(i,j)=0;}
        else if (c==4) {grid2(i,j) = 0;}
      }
      t=0;

Also,
1
2
3
 
    std::random_device rd;
      unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
      std::ranlux48 generator (seed);

You declare a random_device variable, but don't use it. Re-initializing the random_device each loop iteration is probably slow. Remove this.
In fact, you can take the seed and generator out of the loop, too. Declare and seed the generator once, before any loops.

idk if this will significantly affect the runtime, but it shouldn't hurt.

Line 47: you re-set c to 0 each loop. You should just declare it here instead.
int c = 0;

Overall, your function has five levels of loops. This is pretty incredible. (The most I've ever remember using is four layers of loops for very inefficient convolution.) Are you sure this is necessary? Explain what they are for.
1
2
3
4
5
6
7
8
9
10
11
12
 
while (t<n){
  for (int i = 1 ; i <(2*f+1) -1 ; i++) {
    for (int j = 1 ; j <(2*f+1) -1 ; j++) {
      // ...
      t=0;
      for (int i = 1 ; i <(2*f+1) -1 ; i++) {
        for (int j = 1 ; j <(2*f+1) -1 ; j++) {
          if (grid2(i,j)==0)
            t++;
        }
      }


'c', 't', 'p', 'grid & grid2'. What is the purpose of these variables? What do they represent? Use meaningful names.
Last edited on
jlb (4973)
You also have two for() loops using the same control variable:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
       for(int i = 1 ; i < (2 * f + 1) - 1 ; i++) {
            for(int j = 1 ; j < (2 * f + 1) - 1 ; j++) {
			
			...
  
                t = 0;
                for(int i = 1 ; i < (2 * f + 1) - 1 ; i++) {
                    for(int j = 1 ; j < (2 * f + 1) - 1 ; j++) {
                        if(grid2(i, j) == 0)
                            t++;
                    }
                }
            }
jonnin (11441)
a lot of tiny tweaks are obvious but where does the time go in the profiler is the question.

if(grid2(i, j) == 0)
t++;
is the same as
t+= grid(i,j)==0;
its often faster (check it?!) to do extra work (here, adding zero) than to try to bypass it. Add is fast. conditional jumps, even with prediction (which has a lot of limits) isn't always so fast.

line 71 is a mess. you have 4 conditions that do exactly the same thing and it can be greatly simplified via a switch or something.

not 100% sure but did you seed and create a random device in the middle of a while loop? Those take a moment to construct, just make 1 of them -- factoring that out will do wonders I believe
Last edited on
MiquelH (2)
Thanks for the replies! your tips made the code a little faster. I have also changed the names of 'c','t' and the two grids, so that they have meaningfull names.

Thank you all!
Topic archived. No new replies allowed.