Scribd
Upload
9 views3 pages

Influencer Timing Analysis Report

The document reports on the results of running various tests of a find_influencers algorithm on social network graphs of increasing sizes. It provides the timing results of running the algorithm on graphs with 100 to 12800 nodes and edge counts proportional to the number of nodes. It finds that running time increases approximately linearly with graph size. It also analyzes the function call counts and times to identify which functions consume the most time.

Uploaded by

Max Powers
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views3 pages

Influencer Timing Analysis Report

The document reports on the results of running various tests of a find_influencers algorithm on social network graphs of increasing sizes. It provides the timing results of running the algorithm on graphs with 100 to 12800 nodes and edge counts proportional to the number of nodes. It finds that running time increases approximately linearly with graph size. It also analyzes the function call counts and times to identify which functions consume the most time.

Uploaded by

Max Powers
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Page 1

Sample output from my solution to Problem #1: (yours should match the format: the times
depend on your machine’s speed).
Unable to time find_influencers of size 100 nodes and 500 edges
find_influencers of size 200 nodes and 1000 edges
Analysis of 5 timings
avg = 0.00313 min = 0.00000 max = 0.01562 span = 500.0%

Time Ranges
0.00e+00<>1.56e-03[ 80.0%]|**************************************************
1.56e-03<>3.13e-03[ 0.0%]|
3.13e-03<>4.69e-03[ 0.0%]|A
4.69e-03<>6.25e-03[ 0.0%]|
6.25e-03<>7.81e-03[ 0.0%]|
7.81e-03<>9.37e-03[ 0.0%]|
9.38e-03<>1.09e-02[ 0.0%]|
1.09e-02<>1.25e-02[ 0.0%]|
1.25e-02<>1.41e-02[ 0.0%]|
1.41e-02<>1.56e-02[ 0.0%]|
1.56e-02<>1.72e-02[ 20.0%]|************

find_influencers of size 400 nodes and 2000 edges


Analysis of 5 timings
avg = 0.00937 min = 0.00000 max = 0.01562 span = 166.7%

Time Ranges
0.00e+00<>1.56e-03[ 40.0%]|*********************************
1.56e-03<>3.13e-03[ 0.0%]|
3.13e-03<>4.69e-03[ 0.0%]|
4.69e-03<>6.25e-03[ 0.0%]|
6.25e-03<>7.81e-03[ 0.0%]|
7.81e-03<>9.37e-03[ 0.0%]|
9.38e-03<>1.09e-02[ 0.0%]|
1.09e-02<>1.25e-02[ 0.0%]|
1.25e-02<>1.41e-02[ 0.0%]|
1.41e-02<>1.56e-02[ 0.0%]|
1.56e-02<>1.72e-02[ 60.0%]|**************************************************

find_influencers of size 800 nodes and 4000 edges


Analysis of 5 timings
avg = 0.03438 min = 0.03125 max = 0.04688 span = 45.5%

Time Ranges
3.12e-02<>3.28e-02[ 80.0%]|**************************************************
3.28e-02<>3.44e-02[ 0.0%]|
3.44e-02<>3.59e-02[ 0.0%]|A
3.59e-02<>3.75e-02[ 0.0%]|
3.75e-02<>3.91e-02[ 0.0%]|
3.91e-02<>4.06e-02[ 0.0%]|
4.06e-02<>4.22e-02[ 0.0%]|
4.22e-02<>4.38e-02[ 0.0%]|
4.37e-02<>4.53e-02[ 0.0%]|
4.53e-02<>4.69e-02[ 0.0%]|
4.69e-02<>4.84e-02[ 20.0%]|************

find_influencers of size 1600 nodes and 8000 edges


Analysis of 5 timings
avg = 0.15313 min = 0.14062 max = 0.15625 span = 10.2%

Time Ranges
1.41e-01<>1.42e-01[ 20.0%]|************
Page 2
1.42e-01<>1.44e-01[ 0.0%]|
1.44e-01<>1.45e-01[ 0.0%]|
1.45e-01<>1.47e-01[ 0.0%]|
1.47e-01<>1.48e-01[ 0.0%]|
1.48e-01<>1.50e-01[ 0.0%]|
1.50e-01<>1.52e-01[ 0.0%]|
1.52e-01<>1.53e-01[ 0.0%]|
1.53e-01<>1.55e-01[ 0.0%]|A
1.55e-01<>1.56e-01[ 0.0%]|
1.56e-01<>1.58e-01[ 80.0%]|**************************************************

find_influencers of size 3200 nodes and 16000 edges


Analysis of 5 timings
avg = 0.59375 min = 0.57812 max = 0.60938 span = 5.3%

Time Ranges
5.78e-01<>5.81e-01[ 20.0%]|****************
5.81e-01<>5.84e-01[ 0.0%]|
5.84e-01<>5.88e-01[ 0.0%]|
5.88e-01<>5.91e-01[ 0.0%]|
5.91e-01<>5.94e-01[ 0.0%]|
5.94e-01<>5.97e-01[ 60.0%]|**************************************************A
5.97e-01<>6.00e-01[ 0.0%]|
6.00e-01<>6.03e-01[ 0.0%]|
6.03e-01<>6.06e-01[ 0.0%]|
6.06e-01<>6.09e-01[ 0.0%]|
6.09e-01<>6.13e-01[ 20.0%]|****************

find_influencers of size 6400 nodes and 32000 edges


Analysis of 5 timings
avg = 2.40937 min = 2.39062 max = 2.42188 span = 1.3%

Time Ranges
2.39e+00<>2.39e+00[ 20.0%]|*************************
2.39e+00<>2.40e+00[ 0.0%]|
2.40e+00<>2.40e+00[ 0.0%]|
2.40e+00<>2.40e+00[ 0.0%]|
2.40e+00<>2.41e+00[ 0.0%]|
2.41e+00<>2.41e+00[ 40.0%]|**************************************************
2.41e+00<>2.41e+00[ 0.0%]|A
2.41e+00<>2.42e+00[ 0.0%]|
2.42e+00<>2.42e+00[ 0.0%]|
2.42e+00<>2.42e+00[ 0.0%]|
2.42e+00<>2.42e+00[ 40.0%]|**************************************************

find_influencers of size 12800 nodes and 64000 edges


Analysis of 5 timings
avg = 9.82188 min = 9.67188 max = 9.96875 span = 3.0%

Time Ranges
9.67e+00<>9.70e+00[ 20.0%]|*************************
9.70e+00<>9.73e+00[ 0.0%]|
9.73e+00<>9.76e+00[ 0.0%]|
9.76e+00<>9.79e+00[ 0.0%]|
9.79e+00<>9.82e+00[ 40.0%]|**************************************************
9.82e+00<>9.85e+00[ 20.0%]|*************************A
9.85e+00<>9.88e+00[ 0.0%]|
9.88e+00<>9.91e+00[ 0.0%]|
9.91e+00<>9.94e+00[ 0.0%]|
9.94e+00<>9.97e+00[ 0.0%]|
9.97e+00<>1.00e+01[ 20.0%]|*************************
Page 3
Sample output from my solution to Problem #2: (yours should match the format: the
times/counts depend on your machine’s speed and the random graph created).
Mon Mar 9 15:17:28 2020 test_profile

2782535 function calls (2782534 primitive calls) in 1.347 seconds

Ordered by: call count


List reduced from 122 to 20 due to restriction <20>

ncalls tottime percall cumtime percall filename:lineno(function)


817336 0.183 0.000 0.183 0.000 [Link](<lambda>)
408668 0.283 0.000 0.465 0.000 [Link](_trichotomy)
340777 0.023 0.000 0.023 0.000 {built-in method [Link]}
278119 0.039 0.000 0.039 0.000 [Link](_parent)
272337 0.070 0.000 0.089 0.000 [Link](_in_heap)
219428 0.151 0.000 0.151 0.000 [Link](_swap)
151341 0.027 0.000 0.027 0.000 [Link](_left_child)
120996 0.018 0.000 0.018 0.000 [Link](_right_child)
42452 0.058 0.000 0.531 0.000 [Link](updated)
37051 0.253 0.000 0.714 0.000 [Link](_percolate_down)
25401 0.117 0.000 0.397 0.000 [Link](_percolate_up)
18432 0.006 0.000 0.012 0.000 [Link](is_empty)
18432 0.004 0.000 0.005 0.000 [Link](size)
10000 0.025 0.000 0.662 0.000 [Link](remove)
10000 0.001 0.000 0.001 0.000 {method 'pop' of 'list' objects}
10000 0.002 0.000 0.002 0.000 {built-in method [Link]}
1569 0.000 0.000 0.000 0.000 {method 'add' of 'set' objects}
12 0.000 0.000 0.000 0.000 {method 'rstrip' of 'str' objects}
7 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:222(_verbose_message)
7 0.000 0.000 0.000 0.000 {method 'join' of 'str' objects}

Mon Mar 9 15:17:28 2020 test_profile

2782535 function calls (2782534 primitive calls) in 1.347 seconds

Ordered by: internal time


List reduced from 122 to 20 due to restriction <20>

ncalls tottime percall cumtime percall filename:lineno(function)


408668 0.283 0.000 0.465 0.000 [Link](_trichotomy)
37051 0.253 0.000 0.714 0.000 [Link](_percolate_down)
817336 0.183 0.000 0.183 0.000 [Link](<lambda>)
219428 0.151 0.000 0.151 0.000 [Link](_swap)
25401 0.117 0.000 0.397 0.000 [Link](_percolate_up)
272337 0.070 0.000 0.089 0.000 [Link](_in_heap)
1 0.062 0.062 1.347 1.347 [Link](find_influencers3)
42452 0.058 0.000 0.531 0.000 [Link](updated)
278119 0.039 0.000 0.039 0.000 [Link](_parent)
151341 0.027 0.000 0.027 0.000 [Link](_left_child)
10000 0.025 0.000 0.662 0.000 [Link](remove)
340777 0.023 0.000 0.023 0.000 {built-in method [Link]}
120996 0.018 0.000 0.018 0.000 [Link](_right_child)
1 0.013 0.013 0.017 0.017 [Link](<dictcomp>)
18432 0.006 0.000 0.012 0.000 [Link](is_empty)
18432 0.004 0.000 0.005 0.000 [Link](size)
10000 0.002 0.000 0.002 0.000 {built-in method [Link]}
1 0.002 0.002 0.058 0.058 [Link](_heapify)
1 0.002 0.002 0.002 0.002 {built-in method [Link]}
10000 0.001 0.000 0.001 0.000 {method 'pop' of 'list' objects}

You might also like