Câu hỏi Cải thiện hiệu suất của mô phỏng cuộn chết 7 mặt từ việc thực hiện chết 6 mặt


Trong một Giao dịch cổ phiếu, thuật toán sau đây (dựa trên mã hóa số học) đã được trình bày như là một phương pháp hiệu quả để tạo ra kết quả của một chết 7 mặt, khi tất cả những gì được đưa ra là chết 6 mặt:

int rand7()
{
  static double a=0, width=7;  // persistent state

  while ((int)(a+width) != (int)a)
  {
    width /= 6;
    a += (rand6()-1)*width;
  }

  int n = (int)a;
  a -= n; 
  a *= 7; width *= 7;
  return (n+1);
}

Không phải là một nhà toán học thực sự, tôi sẽ cố hết sức để giải thích cách thuật toán này hoạt động như thế nào:

Khi bắt đầu mỗi cuộc gọi đến rand7(), width là tỷ lệ 7S/ 6ta là một giá trị không âm với thuộc tính a + width nằm trong khoảng [0, 7) sau trường hợp cơ sở. Khi nhập while vòng lặp, width là giá trị tối đa có thể được thêm vào a. Nếu floor(a + width) la khac nhau tư floor(a), sau đó chọn ngẫu nhiên {0, width* 1/6, width* 1/3, width* 1/2, width* 2/3, width* 5/6} được thêm vào avà số mũ t được tăng lên một (giảm giá trị của width bởi sức mạnh của 6). Lưu ý rằng sau khi lặp lại, thuộc tính a + width nằm trong khoảng [0, 7) vẫn bất biến. Khi nào width trở nên nhỏ hơn sự khác biệt của ceil(a) - a, lặp lại dừng lại. Vòng lặp thêm entropy vào a miễn là làm như vậy thực sự có thể ảnh hưởng đến kết quả của cuộn chết, và bằng trực giác, đây là xây dựng một số thực ngẫu nhiên trong phạm vi [0, 7) bằng cách sử dụng cơ số 6. Sau khi rời khỏi vòng lặp, các cuộn chết được thực hiện để được floor(a) + 1a được giảm xuống phần phân đoạn của nó. Tại thời điểm đó a + width nằm trong khoảng [0, 1]. Để chuẩn bị cho cuộc gọi tiếp theo và duy trì bất động sản bất biến, cả hai a và width được nhân rộng bởi hệ số 7 (cho width, điều này làm tăng số mũ s bởi 1).

Ở trên giải thích các hoạt động của bước quy nạp. Phân tích các trường hợp cơ bản là trái như là một bài tập cho người đọc quan tâm.

Tất nhiên, từ quan điểm hiệu quả, việc sử dụng số học dấu phẩy động ngay lập tức bật ra như là một hiệu suất kéo (giả sử hiệu suất của rand6() đã đủ và bản thân nó không thể được cải thiện). Trong khi duy trì thuật toán mã hóa số học này, cách tiếp cận tốt nhất để loại bỏ việc sử dụng dấu phẩy động là gì?


16
2017-08-19 02:15


gốc


Cuộc gọi đến rand() chính nó có lẽ là người tiêu dùng thời gian lớn nhất. - Mysticial
Điểm nổi có lẽ không phải là vấn đề về hiệu suất, nhưng đó là một vấn đề lớn đối với tính chính xác. Nó sẽ thiên vị kết quả. - R..
@jxh double có đủ bit mà nó có thể sẽ không đáng kể thiên vị kết quả. Nhưng nó sẽ thiên vị chúng. Ai sử dụng điều này sẽ có quyết định nếu nó thiên vị kết quả quá nhiều cho việc sử dụng của họ hay không. Hoặc để tôi đặt một cách khác, cho dù sự thiên vị có ý nghĩa hay không, phụ thuộc vào trường hợp sử dụng. - hyde
@ hyde: nó tầm thường để chuyển đổi thành điểm cố định, đặc biệt khi phạm vi của hai biến kép cực kỳ hạn chế. Vì không thể có âm hoặc lớn hơn 7, biểu diễn điểm cố định đơn giản nhất sẽ không được ký 4.60 (3.61 cũng có thể hoạt động, nhưng tôi có một số nghi ngờ về tràn). Với điểm cố định, bổ sung chỉ là bổ sung số nguyên và nhân hoặc chia cho một số nguyên chỉ là phép nhân hoặc chia cho cùng một số nguyên. cast to intLà x>>60và x-floor(x)Là x&((1UL<<60)-1UL). Vì vậy, về cơ bản không có chi phí. Và điều đó mang lại cho bạn thêm một số bit để chơi cùng. - rici
@ watere: Có thể sử dụng width /= 6; thay vì có thể chính xác hơn width += 3; width /= 6; giới thiệu một số thiên vị, nhưng đó là một sự thiên vị trong bit thứ 60 hoặc hơn, mà tôi không nghĩ rằng so sánh với lỗi round-off trong bit thứ 53, như với đôi. Tôi không thấy bất kỳ sự thiên vị có thể nhìn thấy nào với các phiên bản hai điểm hoặc điểm cố định, nhưng tôi không làm bất cứ điều gì phức tạp hơn so với biểu đồ và bản đồ pixel, và tôi không nghi ngờ rằng có sự thiên vị. Về mặt triết học, sai lệch 2 ^ -50 gây phiền nhiễu. Tuy nhiên, trong thực tế, rất khó để phát hiện. - rici


Các câu trả lời:


Theo dõi trên một bình luận tôi đã thực hiện, đây là phiên bản điểm cố định của thuật toán. Nó sử dụng unsigned 4.60 (có nghĩa là, có 60 bit trong phần phân số của số), đó là một vài bit nhiều hơn bạn có thể nhận được ra khỏi một double:

int rand7fixed() {
    static uint64_t a = 0;
    static uint64_t width = 7UL<<60;
    static const uint64_t intmask = 0xfUL<<60;

    while (((a+width)&intmask) != (a&intmask)) {
      width /= 6;
      a += (rand6()-1)*width;
    }

    int n = a >> 60;
    a &=~intmask;
    a *= 7;
    width *= 7;
    return n+1;
}

Ở trên hóa ra là khoảng một phần ba nhanh hơn so với phiên bản kép trong OP (xem kết quả điểm chuẩn và ghi chú dưới đây). Tôi nghi ngờ rằng thời gian thải không phải là số học dấu chấm động, mà là các chuyển đổi từ double đến int.

Như R .. chỉ ra, điều này không khắc phục được sự thiên vị; nó chỉ làm giảm nó. Thuật toán không thiên vị đơn giản và hợp lý nhanh sẽ liên tục tạo ra hai rand6() giá trị h và l cho đến khi ít nhất một trong số họ không khác, và sau đó trở lại h*6+l % 7:

int rand7_2() {
  int hi, lo;
  do {
    hi = rand6() - 1;
    lo = rand6() - 1;
  } while (hi + lo);
  return (hi * 6 + lo) % 7 + 1;
}

Nếu bạn cảm thấy cần phải giảm số lượng cuộc gọi đến rand6, bạn có thể sử dụng thực tế là 612 chỉ hơi hơn 711 để tạo ra 11 cuộn 7 cuộn tại một thời điểm. Nó vẫn còn cần thiết để loại bỏ một số bộ 12 cuộn để loại bỏ sự thiên vị; tần suất của các bộ hủy bỏ sẽ là (612−711)/612), hoặc khoảng 1 trong 11, do đó, trung bình bạn sẽ cần khoảng 1,19 6-cuộn mỗi 7 cuộn. Bạn có thể làm tốt hơn bằng cách sử dụng 25 6-cuộn để tạo ra 23 7-cuộn (1,13 6-cuộn cho mỗi 7-cuộn) nhưng điều đó không hoàn toàn phù hợp với số học 64-bit, do đó, lợi thế cận biên trong các cuộc gọi đến rand6 sẽ được nhai bằng cách thực hiện các phép tính trong 128-bit.

Đây là giải pháp 11/12:

int rand7_12() {
    static int avail = 0;
    static uint32_t state = 0;
    static const uint32_t discard = 7*7*7*7*7*7*7*7*7*7*7; // 7 ** 11
    static const int out_per_round = 11;
    static const int in_per_round = 12;

    if (!avail) {
      do {
        state = rand6() - 1;
        for (int needed = in_per_round - 1; needed; --needed)
          state = state * 6 + rand6() - 1;
      }
      while (state >= discard);
      avail = out_per_round;
    }
    int rv = state % 7;
    state /= 7;
    --avail;
    return rv + 1;
}

Về lý thuyết, bạn có thể giảm tỷ lệ xuống log76, khoảng 1.086. Ví dụ, bạn có thể làm điều đó bằng cách tạo ra 895 7-cuộn từ 972 6-cuộn, loại bỏ khoảng một trong 1600 bộ cho mức trung bình là 1,087 6-cuộn / 7-cuộn, nhưng bạn cần số học 2513-bit để giữ trạng thái.

Tôi đã thử nghiệm tất cả bốn chức năng với một điểm chuẩn không chính xác gọi là rand7 700.000.000 lần và sau đó in một biểu đồ của các kết quả. Kết quả:

                                                  User time with
Algorithm       User time      rand6() calls     cycling rand6()
----------      ---------      -------------     ---------------
double          32.6 secs          760223193           13.2 secs
fixed           29.4 secs          760223194            7.9 secs
2 for 1         40.2 secs         1440004276
12 for 11       23.7 secs          840670008

Việc triển khai rand6 () cơ bản ở trên là thư viện chuẩn của Gnu c ++ uniform_int_distribution<>(1,6) sử dụng mt19937_64 (một Misterenne Twister 64-bit) như một PRNG. Để cố gắng xử lý tốt hơn lượng thời gian dành cho thư viện chuẩn, tôi cũng chạy thử nghiệm bằng cách sử dụng một bộ đếm chu kỳ đơn giản như một bộ tạo số giả ngẫu nhiên; còn lại 13,2 và 7,9 giây đại diện cho (khoảng) thời gian dành cho thuật toán, từ đó chúng ta có thể nói rằng thuật toán điểm cố định nhanh hơn khoảng 40%. (Thật khó để có được đọc tốt về các thuật toán kết hợp vì chuỗi cố định làm cho dự đoán nhánh dễ dàng hơn nhiều và giảm số cuộc gọi rand6, nhưng cả hai đều mất chưa đến 5 giây).

Cuối cùng, các biểu đồ trong trường hợp bất kỳ ai muốn kiểm tra sự thiên vị (cũng bao gồm một chạy với std::uniform_int_distribution(1,7) để tham khảo):

Algorithm          1          2          3          4          5          6          7
---------  ---------  ---------  ---------  ---------  ---------  ---------  ---------
reference  100007522  100002456  100015800  100005923   99972185  100008908   99987206
double     100014597  100005975   99982219   99986299  100004561  100011049   99995300
fixed      100009603  100009639  100034790   99989935   99995502   99981886   99978645
2 for 1    100004476   99997766   99999521  100001382   99992802  100003868  100000185
12 for 11   99988156  100004974  100020070  100001912   99997472   99995015   99992401

11
2017-08-19 05:15



Cảm ơn bạn đã hiển thị triển khai điểm cố định. - jxh
Ngoài ra, linh cảm của tôi là rand7fixed() sẽ tốt hơn rand7b(). - jxh
@ jxh: có lẽ, nhưng nó phụ thuộc vào tốc độ rand6() Là. Đối với phần cứng hiện đại, tôi khuyên bạn nên điểm chuẩn. Hunches thường sai; ít nhất là của tôi. (Linh cảm của tôi là rand7fixed sẽ có tốc độ tương tự như của bạn rand7, nhưng không.) - rici
Tôi đã chắc chắn một phiên bản số học số nguyên sẽ tốt hơn phiên bản điểm nổi (trên x86). Tuy nhiên, tôi thực sự nghĩ rằng thuật toán sử dụng cắt ngắn nổi như một phương tiện để đánh bại sự thiên vị. Đo lường hiệu suất của bạn sẽ còn quan trọng hơn nếu bạn tính chi phí gọi điện rand6() chinh no. - jxh
Ngoài ra, lưu ý rằng đối với rand7b(), rand6() trả về các số trong phạm vi {1..6}, vì vậy việc gán cho hi và lo cũng nên được giảm đi 1. - jxh


[Chỉnh sửa]

Cần phải cải thiện phương pháp dưới xa, nhưng sau đây là một cách đơn giản không thiên vị phương pháp. Nó không hiệu quả như nó gọi rand6() ít nhất hai lần. (Giả định rand6() không thiên vị)

int rand7simple(void) {
  int product;
  do {
    int a = rand6() - 1;
    int b = rand6() - 1;
    product = a*6 + b;  // produce unbiased distributed numbers 0 .. 35
  } while (product >= 35);  // Redo 1 in 36 times
  // produce unbiased distributed numbers 0 .. 34
  return product%7 + 1;
}

Cứ 6 lần gọi tới rand7(), rand6() nên được gọi là 7 lần. Khởi tạo một trạng thái số nguyên rộng để giảm thiểu độ lệch.

Cần kiểm tra điều này sau. GTG.

int rand7(void) {
  static int count = -1;
  static unsigned long long state = 0;
  if (count < 0) {
    count = 0;
    for (int i=0; i<25; i++) {
      state *= 6;
      state += rand6();
    }
  int retval = state % 7;
  state /= 7;

  int i = (count >= 6) + 1; 
  if (++count > 6) count = 0;
  while (i-- > 0) {
    state *= 6;
    state += rand6();
  }
  return retval;
}

4
2017-08-19 03:29



Lưu ý rằng 7 ^ 6 = 117649 nhưng 6 ^ 7 = 279936. IOW 6 cuộn xúc xắc 7 mặt có ít giá trị hơn 7 cuộn xúc xắc 6 mặt. Mã của bạn có tài khoản cho điều đó không? - hyde
@hyde Đã nghĩ về điều đó. Tỷ lệ cuộc gọi đến rand6() có thể có thể được điều chỉnh. Lúc đầu đỏ mặt, có vẻ như 7 trong 6 lần là một chút quá thường xuyên. Gọi quá thường xuyên không phải là một vấn đề, chỉ là một sự kém hiệu quả. Tôi sẽ suy nghĩ nhiều hơn, nhưng tôi hy vọng ý tưởng chung là rõ ràng. Kéo số ra bằng retval = state % 7; state /= 7; và lặp lại với 1 hoặc 2 cuộc gọi đến state *= 6; state += rand6();  Bây giờ tôi phải đi! - chux
Khi bạn có thời gian, tôi hy vọng bạn sửa chữa câu trả lời hoặc ít nhất thêm cảnh báo vào văn bản trả lời. Trực giác, tôi nghĩ state sẽ tràn và quấn, bởi vì dices 6 mặt tăng nó hơn dices 7 mặt giảm nó. Ngẫu nhiên, đây là lý do tại sao mã câu hỏi sử dụng double, đơn giản hơn nhiều để đối phó với điều này hơn với số nguyên. - hyde
Cảm ơn ý tưởng. - jxh
Tôi cũng đã viết mã 6 ^ 12 và 7 ^ 11 để có được đầu ra không thiên vị, nhưng chưa hoàn tất xác nhận trước đó @rici câu trả lời tốt đã được chấp nhận - vì vậy sẽ không thêm nó. Bài học tôi lấy đi từ bài đăng này là việc tạo số ngẫu nhiên không thiên vị là khó khăn để thử mã và chứng minh và thường mất một lượng thời gian hợp lý để đảm bảo gremlins không tồn tại. - chux