Ce qui peut être à l'origine de ce comportement dans Optimisation du programme "Nombre d'îlots" avec l'approche récursive DFS

Question

J'ai un problème pour optimiser le programme "nombre d'îlots" que j'ai téléchargé depuis le Web. J'ai essayé d'optimiser comme expliqué ci-dessous, mais je ne pouvais pas obtenir 100% raison.

qu'est ce que le Nombre d'îles?

http://www.geeksforgeeks.org/find-number-of-islands/

Je pris le programme ci-dessous « c » de l'un des sites pour déterminer nombre d'îles dans un graphique donné.

void DFS(int M[][COL], int row, int col, bool visited[][COL]) 
{ 
    // These arrays are used to get row and column numbers of 8 neighbours 
    // of a given cell 
    static int rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1}; 
    static int colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1}; 

    int k = 0; 
    // Mark this cell as visited 
    visited[row][col] = true; 
    printf("\n row=%d, col=%d", row, col); 

    // Recur for all connected neighbours 
    for (k = 0; k < 8; ++k) { 
     printf(" k=%d", k); 
     if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)) 
      DFS(M, row + rowNbr[k], col + colNbr[k], visited); 
    } 
} 

// The main function that returns count of islands in a given boolean 
// 2D matrix 
int countIslands(int M[][COL]) 
{ 
    // Make a bool array to mark visited cells. 
    // Initially all cells are unvisited 
    bool visited[ROW][COL]; 
    memset(visited, 0, sizeof(visited)); 

    // Initialize count as 0 and travese through the all cells of 
    // given matrix 
    int count = 0; 
    int i = 0, j=0; 
    for (i = 0; i < ROW; ++i) { 
     for (j = 0; j < COL; ++j) { 
      if (M[i][j] && !visited[i][j]) // If a cell with value 1 is not 
      {       // visited yet, then new island found 
       DFS(M, i, j, visited);  // Visit all cells in this island. 
       ++count;     // and increment island count 
       printf("\n count is %d", count); 
      } 
     } 
     printf("\n"); 
    } 

    return count; 
} 


// A function to check if a given cell (row, col) can be included in DFS 
int isSafe(int M[][COL], int row, int col, bool visited[][COL]) 
{ 
    // row number is in range, column number is in range and value is 1 
    // and not yet visited 
    printf(" (i=%d, j=%d)", row, col); 
    return (row >= 0) && (row < ROW) &&  
     (col >= 0) && (col < COL) &&  
     (M[row][col] && !visited[row][col]); 
} 

comme ayant deux pour les boucles de la taille totale de la matrice n'est pas la meilleure façon de traiter ce problème, j'ai essayé d'optimiser comme ci-dessous.

En plus de me souvenir du nœud que j'ai visité, j'ai également manipulé les index "i" et "j" pour optimiser et ignorer la vérification du drapeau is_visited. J'espère que mon explication est claire. Code ci-dessous.

// A utility function to do DFS for a 2D boolean matrix. It only considers 
// the 8 neighbours as adjacent vertices 
void DFS_new(int M[][COL], int *row, int *col, bool visited[][COL]) 
{ 
    // These arrays are used to get row and column numbers of 8 neighbours 
    // of a given cell 
    int k; 
    static int rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1}; 
    static int colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1}; 

    // Mark this cell as visited 
    visited[*row][*col] = true; 
    printf("\n row=%d, col=%d", *row, *col); 
    // Recur for all connected neighbours 
    for (k = 0; k < 8; ++k) 
    { 
     printf(" k=%d", k); 
     if (isSafe(M, (*row) + rowNbr[k], (*col) + colNbr[k], visited)) 
     { 
      (*row) = (*row)+rowNbr[k]; 
      (*col) = (*col)+colNbr[k]; 
      DFS_new(M, row, col, visited); 
     } 
    } 
} 

// The main function that returns count of islands in a given boolean 
// 2D matrix 
int countIslands_new(int M[][COL]) 
{ 
    // Make a bool array to mark visited cells. 
    // Initially all cells are unvisited 
    bool visited[ROW][COL]; 
    memset(visited, 0, sizeof(visited)); 

    // Initialize count as 0 and travese through the all cells of 
    // given matrix 
    int count = 0; 
    int i = 0, j = 0; 
    while (i < ROW) 
    { 
     j = 0; 
     while (j < COL) 
     { 
      if (M[i][j] && !visited[i][j]) 
      {        
       DFS_new(M, &i, &j, visited); 
       count++;      
       printf("\n count is %d", count); 
      } 
      j++; 
     } 
     i++; 
    } 
    return count; 
} 

Venons-en maintenant au problème, si j'utilise l'entrée ci-dessous pour tester les deux programmes ci-dessus, mon code donne une sortie mal. Il indique le nombre d'îles sont 4, où en réalité il n'y a que 3 îles. Le programme d'origine fonctionne bien cependant.

// Driver program to test above function 
int main() 
{ 
    int M[][COL]= { {1, 1, 0, 0, 0}, 
      {0, 1, 0, 1, 0}, 
      {0, 0, 0, 0, 0}, 
      {0, 1, 0, 1, 0}, 
      {1, 0, 1, 0, 1} 
      }; 

    printf("Number of islands is: %d\n", countIslands(M)); 

    return 0; 
} 

Une chose particulière que j'ai observée pour laquelle je ne pouvais pas construire la logique est la suivante.

Dans mon programme, je vois que l'extrait de code ci-dessous de mon programme dans la fonction DFS_new est exécuté plus de 8 fois sans que cette fonction soit appelée à nouveau (je veux dire sans appeler la fonction récursive).

for (k = 0; k < 8; ++k) 
{ 
    printf(" k=%d", k); 
} 

sortie du printf ci-dessous:

row=4, col=0 k=0 (i=3, j=-1) k=1 (i=3, j=0) k=2 (i=3, j=1) k=3 (i=4, j=-1) 
k=4 (i=4, j=1) k=5 (i=5, j=-1) **k=6** (i=5, j=0) **k=7** (i=5, j=1) 
**k=6** (i=4, j=1) **k=7** (i=4, j=2) 

espoir cette question est logique à ce forum et attend une réponse positive.

Answer 1

Grande anti-optimisation.

Les pointeurs de déréférencement sont réellement plus lents que l'appel par valeur pour les types entiers.

Compilateurs savent comment et déroulez vectoriser une boucle de la forme for(int i = 0; i < k; ++i) {...} si i est seulement lu et jamais passée par référence dans la boucle.

Ils ont des problèmes avec les boucles de la forme while(i < k) {...; i++; ...}, en particulier si i est passé en tant que référence non const à une autre fonction.

---

Quant à savoir où votre erreur est:

 (*row) = (*row)+rowNbr[k]; 
     (*col) = (*col)+colNbr[k]; 

Vous modifiez les entiers réels dans chaque itération de la boucle, et le décalage pour les voisins est maintenant cumulée au lieu d'être échantillonné un après l'autre.En d'autres termes, vous ne vérifiez plus un carré.

---

Une optimisation EFFECTIVE avait été de faire le décalage static tables pleines const au lieu (champ de const int) et de supprimer tous les résultats de débogage.

Utilisez une matrice aplatie (bool M[ROW][COL]) au lieu d'une matrice de matrices (bool M[][COL]).

Soyez correct à propos de const sur les paramètres.

Utilisez le mot-clé static sur les fonctions que vous ne prévoyez pas d'exporter vers une autre unité de compilation.

Cela permet au compilateur de faire l'optimisation, et il fait beaucoup mieux que vous pouvez:

#include <cstring> 

const int COL = 8; 
const int ROW = 8; 

// A function to check if a given cell (row, col) can be included in DFS 
static int isSafe(const bool M[ROW][COL], const int row, const int col, const bool visited[ROW][COL]) 
{ 
    // row number is in range, column number is in range and value is 1 
    // and not yet visited 
    return (row >= 0) && (row < ROW) &&  
     (col >= 0) && (col < COL) &&  
     (M[row][col] && !visited[row][col]); 
} 

static void DFS(const bool M[ROW][COL], const int row, const int col, bool visited[ROW][COL]) 
{ 
    // These arrays are used to get row and column numbers of 8 neighbours 
    // of a given cell 
    const int rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1}; 
    const int colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1}; 

    int k = 0; 
    // Mark this cell as visited 
    visited[row][col] = true; 

    // Recur for all connected neighbours 
    for (k = 0; k < 8; ++k) { 
     if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)) 
      DFS(M, row + rowNbr[k], col + colNbr[k], visited); 
    } 
} 

// The main function that returns count of islands in a given boolean 
// 2D matrix 
int countIslands(const bool M[ROW][COL]) 
{ 
    // Make a bool array to mark visited cells. 
    // Initially all cells are unvisited 
    bool visited[ROW][COL]; 
    memset(visited, 0, sizeof(visited)); 

    // Initialize count as 0 and travese through the all cells of 
    // given matrix 
    int count = 0; 
    int i = 0, j=0; 
    for (i = 0; i < ROW; ++i) { 
     for (j = 0; j < COL; ++j) { 
      if (M[i][j] && !visited[i][j]) // If a cell with value 1 is not 
      {       // visited yet, then new island found 
       DFS(M, i, j, visited);  // Visit all cells in this island. 
       ++count;     // and increment island count 
      } 
     } 
    } 

    return count; 
} 

compiler le code « optimisé » par exemple avec un récent CLANG 5.0 et -O3, et toutes les boucles sont parties dans l'assemblage. Entièrement remplacé par du code déroulé ou même simplement des instructions vectorielles simples: https://godbolt.org/g/SwxSn3