Cấu trúc dữ liệu để xây dựng và tra cứu tập hợp các dãy số nguyên

Question

Tôi có một bộ số uint32, có thể có hàng triệu mục trong tập hợp. 50-70% trong số đó là liên tiếp, nhưng trong luồng đầu vào chúng xuất hiện theo thứ tự không thể đoán trước.

tôi cần phải:

1. Compress bộ này thành dãy để đạt được không gian đại diện hiệu quả. Đã thực hiện điều này bằng cách sử dụng thuật toán tầm thường, vì phạm vi tính toán chỉ một lần tốc độ không quan trọng ở đây. Sau khi số chuyển đổi này có phạm vi kết quả thường là trong khoảng 5 000-10 000, nhiều trong số đó là một mục duy nhất, tất nhiên.

2. Kiểm tra thành viên của một số số nguyên, thông tin về phạm vi cụ thể trong tập hợp là không bắt buộc. Cái này phải rất nhanh - O (1). Đã suy nghĩ về minimal perfect hash functions, nhưng chúng không chơi tốt với các phạm vi. Bitsets rất không hiệu quả. Các cấu trúc khác, như cây nhị phân, có độ phức tạp của O (log n), điều tồi tệ nhất với chúng là việc triển khai thực hiện nhiều bước nhảy có điều kiện và bộ vi xử lý không thể dự đoán chúng cho hiệu suất kém.

Có cấu trúc dữ liệu hoặc thuật toán chuyên biệt trong dãy số nguyên để giải quyết tác vụ này không?

Answer 1

Về vấn đề thứ hai:

Bạn có thể tra cứu trên Bloom Filters. Bộ lọc Bloom được thiết kế đặc biệt để trả lời câu hỏi thành viên trong O (1), mặc dù phản hồi là no hoặc maybe (không rõ ràng là có/không: p).

Trong trường hợp maybe, tất nhiên, bạn cần xử lý thêm để trả lời câu hỏi (trừ khi câu trả lời xác thực đủ trong trường hợp của bạn), nhưng ngay cả khi Bộ lọc Bloom có ​​thể hoạt động như một trình giữ cổng và từ chối hầu hết các truy vấn hoàn toàn.

Ngoài ra, bạn có thể muốn giữ phạm vi thực tế và làm giảm phạm vi (các phần tử đơn lẻ) trong các cấu trúc khác nhau.

• yếu tố duy nhất có thể được bảo quản tốt nhất trong một bảng băm
• dãy thực tế có thể được lưu trữ trong một mảng được sắp xếp

này làm giảm số phần tử được lưu trữ trong mảng được sắp xếp, và do đó sự phức tạp của tìm kiếm nhị phân được thực hiện ở đó. Vì bạn nói rằng nhiều phạm vi bị thoái hóa, tôi nhận ra rằng bạn chỉ có một số phạm vi 500-1000 (ví dụ, một đơn vị độ lớn ít hơn) và đăng nhập (1000) ~ 10

Do đó tôi sẽ đề xuất các bước sau:

• Bloom Lọc: nếu không, hãy dừng
• mảng Sắp xếp các dãy thực tế: nếu có, dừng
• Hash Table của các yếu tố đơn

các thử nghiệm mảng được sắp xếp được thực hiện đầu tiên, bởi vì fr om số bạn cung cấp (hàng triệu con số coalesced trong một vài nghìn phạm vi) nếu một số được chứa, rất có thể nó sẽ ở trong một phạm vi chứ không phải là duy nhất :)

Lưu ý cuối cùng: hãy cẩn thận của O (1), trong khi nó có vẻ hấp dẫn, bạn không ở đây trong một trường hợp tiệm cận. Khoảng 500-10000 đơn giản là rất ít, như log (10000) là một cái gì đó giống như 13.Vì vậy, không pessimize thực hiện của bạn bằng cách nhận được một giải pháp O (1) với một yếu tố liên tục cao mà nó thực sự chạy chậm hơn so với một giải pháp O (log N) :)

Answer 2

Nếu bạn biết trước phạm vi là gì, bạn có thể kiểm tra xem một số nguyên có sẵn có trong một trong các phạm vi trong O (lg n) hay không bằng cách sử dụng chiến lược được nêu bên dưới. Nó không phải là O (1), nhưng nó vẫn còn khá nhanh trong thực tế.

Ý tưởng đằng sau phương pháp này là nếu bạn đã hợp nhất tất cả các phạm vi với nhau, bạn có một tập hợp các dải phân tách trên dòng số. Từ đó, bạn có thể xác định thứ tự trên các khoảng thời gian đó bằng cách nói rằng khoảng [a, b] ≤ [c, d] iff b ≤ c. Đây là tổng số thứ tự bởi vì tất cả các dải đều bị phân tách. Do đó bạn có thể đặt tất cả các khoảng lại với nhau thành một mảng tĩnh và sau đó sắp xếp chúng theo thứ tự này. Điều này có nghĩa là khoảng thời gian ngoài cùng bên trái nằm trong khe đầu tiên của mảng và khoảng thời gian ngoài cùng bên phải nằm ở khe ngoài cùng bên phải. Công trình này mất thời gian O (n lg n).

Để kiểm tra xem một khoảng thời gian nào đó có chứa một số nguyên nhất định hay không, bạn có thể thực hiện tìm kiếm nhị phân trên mảng này. Bắt đầu từ khoảng giữa, kiểm tra nếu số nguyên được chứa trong khoảng thời gian đó. Nếu vậy, bạn đã hoàn tất. Nếu không, nếu giá trị nhỏ hơn giá trị nhỏ nhất trong phạm vi, hãy tiếp tục tìm kiếm ở bên trái và nếu giá trị lớn hơn giá trị lớn nhất trong phạm vi, hãy tiếp tục tìm kiếm ở bên phải. Đây thực chất là một tìm kiếm nhị phân chuẩn, và nó sẽ chạy trong thời gian O (lg n).

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

Answer 3

AFAIK không có thuật toán nào tìm kiếm trong danh sách số nguyên trong O (1).

Chỉ có thể thực hiện tìm kiếm O (1) với số lượng bộ nhớ khổng lồ.

Vì vậy, nó không phải là rất hứa hẹn để cố gắng tìm O (1) thuật toán tìm kiếm trong danh sách phạm vi của số nguyên.

Mặt khác, bạn có thể thử cách tiếp cận thời gian/bộ nhớ-off bằng cách cẩn thận kiểm tra bộ dữ liệu của bạn (cuối cùng xây dựng một loại bảng băm).

Answer 4

Thay vì lưu trữ/truy xuất dựa trên 'so sánh' (sẽ luôn là O (log (n)), Bạn cần phải làm việc trên lưu trữ/truy xuất dựa trên 'radix'.

Nói cách khác .. giải nén Nibbles từ uint32, và thực hiện một Trie ..

Answer 5

Giữ dãy của bạn thành một mảng được sắp xếp và sử dụng tìm kiếm nhị phân để tra cứu. Dễ dàng thực hiện, O (log N), và sử dụng ít bộ nhớ hơn và cần ít truy cập bộ nhớ hơn bất kỳ phương pháp tiếp cận dựa trên cây nào khác, vì vậy nó có thể cũng sẽ nhanh hơn nhiều.

Answer 6

Bạn có thể sử dụng cây nhanh hoặc cây Emde Boas để đạt được các truy vấn thời gian O (lg w), trong đó w là số bit trong một từ và bạn có thể sử dụng cây kết hợp để đạt được O (lg_w n) truy vấn thời gian. Sự cân bằng tối ưu về n là O (sqrt (lg (n))).

Cách dễ nhất để thực hiện có thể là cây nhanh. Chúng có thể nhanh hơn so với tìm kiếm nhị phân, mặc dù chúng yêu cầu các truy vấn bảng băm O (lg 32) = O (5), trong khi tìm kiếm nhị phân yêu cầu khoảng O (lg n) = O (lg 10000) = O (13) so sánh, do đó, tìm kiếm nhị phân có thể nhanh hơn.

Answer 7

Từ mô tả của bạn vấn đề nó âm thanh như sau đây có thể là một sự thỏa hiệp tốt. Tôi đã mô tả nó bằng cách sử dụng một ngôn ngữ hướng đối tượng, nhưng có thể dễ dàng chuyển đổi sang C bằng cách sử dụng một loại hình công đoàn hoặc cấu trúc với một thành viên loại và một con trỏ.

Sử dụng 16 bit đầu tiên để lập chỉ mục một mảng đối tượng (có kích thước 65536). Trong mảng có 5 đối tượng có thể

• một đối tượng NONE nghĩa là không yếu tố bắt đầu với những 16bits này nằm trong bộ
• một ALL đối tượng có nghĩa là tất cả các yếu tố bắt đầu với 16 bit này nằm trong bộ
• một loạt đối tượng nghĩa là tất cả các mục có 16bits cuối cùng giữa một giới hạn trên và dưới nằm trong tập hợp
• đối tượng SINGLE nghĩa là chỉ một phần tử bắt đầu bằng 16bits nằm trong mảng
• đối tượng BITSET xử lý tất cả các trường hợp còn lại với 65536 bit bitset

Tất nhiên, bạn không cần chia nhỏ với 16bits, bạn có thể điều chỉnh để phản ánh thống kê của tập hợp. Trong thực tế, bạn không cần phải sử dụng bit liên tiếp, nhưng nó tăng tốc độ twiddling bit, và nếu nhiều yếu tố của bạn là liên tiếp khi bạn yêu cầu bồi thường sẽ cung cấp cho tài sản tốt.

Hy vọng điều này có ý nghĩa, vui lòng nhận xét nếu tôi cần giải thích đầy đủ hơn. Hiệu quả bạn đã kết hợp một cây nhị phân độ sâu 2 với một phạm vi và một bitet cho một sự cân bằng thời gian/tốc độ. Nếu bạn cần phải tiết kiệm bộ nhớ sau đó làm cho cây sâu hơn với một sự gia tăng tương ứng nhẹ trong thời gian tra cứu.