Geek asks and answers

2D JAVA peak search algorithm, found one example, but can not encode it

I am trying to rebuild this algorithm:
http://courses.csail.mit.edu/6.006/fall10/lectures/lec02.pdf
(Page 14 "Algorithm II")
(found this with google, unfortunately I'm not in MIT :) and this is not homework)

What is:

•Pick middle column (j=m/2)
•Find global maximum a=A[i,m/2]in that column
    (and quit if m=1)
•Compare a to b=A[i,m/2-1]and c=A[i,m/2+1]
•If b>a   then recurse on left columns
•Else, if c>a   then recurse on right columns
•Else a is a 2D peak!

What I have:

clipped is a vector that contains my size frequencies (blockSizeSmall-minBlockSize).

So this is a 2D matrix with columns trimmed.size()and (blockSizeSmall-minBlockSize).

For simplicity, I save the peaks in 2 int vectors of vector<int> pickhores and peakscolumn .

What is wrong there? I dont understand what

"Find global maximum a=A[i,m/2]in that column (and quit if m=1)"

should lead.

    public void findPeaks() {
        for (int column = trimmed.size() / 2; column < trimmed.size();) {
            int globalmax = 0;
            for (int row = 0; row < (blockSizeSmall - minBlockSize); row++) {
                if (trimmed.elementAt(column).reducedFreqs[row] > globalmax) {
                    globalmax = row; 
                    //find globalmax in row
                }
            }
            if (globalmax == 0) {
                break; //<- ???
            } else {
                if (column - 1 >= 0 && column + 1 < trimmed.size()) {
                //stay in bounds
                    if (trimmed.elementAt(column - 1).reducedFreqs[globalmax] > globalmax) {
                        column--; 
                        //if element at left side is > globalmax, recurse on column--;

                    } else if (trimmed.elementAt(column + 1).reducedFreqs[globalmax] > globalmax) {
                        column++; 
                        //if element at right side is > globalmax, recurse on column++;

                    } else { 
                        //if globalmax is higher than right or left element i have a peak
                        peaksrown.add(globalmax);
                        peakscolumnn.add(column);
                        Log.e(TAG, "" + peaksrown.size());
                    }
                }else{
                //what to do when out of bounds ?? break ??
                //if i break here, how can i be sure the algorithm 
                //went to both sides(column=0 and column=max) ??
                //just tried with break here, still infinit loop
                }
            }
        }
    }

It just ends endlessly.

+3
2

, , . # , , . "and quit if m = 1", , . , Peak() , .

    static void Peak(int[,] map, int left, int right)
    {
        // calculate middle column
        int column = (right + left) / 2;


        // get max row in column
        int arow = 0;
        for (int row = 0; row < map.GetLength(0); row++)
            if (map[row, column] > map[arow, column])
                arow = row;

        int a = map[arow, column];

        // get left value
        int b = 0;
        if (column - 1 >= left) b = map[arow, column - 1];
        // get right value
        int c = 0;
        if (column + 1 <= right) c = map[arow, column + 1];

        // if left is higher, recurse left
        if (b > a) Peak(map, left, column - 1);
        // else if right is higher, recurse right
        else if (c > a) Peak(map, column + 1, right);
        // else, peak
        else Console.WriteLine("Peak: " + arow + " " + column + " " + a);
    }

    static void Main(string[] args)
    {
        int[,] map = { {12, 8, 5},
                       {11, 3, 6 },
                       {10, 9, 2 },
                       { 8, 4, 1 } };
        Peak(map, 0, 2);
        Console.ReadLine();
    }
+3

, . (, ). , ( ) ( , ), .

0
source

More articles:


All Articles