Lisp nguyên mẫu:
(declaim (optimize (speed 3) (safety 0)))
(defun bit-transpose (a)
(declare (type (simple-array unsigned-byte 1) a))
(let ((b (make-array 8 :element-type '(unsigned-byte 8))))
(dotimes (j 8)
(dotimes (i 8)
(setf (ldb (byte 1 i) (aref b j))
(ldb (byte 1 j) (aref a i)))))
b))
Đây là cách bạn có thể chạy mã:
#+nil
(bit-transpose (make-array 8 :element-type 'unsigned-byte
:initial-contents '(1 2 3 4 5 6 7 8)))
;; => #(85 102 120 128 0 0 0 0)
Thỉnh thoảng tôi tháo rời mã để kiểm tra xem không có cuộc gọi không cần thiết nào với các chức năng an toàn.
#+nil
(disassemble #'bit-transpose)
Đây là điểm chuẩn. Chạy chức năng thường xuyên đủ để xử lý hình ảnh HDTV (nhị phân).
#+nil
(time
(let ((a (make-array 8 :element-type 'unsigned-byte
:initial-contents '(1 2 3 4 5 6 7 8)))
(b (make-array 8 :element-type 'unsigned-byte
:initial-contents '(1 2 3 4 5 6 7 8))))
(dotimes (i (* (/ 1920 8) (/ 1080 8)))
(bit-transpose a))))
Điều đó chỉ mất 51ms. Lưu ý rằng tôi đang bảo vệ khá nhiều bởi vì hàm này phân bổ các mảng 8 byte mới tất cả thời gian. Tôi chắc rằng một triển khai trong C có thể được tinh chỉnh nhiều hơn nữa.
Evaluation took:
0.051 seconds of real time
0.052004 seconds of total run time (0.052004 user, 0.000000 system)
101.96% CPU
122,179,503 processor cycles
1,048,576 bytes consed
Dưới đây là một số trường hợp thử nghiệm hơn:
#+nil
(loop for j below 12 collect
(let ((l (loop for i below 8 collect (random 255))))
(list l (bit-transpose (make-array 8 :element-type 'unsigned-byte
:initial-contents l)))))
;; => (((111 97 195 202 47 124 113 164) #(87 29 177 57 96 243 111 140))
;; ((180 192 70 173 167 41 30 127) #(184 212 221 232 193 185 134 27))
;; ((244 86 149 57 191 65 129 178) #(124 146 23 24 159 153 35 213))
;; ((227 244 139 35 38 65 214 64) #(45 93 82 4 66 27 227 71))
;; ((207 62 236 89 50 64 157 120) #(73 19 71 207 218 150 173 69))
;; ((89 211 149 140 233 72 193 192) #(87 2 12 57 7 16 243 222))
;; ((97 144 19 13 135 198 238 33) #(157 116 120 72 6 193 97 114))
;; ((145 119 3 85 41 202 79 134) #(95 230 202 112 11 18 106 161))
;; ((42 153 67 166 175 190 114 21) #(150 125 184 51 226 121 68 58))
;; ((58 232 38 210 137 254 19 112) #(80 109 36 51 233 167 170 58))
;; ((27 245 1 197 208 221 21 101) #(239 1 234 33 115 130 186 58))
;; ((66 204 110 232 46 67 37 34) #(96 181 86 30 0 220 47 10)))
Bây giờ tôi thực sự muốn xem cách mã của tôi so với Andrejs Cainikovs' giải pháp C (Chỉnh sửa: Tôi nghĩ rằng nó sai):
#include <string.h>
unsigned char bytes_in[8]={1,2,3,4,5,6,7,8};
unsigned char bytes_out[8];
/* please fill bytes_in[] here with some pixel-crap */
void bit_transpose(){
memset(bytes_out, 0, 8);
int i,j;
for(i = 0; i < 8; i++)
for(j = 0; j < 8; j++)
bytes_out[i] = (bytes_out[i] << 1) | ((bytes_in[j] >> (7 - i)) & 0x01);
}
int
main()
{
int j,i;
for(j=0;j<100;j++)
for(i=0;i<(1920/8*1080/8);i++)
bit_transpose();
return 0;
}
Và đo điểm chuẩn:
[email protected]:~/0803/so$ gcc -O3 trans.c
[email protected]:~/0803/so$ time ./a.out
real 0m0.249s
user 0m0.232s
sys 0m0.000s
Mỗi vòng lặp trên hình ảnh HDTV mất 2,5 mili giây. Đó là khá nhanh hơn rất nhiều so với Lisp không được tối ưu hóa của tôi.
Đáng tiếc là mã C không cho kết quả tương tự như lisp của tôi:
#include <stdio.h>
int
main()
{
int j,i;
bit_transpose();
for(i=0;i<8;i++)
printf("%d ",(int)bytes_out[i]);
return 0;
}
[email protected]:~/0803/so$ ./a.out
0 0 0 0 1 30 102 170
Vì vậy, câu trả lời phải là * nhanh nhất * hoặc * dễ nhất *? –
Tôi giả sử bạn muốn Byte0Out = Byte0inBit0 + Byte1inBit0 * 2 + ... – whoplisp
Thuật ngữ mà bạn đang tìm kiếm là "chuyển vị". – Damon