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
2 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
Phần % 63 là một số sai sót của mình, đáng lẽ phải là 64. Mình sẽ thử lại tối ưu hàm mark
Mình đã thử lại với các góp ý của bạn và thực sự nó không giúp tăng tốc độ. Không biết là bitset có thực sự tăng tốc độ không mình rất thắc mắc, vì tìm kiếm ở đâu cũng thấy là bitset có tốc độ nhanh hơn mảng bool trong khi mình chạy thực tế lại không như vậy
0
#include <time.h>
const int limit = 1e8 + 8;
long long 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 (long long j = i * i; j < limit; j += i * 2) {
mark(j);
}
}
}
}
#define ri register int
void sieve2() {
ri pSize = limit / 64 + 11;
for(ri i=0; i<pSize; ++i) {
p[i] = 0;
}
register long long* pNum = p;
for (ri i = 3; i < limit; i+=2) {
if (*pNum & (1ULL << (i & 0xff)) == 0) {
for (ri j = i + i; j < limit; j += i) {
p[j >> 8] |= (1ULL<<(j & 0xff));
}
}
if(i & 0xff == 0) {
pNum++;
}
}
}
int main() {
clock_t start = clock();
sieve();
printf("%ld\n", clock() - start);
start = clock();
sieve2();
printf("%ld\n", clock() - start);
getchar();
return 0;
}
- Có thể tối ưu bằng cách sử dụng thanh ghi (register).
- Phép chia cho 64 có thể thay bằng dịch 8 bit sang phải.
- Chia lấy dư cho 64 có thể sử dụng phép và bit với 255 (
& 0xff). - Có thể loại các trường hợp số chia hết cho 2.
- Sử dụng
pNumđể duyệt từng phần tử của mảngp, tránh mỗi lần lại tìm lại phần tử theo chỉ số. - Còn việc tính đến sqrt(limit) thì mình không chắc có đúng không, vì nếu chỉ lấy đến sqrt(limit) thì khai báo limit ngay từ đầu được rồi, cần gì làm limit cho thừa.
hình như hàm sieve2 của bạn bị sai, mình thử in ra bitset của mảng p thì tất cả đều bằng 0. Mình cũng mong bạn giải đáp bitset có thực sự tăng tốc độ không. và nếu tối ưu thì mình mong bạn chỉ tối ưu về phần xử lí bit và không thay đổi những cái khác để mình dễ so sánh
#include <stdio.h>
#include <time.h>
const int limit = 1e8 + 8;
uint64_t p[limit / 64 + 11];
bool test(int idx) {
return (p[idx >> 6] & (1ULL<<(idx & 63))) == 0;
}
void mark(int idx) {
p[idx >> 6] |= (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);
}
}
}
}
bool p4[limit + 11] = {false};
bool test4(int idx) {
return p4[idx] == false;
}
void mark4(int idx) {
p4[idx] = true;
}
void sieve4() {
mark4(false);
mark4(true);
for (int i = 3; i * i < limit; i += 2) {
if (test4(i)) {
for (int j = i * i; j < limit; j += i * 2) {
mark4(j);
}
}
}
}
int main() {
const int MAX_TRY = 1;
clock_t start, end;
start = clock();
for(int i=0; i<MAX_TRY; ++i) {
sieve4();
}
end = clock();
printf("sieve bool: %ld ms\n", end - start);
start = clock();
for(int i=0; i<MAX_TRY; ++i) {
sieve();
}
end = clock();
printf("sieve: %ld ms\n", end - start);
return 0;
}
sieve bool: 727587 ms
sieve: 324367 ms
Link test: https://onecompiler.com/cpp/42sr7zes4
