Comparing parts of a byte[] to determine whether two byte[] could be the same

Question

I have a Cursor adapter where I potentially have a number of images in a grid setup.

When the bindView method runs it needs to complete very quickly and therefore as part of a performance/efficiency boost I would like to compare the images before I make any changes(so I don't start running my Async Tasks etc multiple times). However, I can't store the entire byte[] (e.g. in the ViewHolder) as this clearly eats through memory.

However, I was thinking I could take a part of an image byte array (20 characters or so) and compare it with what is currently in the ViewHolder and if different this could be verified.

Is this a viable option or is there a better way to do this? Secondly, what part of the byte[] is going to produce the most unique set of characters?

why dont you use checksums? store md5 value and compare them to see if its equal? — damian, Apr 24 '13 at 11:16
The storing is the actual issue. Wouldn't an md5 checksum be as long as the `byte[]` itself? I need a very small footprint. — HGPB, Apr 24 '13 at 11:20
no. md5 is 32 digits. what you should not use is something like base64 which actually "ciphers" or puts a "wrapper" around the data. checksums are exactly for such cases and are optimized to have as few collisions as possible. — damian, Apr 24 '13 at 11:21
Excellent - thank you both. Leave an answer and I will accept it. — HGPB, Apr 24 '13 at 11:23
You have a small logic issue: `I can't store the entire byte[] (e.g. in the ViewHolder) as this clearly eats through memory.` Which is wrong, you don't store the byte[], you should store an ImageView and assign a bitmap, so no byte[] to bitmap converting on each bindView call. I store more than 50 bitmaps for a gridview without any problems, so you should think about your bitmap storage methods... — WarrenFaith, Apr 24 '13 at 11:24
Are your images stored as Bitmaps? If youre developing for Android 3.1 or above you could use Bitmap.sameAs() — Akash, Apr 24 '13 at 11:25
@WarrenFaith I actually store images in the database. So when the cursor extracts the data I want to compare it quickly without converting the entire `byte[]` to an image for comparison(which would need to be done off the UI thread). So I was looking at storing a small `byte[]` in the `ViewHolder`. Which I can now approach by implementing an MD5 hash. — HGPB, Apr 24 '13 at 11:30
@Haraldo you still should implement a in-memory cache to prevent continuously decoding of the byte[] array. The same would be the case when you decode from filesystem. It should be done only once, put in the cache and the cache should handle the memory consumption and free some if necessary and, of course, decode a bitmap again if necessary. With that you don't need a comparison, just a memory where you get a bitmap by id (row id for example) and the rest is done by the cache. LRUCache, for example or LRUDiskCache (just modified for database access) would do the trick. — WarrenFaith, Apr 24 '13 at 11:49

score 1 · Accepted Answer · edited May 23 '17 at 11:50

1

1- Get a MD5 checksum with java.security.DigestInputStream (see Getting a File's MD5 Checksum in Java)

MessageDigest md = MessageDigest.getInstance("MD5");
InputStream is = new FileInputStream("file.txt");
try {
    is = new DigestInputStream(is, md);
    // read stream to EOF as normal...
}
finally {
  is.close();
}
byte[] digest = md.digest();

2- a small method to compare two byte[]

boolean safeArrayEquals(byte[] a1, byte[] a2) {
    if (a1 == null || a2 == null) {
        return (a1 == a2);
    }

    if (a1.length != a2.length) {
        return false;
    }

    byte result = 0;
    for (int i = 0; i < a1.length; i++) {
        result |= a1[i] ^ a2[i];
    }

    return (result == 0);
}

edited May 23 '17 at 11:50

Community

1
1

answered Apr 24 '13 at 11:47

willome

3,062
19
32

I normally compare primitive arrays as follows: `Arrays.equals` – HGPB Apr 24 '13 at 12:14
I am pretty sure that this method (safeArrayEquals) is faster than Arrays.equals (see http://stackoverflow.com/questions/8777257/equals-vs-arrays-equals-in-java for Arrays.equals source code) – willome Apr 25 '13 at 08:36

Comparing parts of a byte[] to determine whether two byte[] could be the same

1 Answers1