OSDN Git Service

improve performance of blockimgdiff
authorDoug Zongker <dougz@google.com>
Tue, 9 Feb 2016 16:28:09 +0000 (08:28 -0800)
committerDoug Zongker <dougz@google.com>
Wed, 10 Feb 2016 15:44:21 +0000 (07:44 -0800)
commit2d2dd1526dba2f9b533c4e0f2655524fea2cca4d
tree4d5b326da4996ba10ef558f97c685259026a13f7
parenta465cf681bb5fbc0b5a038302e982aa933a0a8ac
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
tools/releasetools/blockimgdiff.py