# Inefficient code - Solutions

Jerry J jhj at jhj.com
Tue Jun 30 21:39:51 CDT 2009

```Here's a different approach - a recursive algorithm that is very
compact. Its only the fastest of the examples when very few pixels
differ, but it hangs in there pretty well throughout. I had no idea
how it would do - its very heavy on handler calls and I wondered if it
would hit the recursion limit (which is what?). It doesn't seem to,
with the given test images. I'm wondering if taking advantage of
adjacent changed pixels more than the algorithm already does could
help a bit. Or anything else anybody can think of, of course!

Anyway, an expanded versioin of your test stack is here:
http://jhj.com/Compare-Jerry2.rev.zip

Bill, all told, I think yours is still the overall king of the heap!

The algorithm:

pixDive 1, length(imageA)

on pixDive pStart, pEnd -- WARNING: RECURSION
local tMid
if byte pStart to pEnd of imageA <> byte pStart to pEnd of imageB
then
if pEnd - pStart <= 4 then -- its a single changed pixel, mark
it and move along
put pStart & return after diffPixels
else -- not dived down to one pixel yet
--split it in two and dive into each part
put  pStart + ((((pEnd - pStart + 1) / 4) div 2) * 4) into
tMid
pixDive pStart, tMid - 1  -- RECURSION
pixDive tMid, pEnd  -- RECURSION
end if -- comparing one pixel or more
end if -- nothing to see here, move along
end PixDive

On Jun 30, 2009, at 2:43 PM, Bill Marriott wrote:

> Thanks for the encouragement! I have uploaded the test stack to [the
> new] revOnline, with some enhancements to make it easier and more
> fun to test. the tags are:
>
> compare algorithm benchmark bitmap difference
> imageData performance pixels
>
> I've also uploaded it here:
>
>
> The full script for my algorithm is:
>
>  --
>  --
>
>  put 0 into currPixel
>  -- ImageA contains the imageData of image A
>  -- ImageB contains the imageData of image B
>  -- script assumes both images are the same dimension
>  put the length of ImageA into dataLength
>  put dataLength into rangeToCheck
>
>  -- check a range of pixels for differences.
>  -- the range begins with the full image
>  repeat while currPixel < dataLength
>     -- keep slicing the range in half until we find unchanged pixels
>     repeat while byte currPixel+1 to currPixel+rangeToCheck of
> ImageA <> \
>            byte currPixel+1 to currPixel+rangeToCheck of ImageB
>        -- aha, the range we're testing has changes
>        if rangeToCheck >= 8 then
>           -- eight bytes is at least two pixels...
>           -- it's still too big; slice it in half
>           put rangeToCheck div 4 div 2 * 4 into rangeToCheck
>        else
>           -- we're down to a single changed pixel now
>           -- record which pixel has changed (offset within the
> imageData)
>           put 1 into bytesChanged[currPixel+1]
>           -- move to the next pixel;
>           -- assume that changed pixels are near each other
>           add 4 to currPixel
>        end if
>     end repeat
>     -- we found one or more unchanged pixels; skip this section of
> data
>     add rangeToCheck to currPixel
>     -- and update the range to encompass the remainder of the image
>     put dataLength - currPixel into rangeToCheck
>  end repeat
>
>  --
>  --
>
> "Jerry J" <jhj at jhj.com> wrote in message news:F1333741-0799-4E69-B341-EB047C9D928A at jhj.com
> ...
>> Bill, I'd like to see your final test stack also. I have another
>> approach, but it doesn't give correct answers yet, at least I
>> don't  think so - at this point I'm no longer sure what the right
>> answers  are. Mine's recursive, and I can't wait to get it running
>> right so we  can see how fast it is (or not).
>> --Jerry J
>
>
> _______________________________________________
> use-revolution mailing list
> use-revolution at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your
> subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-revolution

```