基于矩阵加窗的Java代码优化计算时间

Question

我有一个矩阵，它代表一幅图像，我需要在上循环每一个像素，对于每一个像素，我必须计算它的所有邻居的和，即属于以像素为中心的半径rad窗口的像素。

我想出了三种选择：

• 最简单的方法，就是重新计算每个像素的窗口。
• 使用队列存储窗口列和并循环遍历矩阵列的更优化方法通过添加新元素和移除旧元素来更新此队列。
• 更优化的方法不需要为每一行重新计算队列，而是增量地调整先前保存的队列。

我在c++中实现了它们，使用了第二种方法的队列和第三种方法的分解组合(我需要迭代它们的元素而不破坏它们)，并对它们的时间进行评分，看看是否有实际的改进。看来第三种方法确实更快。

然后，我尝试将代码移植到Java (我必须承认，我对它不太满意)。我使用ArrayDeque作为第二种方法，而LinkedLists用于第三种方法，导致第三种方法在时间上效率低下。

下面是C++中最简单的方法(我不会发布java版本，因为它几乎是相同的)：

void normalWindowing(int  mat[][MAX], int cols, int rows, int rad){
    int i, j;
    int h = 0;
    for (i = 0; i < rows; ++i)
    {
        for (j = 0; j < cols; j++) 
        {
            h = 0;
            for (int ry =- rad; ry <= rad; ry++) 
            {
                int y = i + ry;
                if (y >= 0 && y < rows) 
                {
                    for (int rx =- rad; rx <= rad; rx++) 
                    {
                        int x = j + rx;
                        if (x >= 0 && x < cols) 
                        {
                            h += mat[y][x];
                        }
                    }
                }
            }
        }
    }   
}

下面是C++中的第二个方法(通过列优化的方法)：

 void opt1Windowing(int  mat[][MAX], int cols, int rows, int rad){
    int i, j, h, y, col;
    queue<int>* q = NULL;
    for (i = 0; i < rows; ++i)
    {
        if (q != NULL)
            delete(q);
        q = new queue<int>();
        h = 0;
        for (int rx = 0; rx <= rad; rx++) 
        {
            if (rx < cols) 
            {
                int mem = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        mem += mat[y][rx];
                    } 
                }
                q->push(mem);
                h += mem;
            }
        }
        for (j = 1; j < cols; j++) 
        {
            col = j + rad;
            if (j - rad > 0)
            {
                h -= q->front();
                q->pop();
            }
            if (j + rad < cols)
            {
                int mem = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        mem += mat[y][col];
                    } 
                }
                q->push(mem);
                h += mem;
            }
        }
    }
}

以下是Java版本：

public static void opt1Windowing(int [][] mat, int rad){
    int i, j = 0, h, y, col;
    int cols = mat[0].length;
    int rows = mat.length;
    ArrayDeque<Integer> q = null;
    for (i = 0; i < rows; ++i)
    {
        q = new ArrayDeque<Integer>();
        h = 0;
        for (int rx = 0; rx <= rad; rx++)
        {
            if (rx < cols)
            {
                int mem = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        mem += mat[y][rx];
                    }
                }
                q.addLast(mem);
                h += mem;
            }
        }
        j = 0;
        for (j = 1; j < cols; j++)
        {
            col = j + rad;
            if (j - rad > 0)
            {
                h -= q.peekFirst();
                q.pop();
            }
            if (j + rad < cols)
            {
                int mem = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        mem += mat[y][col];
                    }
                }
                q.addLast(mem);
                h += mem;
            }
        }
    }
}

我知道这篇文章将是一堵墙的文字。下面是C++中的第三种方法：

void opt2Windowing(int  mat[][MAX], int cols, int rows, int rad){
    int i = 0;
    int j = 0;
    int h = 0;
    int hh = 0;
    deque< deque<int> *> * M = new deque< deque<int> *>();
    for (int ry = 0; ry <= rad; ry++)
    {
        if (ry < rows)
        {
            deque<int> * q = new deque<int>();
            M->push_back(q);
            for (int rx = 0; rx <= rad; rx++) 
            {
                if (rx < cols) 
                {
                    int val = mat[ry][rx];
                    q->push_back(val);
                    h += val;
                }
            }
        } 
    }
    deque<int> * C = new deque<int>(M->front()->size());
    deque<int> * Q = new deque<int>(M->front()->size());
    deque<int> * R = new deque<int>(M->size());

    deque< deque<int> *>::iterator mit;
    deque< deque<int> *>::iterator mstart = M->begin();
    deque< deque<int> *>::iterator mend = M->end();

    deque<int>::iterator rit;
    deque<int>::iterator rstart = R->begin();
    deque<int>::iterator rend = R->end();

    deque<int>::iterator cit;
    deque<int>::iterator cstart = C->begin();
    deque<int>::iterator cend = C->end();

    for (mit = mstart, rit = rstart; mit != mend, rit != rend; ++mit, ++rit)
    {
        deque<int>::iterator pit;
        deque<int>::iterator pstart = (* mit)->begin();
        deque<int>::iterator pend = (* mit)->end();
        for(cit = cstart, pit = pstart; cit != cend && pit != pend; ++cit, ++pit)
        {
            (* cit) += (* pit);
            (* rit) += (* pit);
        }
    }

    for (i = 0; i < rows; ++i)
    {        
        j = 0;
        if (i - rad > 0)
        {
            deque<int>::iterator cit;
            deque<int>::iterator cstart = C->begin();
            deque<int>::iterator cend = C->end();

            deque<int>::iterator pit;
            deque<int>::iterator pstart = (M->front())->begin();
            deque<int>::iterator pend = (M->front())->end();

            for(cit = cstart, pit = pstart; cit != cend; ++cit, ++pit)
            {
                (* cit) -= (* pit);
            }
            deque<int> * k = M->front();
            M->pop_front();
            delete k;
            h -= R->front();
            R->pop_front();
        }
        int row = i + rad;
        if (row < rows && i > 0)
        {
            deque<int> * newQ = new deque<int>();
            M->push_back(newQ);

            deque<int>::iterator cit;
            deque<int>::iterator cstart = C->begin();
            deque<int>::iterator cend = C->end();
            int rx;
            int tot = 0;
            for (rx = 0, cit = cstart; rx <= rad; rx++, ++cit) 
            {
                if (rx < cols) 
                {
                    int val = mat[row][rx];
                    newQ->push_back(val);  
                    (* cit) += val;
                    tot += val;
                }
            }
            R->push_back(tot);
            h += tot;
        }        
        hh = h;
        copy(C->begin(), C->end(), Q->begin());

        for (j = 1; j < cols; j++) 
        {
            int col = j + rad;
            if (j - rad > 0)
            {
                hh -= Q->front();
                Q->pop_front();
            }
            if (j + rad < cols)
            {
                int val = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    int y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        val += mat[y][col];
                    } 
                }
                hh += val;
                Q->push_back(val);   
            }
        }
    }
}

最后，它的Java版本：

public static void opt2Windowing(int [][] mat, int rad){
    int cols = mat[0].length;
    int rows = mat.length;
    int i = 0;
    int j = 0;
    int h = 0;
    int hh = 0;
    LinkedList<LinkedList<Integer>> M = new LinkedList<LinkedList<Integer>>();
    for (int ry = 0; ry <= rad; ry++)
    {
        if (ry < rows)
        {
            LinkedList<Integer> q = new LinkedList<Integer>();
            M.addLast(q);
            for (int rx = 0; rx <= rad; rx++)
            {
                if (rx < cols)
                {
                    int val = mat[ry][rx];
                    q.addLast(val);
                    h += val;
                }
            }
        }
    }
    int firstSize = M.getFirst().size();
    int mSize = M.size();
    LinkedList<Integer> C = new LinkedList<Integer>();
    LinkedList<Integer> Q = null;
    LinkedList<Integer> R = new LinkedList<Integer>();
    for (int k = 0; k < firstSize; k++)
    {
        C.add(0);
    }
    for (int k = 0; k < mSize; k++)
    {
        R.add(0);
    }

    ListIterator<LinkedList<Integer>> mit;
    ListIterator<Integer> rit;
    ListIterator<Integer> cit;
    ListIterator<Integer> pit;
    for (mit = M.listIterator(), rit = R.listIterator(); mit.hasNext();)
    {
        Integer r = rit.next();
        int rsum = 0;
        for (cit = C.listIterator(), pit = (mit.next()).listIterator();
            cit.hasNext();)
        {
            Integer c = cit.next();
            Integer p = pit.next();
            rsum += p;
            cit.set(c + p);

        }
        rit.set(r + rsum);
    }

    for (i = 0; i < rows; ++i)
    {
        j = 0;
        if (i - rad > 0)
        {
            for(cit = C.listIterator(), pit = M.getFirst().listIterator();
               cit.hasNext();)
            {
                Integer c = cit.next();
                Integer p = pit.next();
                cit.set(c - p);
            }
            M.removeFirst();
            h -= R.getFirst();
            R.removeFirst();
        }
        int row = i + rad;
        if (row < rows && i > 0)
        {
            LinkedList<Integer> newQ = new LinkedList<Integer>();
            M.addLast(newQ);
            int rx;
            int tot = 0;
            for (rx = 0, cit = C.listIterator(); rx <= rad; rx++)
            {
                if (rx < cols)
                {
                    Integer c = cit.next();
                    int val = mat[row][rx];
                    newQ.addLast(val);
                    cit.set(c + val);
                    tot += val;
                }
            }
            R.addLast(tot);
            h += tot;
        }
        hh = h;
        Q = new LinkedList<Integer>();
        Q.addAll(C);

        for (j = 1; j < cols; j++)
        {
            int col = j + rad;
            if (j - rad > 0)
            {
                hh -= Q.getFirst();
                Q.pop();
            }
            if (j + rad < cols)
            {
                int val = 0;
                for (int ry =- rad; ry <= rad; ry++)
                {
                    int y = i + ry;
                    if (y >= 0 && y < rows)
                    {
                        val += mat[y][col];
                    }
                }
                hh += val;
                Q.addLast(val);
            }
        }
    }
}

我想，这主要是因为LinkedList在Java中的选择不佳，以及两个LinkedList之间缺乏有效的(而不是浅层的)复制方法。

如何改进第三个Java方法？我是不是做了一些概念上的错误？一如既往，任何批评都是受欢迎的。

更新，即使它没有解决这个问题，按照建议使用ArrayLists而不是LinkedList改进了第三种方法。第二种方法的性能更好(但当矩阵的行数和列数小于300且窗口半径较小时，第一个未优化的方法在Java中是最快的)

UPDATE2，我可以使用哪个工具来分析我的代码，并对哪一条指令花费最多的时间有更丰富的理解？我在Mac上，使用NetBeans Profiler只是向我展示了这三种方法的结束时间不同(看来我无法在每种方法中进行分析)

UPDATE3 I使用System.nanoTime()在java中对时间进行评分，这会导致不准确的估计吗？

    long start, end;

    start = System.nanoTime();
    simpleWindowing(mat, rad);
    end = System.nanoTime();
    System.out.println(end-start);

    start = System.nanoTime();
    opt1Windowing(mat, rad);
    end = System.nanoTime();
    System.out.println(end-start);

    start = System.nanoTime();
    opt2Windowing(mat, rad);
    end = System.nanoTime();
    System.out.println(end-start);

Answer 1

我确实为该例程实现了两个优化版本：

• 第一个，正如User216237所建议的，它使用一个int数组作为队列，在算法按列扫描图像时缓存汇总的列值。
• 另一个实现了一个总和面积表，通过只访问该表四次(它与窗口半径无关)来计算每个矩形的和面积。

根据其实现的特定领域，一种技术可以比另一种技术更快地任意执行。在矿井中，需要对面积表进行多次计算，因此，对于半径小于20像素的方法，其计算速度比第一种方法要慢。

Answer 2

对于具有随机访问权限的列表来说，LinkedList是一个非常糟糕的选择。对于每个get(int)，都会扫描列表，直到到达请求索引为止。

get(1)相当快，但是get(100)比get慢100倍，get(1000)比get慢1000倍。

您应该将其改为使用ArrayList，并按照预期的大小初始化ArrayList，以避免不必要地调整内部数组的大小。

编辑

虽然关于get()和LinkedList的内容是正确的，但它们并不适用于这种上下文。我不知何故忽略了这份名单是没有随机访问的。

Answer 3

使用int[]而不是List。

Lists存储需要从int转换到Integer和back的对象。