Cấu trúc dữ liệu xử lý dữ liệu lớn trên RAM nhỏ

có lẽ dùng prefix tree lưu. Hóng cách làm khác

Bài này hay, ai thích nghiên cứu giải thuật vào xem thử. Một ngày mình sẽ phải làm cái này đấy.

có vẻ bài này khá khoai :3

Watching, hóng đáp án

Nếu nhớ ko lầm thì FreePascal có Tfilestream ko load dữ liệu vào RAM thì phải

Câu của bạn thớt hỏi thực chất một câu hỏi Phóng vấn được bàn trên Stackoverflow khá lâu

Find an integer not among four billion given ones

hay quá, mỗi tội đọc trên đó thì chỉ hiểu được mấy chỗ
mọi người thử đọc xem ý tưởng của họ là gì v?

Vậy là họ làm thế nào vậy ạ, tiếng anh cùi em dịch mà vẫn chưa hiểu lắm

TH 1: Với ram 4GB là ta có 41024^38 = 32 tỷ bits
mà đề chỉ cho 4 tỷ số thôi. Nên ta dư sức dùng xử lý bit làm mảng đánh dấu!

TH 2: là chia để trị
ví dụ ta có 4b số, chia thành nhiều đoạn, giả sử mình chia thành 4000 đoạn -> mỗi đoạn phải có đúng 1tr phần tử
-> khởi tạo 2 mảng
1 mảng gồm 4k phần tử để đếm các số trong đoạn trên, và 1 mảng gồm 1tr phần tử. (với range của vị trí i trong mảng là khoảng đoạn (10^6*(i-1),10^6*i]
2 mảng này chỉ tốn cỡ hơn 32tr bit so với 10MB (80tr bit) đề ch
Nếu ở vị trí nào trong mảng 4k phần tử mà lớn hơn 1tr phần tử -> vùng đó sẽ bị dư
Đọc lại file lần nữa, duyệt các số đúng giới hạn trong mảng 4k và dùng mảng 1tr phần tử kia đánh dấu

Ví dụ mảng nhỏ dễ hiểu
cho 10 phần tử 1 2 2 3 4 5 6 7 8 9 (sort cho dễ nhìn)
mình chia thành 2 đoạn. đoạn 1 gồm các số 0 < value <= 5, đoạn 2 gồm các số 5 < value <= 10
-> khi đếm đoạn 1 mình thấy có 6 phần tử trong khi đáng lẻ nó chỉ là 5 -> biết ngay đoạn này dư

• vì đoạn này có giá trị [1,5]
  -> duyệt lại file, nếu số mình đọc vào trong đoạn [1,5] thì +1 vô mảng dem[số]
  nếu dem[số] đã có giá trị rồi mà còn +1 nữa thì -> đó là số bị dư ra cần tìm.

bạn dịch tiếng anh tốt quá, k biết bao giờ mh ms dc như này