Các bác giúp em sao cho nó chạy nhanh hơn nhé, có hai file mỗi file chứa 1 triệu số ngẫu nhiên (có thể lặp lại) trong khoảng từ 1 đến 10 mũ 8, giờ tạo ra file thứ ba là tập hợp các số có trong file thứ nhất mà không có trong file thứ hai, các số trong file thứ ba không được phép lặp lại và phải xếp theo giá trị từ bé tới lớn. Em định giải quyết Đọc vào file thứ hai trước rồi sắp xếp lại, không cần vứt đi các số giống nhau, sau đó đọc lần lượt các số trong file thứ nhất rồi tìm kiếm nội suy nó trong mảng đã sắp xếp của file thứ hai, nếu không tìm thấy thì thêm vào mảng hiệu, sau khi có mảng hiệu thì có cách nào vừa sắp xếp vừa loại bỏ các số giống nhau cho nhanh không ạ?
Nếu các số đều là số nguyên (từ 1 đến 10^8) thì chỉ việc khai báo 1 mảng flag có 10^8 byte (100MB RAM chắc giờ máy nào cũng có). Tốn bộ nhớ một chút nhưng chỉ quét mỗi file một lần là xong không phải sắp xếp chi cả. Nếu là số thực thì lâu hơn chút. Được werty98 sửa chữa / chuyển vào 22:20 ngày 13/05/2008
Ối bác ơi, em chỉ khai báo trong BEA được đến tầm 61 893 596 là nó đã thông báo Exception in thread "main" java.lang.OutOfMemory Em dinh xu ly luc dau chi doc cac so nho hon 50 000 000 roi moi lam lan hai cac so tu 50 000 000 den 100 000 000 Tao mang 50 000 000 thi van Oke
import java.io.*; class Priklad3{ int GiaTriBotDi=0; boolean GhiThem=false; boolean [] C = new boolean[50000001]; boolean GiaTriSoSanh = true; public static void main (String[] args) { Priklad3 f = new Priklad3(); f.readMyFile(args[0]); f.GiaTriSoSanh=false; f.readMyFile(args[1]); f.inKQ(args[2]); f.GiaTriSoSanh=true; f.GiaTriBotDi=50000000; f.GhiThem=true; f.LamSach(); f.readMyFile(args[0]); f.GiaTriSoSanh=false; f.readMyFile(args[1]); f.inKQ(args[2]); } public void inKQ(String args1){ FileOutputStream fout; try { // Open an output stream fout = new FileOutputStream (args1,GhiThem); // Print a line of text for (int i=1;i<=50000000;i++){ if (C){ new PrintStream(fout).println(i+GiaTriBotDi); } } // Close our output stream fout.close(); } // Catches any error con***ions catch (IOException e) { System.err.println ("Unable to write to file"); System.exit(-1); } } //Doc du lieu tu file public void readMyFile(String args0) { DataInputStream dis = null; String SoDocVao; int So; try { //File f = new File("vstup1.txt"); File f = new File(args0); FileInputStream fis = new FileInputStream(f); BufferedInputStream bis = new BufferedInputStream(fis); dis = new DataInputStream(bis); while ( (SoDocVao=dis.readLine()) != null ) { So=Integer.parseInt(SoDocVao); if ((So<=50000000)&(!GhiThem)){ C[So]=GiaTriSoSanh; } if ((So>50000000)&(GhiThem)){ C[So-GiaTriBotDi]=GiaTriSoSanh; } } } catch (IOException e) { // catch io errors from FileInputStream or readLine() System.out.println("Uh oh, got an IOException error!" + e.getMessage()); } finally { // if the file opened okay, make sure we close it if (dis != null) { try { dis.close(); } catch (IOException ioe) { } } } } public void LamSach(){ for (int i=0;i<=50000000;i++){ C=false; } } }
Không biết Java cần mấy byte để lưu một biến boolean nhỉ? Dùng C thì chỉ cần 1 byte là OK. Nếu cần thì gắn thêm RAM
Hồi cấp 3 suốt ngày bị làm mấy bài toán kiểu này Làm xong rồi thì xem chương trình đứa nào chạy nhanh hơn Nhớ quá đi thôi. Vào hóng hớt tí chứ ko giúp gì dc cho bác chủ topic
Đây là bài toán điển hình cho sự tương quan tỉ lệ nghịch giữa không gian bộ nhớ và thời gian thực hiện. Bộ nhớ tiêu tốn 100MB là hoàn toàn chấp nhận được. Có thể giảm dung lượng nhớ này đi nhiều lần bằng cách sử dụng các toán tử thao tác bit (trong C là & và |) hoặc dịch bit (<< và >> nhưng đồng thời các thao tác xử lý lại tăng lên để tính đúng vị trí các bit. Khi đó mỗi giá trị Boolean được biểu diễn bằng một bit. Vấn đề còn lại là thuật toán thì hết sức đơn giản.
Theo tôi với bài toán cơ bản như thế này thì người ta không bao giờ lại tạo một mảng cả. và cũng thật bất ngớ khi ai đó bảo rằng cần một bộ nhớ trong đến cả 100Mb, thật nực cười! Ban nên nhớ rằng kiểu file được tạo ra không phải để đọc trở lại vào mảng. vơi bài toán của bạn tôi xin có ý kiến như sau: +theo cách thông thường, đối với những bài toán có dữ liệu vào nhiều như thế này hơn nữa kiểu dữ liệu lại có thứ tự thì việc sắp xếp được xét đến đầu tiên. như vậy ta cần sắp xếp lại hai file ban đầu vào hai file mới.( xem các thoật toán sắp xếp tại http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_s%E1%BA%AFp_x%E1%BA%BFp ) tiếp theo ta sử dụng hai vòng lặp while ***g nhau với dữ liệu vào là hai file mới vừa tạo ra. trong bước này ta cần sử dụng thoật toán tìm kiếm ( ban có thể xem tại http://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_thu%E1%BA%ADt_t%C3%ACm_ki%E1%BA%BFm ) công thêm câu lệnh rẽ nhánh nữa là xong. nếu việc so sánh trực tiếp ban đầu trong trường hợp xáu nhất cần đến 10^16 làn so sánh thì trong cách giải này số công viẹc thực hiện chắc chắn ít hơn. và bạn cần lựa chọn thuật toán phù hợp trong các thuật toáđuwọc đề nghị. có thể thấy cách trên vẫn chưa thực sự hiệu quả bởi công việc thực hiện vẫn còn quá lớn. vì thế tôi đề nghị cách giải sau: 1/sắp xếp hai file dữ liệu vào và lưu vào hai file mới. 2/ sắp xếp dữ liệu của hai file vào một file duy nhất. (bước 1 là để làm bước 2 thực hiện nhanh hơn) 3/ ghi kết quả vào file. cách giải này thì có vẻ đơn giản hơn. hơn nữa mỗi file chỉ cần đọc một lần duy nhất vì thế tốc độ thực hiên sẽ nhanh hơn rất nhiều. còn việc viết ra mã cụ thể thì chắc là bạn tự làm vậy. tôi chỉ quan tâm đến pascal ( bắt buộc) và java script (hứng thú ) chứ còn java thì tôi chỉ xem qua thôi. bài toán bạn đưa ra thuộc loại cơ bản, hẳn là bạn mới làm quen với java, nếu bạn muốn tìm hiểu sâu hơn có thể vào trang www.javavietnam.org
