Cách tạo mảng có kích thước lớn hơn số nguyên tối đa

Question

Tôi đã cố gắng lấy tất cả số nguyên tố trước 600851475143. Tôi đã sử dụng Sieve of Eratosthenes cho việc này. Điều này đòi hỏi tôi phải tạo một mảng boolean có kích thước lớn. Ý tưởng tồi, bạn có thể hết bộ nhớ. Bất kỳ cách nào khác. Tôi đã thử sử dụng một chuỗi, sử dụng từng chỉ mục với các giá trị 0 & 1 để biểu thị đúng hoặc sai. nhưng phương thức indexOf cũng trả về int.

Tiếp theo tôi đang sử dụng mảng 2d cho vấn đề của mình. Bất kỳ cách nào tốt hơn để lưu trữ một mảng lớn như vậy?

Answer 1

Sử dụng BitSet. Sau đó, bạn có thể đặt bit bất kỳ phần tử chỉ mục nào. 600851475143 là 2^39 do đó chỉ lấy 39 bit nội bộ (thực tế trong thực tế nó sẽ chiếm 64 bit vì nó sử dụng lâu dài).

Bạn có thể Infact di chuyển tối đa 2^63 đó là lớn đối với hầu hết các mục đích

Answer 2

Tôi đã có một vấn đề tương tự và tôi sử dụng một bộ bit (về cơ bản thiết lập 1 hoặc 0 cho mong muốn bù đắp theo thứ tự) và tôi khuyên bạn nên sử dụng EWAHCompressedBitmap nó cũng sẽ nén chút bạn thiết lập

EDIT

Như Alan cho biết BitSet sẽ chiếm 70GB bộ nhớ nhưng bạn có thể làm một điều: có nhiều BitSets (những người liên tục để bạn có thể tính toán vị trí tuyệt đối) và tải trong bộ nhớ chỉ BitSet mà bạn cần trong thời điểm đó một cái gì đó giống như một tải lười biếng, trong trường hợp này bạn sẽ có quyền kiểm soát bộ nhớ được sử dụng.

Answer 3

Yêu cầu bộ nhớ cho 600851475143 booleans ở mức 70Gb tốt nhất. Điều này là không khả thi. Bạn cần phải sử dụng nén theo gợi ý của Stephan, hoặc tìm một thuật toán khác để tính số nguyên tố.

Answer 4

Nó không thực sự thực tế để nhớ cho mỗi số nếu nó là một nguyên tố hay không cho một số lượng lớn như vậy (sàng là một cách tiếp cận rất chậm cho số lượng lớn nói chung).

Từ số link này, bạn sẽ biết được có bao nhiêu số nguyên tố được mong đợi nhỏ hơn X. Đối với phạm vi 600 tỷ bạn có thể mong đợi khoảng 20 tỷ số nguyên tố tồn tại trong phạm vi đó. Lưu trữ chúng lâu [] sẽ yêu cầu khoảng 160GB bộ nhớ ... đáng chú ý hơn 70GB được đề xuất để lưu trữ một bit cho mỗi số, một nửa nếu bạn loại trừ số chẵn (2 là số nguyên tố duy nhất).

Đối với máy tính để bàn 35 GB bộ nhớ có thể hơi nhiều, nhưng một máy trạm tốt có thể có nhiều RAM. Tôi sẽ thử một mảng hai chiều với bit shifting/masking.

Tôi vẫn mong đợi mã sàng của bạn chạy một thời gian đáng kể (một vài thứ từ vài năm đến nhiều năm). Tôi đề nghị bạn điều tra các phương pháp phát hiện nguyên tố tiên tiến hơn sàng.

Answer 5

Bạn có thể sử dụng API sun.misc.Unsafe nội bộ của HotSpot để phân bổ một mảng lớn hơn. I wrote a blogpost how to simulate an array with it Tuy nhiên, nó không phải là một API Java chính thức, do đó, nó đủ điều kiện như là một hack.