Come trovare byte identici [] - oggetti in due array contemporaneamente?

Question

Sto tentando di implementare un attacco di collisione sugli hash (sto visitando il corso "crittografia"). Pertanto ho due matrici di hash (= sequenze di byte byte[]) e voglio trovare gli hash che sono presenti in entrambi gli array. Dopo alcune ricerche e un sacco di pensiero sono sicuro che la soluzione migliore su una macchina single-core sarebbe un HashSet (aggiungi tutti gli elementi del primo array e verifica tramite contains se sono già presenti elementi del secondo array).

Tuttavia, voglio implementare una soluzione concorrente, dal momento che ho accesso a una macchina con 8 core e 12 GB di RAM. La soluzione migliore a cui posso pensare è ConcurrentHashSet, che potrebbe essere creata tramite Collections.newSetFromMap(new ConcurrentHashMap<A,B>()). Usando questa struttura dati potrei aggiungere tutti gli elementi del primo array in parallelo e - dopo tutti gli elementi dove sono stati aggiunti - posso verificare contemporaneamente tramite contains per gli hash identici.

Quindi la mia domanda è: Conosci un algoritmo progettato per questo problema esatto? In caso contrario, si ha esperienza nell'utilizzo di un tale ConcurrentHashSet in merito a problemi e complessità effettiva del runtime? Oppure puoi consigliare un'altra struttura di dati precostruita che potrebbe aiutarmi?

PS: Se qualcuno è interessato ai dettagli: ho intenzione di utilizzare Skandium per parallelizzare il mio programma.

Answer 1

Penso che sarebbe una completa perdita di tempo utilizzare qualsiasi forma di HashMap. Sto indovinando che stai calcolando hash multi-byte di vari dati, questi sono già hash es, non è necessario eseguire altro hashing su di essi.

Anche se non lo si specifica, suppongo che i propri hash siano sequenze byte. Chiaramente uno trie o uno dawg sarebbe l'ideale per archiviarli.

Suggerirei pertanto di implementare uno trie/dawg e utilizzarlo per memorizzare tutti gli hash nel primo array. È quindi possibile utilizzare tutta la potenza di calcolo in parallelo per cercare ogni elemento nel secondo array in questo trie. Non sarebbero richieste serrature.

Aggiunto

Ecco una semplice implementazione Dawg bussai insieme. Sembra funzionare.

public class Dawg { 
    // All my children. 
    Dawg[] children = new Dawg[256]; 
    // Am I a leaf. 
    boolean isLeaf = false; 

    // Add a new word. 
    public void add (byte[] word) { 
    // Finds its location, growing as necessary. 
    Dawg loc = find (word, 0, true); 
    loc.isLeaf = true; 
    } 

    // String form. 
    public void add (String word) { 
    add(word.getBytes()); 
    } 

    // Returns true if word is in the dawg. 
    public boolean contains (byte [] word) { 
    // Finds its location, no growing allowed. 
    Dawg d = find (word, 0, false); 
    return d != null && d.isLeaf; 
    } 

    // String form. 
    public boolean contains (String word) { 
    return contains(word.getBytes()); 
    } 

    // Find the Dawg - growing the tree as necessary if requested. 
    private Dawg find (byte [] word, int i, boolean grow) { 
    Dawg child = children[word[i]]; 
    if (child == null) { 
     // Not present! 
     if (grow) { 
     // Grow the tree. 
     child = new Dawg(); 
     children[word[i]] = child; 
     } 
    } 
    // Found it? 
    if (child != null) { 
     // More to find? 
     if (i < word.length - 1) { 
     child = child.find(word, i+1, grow); 
     } 
    } 
    return child; 
    } 

    public static void main (String[] args) { 
    Dawg d = new Dawg(); 
    d.add("H"); 
    d.add("Hello"); 
    d.add("World"); 
    d.add("Hell"); 
    System.out.println("Hello is "+(d.contains("Hello")?"in":"out")); 
    System.out.println("World is "+(d.contains("World")?"in":"out")); 
    System.out.println("Hell is "+(d.contains("Hell")?"in":"out")); 
    System.out.println("Hal is "+(d.contains("Hal")?"in":"out")); 
    System.out.println("Hel is "+(d.contains("Hel")?"in":"out")); 
    System.out.println("H is "+(d.contains("H")?"in":"out")); 
    } 
} 

Aggiunto

Questo potrebbe essere un buon punto di partenza in una versione senza blocchi concorrente. Queste cose sono notoriamente difficili da testare quindi non posso garantire che funzionerà, ma a mio avviso certamente dovrebbe.

import java.util.concurrent.atomic.AtomicReferenceArray; 


public class LFDawg { 
    // All my children. 
    AtomicReferenceArray<LFDawg> children = new AtomicReferenceArray<LFDawg> (256); 
    // Am I a leaf. 
    boolean isLeaf = false; 

    // Add a new word. 
    public void add (byte[] word) { 
    // Finds its location, growing as necessary. 
    LFDawg loc = find(word, 0, true); 
    loc.isLeaf = true; 
    } 

    // String form. 
    public void add (String word) { 
    add(word.getBytes()); 
    } 

    // Returns true if word is in the dawg. 
    public boolean contains (byte[] word) { 
    // Finds its location, no growing allowed. 
    LFDawg d = find(word, 0, false); 
    return d != null && d.isLeaf; 
    } 

    // String form. 
    public boolean contains (String word) { 
    return contains(word.getBytes()); 
    } 

    // Find the Dawg - growing the tree as necessary if requested. 
    private LFDawg find (byte[] word, int i, boolean grow) { 
    LFDawg child = children.get(word[i]); 
    if (child == null) { 
     // Not present! 
     if (grow) { 
     // Grow the tree. 
     child = new LFDawg(); 
     if (!children.compareAndSet(word[i], null, child)) { 
      // Someone else got there before me. Get the one they set. 
      child = children.get(word[i]); 
     } 
     } 
    } 
    // Found it? 
    if (child != null) { 
     // More to find? 
     if (i < word.length - 1) { 
     child = child.find(word, i + 1, grow); 
     } 
    } 
    return child; 
    } 

    public static void main (String[] args) { 
    LFDawg d = new LFDawg(); 
    d.add("H"); 
    d.add("Hello"); 
    d.add("World"); 
    d.add("Hell"); 
    System.out.println("Hello is " + (d.contains("Hello") ? "in" : "out")); 
    System.out.println("World is " + (d.contains("World") ? "in" : "out")); 
    System.out.println("Hell is " + (d.contains("Hell") ? "in" : "out")); 
    System.out.println("Hal is " + (d.contains("Hal") ? "in" : "out")); 
    System.out.println("Hel is " + (d.contains("Hel") ? "in" : "out")); 
    System.out.println("H is " + (d.contains("H") ? "in" : "out")); 
    } 
} 

Answer 2

Un approccio più semplice sarebbe quella di dividere solo il primo array in n parti uguali (o quasi uguali) (con 8 core, n = 8 sembra ragionevole). Quindi risolvi il programma nel modo "normale", osservando se sono presenti alcuni hash nel 2 ° array negli N sub-first-array più piccoli. Questo può essere fatto in parallelo.

Detto questo, non ho mai sentito di tentativi/dawgs prima e ho trovato la discussione principale affascinante e informativo.(Io lavoro principalmente con i numeri, non con le parole)

Ciò presuppone che gli hash del byte [] siano di una lunghezza finita e ridotta in modo tale da poter realmente dividere il file originale da elaborare in parallelo. È questo il caso?

EDIT AGGIUNTO

Per un esempio di questa idea, vedi GPU grafiche Gems, a cura di Wen-Mei W. Hwu, capitolo 11, un articolo di Ligowski, Rudnicki, Liu e Schmidt. Parallelizzano un'enorme ricerca nel database delle sequenze proteiche suddividendo l'enorme singolo database in molti pezzi più piccoli, quindi eseguendo l'algoritmo normale su ciascuna sottosezione. Mi piace questa citazione. "L'algoritmo descritto è imbarazzantemente parallelo". Nel loro caso hanno usato CUDA e hanno dovuto fare un sacco di ottimizzazione della memoria, ma il principio dovrebbe ancora applicarsi alle macchine multi-core.

SEGUE semi-PSEUDOCODE. Userò gli elenchi per gli hash byte in entrata [], spero che sia o.k.

originale, 1 metodo del nucleo

originalProcess(List<byte[]> list1, List<byte[]> list2) { 
    HashSet<byte[]> bigHugeHashOfList1 = new HashSet<byte[]>(); 
    bigHugeHashOfList1.addAll(list1); 
    for (byte[] hash : list2) 
     if (bigHugeHashOfList1.contains(hash) 
     // do something 
} 

Nuovo metodo. Utilizza lo stesso identico metodo di processo (in seguito). No DAWGS o TRIES qui ...

preprocess(List<byte[]> list1, List<byte[]> list2) { 
    List<byte[]>[] splitLists = new ArrayList<byte[]>[8]; 
    for (int i=0; i<8; i++) 
     splitLists[i] = new ArrayList<byte[]>(); 
    for (byte[] hash : list1) { 
     int idx = hash[0]&7; // I'm taking the 3 low order bits, YMMV 
     splitLists[idx].add(hash); 
     // a minor speedup would be to create the HashSet here instead of in originalProcess() 
    } 

    // now, using your favorite parallel/concurrency technique, 
    // do the equivalent of 
    for (int i=0; i<8; i++) 
     originalProcess(splitLists[i], list2); 
}