Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 31.626 phút đọc

Bitset lớn và ứng dụng

Sau bài này bạn sẽ làm được

  • Cài bitset hỗ trợ hàng triệu bit bằng mảng số nguyên
  • Tính chỉ số từ và vị trí bit từ chỉ số bit
  • Cài sàng Eratosthenes bằng bitset và đo bộ nhớ tiết kiệm
  • Đếm số bit bật trong cả bitset

Một mảng mười triệu giá trị đúng sai tốn mười megabyte nếu dùng char, và một phẩy hai megabyte nếu dùng bit. Bài này cài bitset, rồi đo xem tiết kiệm tám lần bộ nhớ đổi lại được gì về tốc độ.

#Một bit thay cho một byte

Bitset
Mảng giá trị đúng sai được gói vào từng bit của một mảng số nguyên. Bit thứ i nằm ở từ thứ i / 64, tại vị trí i % 64.
Cách lưuBộ nhớ cho 10 triệu giá trịSo với bitset
uint64_t bitset1,25 MB1x
unsigned char10 MB8x
int40 MB32x
bool trong C, tức _Bool10 MB8x
terminal
./bitset --bo-nho
bitset 10000000 bit  : 1250000 byte
mang char       : 10000000 byte
mang int        : 40000000 byte
ty le tiet kiem : 8x so voi char, 32x so voi int

#Cài đặt

bitset.h
#ifndef BITSET_H
#define BITSET_H

#include <stddef.h>
#include <stdint.h>

typedef uint64_t Tu;

#define BIT_MOI_TU  (sizeof(Tu) * 8)
#define SO_TU(n)    (((n) + BIT_MOI_TU - 1) / BIT_MOI_TU)

typedef struct {
    Tu    *tu;
    size_t so_bit;
} BitSet;

int    bs_tao(BitSet *b, size_t n);
void   bs_huy(BitSet *b);

void   bs_bat(BitSet *b, size_t i);
void   bs_tat(BitSet *b, size_t i);
void   bs_dao(BitSet *b, size_t i);
int    bs_kiem(const BitSet *b, size_t i);

void   bs_bat_het(BitSet *b);
void   bs_xoa_het(BitSet *b);
size_t bs_dem(const BitSet *b);

#endif /* BITSET_H */
bitset.c
#include <stdlib.h>
#include <string.h>

#include "bitset.h"

int bs_tao(BitSet *b, size_t n) {
    if (n > SIZE_MAX - BIT_MOI_TU + 1) return -1;      /* chong tran */

    b->tu     = calloc(SO_TU(n), sizeof *b->tu);       /* calloc: moi bit bang 0 */
    b->so_bit = n;

    return b->tu ? 0 : -1;
}

void bs_huy(BitSet *b) {
    free(b->tu);
    b->tu     = NULL;
    b->so_bit = 0;
}

void bs_bat(BitSet *b, size_t i) {
    b->tu[i / BIT_MOI_TU] |= (Tu)1 << (i % BIT_MOI_TU);
}

void bs_tat(BitSet *b, size_t i) {
    b->tu[i / BIT_MOI_TU] &= ~((Tu)1 << (i % BIT_MOI_TU));
}

void bs_dao(BitSet *b, size_t i) {
    b->tu[i / BIT_MOI_TU] ^= (Tu)1 << (i % BIT_MOI_TU);
}

int bs_kiem(const BitSet *b, size_t i) {
    return (b->tu[i / BIT_MOI_TU] >> (i % BIT_MOI_TU)) & 1u;
}

void bs_bat_het(BitSet *b) {
    memset(b->tu, 0xFF, SO_TU(b->so_bit) * sizeof *b->tu);
}

void bs_xoa_het(BitSet *b) {
    memset(b->tu, 0x00, SO_TU(b->so_bit) * sizeof *b->tu);
}

size_t bs_dem(const BitSet *b) {
    size_t c = 0;

    for (size_t i = 0; i < SO_TU(b->so_bit); ++i)
        c += (size_t)__builtin_popcountll(b->tu[i]);

    return c;
}
terminal
./bitset --chi-so
  bit  0 -> tu 0, vi tri  0
  bit  1 -> tu 0, vi tri  1
  bit  2 -> tu 0, vi tri  2
  bit 63 -> tu 0, vi tri 63
  bit 64 -> tu 1, vi tri  0
  bit 65 -> tu 1, vi tri  1

#Sàng Eratosthenes

sang.c
#include <stdio.h>

#include "bitset.h"

int main(void) {
    const size_t N = 10000000;

    BitSet s;

    if (bs_tao(&s, N + 1) != 0) return 1;

    /* Gia dinh moi so tu 2 tro len la nguyen to */
    for (size_t i = 2; i <= N; ++i) bs_bat(&s, i);

    /* Voi moi so nguyen to i, tat moi boi cua no */
    for (size_t i = 2; i * i <= N; ++i)
        if (bs_kiem(&s, i))
            for (size_t j = i * i; j <= N; j += i)
                bs_tat(&s, j);

    printf("so nguyen to <= %zu : %zu\n", N, bs_dem(&s));

    bs_huy(&s);

    return 0;
}
terminal
gcc -std=c11 -O2 -o sang sang.c bitset.c && ./sang
thoi gian : 0.033 giay
so nguyen to <= 10000000 : 664579
5 so dau  : 2 3 5 7 11

#Đo bộ nhớ và tốc độ

terminal
# Sàng tới một trăm triệu, hai cách lưu
gcc -std=c11 -O2 -o so-sanh so-sanh.c && ./so-sanh
mang char : 0.852 giay, 5761455 so nguyen to, 95 MB
bitset    : 0.427 giay, 5761455 so nguyen to, 11 MB
NBộ nhớ charBộ nhớ bitsetNhanh hơn
1 triệu1 MB0,12 MBGần như nhau, cả hai vừa bộ nhớ đệm
10 triệu10 MB1,25 MBBitset nhanh hơn chút
100 triệu95 MB11 MBBitset nhanh gấp đôi
1 tỉ954 MB119 MBBitset nhanh hơn nhiều
Con số tùy CPU và kích thước bộ nhớ đệm. Hãy tự đo trên máy bạn.

#Bốn thao tác mở rộng

Một: hợp, giao, hiệu của hai tập

/* Ba ham nay xu ly 64 gia tri moi vong lap */

void bs_hop(BitSet *a, const BitSet *b) {
    for (size_t i = 0; i < SO_TU(a->so_bit); ++i) a->tu[i] |= b->tu[i];
}

void bs_giao(BitSet *a, const BitSet *b) {
    for (size_t i = 0; i < SO_TU(a->so_bit); ++i) a->tu[i] &= b->tu[i];
}

void bs_hieu(BitSet *a, const BitSet *b) {
    for (size_t i = 0; i < SO_TU(a->so_bit); ++i) a->tu[i] &= ~b->tu[i];
}

/* Voi mang char thi ba ham nay xu ly MOT gia tri moi vong.
   Day la cho bitset thang tuyet doi: nhanh hon 64 lan,
   va gcc con vector hoa duoc thanh 256 hoac 512 bit moi lenh. */

Hai: duyệt các bit đang bật

/* Duyet NGAY tung bit bat, khong duyet bit tat */
void bs_duyet(const BitSet *b, void (*f)(size_t, void *), void *ctx) {
    for (size_t t = 0; t < SO_TU(b->so_bit); ++t) {
        Tu w = b->tu[t];

        while (w) {
            int n = __builtin_ctzll(w);          /* bit 1 thap nhat */

            f(t * BIT_MOI_TU + (size_t)n, ctx);

            w &= w - 1;                          /* xoa bit do */
        }
    }
}

/* Voi mot bitset 10 trieu bit ma chi co 1000 bit bat, vong lap
   nay chay 1000 lan cong voi so lan duyet tu, thay vi 10 trieu lan.

   Bai 31.5 da gioi thieu ca hai ky thuat: ctz de tim bit thap nhat,
   va x & (x-1) de xoa no. */

Ba: tìm bit bật đầu tiên từ một vị trí

/* Tra ve chi so bit bat dau tien tu vi tri tu tro di,
   hoac so_bit neu khong con bit nao bat. */
size_t bs_tim_tiep(const BitSet *b, size_t tu) {
    if (tu >= b->so_bit) return b->so_bit;

    size_t t = tu / BIT_MOI_TU;

    /* Che bo cac bit truoc vi tri tu trong tu dau tien */
    Tu w = b->tu[t] & (~(Tu)0 << (tu % BIT_MOI_TU));

    while (1) {
        if (w) {
            size_t k = t * BIT_MOI_TU + (size_t)__builtin_ctzll(w);

            return k < b->so_bit ? k : b->so_bit;
        }

        if (++t >= SO_TU(b->so_bit)) return b->so_bit;

        w = b->tu[t];
    }
}

/* Dung: */
for (size_t i = bs_tim_tiep(&s, 0); i < s.so_bit; i = bs_tim_tiep(&s, i + 1))
    xu_ly(i);

Bốn: đếm bit bật trong một khoảng

size_t bs_dem_khoang(const BitSet *b, size_t dau, size_t cuoi) {
    if (dau >= cuoi) return 0;

    size_t t_dau = dau  / BIT_MOI_TU;
    size_t t_cuoi = (cuoi - 1) / BIT_MOI_TU;

    if (t_dau == t_cuoi) {                       /* nam gon trong mot tu */
        Tu che = (~(Tu)0 << (dau % BIT_MOI_TU))
               & (~(Tu)0 >> (BIT_MOI_TU - 1 - ((cuoi - 1) % BIT_MOI_TU)));

        return (size_t)__builtin_popcountll(b->tu[t_dau] & che);
    }

    size_t c = (size_t)__builtin_popcountll(
                   b->tu[t_dau] & (~(Tu)0 << (dau % BIT_MOI_TU)));

    for (size_t i = t_dau + 1; i < t_cuoi; ++i)
        c += (size_t)__builtin_popcountll(b->tu[i]);

    c += (size_t)__builtin_popcountll(
             b->tu[t_cuoi]
             & (~(Tu)0 >> (BIT_MOI_TU - 1 - ((cuoi - 1) % BIT_MOI_TU))));

    return c;
}

Tự làm thử

  1. Cài BitSet đầy đủ và kiểm sáu hàm cơ bản với bit 0, 63, 64, 65.
  2. Chạy sàng Eratosthenes tới mười triệu và so kết quả với bảng số nguyên tố.
  3. So bộ nhớ và tốc độ của bitset với mảng char ở N một triệu, mười triệu, một trăm triệu.
  4. Cài bản sàng chỉ lưu số lẻ và xác nhận nó cho cùng kết quả với một nửa bộ nhớ.
  5. Cài bs_duyet dùng ctzll và đo nó với một bitset thưa.
  6. Cài bs_dem_khoang rồi kiểm nó với bản ngây thơ trên mọi cặp chỉ số nhỏ hơn 200.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

  • Bitset gói tám giá trị đúng sai vào một byte, tiết kiệm tám lần so với char và ba mươi hai lần so với int.
  • Bit thứ i nằm ở từ i / 64, vị trí i % 64, và phải ép (Tu)1 trước khi dịch.
  • Với dữ liệu lớn, bitset nhanh hơn mảng thường, và lý do là bộ nhớ đệm chứ không phải phép toán.
  • Với dữ liệu nhỏ vừa bộ nhớ đệm thì bitset chậm hơn, nên phải đo trước khi chọn.
  • Hợp, giao và hiệu của hai tập xử lý sáu mươi tư giá trị mỗi lệnh, và đó là chỗ bitset thắng tuyệt đối.