遞歸優化

Question

我目前正在研究算法，並且在某些時候我必須通過一個圖像並對具有相同屬性的像素進行分組。我從最左上角的像素開始，使用遞歸：從輸入像素中，我可以得到相鄰像素的高度，如果第一個像素具有相同的屬性，那麼我將這個像素作爲輸入像素來調用相同的函數。

這裏有一些代碼（請記住，這仍然是在進行中）。 基礎來電者：

// R.A.G. 
for(std::vector<Cell*>::iterator iterCell = cellVec.begin(); 
    iterCell != cellVec.end(); ++iterCell) 
{ 
    Cell* mother = (*iterCell); 

    if(mother->visited != true) 
    { 
     mother->visited = true; 
    } 
    CheckNeighbors(mother); 
} 

的遞歸函數：

void 
CheckNeighbors(Cell* mother) 
{ 
    Cell* cell = nullptr; 

    // Get the neighbours for the cell. 
    // 5 6 7 
    // 4 c 0 
    // 3 2 1 
    if((cell=CheckCell(1, 0, mother)) != mother) 
    { 
     mother = cell; 
     CheckNeighbors(mother); 
    } 
    if((cell=CheckCell(1, 1, mother)) != mother) 
    { 
     mother = cell; 
     CheckNeighbors(mother); 
    } 
    if((cell=CheckCell(0, 1, mother)) != mother) 
    { 
     mother = cell; 
     CheckNeighbors(mother); 
    } 
    if((cell=CheckCell(-1, 1, mother)) != mother) 
    { 
     mother = cell; 
     CheckNeighbors(mother); 
    } 
    if((cell=CheckCell(-1, 0, mother)) != mother) 
    { 
     mother = cell; 
     CheckNeighbors(mother); 
    } 
    if((cell=CheckCell(-1, -1, mother)) != mother) 
    { 
     mother = cell; 
     CheckNeighbors(mother); 
    } 
    if((cell=CheckCell(0, -1, mother)) != mother) 
    { 
     mother = cell; 
     CheckNeighbors(mother); 
    } 
    if((cell=CheckCell(1, -1, mother)) != mother) 
    { 
     mother = cell; 
     CheckNeighbors(mother); 
    } 
} 

如何我檢查細胞：

Cell* 
CheckCell(int x, int y, Cell* cell) 
{ 
    // Here a cell is one pixel, but it depends on the size of the window we choose. 
    // So for an image of 640*480, windowSize = 1, w = 640, h = 480 
    x += cell->window.x()/windowSize; 
    y += cell->window.y()/windowSize; 

    // The cell at (x, y) coordinates is not in the map 
    if(x < 0 || x >= w || y < 0 || y >= h) return cell; 

    // Get the neighbor cell in (x, y) 
    // NB: cellVec has been filled up earlier and contains all the cells 
    Cell* neighbor = cellVec.at((y*w) + x); 

    // The neighbor cell has already been visited 
    if(neighbor->visited) return cell; 

    // The neighbor cell is of the same class as the mother cell 
    if(neighbor->cClass != cell->cClass) return cell; 

    // Set the region number for the neighbor 
    neighbor->visited = true; 

    return neighbor; 
} 

因此，這裏是我的問題：我敢肯定，這可以提高但我想知道如何。 我應該使用遞歸的其他東西嗎？ 如何改進這種遞歸？ 我讀了this article關於尾部呼叫優化，但因爲我不能拋棄呼叫者的狀態在我的情況下，這不能被應用。但是我還有其他一些技巧可以使用嗎？

感謝您的回答，我希望我已經足夠明確。

注意：如果我有一個圖像是單色，大小爲640 * 480，單元格大小爲2 * 2像素，我有153765個調用。當然還有1 * 1單元大小的段錯誤。我知道我可以增加堆棧的大小，但我更願意找到另一種解決方案。

Answer 1

您在做什麼是Flood fill，實施爲Depth First Search。

爲了改善它，您可以：

• 重新編碼它作爲一個Breadth First Search。
• 使用堆棧實現深度優先搜索。這仍然是相同的想法，但使用堆棧而不是遞歸應該使您的代碼更快，並使用更少的內存。

Answer 2

使用迭代方法時，您會更快，因爲您已經讀取了矢量中的所有元素，並且可以線性運行它。這是更爲緩存友好，您擺脫所有的東西抵消

// Copy all elements starting from the selected cell pointed to by the iterator, if 
// they are equal to the cell 
void checkAllCells(vector<Cell*> input, vector<Cell*>::iterator it; vector<Cell*> output) 
{ 
    auto localIt = it; 
    while(localIt != input.end()) 
    { 
     if ((*localIt)->class == (*it)->class) 
     { 
      output.pushback(*it); 
     } 
    } 
} 

注意，你不需要做簿記像visited等，因爲在開始的第一個元素，你會發現所有的人這是平等的。如果您接着拿第二個元素，您知道，您已經考慮過以前的元素了