Find a binary gap

GPLv3

Gần đây, mình gặp 1 bài toán khá đơn giản, nhưng thú vị như sau:

Input: A number

Output: The maximum 0 is written between the two numbers 1 in binary form with the fastest possible speed.

Ví dụ:

1
2
3
4
5
6
7
8
>>> bin(10)
'0b1010'
>>> binary_gap(10)
1
>>> bin(12)
'0b1100'
>>> binary_gap(12)
0

Cách xử lí của mình

Có 2 cách để giải:

  1. Solution 1: Vì số được lưu trong bộ nhớ ở dạng nhị phân , nên mình sẽ ko chuyển từ thập phân sang nhị phân mà đọc từng bit trong bộ nhớ. Vì phép tính nhân chia tốn thời gian hơn phép xor nên mình sẽ sử dụng hoàn toàn các phép xor bit thay nhân chia.

  2. Solution2: Chuyển số từ thập phân sang nhị phân, chia thành các đoạn bằng dsố 1, lấy độ dài đoạn dài nhất.

Code

Solution1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def binary_gap(number):
	mark=1
	count0=0
	max0=0
	runner=number

	#find first 1
	while runner>0 and runner&mark!=1:
		runner=runner>>1

	while runner>0:
		#check last number is 1
		if runner&mark==1:
				if count0>max0:
					max0=count0
				pass
				count0=0
		else:
			count0+=1
		pass
		#shift right 1bit
		runner=runner>>1
	pass
	return max0

Độ phức tạp của thuật toán là O(n) với n là độ dài của số ở dạng nhị phân.
Thời gian chạy thử 10000 số từ 1000000000 đến 1000010001 như bảng dưới đây .
Thời gian tính theo đơn vị giây.

S1

Solution2

1
2
def binary_gap2(number):
	return len(max( bin(number)[2:].split('1')))

Độ phức tạp của bin là O(n) , split là O(n), max là O(n), len là O(1). Vậy tổng là O(n) với n là độ dài của số ở dạng nhị phân.
Thời gian chạy thử 10000 số từ 1000000000 đến 1000010001 như bảng dưới đây .
Thời gian tính theo đơn vị giây.

S2

Solution2 làm nhiều thao tách hơn Solution1 nhưng tốc độ lại nhanh hơn Solution1. Dù cách làm không tối ưu.
Nguyên nhân có thể là vì, Solution2 sử dụng hoàn toàn các hàm có sẵn của hệ thống, đã được biên dịch sẵn. Trong khi Solution1 chạy ở dạng phiên dịch.

Update:2018/08/13

Để kiểm tra suy đoán trên, mình sẽ tạo file thực thi để chạy thẳng code, không thông qua python.
Để làm được điều này, mình sử dụng pyinstaller

1
2
3
sudo pip install pyinstaller
pyinstaller Solution1.py --onefile
pyinstaller Solution2.py --onefile

Kết quả chạy thử Solution1 như sau:
S1check

Kết quả chạy thử Solution2 như sau:
S2check

Thời gian của Solution1 giảm đáng kể. Trong khi đó, thời gian của Solution2 ko giảm.

Vậy Cách 1 tốt hơn Cách 2 trên lý thuyết và trong thực tế chạy trực tiếp. Suy đoán phía trên là chính xác.
Cách 2 dễ viết hơn, chạy nhanh hơn trong môi trường biên dịch. Cách 2 chạy trực tiếp lâu hơn có thể vì trình biên dịch chưa tối ưu.