Inefficient code - Solutions

[Jerry J]

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:
>
> http://bill.on-rev.com/linked/Compare2.zip
>
> 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