Простой алгоритм поиска дубликатов блоков хуже работает при использовании BloomFilter для поиска

Question

Я объединил два файла ISO в один файл. Оба отдельных файла ISO - это дистрибутивы Linux одного и того же поставщика, но разные версии. В программе, которую я написал (показано ниже), вычисляется объединительный файл в считанных блоках по 512 байт и MD5sum блока. MD5sum хранится в Hashet<String>. Если обнаружен блок с той же сигнатурой с использованием HashSet, это записывается.

Точно такой же алгоритм также выполняется с использованием BloomFilter до фактического поиска на HashSet. Поскольку BloomFilter предоставляет гарантии только на «неконкурентоспособность» и может предоставлять ложные срабатывания при сдерживании, я также просматриваю HashSet, если BloomFilter сообщает, что ключ может присутствовать уже.

Размер объединенного файла составляет> 1 ГБ, и, следовательно, количество 512-байтовых подписей блоков превышает 1,77 млн. Производительность подхода с использованием BloomFilter последовательно ~ в шесть раз больше, чем у первого подхода.

Любые причины, почему это может быть так? Что-то не так я здесь сделал?

import com.google.common.base.Charsets; 
import com.google.common.hash.BloomFilter; 
import com.google.common.hash.Funnel; 
import com.google.common.hash.PrimitiveSink; 
import java.io.File; 
import java.io.FileInputStream; 
import java.io.IOException; 
import java.util.HashSet; 
import java.util.concurrent.TimeUnit; 
import org.apache.commons.codec.digest.DigestUtils; 
import org.apache.commons.lang3.time.StopWatch; 

public class SimpleDedupTrial { 

    public static void main(String[] args) throws IOException { 

     int blockSize = 512; 

     HashSet<String> signatureSet = new HashSet<>(); 

     File f = new File(
      "D:\\keshav\\per\\projects\\work-area\\dedup-temp\\merged-iso" 
     ); 

     FileInputStream fis = new FileInputStream(f); 

     long length = f.length(); 
     long sizeSaved = 0l; 

     StopWatch sw = new StopWatch(); 

     int len; 
     byte[] buffer = new byte[blockSize]; 
     while ((len = fis.read(buffer)) != -1) { 

      String md5Hex = DigestUtils.md5Hex(buffer); 

      if (sw.isStopped()) { 
       sw.start(); 
      } 
      if (sw.isSuspended()) { 
       sw.resume(); 
      } 

      if (signatureSet.contains(md5Hex)) { 
       sizeSaved += len; 
      } else { 
       signatureSet.add(md5Hex); 
      } 

      sw.suspend(); 
     } 

     sw.stop(); 

     fis.close(); 

     System.out.println("Time: "+sw.getTime(TimeUnit.MILLISECONDS)); 
     System.out.println("File size in MB: "+convertToMB(length)); 
     System.out.println("Size saved in MB: "+convertToMB(sizeSaved)); 
     System.out.println("Signature set size: "+signatureSet.size()); 
     System.out.println("Duplicate ratio: "+ ((double)sizeSaved * 100/length)); 

     System.out.println("With Blooom:"); 
     useBloomFilter(); 
    } 

    private static long convertToMB(long sizeInBytes) { 
     return sizeInBytes/(1024 * 1024); 
    } 

    private static void useBloomFilter() throws IOException { 
     int blockSize = 512; 

     Funnel<String> strFunnel = (String t, PrimitiveSink ps) -> { 
      ps.putString(t, Charsets.US_ASCII); 
     }; 

     HashSet<String> signatureSet = new HashSet<>(); 

     File f = new File(
      "D:\\keshav\\per\\projects\\work-area\\dedup-temp\\merged-iso" 
     ); 

     FileInputStream fis = new FileInputStream(f); 

     long length = f.length(); 
     long sizeSaved = 0l; 

     BloomFilter<String> signatureBloomFilter = BloomFilter.create(
      strFunnel, (length/blockSize) 
     ); 

     StopWatch sw = new StopWatch(); 

     int len; 
     byte[] buffer = new byte[blockSize]; 
     while ((len = fis.read(buffer)) != -1) { 

      String md5Hex = DigestUtils.md5Hex(buffer); 

      if (sw.isStopped()) { 
       sw.start(); 
      } 
      if (sw.isSuspended()) { 
       sw.resume(); 
      } 

      if (signatureBloomFilter.mightContain(md5Hex)) { 
       if (!signatureSet.contains(md5Hex)) { 
        signatureBloomFilter.put(md5Hex); 
        signatureSet.add(md5Hex); 
       } else { 
        sizeSaved += len; 
       } 
      } else { 
       signatureBloomFilter.put(md5Hex); 
       signatureSet.add(md5Hex); 
      } 
      sw.suspend(); 
     } 

     sw.stop(); 

     fis.close(); 

     System.out.println("Time: "+sw.getTime(TimeUnit.MILLISECONDS)); 
     System.out.println("File size in MB: "+convertToMB(length)); 
     System.out.println("Size saved in MB: "+convertToMB(sizeSaved)); 
     System.out.println("Signature set size: "+signatureSet.size()); 
     System.out.println("Duplicate ratio: "+ ((double)sizeSaved * 100/length)); 
    } 
} 

Пример вывода:

Time: 819 
File size in MB: 1071 
Size saved in MB: 205 
Signature set size: 1774107 
Duplicate ratio: 19.183032558071734 
With Blooom: 
Time: 4539 
File size in MB: 1071 
Size saved in MB: 205 
Signature set size: 1774107 
Duplicate ratio: 19.183032558071734 

Answer 1

Похоже, вы пропустили точку Bloom filter немного. Мы используем их, когда мы не можем позволить себе память и соглашаемся потерять некоторую точность. Например, решите доставить 2 push-уведомления до 1/100 (или не отправлять им) пользователей для сохранения при сохранении коллекции тех, кто уже получил уведомление.

В HashSet вы ожидали времени доступа O(1), поэтому Bloom filter не ускорит процесс и, как вы видите, замедляет его. С другой стороны, он использует очень мало памяти, которая недостаточно значительна, чтобы появляться в вашей статистике.

Это потому, что требуется примерно то же самое время, чтобы указать not in и более для in.

Вы можете прочитать больше here.