Thuật toán song song để xây dựng một trie?

Question

Bởi vì cấu trúc dữ liệu trie có một yếu tố phân nhánh lớn và mỗi cây con hoàn toàn độc lập với nhau, có vẻ như phải có một cách để tăng tốc độ xây dựng trie cho một từ điển nhất định bằng cách thêm tất cả các từ song song. Ý tưởng ban đầu của tôi về cách thực hiện điều này như sau: liên kết một mutex với mỗi con trỏ trong trie (bao gồm cả con trỏ tới gốc) và sau đó có mỗi chuỗi theo thuật toán thông thường để chèn một từ vào trong trie. Tuy nhiên, trước khi làm theo bất kỳ con trỏ nào, một luồng trước tiên phải lấy khóa trên con trỏ đó để nếu nó cần thêm một nút con mới vào trie, thì nó có thể làm như vậy mà không giới thiệu bất kỳ cuộc đua dữ liệu nào.

Việc nắm bắt với phương pháp này là nó sử dụng một khổng lồ số ổ khóa - một cho mỗi con trỏ trong Trie - và làm một số khổng lồ của mua lại và phát hành - một cho mỗi nhân vật trong mỗi chuỗi đầu vào.

Có cách nào để xây dựng một trie song song mà không sử dụng gần như nhiều khóa không?

Answer 1

Một thuật toán lock-free rõ ràng sẽ là:

1. Bucket-sort các chuỗi đầu vào bằng một length- k tiền tố (thường, k = 1, nhưng với bảng chữ cái nhỏ, tăng k).
2. Đối với mỗi chữ cái, hãy tạo một trie chứa k -suffix của tất cả các chuỗi bắt đầu bằng chữ cái đó.
3. Hợp nhất các lần thử từ bước trước đó (khi k = 1, chỉ cần thêm nút gốc).

Giả sử phân phối đồng đều các tiền tố, điều này có thể giúp bạn tăng tốc tuyến tính lên kích thước bảng chữ cái thành công suất .

Answer 2

Vâng, có sự giao dịch rõ ràng giữa độ chi tiết thô mịn VS đặt khóa cho một tập hợp các nút (thay vì một).

Cách đơn giản để thực hiện là qua băm - có m các khóa khác nhau và cho mỗi nút bạn muốn truy cập có được khóa số hash(node) % m.
Lưu ý rằng phương pháp này về cơ bản là khái quát hóa phương pháp được đề xuất (với băm hoàn hảo và n == m) và phương pháp tiếp cận nối tiếp (với m == 1).

Một điều mà có thể được sử dụng là optimistic design - nếu phương pháp này thực sự sẽ làm tăng hiệu suất phụ thuộc vào sự phân bố của các từ điển và kích thước của Trie tất nhiên, và có thể giúp đỡ rất nhiều nếu va chạm có xu hướng rất hiếm (có thể là trường hợp cho một từ điển từ rất dài).
Ý tưởng là chỉ thêm từ vào trie mà không cần đồng bộ hóa và nếu bạn gặp phải xung đột - quay trở lại trạng thái ổn định đã biết cuối cùng (điều này tất nhiên yêu cầu chụp nhanh dữ liệu và có thể không khả thi nếu chúng tôi đang nói về các luồng dữ liệu không thể lưu trữ được).

Answer 3

Nó chỉ xảy ra với tôi rằng điều này có thể được thực hiện khóa miễn phí bằng cách sử dụng nguyên tử thử nghiệm và thiết lập hoạt động trên con trỏ thay vì ổ khóa. Cụ thể, nếu một chuỗi muốn theo một con trỏ, nó thực hiện như sau:

1. Đọc nguyên tử giá trị con trỏ.
2. Nếu con trỏ không rỗng, hãy theo dõi nó. Bạn đã hoàn tất.
3. Nếu không, hãy cấp phát một nút mới.
4. Kiểm tra nguyên tử con trỏ cho giá trị rỗng và đặt nó thành nút mới nếu nó là rỗng.
5. (Ghi chú: Con trỏ chắc chắn là không null ở đây. Hoặc là chúng ta chỉ cần đặt nó, hoặc nó được thiết lập bởi một luồng khác).
6. Làm theo con trỏ.

Tùy thuộc vào phần cứng, điều này có thể nhanh hơn nhiều, vì nó tránh nỗ lực khóa và mở khóa mọi lúc và đảm bảo rằng không có chuỗi nào đang chờ đợi vô thời hạn.

Một nhược điểm là số lượng phân bổ liên quan tăng lên, vì nhiều luồng có thể thử phân bổ một nút để đặt vào trie tại một vị trí nhất định, nhưng chỉ có thể đặt nó ở đó. May mắn thay, điều này có thể được giảm thiểu bằng cách tối ưu hóa sau đây: nếu một thread bao giờ phân bổ một nút không cần thiết, thay vì ngay lập tức giải phóng nó, nó chỉ lưu trữ các nút trong không gian tạm thời. Nếu sau này cần phân bổ một nút mới, nó có thể sử dụng nút được lưu trong bộ đệm. Nếu không, nó có thể giải phóng nó ở cuối cùng.

Hy vọng điều này sẽ hữu ích!

Answer 4

Tùy thuộc vào từ điển của bạn trông như thế nào, bạn có thể không cần khóa, nếu bạn có thể nhận từng chuỗi để tạo các subtrees độc lập. Nếu đây không phải là thuật toán trực tuyến, hãy sắp xếp các từ theo tiền tố (chữ cái đầu tiên nếu bạn có < 26 luồng, thứ nhất và thứ hai nếu bạn có nhiều hơn hoặc bạn biết rằng dữ liệu không được cân bằng, ví dụ: 90% từ bắt đầu với A). Về cơ bản, đây sẽ là một hoạt động O (n), nơi bạn thực hiện một lần đếm để đếm có bao nhiêu từ bắt đầu bằng một chữ cái, sau đó một đường để sắp xếp (dọc theo các dòng của một kiểu sắp xếp theo tiền tố bạn chọn). Sau đó, phân chia các tiền tố giữa các luồng và có mỗi luồng xây dựng các cây phụ độc lập này. Cuối cùng, có một chủ đề thêm mỗi subtrees vào thư mục gốc. Tôi sẽ xem qua một ví dụ bên dưới.

từ điển của bạn:
Bark
của Apple
Cookie
Và
bé
ngô
xanh
Bánh
Bacon

Sau khi sắp xếp:
của Apple
Và
Bark
bé
xanh
Bacon
ngô
Cookie
Bánh

Sau đó chúng tôi chia tiền tố giữa các chủ đề.Ví dụ này, chúng ta có 3 chủ đề, trong đó có các tiền tố [A] [B] [C], và xây dựng các cây sau:

 
A --|   B -------|   C -------|  
P N  |-- A ---| L   O ---| A 
P D  R B C U   O R K 
L   K Y O E   K N E 
E     N    I 
            E 

Và sau đó bạn có một thread kết hợp các ở thư mục gốc như:

 
|----------- Root------------------| 
A --|   B -------|   C -------|  
P N  |-- A ---| L   O ---| A 
P D  R B C U   O R K 
L   K Y O E   K N E 
E     N    I 
            E 

Tôi hy vọng điều đó có ý nghĩa.

Ưu điểm của phương pháp này: Các chủ đề hoạt động độc lập về cơ bản và bạn không phải chịu chi phí phải đối phó với việc mua và giải phóng khóa.

Hạn chế đối với phương thức này: Nếu bạn không biết gì về từ điển, có thể mất cân bằng tải công việc nghiêm trọng và trong trường hợp xấu nhất (Nói, tất cả các từ bắt đầu bằng 'A') là một sợi đơn dựng một cái cây. Có một vài cách để làm điều này tốt hơn, ví dụ, bạn có thể thêm một số kiểm tra khi bạn sắp xếp như vậy nếu khối lượng công việc bị mất cân đối nghiêm trọng khi giao dịch với một tiền tố chữ cái duy nhất, để du lịch bằng 2 chữ cái đầu tiên, nhưng thực sự bạn có thể ' t đảm bảo rằng nó sẽ được cân bằng.

Bạn cũng có thể không có chủ đề nhàn rỗi nếu nói bạn có 20 chủ đề và sắp xếp theo chữ cái đầu tiên, sau đó bạn sẽ có một số 6 chủ đề phải làm hai subtrees, trong khi 14 trong số họ ngồi nhàn rỗi trong một nửa thời gian. Bạn có thể chia nhỏ các subtrees để giải quyết vấn đề này, nhưng đó là thêm thời gian cho một bước tiền xử lý.

Dù sao, không đảm bảo rằng điều này nhanh hơn phương pháp của bạn, nhưng nó cần xem xét.