tree 81eaffa516631d8418f2eb1fc4f9e62c5570e0fd
parent f9f0a6180c905fa24166ee2ae8ecda35df58dd37
author Doug Zongker <dougz@google.com> 1455035289 -0800
committer Tao Bao <tbao@google.com> 1455125782 -0800

improve performance of blockimgdiff

Substantially improves the performance of some BlockImageDiff steps on
large images.  GenerateDigraph and AssertSequenceGood are now linear in
the number of blocks in the target image rather than quadratic in the
size of the partition.  FindVertexSequence tracks the score of each
vertex, the set of sources and sinks, and maintains a heap for finding
the best vertex to use for the greedy step, instead of repeatedly
re-scanning the set of remaining vertexes.

Change-Id: Ifeea5053d80ef4f06a5aa239c9a1797dd5e47841
(cherry picked from commit 2d2dd1526dba2f9b533c4e0f2655524fea2cca4d)