How often has it happened to you… you build a simple script to calculate something, run some bulk process, and coming back after an hour or so it just hangs with no output. Is it doing something or stuck? You could debug it, using WinPdb or Visual Studio Code debugger or GDB to run it step by step, but that would lose the time that it has been processing. Instead, you can use Pyrasite, a program for looking in to a running Python script!
Installation and workarounds
Install Pyrasite for Python3 on Ubuntu using:
pip3 install pyrasiteNow if like me you do not have ~/.local/bin in PATH, you can just run it directly:
$ ~/.local/bin/pyrasite
WARNING: ptrace is disabled. Injection will not work.
You can enable it by running the following:
echo 0 | sudo tee /proc/sys/kernel/yama/ptrace_scope
usage: pyrasite [-h] [-l] [--gdb-prefix GDB_PREFIX] [--verbose]
[pid] [payload]
pyrasite - inject code into a running python process
positional arguments:
pid The ID of the process to inject code into
payload The Python script to be executed inside the running
process. Can be one of the standard payloads (see
--list-payloads) or a filname.
optional arguments:
-h, --help show this help message and exit
-l, --list-payloads List standard payloads
--gdb-prefix GDB_PREFIX
GDB prefix (if specified during installation)
--verbose Verbose mode
For updates, visit https://github.com/lmacken/pyrasiteCool. The ptrace issue is a somewhat controversial decision for Ubuntu as documented here. Running that “echo 0…” command line it suggests, gets rid of that warning. (Note that on next reboot you would need to set that setting again). Now, if you have the “ID” number from the ID column of System Monitor, you can start up a shell as documented with the ID following the command:
~/.local/bin/pyrasite-shell 14134but wait… no command line shell as described is shown? Why? It turns out the Pyrasite code is very old and not updated for recent GDB debugger. A simple one line fix is documented here and if you edit your local ~/.local/lib/python3.6/site-packages/pyrasite/injector.py to include that modified line:
' '.join(["-eval-command='call (void*) %s'" % cmd for cmd in gdb_cmds])),It should now work and I can inject commands looking at the state of the running script:
$ ~/.local/bin/pyrasite-shell 14134
Pyrasite Shell 2.0
Connected to 'python3 ./Euler243.py'
Python 3.6.9 (default, Oct 8 2020, 12:12:24)
[GCC 8.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
(DistantInteractiveConsole)
>>> print(i)
924915
>>> print(i)
925344 Project Euler example
The above example is using the following code that “should” find the answer to Project Euler 243.
from math import gcd
def R(denom):
resilient = 0
for i in range(1,denom):
if gcd(i,denom) == 1:
resilient += 1
return resilient/(denom-1)
for i in range(2,10000000):
#print('for %s is %s' % (i, R(i)))
if R(i) < 15499/94744:
print(i)
exit()
Even after running this many hours, it had found less than a million resilient values. This is O(n^2) meaning each value is looking through each element – although the code above is working, there needs to be a faster way! It will get slower and slower with each new iteration.
One possible optimization would be to not go through every single one, but only those that have possibility of having numerator. This would save checks for numerous numerators but it appears this one is also not fast enough:
from math import gcd
primes = [2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,
233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,
607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,
739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,
877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997,1009,1013,
1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,
1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,
1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,
1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,
1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,
1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,
1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,
1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,
1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,
1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,
1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,
1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,
1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,
1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,
2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,
2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,
2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,
2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,
2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,
2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,
2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,
2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,
2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,
2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,
2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,
2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,
3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,
3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,
3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,
3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,
3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,
3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,
3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,
3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,
3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,
3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,
3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,
3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,
4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,
4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,
4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,
4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,
4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,
4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,
4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,
4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,
4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,
4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,
4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,
4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,
5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,
5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,
5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,
5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,
5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,
5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,
5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,
5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,
5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,
5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,
5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,
5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,
6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,
6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,
6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,
6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,
6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,
6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,
6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,
6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,
6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,
6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,
6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,
7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,
7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,
7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,
7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,
7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,
7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,
7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,
7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,
7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,
7841,7853,7867,7873,7877,7879,7883,7901,7907,7919]
def R(denom):
resilient = 0
for i in range(1,denom):
if gcd(i,denom) == 1:
resilient += 1
return resilient/(denom-1)
def smartR(denom):
numerators = []
for prime in primes:
if prime > denom:
break
if denom % prime > 0:
#Not divisible. look at fractions:
for i in range(prime,denom,prime):
if gcd(i,denom) == 1 and not i in numerators:
numerators.append(i)
return (1+len(numerators))/(denom-1)
for i in range(2,1000000):
# print('for %s is %s %s' % (i, R(i), smartR(i)))
if smartR(i) < 15499/94744:
print(i)
exit()
It appears there is another trick that may be part of this one, it still takes too loong to run. So there is another trick to this one… here’s a hint, you will need to add more primes to get the accurate answer, I had to extend this list with list available online.
Open questions…
- What is the Big O notation of this optimized loop?
- What insight might speed this up or go about it in a different way?
Comments below: