Cấu trúc dữ liệu tốt nhất cho các ràng buộc sau đây?

Question

Dưới đây là một số ràng buộc đối với cấu trúc dữ liệu tôi cần. Có vẻ như không có cấu trúc dữ liệu chung nào (tôi sẽ đề cập đến những cấu trúc mà tôi đã nghĩ đến dưới đây) phù hợp với tất cả những điều đó. Bất cứ ai có thể đề nghị một mà tôi có thể đã không nghĩ đến?

1. Tôi cần có khả năng thực hiện tra cứu bằng các phím số không dấu.
2. Các mục cần lưu trữ là cấu trúc do người dùng xác định.
3. Các chỉ số này sẽ thưa thớt, thường là rất lớn. Các mảng thường xuyên bị loại bỏ.
4. Tần suất của từng chỉ mục sẽ có phân phối không đồng đều, với các chỉ số nhỏ thường xuyên hơn nhiều so với chỉ số lớn.
5. N thường sẽ nhỏ, có thể không lớn hơn 5 hoặc 10, nhưng tôi không muốn dựa vào quá nhiều vì đôi khi nó có thể lớn hơn nhiều.
6. Cụm từ liên tục quan trọng rất nhiều. Tôi cần tra cứu nhanh khi N nhỏ. Tôi đã thử các bảng băm chung và, theo kinh nghiệm, chúng quá chậm, ngay cả khi N = 1, có nghĩa là không có va chạm, có thể là do số lượng liên quan đến không liên quan. Tuy nhiên, tôi muốn mở các đề xuất về các bảng băm chuyên dụng tận dụng các ràng buộc khác được đề cập.
7. Thời gian chèn là không phải quan trọng miễn là thời gian truy xuất nhanh. Ngay cả O (N) thời gian chèn là đủ tốt.
8. Hiệu quả không gian không quan trọng lắm, mặc dù điều quan trọng là không chỉ sử dụng các mảng thông thường.

Answer 1

Khi N là một mảng đơn giản hoặc danh sách liên kết đơn có khóa + giá trị dưới dạng trọng tải là rất hiệu quả. Ngay cả khi nó không phải là tốt nhất khi N được lớn hơn.

Bạn nhận được thời gian tra cứu O (N) có nghĩa là tra cứu mất k * N thời gian. Tra cứu O (1) mất một thời gian K không đổi. Vì vậy, bạn nhận được hiệu suất tốt hơn hiệu suất với O (N) cho N < K/k. Ở đây k là rất nhỏ, do đó bạn có thể nhận được các giá trị thú vị của N. Hãy nhớ rằng ký hiệu Big O chỉ mô tả hành vi cho lớnN s, không phải những gì bạn đang làm sau. Đối với các bảng nhỏ

void *lookup(int key_to_lookup) 
{ 
    int n = 0; 
    while (table_key[n] != key_to_lookup) 
    n++; 
    return table_data[n]; 
} 

có thể khó đánh bại.

Đo điểm chuẩn bảng băm, cây cân đối và danh sách liên kết/mảng đơn giản và xem giá trị nào của N chúng bắt đầu tốt hơn. Sau đó, bạn sẽ biết cái nào tốt hơn cho bạn.

Tôi gần như quên: giữ các phím thường xuyên truy cập ở đầu mảng của bạn. Với mô tả của bạn có nghĩa là giữ cho nó được sắp xếp.

Answer 2

Bạn có thể cố gắng kết hợp tốt nhất của cả hai thế giới: Nếu khóa nhỏ, hãy đặt nó vào một cấu trúc dữ liệu giống như mảng không lớn hơn khóa tối đa được xác định trước. Nếu khóa lớn, hãy đặt nó thành một hashtable.

Answer 3

Một tra cứu bảng băm là về nhanh như nó có thể là:

Điều duy nhất mà phân biệt nó từ một tra cứu mảng thường xuyên là việc tính toán băm và (nếu hashfunction của bạn là đủ tốt, hoặc bạn bỏ ra đủ thời gian để tạo ra một hàm băm tối ưu trong khi chèn, mà sẽ làm cho việc chèn của bạn lấy O (N)) sau đó về cơ bản là một tra cứu mảng.

Về cơ bản vì nó có thể xảy ra (trừ khi bạn sử dụng hàm băm tối ưu), bạn phải khôi phục hoặc theo một danh sách được liên kết rất nhỏ.

Vì hầu hết hàm băm được sử dụng cho bảng băm là k * c_1% c_2, sự khác biệt đối với tra cứu mảng trong bảng băm khá thưa thớt và/hoặc tối ưu bao gồm một số, hai phép nhân, phép trừ và phép chia (một thực hiện modulo hiệu quả bằng cách sử dụng các capusites cpus có thể làm giảm điều đó bằng phép trừ và phép nhân) và tra cứu mảng.

Đơn giản là không nhanh hơn.

Answer 4

Tôi muốn xem xét một hashtable xử lý các va chạm băm với một cây nhị phân tự cân bằng thay vì chuỗi đơn giản. Bạn sẽ có thể nhận được O (1) trả dần giá trị trên tất cả các khóa và tra cứu trường hợp xấu nhất của O (logN). Vì phân phối khóa của bạn bị lệch, có khả năng bạn sẽ có xung đột với giá trị thấp của chỉ mục và việc tra cứu cây sẽ thực sự trả tiền ở đó.

Answer 5

lời khuyên này giả cpu hiện đại với:

• cache nhanh
• chậm hơn bộ nhớ độ trễ so với tốc độ đồng hồ.
• dự đoán hợp lý chi nhánh (thực sự tuyệt vời trong bộ vi xử lý máy tính để bàn/máy chủ mới nhất)

tôi sẽ đề nghị rằng các cấu trúc lai có thể cũng trump một cấu trúc duy nhất.

Sử dụng cặp giá trị khóa dựa trên mảng đơn giản với truy cập O (N) như đã đề cập nhưng các yếu tố không đổi rất thấp và hành vi lưu vào bộ đệm cực kỳ tốt. Cấu trúc ban đầu này nên nhỏ (có thể không lớn hơn 16 và có thể là 8 giá trị) để tránh vượt quá một dòng bộ nhớ cache duy nhất. Đáng tiếc là một tham số bạn sẽ cần phải điều chỉnh chính mình. Khi bạn vượt xa con số đó, bạn sẽ muốn quay trở lại cấu trúc với hành vi O (N) tốt hơn, tôi khuyên bạn nên thử một bảng băm phong nha để bắt đầu vì điều này có thể sẽ hợp lý từ 16 đến vài nghìn phạm vi và nếu bạn có xu hướng tìm kiếm các giá trị tương tự thường xuyên hơn sẽ có xu hướng ở lại trong bộ đệm nhanh hơn.

Nếu bạn cũng xóa cũng như chèn, bạn phải cẩn thận để không bị va chạm qua lại giữa hai trạng thái. Yêu cầu số lượng co lại thành một nửa việc cắt bỏ 'nâng cấp' thành cấu trúc phụ nên ngăn chặn điều này nhưng hãy nhớ rằng bất kỳ hành vi xuyên qua xác định nào sẽ dễ bị tác động đến trường hợp xấu nhất.
Đây có thể là vấn đề nếu bạn đang cố gắng bảo vệ khỏi dữ liệu đầu vào độc hại. Nếu như vậy sử dụng một yếu tố ngẫu nhiên trong quyết định bảo vệ chống lại nó. Có thể bạn không quan tâm về điều này mặc dù vì bạn đã không đề cập đến nó.

Nếu bạn muốn, bạn có thể thử tạo mảng chính ban đầu được sắp xếp, cho phép tìm kiếm nhị phân là O (log (N)) nhưng với chi phí của một mã tìm kiếm phức tạp hơn.Tôi nghĩ rằng việc đi bộ mảng đơn giản sẽ thực sự đánh bại nó, nhưng bạn sẽ muốn điểm chuẩn này cho các giá trị khác nhau của N, nó có thể cho phép bạn gắn bó với một mảng chính lâu hơn, nhưng tôi nghĩ đây là một hàm có kích thước kích thước đường bộ nhớ cache nhiều hơn hành vi O (N).

tùy chọn khác bao gồm:

• Xử lý tất cả các giá trị chính < 256 cách khác nhau và lưu trữ chúng trong một byte -> cặp struct của mảng tiết kiệm không gian trên các phím (và có thể cho phép họ vẫn ở đó khi bạn chuyển sang cấu trúc thứ cấp) điều này có thể hoạt động kém do cần phải giải nén mảng khi đang di chuyển đến độ dài từ gốc.
• sử dụng cấu trúc giống như trie làm một byte tại thời điểm khóa. Tôi nghi ngờ sự phức tạp của điều này sẽ làm cho nó hoạt động tốt trong thực tế

Một lần nữa tôi sẽ lặp lại lời khuyên rất tốt từ kmkaplan. Đánh dấu nó triệt để tránh microbenchmarks. Trong loại phân tích này, các số thực có thể khác biệt đáng ngạc nhiên với lý thuyết ...

Answer 6

Bạn có thể thử băm mở địa chỉ với thăm dò bậc hai thay vì chuỗi riêng biệt, nếu N của bạn thường nhỏ. Bạn sẽ cần phải phân bổ lại từ, ví dụ, kích thước ban đầu là 32 đến độ rộng lớn hơn nếu bạn nhận được trường hợp N hiếm hoi lấp đầy nó. Việc dò tìm tuyến tính hoặc băm cuckoo sẽ cung cấp cho bạn hiệu năng tốt nếu bạn có thể có được toàn bộ cấu trúc để vừa với một vài dòng bộ nhớ cache.

Thành thật mà nói, ngay cả một bảng băm tiêu chuẩn cũng mang đến cho bạn hiệu suất khốn khổ như vậy. Có lẽ bạn có thể cấu hình vào nó để xem chỉ những gì làm cho nó quá chậm - nếu đó là hàm băm chính nó, sử dụng một cái đơn giản như mô-đun hai điện (ví dụ, khóa & (N-1) trong đó N được biết đến là 2^x), điều này sẽ ủng hộ phân phối tập trung vào khoảng 0. Nếu đó là lỗi dcache theo đuổi chuỗi riêng biệt, hãy viết một triển khai lưu trữ bốn phần tử đầu tiên trong mỗi nhóm trong chính nhóm đó để bạn ít nhất có được chúng một cách nhanh chóng. Làm thế nào chậm là N = 1?

Tôi sẽ lưu trữ con trỏ tới cấu trúc chứ không phải cấu trúc trong chuỗi thùng: nếu cấu trúc lớn, sau đó đi bộ một chuỗi trong số đó sẽ có nhiều lần nhớ cache. Mặt khác, bạn có thể phù hợp với khoảng 16 cặp khóa/con trỏ trên một dòng bộ nhớ cache duy nhất và chỉ trả tiền khi bạn tìm thấy phần tử chính xác.

Answer 7

Giải thích duy nhất tôi có thể thấy cho vấn đề được mô tả là hàm băm quá phức tạp. Tôi sẽ nghiêng về cách tiếp cận hai giai đoạn:

1) Đối với các phím nhỏ, một chuỗi con trỏ đơn giản. Không có băm hay gì cả.

2) Đối với các phím được lớn hơn kích thước của bảng bạn phân bổ:

Làm thế nào về một hàm băm rất đơn giản mà sẽ lan rộng ra các phím cụm:

Các trái bậc 5 bit (Tôi giả định số nguyên 32 bit. Nếu đó là 64 bit thì thêm một bit nữa.) Là số bit thực sự chứa dữ liệu, phần còn lại chỉ đơn giản là tổng (loại bỏ mang) của khóa gốc được cắt thành các khối nhiều bit bạn đang sử dụng cho mục đích và thêm vào với nhau.

Lưu ý rằng số bit quan trọng có thể được tính toán một phần - xây dựng bảng 64k giá trị bit cao. Nếu từ thứ tự cao khác không, hãy sử dụng nó làm chỉ mục cho bảng và thêm 16, nếu không thì sử dụng từ thứ tự thấp làm chỉ mục. Đối với các số nguyên 64 bit, bạn rõ ràng phải sử dụng 4 bước thay vì hai bước.

Answer 8

Bạn có thể xem xét Judy Arrays:

Judy là một thư viện C cung cấp một công nghệ cốt lõi nhà nước-of-the-art mà thực hiện một mảng động thưa thớt. Các mảng Judy được khai báo đơn giản với con trỏ rỗng . Một mảng Judy tiêu thụ bộ nhớ chỉ khi nó được phổ biến, tuy nhiên có thể phát triển để tận dụng lợi thế của tất cả các bộ nhớ có sẵn nếu muốn ... Judy có thể thay thế nhiều dữ liệu chung cấu trúc, chẳng hạn như mảng, thưa thớt mảng, bảng băm, B-cây, số nhị phân cây, danh sách tuyến tính, skiplists, thuật toán sắp xếp và tìm kiếm khác và chức năng đếm.

Answer 9

Đây là ý tưởng chung cho hàm băm. Bạn nói chèn có thể tốn kém.

Hash chìa khóa, đó là một số nguyên, với một mô đun đơn giản, lưu trữ với mỗi trường hợp của một Hashtable

nếu chèn sẽ gây ra một vụ va chạm, lại tối ưu hóa Hashtable của bạn bằng cách tính toán số lượng va chạm điều đó sẽ xảy ra đối với mỗi mô đun trong một phạm vi hợp lý, giả sử, số lượng các phần tử trong bản đồ của bạn thông qua một số bội số không đổi của nó.

Rõ ràng, chèn của bạn thực sự trở nên khá đắt, khoảng O (n^2) nếu bạn giảm thiểu phân bổ, nhưng có thể bạn sẽ có thể đạt được tra cứu với một bộ phận nguyên duy nhất và một con trỏ đơn, và bạn biết, bạn tính nó vào thời gian chèn, những gì các trường hợp xấu nhất tra cứu sẽ được.

Answer 10

Tôi muốn giới thiệu một số Skip list tại đây. Gói java.util.concurrent có triển khai tốt nếu bạn tham gia vào đó.