Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Tìm kiếm như thế nào khi số phần tử rất lớn trong file

  1. #1
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    Mặc định Tìm kiếm như thế nào khi số phần tử rất lớn trong file

    Tui có 1 triệu record là tên các cty hoặc người chẳng hạn được lưu trong file có cấu trúc như thế nào cũng được, tùy chọn cấu trúc file sao cho thuận lợi cho việc tìm kiếm. Bây giờ cho một tên bất kỳ làm sao tìm được tên sinh viên đó với tốc độ nhanh

    Vì chắc chắn không thể load hết toàn bộ danh sách tên vào bộ nhớ, làm như thế nào đây
    Ai làm được cho 1 chầu cafe ở tpHCM,

  2. #2
    Ngày gia nhập
    11 2007
    Bài viết
    47

    Trích dẫn Nguyên bản được gửi bởi nguyentuan2 Xem bài viết
    Tui có 1 triệu record là tên các cty hoặc người chẳng hạn được lưu trong file có cấu trúc như thế nào cũng được, tùy chọn cấu trúc file sao cho thuận lợi cho việc tìm kiếm. Bây giờ cho một tên bất kỳ làm sao tìm được tên sinh viên đó với tốc độ nhanh

    Vì chắc chắn không thể load hết toàn bộ danh sách tên vào bộ nhớ, làm như thế nào đây
    Ai làm được cho 1 chầu cafe ở tpHCM,
    Bạn ghi cái đó theo thứ tự tăng dần. Tìm kiếm nhị phân sẽ giảm đáng kể thời gian.
    Nếu 1 tr record, bạn nên chia nhỏ nó vào các file. Như thế cũng sẽ giảm được thời gian và bộ nhớ

  3. #3
    Ngày gia nhập
    09 2006
    Bài viết
    711

    Ừ, sắp xếp tăng dần, rồi dùng memory mapping file API để search, bảo đãm không nhanh không uống cafe của cậu.
    1 triệu thì "xi nhê" gì, hồi xưa tui có đụng 1 project của tụi Nhật, MAX_ULONG record, vậy mà search nhanh đến mức tụi nó ngạc nhiên, mail riêng cho tui hỏi làm sao biết cách đó.
    Độ dài tối đa của name là bao nhiêu, vd tui cho tối đa l2 60 ký tự, lưu dạng binary theo từng block 60 byte, padding = space, phân cách = NULL char, search sẽ nhanh hơn.
    Nhờ dùng memory mapping API mà hồi đó tui viết các hàm read .INI file nhanh hơn các hàm của Windows gần 30 lần, lúc đó tui cũng không tin vào kết quả profiler.
    Đã được chỉnh sửa lần cuối bởi TQN : 12-12-2007 lúc 08:36 AM.

  4. #4
    Ngày gia nhập
    10 2007
    Nơi ở
    HCMUNS
    Bài viết
    459

    Trong .net có cái nào liên quan tới vụ "map gì gì đó" không anh ? Nếu import thì làm chậm chương trình.
    Đã được chỉnh sửa lần cuối bởi nhc1987 : 12-12-2007 lúc 08:57 AM.
    Keep moving forward!

    ... Retired ...

  5. #5
    Ngày gia nhập
    09 2006
    Bài viết
    711

    Hỏi .NET thì anh mù chay à, có biết đâu. Không biết có wrap sẵn hay không. Em dùng Reflector, CodeSearch plugin, search CreateFileMappingA/W thử xem sao.
    À, không có em à, chỉ có wrap cho class internal System.Globalization.MemoryMapFile thôi. Em base trên đó cũng được hay tự viết lại = import API cũng được.

  6. #6
    Ngày gia nhập
    08 2006
    Nơi ở
    TpHCM
    Bài viết
    202

    Mặc định Tìm kiếm như thế nào khi số phần tử rất lớn trong file

    Thực ra mình đang muốn đề cập đến mặt thuật toán, chứ không phải kỹ thuật truy xuất đọc hay ghi

    Tức là mong muốn sẽ giải quyết vấn đề trong cả Linux lẫn Windows, nên tạm thời bỏ qua Mapping File

    Ghi file theo thứ tự records tăng dần cũng là 1 cách, tuy nhiên lưu ý là các record có thể có kích thước khác nhau vì có thuộc tính chuỗi, nên cần có thêm 1 vài xử lý để có thể giải quyết được. Ví dụ như có thể tạo ra 1 file indexer, trong file indexer thì các record có kích thước bằng nhau và mỗi record có chứa offset đến dữ liệu trong file data.

    Giải thuật kinh điển và có vẻ là hay nhất là sử dụng BTree, lưu xuống file BTree.serialize(). Khi build BTree từ file, nó sẽ không load toàn bộ các Node mà load từng phần ví dụ mỗi lần có thể load 3 cấp của cây, khi so sánh rơi vào node lá nào mà vẫn chưa so trùng, thì load tiếp 3 cấp khác của nhánh đó

    Giải thuật dùng BTree này hay dùng trong việc xây dựng hệ quản trị cơ sở dữ liệu, ví dụ MSSQL server 2000 trở lên.
    Sau khi xây dựng giải thuật này áp dụng thêm kỹ thuật Mapping File trong Windows sẽ cho ra kết quả mỹ mãn không ngờ

  7. #7
    Ngày gia nhập
    06 2007
    Nơi ở
    Hà Nội
    Bài viết
    361

    em dùng tìm kiếm nhị phân làm từ điển , chả bao giờ load hết danh sách cả , không hiểu ý của anh , còn việc sắp xếp tăng dần tên á, theo em, không sắp xếp theo kiểu đó , anh chắc thạo cái con trỏ phải không, cái sắp xếp theo thứ tự là vị trí con trỏ chỉ tới tên :4byte - kích thước cố định, phần lưu vị trí này giống hệt mảng con trỏ thôi, search nhị phân thoải mái , không cần block 60 ký tự làm gì cho lãng phí bộ nhớ , còn tên xếp tùm lum cũng kệ , giống như cây nhị phân vậy, sắp xếp thứ tự chỉ là cây, còn dữ liệu thì tùm lum . Làm cái tìm kiếm nhị phân thì code đơn giản hơn cây rất nhiều, dung lượng cũng nhỏ nữa mà tốc độ tìm kiếm hai cái đều như nhau (nếu cây nhị phân cân bằng , còn không thì ).
    Đã được chỉnh sửa lần cuối bởi tienlbhoc : 14-12-2007 lúc 08:41 AM.
    Blog tổng quan kiến thức về viễn thông : http://tongquanvienthong.blogspot.com/

    mSPDict từ điển android hỗ trợ liên kết tra trên các trình đọc sách điện tử và tra sách giấy thông qua camera
    http://www.tinhte.vn/threads/691731/

Các đề tài tương tự

  1. Crop 1 file ảnh ra thành nhiều phần trong C# như thế nào ?
    Gửi bởi kamen1412 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 18-11-2011, 09:06 AM
  2. Mình muốn chỉnh sửa file host trong Win 7 phải làm thế nào .Xin giúp mình với
    Gửi bởi vncoder trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 1
    Bài viết cuối: 30-06-2011, 09:22 AM
  3. tìm kiếm trong file xml trên C# như thế nào
    Gửi bởi thanh06 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 7
    Bài viết cuối: 19-11-2010, 10:56 PM
  4. Tìm kiếm trong File TXT như thế nào?
    Gửi bởi daovthinh trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 14
    Bài viết cuối: 16-11-2010, 10:24 PM
  5. Code tìm kiếm trong cây nhị phân trong C++. Lỗi chỉ tìm được từ đầu tiên trong file thôi sửa thế nào?
    Gửi bởi elvish trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 1
    Bài viết cuối: 11-04-2010, 09:43 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn