0
Bitset có nhanh hơn mảng bool trong c++ không?
Mọi người ơi em đang cố gắng để tối ưu sàng nguyên tố eratothenes trong C++ và sau khi tham khảo một số nguồn tin trên google, facebook..v..v.... Thì e biết được là dùng bitset sẽ chiếm ít bộ nhớ và có tốc độ nhanh hơn, em cũng thử code sàng với bitset và thao tác bit thì nó chạy chậm hơn sàng thường sử dụng mảng bool 2 lần.
Code: //code này em bỏ qua sét số chẵn
const int limit = 1e8 + 8;
uint64_t p[limit / 64 + 11];
bool test(int idx) {
return (p[idx / 64] & (1ULL<<(idx % 63))) == 0;
}
void mark(int idx) {
p[idx / 64] |= (1ULL<<(idx % 63));
}
void sieve() {
mark(0);
mark(1);
for (int i = 3; i * i < limit; i += 2) {
if (test(i)) {
for (int j = i * i; j < limit; j += i * 2) {
mark(j);
}
}
}
}
Em muốn hỏi:
- Có phải bitset thật sự nhanh hơn mảng bool không?
- Nếu bitset nhanh hơn mảng bool, vậy tại sao em code thời gian chạy lại lâu hơn?
- Cách fix?
Thêm một bình luận
1 CÂU TRẢ LỜI
0
Do các hàm test và mark sai địa chỉ, dẫn đến thuật toán chạy liên tục mà không loại bỏ được nhiều phần tử.
1ULL<<(idx % 63) phải là 1ULL<<(idx % 64) (63 sẽ sai với idx = 63)
Một số điểm cần tối ưu:
- Xác định chỉ test số lẻ, có thể chỉ tạo mảng số lẻ sẽ tiết kiệm bộ nhớ.
- i * i < limit => tính trước sqrt(limit)
- Trước hàm mark có thể tối ưu hơn nữa:
// bằng cách này, mình chỉ truy xuất bộ nhớ 1 lần, các tính toán hoàn toàn nằm trong cpu
// cách cũ, mỗi lần gọi hàm mark, cpu đọc lại từ bộ nhớ ô nhớ thứ j / 64
uint64_t marked;
uint64_t j;
for (j = i * i; j < limit; j += i * 2) {
marked |= 1ULL<<(j % 64);
}
p[j / 64] = marked;
PS: phần tối ưu hàm mark chưa đúng và không hiểu quả với i > 31
