Làm thế nào để tìm các byte giống nhau [] - các đối tượng trong hai mảng đồng thời?

Question

Tôi đang cố gắng thực hiện một cuộc tấn công va chạm vào băm (tôi đang truy cập khóa học 'mật mã'). Vì vậy, tôi có hai mảng băm (= byte-chuỗi byte[]) và muốn tìm băm có trong cả hai mảng. Sau một số nghiên cứu và suy nghĩ rất nhiều, tôi chắc chắn rằng giải pháp tốt nhất trên máy đơn lõi sẽ là HashSet (thêm tất cả các phần tử của mảng đầu tiên và kiểm tra qua contains nếu các phần tử của mảng thứ hai đã có).

Tuy nhiên, tôi muốn triển khai giải pháp đồng thời vì tôi có quyền truy cập vào máy có 8 lõi và RAM 12 GB. Giải pháp tốt nhất tôi có thể nghĩ là ConcurrentHashSet, có thể được tạo thông qua Collections.newSetFromMap(new ConcurrentHashMap<A,B>()). Sử dụng cấu trúc dữ liệu này tôi có thể thêm tất cả các phần tử của mảng đầu tiên song song và - sau khi tất cả các phần tử được thêm vào - tôi có thể kiểm tra đồng thời qua contains cho các băm giống nhau.

Vì vậy, câu hỏi của tôi là: Bạn có biết thuật toán được thiết kế cho vấn đề chính xác này không? Nếu không, bạn có kinh nghiệm sử dụng ConcurrentHashSet như vậy liên quan đến các vấn đề và thời gian chạy hiệu quả phức tạp không? Hoặc bạn có thể giới thiệu một cấu trúc dữ liệu dựng sẵn khác có thể giúp tôi không?

PS: Nếu có ai quan tâm đến chi tiết: Tôi định sử dụng Skandium để song song chương trình của mình.

Answer 1

Tôi nghĩ rằng sẽ hoàn toàn lãng phí thời gian để sử dụng bất kỳ hình thức nào của HashMap. Tôi đoán bạn đang tính toán băm multi-byte của các dữ liệu khác nhau, đây là những đã được hash es, không cần phải thực hiện bất kỳ băm nữa trên chúng.

Mặc dù bạn không nói rõ, tôi đoán băm của bạn là các chuỗi byte. Rõ ràng hoặc là trie hoặc dawg sẽ là lý tưởng để lưu trữ chúng.

Tôi khuyên bạn nên triển khai trie/dawg và sử dụng nó để lưu trữ tất cả các băm trong mảng đầu tiên. Sau đó, bạn có thể sử dụng tất cả sức mạnh máy tính của mình song song để tra cứu từng phần tử trong mảng thứ hai của mình trong trie này. Không cần khóa.

Added

Dưới đây là một Dawg thực hiện đơn giản, tôi gõ với nhau. Dường như nó hoạt động.

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")); 
    } 
} 

Added

Đây có thể là một khởi đầu tốt tại một phiên bản lock-free đồng thời. Những điều này nổi tiếng là khó kiểm tra vì vậy tôi không thể đảm bảo điều này sẽ làm việc nhưng với tâm trí của tôi nó chắc chắn nên.

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

Cách tiếp cận đơn giản hơn là chia mảng đầu tiên thành N phần bằng (hoặc gần bằng) (với 8 lõi, n = 8 có vẻ hợp lý). Sau đó, giải quyết chương trình theo cách "bình thường", bằng cách tìm xem có băm nào trong mảng thứ hai có mặt trong N mảng con đầu tiên nhỏ hơn không. Điều này có thể được thực hiện song song.

Điều đó nói rằng, tôi chưa bao giờ nghe nói về cố gắng/dawgs trước và tôi đã tìm thấy cuộc thảo luận chính hấp dẫn và mang tính thông tin.(Tôi chủ yếu làm việc với các số, không phải từ)

Giả định rằng băm byte [] có một số độ dài ngắn, hữu hạn để bạn thực sự có thể chia nhỏ tệp gốc để xử lý song song. Đó là trường hợp?

EDIT THÊM

Đối với một ví dụ về ý tưởng này, xem GPU Graphics Gems, thay đổi nội dung bởi Wen-Mei W. Hwu, chương 11, một bài viết của Ligowski, Rudnicki, Liu và Schmidt. Họ song song một tìm kiếm cơ sở dữ liệu chuỗi protein lớn bằng cách tách cơ sở dữ liệu đơn cực thành nhiều phần nhỏ hơn, sau đó chạy thuật toán thông thường trên mỗi phần con. Tôi thích câu nói này. "Thuật toán được mô tả là lúng túng song song". Trong trường hợp của họ, họ đã sử dụng CUDA và phải làm rất nhiều việc tối ưu hóa bộ nhớ, nhưng nguyên tắc vẫn nên áp dụng cho các máy đa lõi.

CÁC L semiI bán PSEUDOCODE. Tôi sẽ sử dụng Danh sách cho băm byte [] đến, hy vọng đó là o.k.

gốc, 1 phương pháp cốt lõi

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 
} 

Phương pháp mới. Sử dụng chính xác phương pháp xử lý tương tự (sau này). Không có DAWGS hoặc TRIES ở đây ...

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); 
}