hadv
commented
9 years ago Anh hãy cải tiến, chỉ loop theo các cell nằm trong tập hợp currentGeneration => O(N).
A đã cải tiến bằng việc implement code xoay quanh những live cell trong currentGeneration như commit bên dưới. Em xem giúp anh có ok không nhé!
https://github.com/hadv/ConwayGoL/commit/ec3e163f0a98d945ddaf4b15d9966a6d1d945b61
Phần code sau thì anh thấy cũng chưa hoàn toàn tối ưu đâu. Ngày mai anh sẽ xem xét để cái tiến vì có vẻ như đang bị tính toán lặp lại một số phần.
// Check if any dead cells around current live cell will become live cell or not
for (int i = p.getX() - 1; i <= p.getX() + 1; i++) {
for (int j = p.getY() - 1; j <= p.getY() + 1; j++) {
Point pt = new Point(i, j);
if (currentGeneration.get(pt) == null) {
if (countLiveNeighbourCells(pt) == 3) {
tempGeneration.put(pt, LIVE_CELL_VAL);
}
}
}
}Ngoài ra cách làm với BitSet thì anh dùng integer làm index 1 chiều. Cách làm với Map này anh lại chế thêm cái Point làm gì cho nó loằng ngoằng ra. Anh chỉ cần dùng Integer làm key cho Map là được rồi, vừa đơn giản lại tốn ít bộ nhớ.
Phần này anh sẽ làm trong ngày mai Ngọc nhé, hiện tại a vẫn sử dụng Point vì nó dễ hiểu hơn cách dùng index theo 1 chiều.
Sau khi cải tiến xong, anh hãy viết ra cái discussion là 2 biến thể này sẽ ảnh hưởng đến bài làm của anh như thế nào. Cho đến giờ anh làm theo biến thể 1, nếu làm theo biến thể 2 thì dự là anh sẽ cần sửa code như thế nào? Nếu máu me thì anh code thử luôn, còn k thì xong bài này mình sẽ sang tiếp bài khác.
OK Ngọc, sau khi hoàn thành code theo biến thể số 1 thì mình sẽ quyết định có làm tiếp biến thể số 2 hay làm bài khác nhé. biến thế số 2 có ít tương đồng với việc anh đã implement nhầm theo hướng sử dụng gridMap nhỉ? :smile:
ngocdaothanh
https://github.com/hadv/ConwayGoL/blob/bee65bd69cbfe18eebcb2a886a55a56c8877da31/src/com/company/ConwayGOL.java
Nhận xét code
Người pv chưa cần soi kĩ, chỉ cần nhìn thoáng thấy code anh viết thấy có 2 vòng lặp lồng vào nhau thế này là cho anh điểm trừ luôn rồi, vì code này k phản ánh được tinh thần là "sparse" mà cách làm dùng
Maphướng đến:Tại vì nó vẫn cố vét cạn hết các cell nằm trong hình chữ nhật => O(N^2).
Anh hãy cải tiến, chỉ loop theo các cell nằm trong tập hợp
currentGeneration=> O(N).Ngoài ra cách làm với
BitSetthì anh dùng integer làm index 1 chiều. Cách làm vớiMapnày anh lại chế thêm cáiPointlàm gì cho nó loằng ngoằng ra. Anh chỉ cần dùngIntegerlàm key choMaplà được rồi, vừa đơn giản lại tốn ít bộ nhớ.Ghi chú về các trạng thái của cell:
Bài này có 2 biến thể chính:
Sau khi cải tiến xong, anh hãy viết ra cái discussion là 2 biến thể này sẽ ảnh hưởng đến bài làm của anh như thế nào. Cho đến giờ anh làm theo biến thể 1, nếu làm theo biến thể 2 thì dự là anh sẽ cần sửa code như thế nào? Nếu máu me thì anh code thử luôn, còn k thì xong bài này mình sẽ sang tiếp bài khác.