Tản mạn một bài toán trong Project
Cách giải đơn giản
1 | 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
1 2 | (a*b) % c = ((a % c) * (b % c) )% c (1) (a+b) % c = ((a % c) + (b % c) )% c (2) |
Solution
1 2 3 4 5 6 7 8 9 10 11 | 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
1 | 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | 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 Vũ Nhật Minh
- 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | 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
ITZone via kipalog