Thuật toán xử lý dữ liệu lớn

Xử lý bài toán với dữ liệu lớn

Lê Văn Chương

Các bài toán có dữ liệu vàorất lớn, thường gây cho ta rất nhiều khó khăn. Để giải được các

bài toán đó thìcần phải tìm cấu trúc dữ liệu và giải thuật thật hợp lý. Đa số các bài

toándạng này thì phải vừa đọc vừa xử lý. Lấy ví dụ bài toán đơn giản sau:

Bài toán: Tìmdòng đặc biệt

Cho một tệp văn bản có ndòng (n ≤ 100000) mỗi dòng có độ dài không quá 255 ký tự..

Trong đó có một dòng chỉ xuất hiện một lần duy nhất, còn các dòng còn lại có số lần xuất

hiện là một số chẵn. Bạn hãy lập trình để chỉ ra dòng đặc biệt đó.

Dữ liệu vào: tệp dacbiet.inp

- Ghi cácdòng thông tin và kết thúc tệp bởi 1 dòng có 3 ký tự ###

Dữ liệu ra: tệp dacbiet.out

- Ghi radòng đặc biệt tìm được

Ex:

Giải: Với dữ liệuvào rất lớn n ≤ 10000 thì giải thuật đơn giản nhất là cứ đọc một dòng bất

kỳsau đó so sánh với các dòng tiếp, nếu không thấy xuất hiê.n quá 1 lần thì nóchính là

dòng đặc biệt, ngược lại thì thực hiện với dòng kế tiếp. Nhưng nếudòng đặc biệtt đó là

dòng cuối cùng thì số lần đọc tệp sẽ rất nhiều nên thờigian chạy chương trình cũng rất lâu.

Mặt khác ta không thể lưu trữ vào mảngđượcc nên ta phải vừa đọc, vừa xử lý.

Thuật toán: sử dụngphép XOR. Như ta đã biết: