Bạn có chắc chắn muốn xóa bài viết này không ?
Bạn có chắc chắn muốn xóa bình luận này không ?
Tản mạn một bài toán trong ProjectEuler
Hôm nay vô tình đọc được bài của anh @huytd về Bàn về phương pháp tối ưu tính tổng các số Fibonacci
Theo chuỗi cảm hứng mình cũng xin chia sẻ về bài toán projectEuler48
Cách giải đơn giản
sum((pow(i,i) for i in range(1,1000))) % 10**10
Problem: Điều gì sẽ sảy ra là thay 1000 bằng 10^6 hoặc một số lớn hơn nữa? máy tính có tính được luôn (10^6)^(10^6)?
kết quả tìm kiếm trên google theo cách làm bên dưới, và họ cũng hướng dẫn cách giảm số phép module lại( dựa vào thời gian thực hiện phép so sánh nhanh hơn phép module trong một số case) sẽ làm tăng tốc độ
Lợi dụng 2 tính chất của phép toán module dưới đây
(a*b) % c = ((a % c) * (b % c) )% c (1)
(a+b) % c = ((a % c) + (b % c) )% c (2)
Solution
modulo = 10**10
result = 0
for i in range(1,10**6):
temp = i
for j in range(1,i):
temp *= i
temp %= modulo
result += temp
result %= modulo
print result
Discussion Cách này sẽ cho kết quả nhưng chắc là phải đợi lâu. Có cách nào để giải quyết bài toán này?
- Tìm ra 1 công thức toán học, tính 1 phát ra luôn( Mình không biết, có bạn nào biết bảo mình với nhé)
- Tìm cách cải thiện việc tính (a^a % modulo)
Thay đổi cách tính (a^a % modulo)
Thêm một tính chất của phép lũy thừa
a^(x+y) = a^x * a^y (3)
Áp dụng (1) và (3) ta có thể cải tiến code theo cách dưới đây
modulo = 10**10
def module_of_sum(a, b, modulo):
return (a + b) % modulo
def module_of_pow(a, n):
"""
caculate module pow
"""
if n == 0:
return 1
if n == 1:
return a % modulo
tmp = module_of_pow(a, n/2)
return (tmp*tmp*module_of_pow(a, n - n/2*2)) % modulo
for i in range(1, 10**6):
total_of_module = module_of_sum(total_of_module, module_of_pow(i, i), modulo)
print "result is {0}".format(total_of_module % modulo)
return total_of_module
Discussion Cách trên đã nhanh hơn, với máy tính của mình tầm 14s.
Cải tiến việc tính (a^a % modulo) một chút
Nếu để ý một chút bạn sẽ thấy:
- module_of_pow(2,2) và module_of_pow(4,4) có liên quan gì không nhỉ? bạn có thể làm gì được ở đây? Nếu bạn tìm ra chúng thì chúc mừng bạn, bạn có thể áp dụng memorize pattern. Tham khảo về cách này trong bài viết Memoization and Decoratorcủa anh @VuNhatMinh
- Nếu bạn cho rằng nó không liên quan tới nhau, thì cũng xin chúc mừng bạn, vì nó giúp bạn nghĩ đến việc tính toán song song. Tham khảo Sử dụng coroutine trong python để cài đặt thuật toán điều phối các request của anh @kiennt
Cách áp dụng memorize pattern:
Với k là số nguyên tố, và việc áp dụng k =2, k= 3, k= 5... hoặc áp dụng tất cả là do bạn.
Mình đã thử với range(1, 10^6), trên spec máy của mình thì kết quả là khi áp dụng k = {2,3,5,7} thì việc tính toán nhanh hơn được 40%
Solution
def module_of_pow_using_memorize(k_prime_list):
"""
apply memorize pattern to cache previos result
As you see
If a == k*b:
a^a = (k*b)^(k*b)
= ((k*b)^b)^k
= (k^b * b^b)^k
In this case, we only consider k is prime number
because b always less than or equal to a(b <= a),
so if we cache caculted of b^b and k^b result,
and using it to caculate a^a
"""
# array to store b^b
memory_b = [1]
# array to store k^b
memory_k = []
for i in range(0, max(k_prime_list) + 1):
# init data for k^0
memory_k.append(1)
def wrapper(a, n):
if n == 0:
result = 1
if n == a:
memory_b.append(result)
return result
if n == 1:
result = (a % modulo)
if n == a:
memory_b.append(result)
return result
k = 0
# cache k^b
for i in k_prime_list:
if a %i == 0:
memory_k[i] = (memory_k[i] * i) % modulo
k = i
if k != 0:
memory_k[k] = (memory_k[k]) % modulo
# caculate a^a
b = a/k
result = ((memory_b[b]*memory_k[k])**k) % modulo
# cache a^a
memory_b.append(result)
return result
tmp = wrapper(a, n/2)
result = tmp*tmp*wrapper(a, n - n/2*2) % modulo
if n == a:
memory_b.append(result)
return result
return wrapper
Cách áp dụng tính toán song song( mình chưa implement bằng python)
Một người bạn đã chỉ mình cách này và implement bằng C++ và nhận được kết quả nhanh hơn 75% so với cách tính tuần tự không áp dụng memorize trên spec máy 4 core của anh ấy) chắc cách này không lạ gì với các anh trong nhóm #hardcode






