VImask
Senior Member
Hên quá mình code mobile toàn gọi Api nên k dính cái này. Chắc làm thợ code thôi
via theNEXTvoz for iPhone
via theNEXTvoz for iPhone
thắc mắc [Học tập] Toán Rời Rạc trong cuộc đời lập trình viên
- Thread starter cuuthu
- Start date
Cryolite.2
Member
Hồi đi học OOP thì thầy mình mới bảo chả nhớ gì kiến thức của mấy môn toán ngày xưa học nữa, mà chắc mình nghĩ lúc làm thì người ta chả còn để ý nó là toán nữa 
(Em xin lỗi thầy T*** A** nhiều lắm, bài thi cuối kỳ tụi em chả ra gì
)
(Em xin lỗi thầy T*** A** nhiều lắm, bài thi cuối kỳ tụi em chả ra gì
)
ductam125
Senior Member
Quyển này hả anh? Nó hơn 800 trang mà
7a2vodoi
Senior Member
Cuốn này giờ còn ở đâu bán không bác, hay còn sách cũ thôi ạ.
Thấy trên mạng có PDF nhưng mà vẫn thích mua sách hơn
Chả hiểu sao bị miss noti.
Không hề tốt tí nào, chi phí để tìm là quá lớn, và kinh khủng nhất là khi cái dict kia được update
Last edited:
Thím thông não giúp em chỗ này với ạ
ductam125
Senior Member
Giờ mua sách cũ đã khó rồi anh ạ, sách mới chắc ko tìm dc đâuCuốn này giờ còn ở đâu bán không bác, hay còn sách cũ thôi ạ.
Thấy trên mạng có PDF nhưng mà vẫn thích mua sách hơn
Thím thông não giúp em chỗ này với ạ
Bản chất của các loại tree là mỗi node có một danh sách con trỏ, những con trỏ này là trỏ đến một node khác. Địa chỉ bộ nhớ các node không liên tục mà rải rác nên không tận dụng tốt CPU Cache, vì cache có đặc tính Spatial locality, khi load giá trị trong RAM tại một địa chỉ thì nó cũng tự động prefetch một số ô nhớ gần đó để đưa vào cache. Linked list cũng có tính chất tương tự tree, cho nên mới có lời khuyên là nên ưu tiên dùng array, khi không dùng được thì tìm cách convert về array.
Đoạn sau là đang giả sử tình huống tệ nhất, tất các các phép reference đến node con trong trie đều miss cache, phải load lại từ đầu trong RAM ra, một lần như vậy mất khoảng 150 - 200 CPU cycle.
lamson_2372007
Đã tốn tiền
Thread hay mình bookmark phát 
7a2vodoi
Senior Member
DaiSuThichAnMan
Member
Lập trình viên nên thở ra mấy câu dạng "pointer is mah bitch" chứ đừng tránh nó phen àRa trường anh đi làm code C++ được bao nhiêu năm mà cứ tỏ ra nguy hiểm thế
Giờ ở Tây môn Low Level Programming tức dạy về Pointer của C++ họ dạy ở năm gần cuối chứ không phải dạy ngay từ đầu như Việt Nam
))
NobiEmon
Senior Member
em mới tốt nghiệp cao đẳng, đang chờ liên thông đại học nhưng sợ ngộp toán nên quyết định học qua trước khi đến trường, list thím liệt kê ở trên là đầy đủ và đúng thứ tự đúng ko ạMới ngó qua mục lục của cuốn toán rời rạc thì thấy cái chủ đề nào cũng là những cái ngày xưa học mòn, và giờ nghĩ là cũng khá cần thiết đó.
Chương 1: Logic, Tập hợp và Hàm
Chương 2: Thuật toán, các số nguyên và ma trận -> bắt buộc phải học
Chương 3: Suy luận toán học
Chương 4: Đếm các phần tử
Chương 5: Kĩ thuật đếm cao cấp
Chương 6: Quan hệ
Chương 7: Đồ thị -> bắt buộc phải học
Chương 8: Cây -> bắt buộc phải học
Chương 9: Đại số boole -> bắt buộc phải học
Chương 10: Mô hình toán
Mà để học dc chương 7 8 9 thì sẽ cần kiến thức của các chương trước
em mới tốt nghiệp cao đẳng, đang chờ liên thông đại học nhưng sợ ngộp toán nên quyết định học qua trước khi đến trường, list thím liệt kê ở trên là đầy đủ và đúng thứ tự đúng ko ạ
List theo sách nên thứ tự mình nghĩ là chuẩn đấy bạn ạ.
NobiEmon
Senior Member
à thím cho em hỏi thêm ở hẹ đại học có cả thảy là bao nhiêu loại toán vậy, tại thấy cái gì mà cao cấp rồi lại rời rạc rồi lại xác xuất
à thím cho em hỏi thêm ở hẹ đại học có cả thảy là bao nhiêu loại toán vậy, tại thấy cái gì mà cao cấp rồi lại rời rạc rồi lại xác xuấtnên thấy lộn xộn quá, thím có thể cụ thể cho em biết được không ạ
Toán rời rạc, giải tích, đại số.
Bảo chia loại toán thì mình cũng ko rõ, chắc là tùy theo giáo án của từng trường.
Giải tích và đại số thì dễ hiểu rồi.
Còn toán rời rạc thì kiểu nó là tên chung của các ngành toán mà đối tương là các tập hợp rời rạc, và là cơ sở cho khoa học máy tính, ví dụ như lý thuyết đồ thị, mật mã học, lý thuyết tính toán, v.v...
Xác suất thống kê thì cũng quan trọng, liên quan tới máy học, AI các kiểu sau này.
Toán cao cấp nếu mình nhớ ko nhầm là học giải tích với đại số, ma trận các kiểu thì phải. Lâu quá nên ko nhớ chính xác.
NobiEmon
Senior Member
thanks thím
Billr_rizer
Junior Member
Tính thì cũng không nhiều lắm, với các ngành khác ngành Toán nói chung thì chung quy lại có Giải tích (1, 2 ,3), Đại số tuyến tính (khác với Cấu trúc đại số), Toán rời rạc, Phương pháp tính, Xác suất thống kê. Phương pháp tính là môn dạy giải toán bằng các phương pháp số, khác với các phương pháp giải tích (mấy cái thuật toán chia đôi, Newton,... là các phương pháp giải số phương trình).à thím cho em hỏi thêm ở hẹ đại học có cả thảy là bao nhiêu loại toán vậy, tại thấy cái gì mà cao cấp rồi lại rời rạc rồi lại xác xuấtnên thấy lộn xộn quá, thím có thể cụ thể cho em biết được không ạ
Mấy ông học bên Toán thì học nhiều hơn, thêm Cấu trúc đại số, giải tích hàm, giải tích số (môn này thay cho và rộng hơn Phương pháp tính bên trên), giải tích phức, PDE (ông nào học cơ khí, điện,... sẽ biết), tối ưu, mô hình ngẫu nhiên (BESTTTTTTT),...
Bên SP Toán học còn nhiều hơn, chưa có dịp trải nghiệm nên không biết như nào
Cá nhân mình thấy học mấy môn này cũng hay, thím nào mà giỏi code học mấy môn toán này, code xong sau dùng đc nhiều chỗ lắm
Bác cho em hỏi thếm mấy cái này được không ạ
Ngày xưa em dốt OS lắm 
Mấy cái tree này nó không có cơ chế như TLB (Translation lookaside buffer) của RAM hả bác? Theo em nghĩ nó có thể implement 1 cái như multi indexing trong DBMS để tránh việc miss cache mà nhỉ?
Tại sao dùng Array lại tận dụng tốt cache hơn ạ?
Với lại sao bác tính được là khoảng 150-200 CPU cycle được ạ
Bác cho em hỏi thếm mấy cái này được không ạ
Mấy cái tree này nó không có cơ chế như TLB (Translation lookaside buffer) của RAM hả bác? Theo em nghĩ nó có thể implement 1 cái như multi indexing trong DBMS để tránh việc miss cache mà nhỉ?
Tại sao dùng Array lại tận dụng tốt cache hơn ạ?
Với lại sao bác tính được là khoảng 150-200 CPU cycle được ạ
TLB là để cache lại quá trình translate từ địa chỉ ảo sang địa chỉ vật lý, còn giá trị tại các ô nhớ thì là ở CPU Cache (L1/L2/L3).
Về cơ bản một cài đặt tree kiểu bình thường là như này: allocate một node X tại địa chỉ A, rồi allocate node Y tại địa chỉ B,... Vì các phép allocate là riêng biệt tách rời nhau nên tùy vào thuật toán cụ thể mà A với B có thể có giá trị cách xa nhau trong không gian bộ nhớ.
Trong trường hợp đó, khi truy cập node X, cpu sẽ prefetch bộ nhớ tại địa chỉ A và các địa chỉ lân cận vào cache. Nếu cache mà hết thì sẽ phải xoá (evict) bớt những mục cũ đưa xuống cache level thấp hơn, từ L1 xuống L2, L2 xuống L3, nếu bị xoá khỏi L3 thì tức không còn trong cache.
Sau đó, đến lúc truy cập vào Y tại địa chỉ B, vì A B cách xa nhau nên nhiều khả năng là B sẽ không tìm thấy trong cache, hoặc chỉ có ở cache level thấp. Khi đó CPU lại phải load lại giá trị của ô nhớ B từ RAM vào.
Vì thế cho nên mới nói tree thường dùng cache không hiệu quả. Với array thì khác, các element của nó được lưu ở các địa chỉ liên tục, lại kích thước nhỏ (không phải lưu địa chỉ của node khác trong array) nên khi truy cập tuần tự khả năng một node đã có trong cache là rất cao.
Tất nhiên vẫn có cách tối ưu hóa tree, nếu biết được access pattern của các node trong tree thì có thể viết custom allocator để sao cho các node thường được truy cập liên tiếp ở gần nhau trong bộ nhớ.
150 - 200 CPU cycle là latency của phép truy cập bộ nhớ RAM từ CPU. Giả sử CPU 4 GHz thì thời gian tuyệt đối là 50 ns. Con số này khoảng mấy chục năm nay chưa được cải thiện mấy.
Đoạn trên mình đã bỏ qua phần địa chỉ ảo - địa chỉ vật lý để cho đơn giản, đem vào thì vấn đề còn phức tạp hơn. Vì thực tế memory được chia thành từng page kích thước chuẩn là 4KB, nếu địa chỉ nằm trong cùng một page ảo thì nó sẽ mới thực sự gần nhau về mặt vật lý. Nhưng nếu thuộc 2 page khác nhau thì không, khi vượt qua page boundary thì vẫn phải fetch lại từ RAM như thường, và có thể còn tốn hơn vì có thể lúc đó TLB cache cũng bị miss. Cho nên hiện nay có khái niệm Huge Pages, tức là page kích thước lớn, khoảng 2MB hoặc 1GB, nhiều ứng dụng nhất là database cho phép cấu hình sử dụng hugepage để tự mình nó quản lý bộ nhớ, giảm vấn đề như trên.
Sent from Xiaomi Redmi 5A using vozFApp
Similar threads
