aholachek/vis-services — pull request #3 by romanchyla (2014-12-31 03:47:32+00:00)
Title: Optimizing paper network

I was able to improve the speed, but the algorithm remains O(n^2) - and I'm not sure I'll be able to change that

here is the log of actions and the effect it had; I'd like to invite you to study these changes - in some places, I have left comments; especially the weighting part seems suspicious; I'll also add comments next to the code

these are the measurements of the original algorithm:

```
size	time
2	0.0001186847687
4	0.00037586689
8	0.000479722023
16	0.002220916748
32	0.01049380302
64	0.03312058449
128	0.1267955542
256	0.5846193075
512	3.569471931
999	16.42297032
```

and this is the optimized version:
```
size	avg_time
2	0.0002013921738
4	0.001595258713
8	0.005114150047
16	0.006850838661
32	0.01430575848
64	0.03850052357
128	0.08786797524
256	0.2817896605
512	1.917691994
999	10.49049089
```

here is the log of all changes:
```
original:

rchyla@argo:/dvt/workspace/vis-services$ python -c "import pstats;ps=pstats.Stats('profile').sort_stats('pcalls').print_stats('paper')"
Tue Dec 30 19:25:16 2014 profile

8422519 function calls (8319999 primitive calls) in 19.173 seconds

Ordered by: primitive call count
List reduced from 1265 to 13 due to restriction <'paper'>

ncalls tottime percall cumtime percall filename:lineno(function)
4883778 3.283 0.000 3.283 0.000 lib/paper_network.py:220()
881834 1.925 0.000 1.925 0.000 lib/paper_network.py:254()
26214 0.039 0.000 3.140 0.000 lib/paper_network.py:210()
3162 0.004 0.000 0.007 0.000 lib/paper_network.py:153()
3068 0.002 0.000 0.002 0.000 lib/paper_network.py:123()
1536 0.001 0.000 0.001 0.000 lib/paper_network.py:196()
755 0.001 0.000 0.002 0.000 lib/paper_network.py:108()
28 0.000 0.000 0.000 0.000 lib/paper_network.py:127()
3 0.000 0.000 0.000 0.000 lib/paper_network.py:39(_get_paper_data)
3 0.001 0.000 0.001 0.000 lib/paper_network.py:29(_get_reference_mapping)
3 1.034 0.345 18.849 6.283 lib/paper_network.py:178(get_papernetwork)
3 0.086 0.029 2.878 0.959 lib/paper_network.py:67(augment_graph_data)
1 0.001 0.001 0.220 0.220 lib/paper_network.py:5()

1. removed unnecessary memory allocation

rchyla@argo:/dvt/workspace/vis-services$ python -c "import pstats;ps=pstats.Stats('profile').sort_stats('pcalls').print_stats('paper')"
Tue Dec 30 19:48:40 2014 profile

9479769 function calls (9361042 primitive calls) in 21.540 seconds

Ordered by: primitive call count
List reduced from 1265 to 12 due to restriction <'paper'>

ncalls tottime percall cumtime percall filename:lineno(function)
5229074 3.539 0.000 3.539 0.000 lib/paper_network.py:219()
1033175 2.235 0.000 2.235 0.000 lib/paper_network.py:253()
27136 0.040 0.000 3.343 0.000 lib/paper_network.py:209()
3465 0.002 0.000 0.002 0.000 lib/paper_network.py:123()
3355 0.004 0.000 0.007 0.000 lib/paper_network.py:153()
1536 0.001 0.000 0.001 0.000 lib/paper_network.py:196()
797 0.001 0.000 0.002 0.000 lib/paper_network.py:108()
27 0.000 0.000 0.000 0.000 lib/paper_network.py:127()
3 0.001 0.000 0.001 0.000 lib/paper_network.py:29(_get_reference_mapping)
3 1.184 0.395 21.209 7.070 lib/paper_network.py:178(get_papernetwork)
3 0.100 0.033 3.651 1.217 lib/paper_network.py:67(augment_graph_data)
1 0.001 0.001 0.221 0.221 lib/paper_network.py:5()

2. transformed ref_list into a dictionary for fast lookup (noticeable improvement)

rchyla@argo:/dvt/workspace/vis-services$ python -m cProfile -o profile tests/run_benchmark.py 512 3 513
running test with size: 512
size: 512 num rounds: 3 finished in: 16.3725719452
size	avg_time
512	5.45581928889
rchyla@argo:/dvt/workspace/vis-services$ python -c "import pstats;ps=pstats.Stats('profile').sort_stats('pcalls').print_stats('paper')"
Tue Dec 30 19:57:07 2014 profile

8671410 function calls (8561891 primitive calls) in 16.636 seconds

Ordered by: primitive call count
List reduced from 1265 to 12 due to restriction <'paper'>

ncalls tottime percall cumtime percall filename:lineno(function)
4713591 3.195 0.000 3.195 0.000 lib/paper_network.py:222()
919705 1.947 0.000 1.947 0.000 lib/paper_network.py:256()
25243 0.034 0.000 0.053 0.000 lib/paper_network.py:212()
3457 0.002 0.000 0.002 0.000 lib/paper_network.py:123()
3036 0.004 0.000 0.006 0.000 lib/paper_network.py:153()
1536 0.001 0.000 0.001 0.000 lib/paper_network.py:196()
768 0.001 0.000 0.002 0.000 lib/paper_network.py:108()
29 0.000 0.000 0.000 0.000 lib/paper_network.py:127()
3 0.001 0.000 0.001 0.000 lib/paper_network.py:29(_get_reference_mapping)
3 1.066 0.355 16.307 5.436 lib/paper_network.py:178(get_papernetwork)
3 0.091 0.030 3.460 1.153 lib/paper_network.py:67(augment_graph_data)
1 0.001 0.001 0.222 0.222 lib/paper_network.py:5()

3. transformed papers (list) to a dictionary: small improvement

rchyla@argo:/dvt/workspace/vis-services$ git commit -a -m "2. transformed ref_list into a dictionary for fast lookup (noticeable improvement)"
[master 1fda600] 2. transformed ref_list into a dictionary for fast lookup (noticeable improvement)
1 file changed, 5 insertions(+), 2 deletions(-)
rchyla@argo:/dvt/workspace/vis-services$ python -m cProfile -o profile tests/run_benchmark.py 512 3 513
running test with size: 512
size: 512 num rounds: 3 finished in: 15.608656168
size	avg_time
512	5.20121534665
rchyla@argo:/dvt/workspace/vis-services$ python -c "import pstats;ps=pstats.Stats('profile').sort_stats('pcalls').print_stats('paper')"
Tue Dec 30 20:06:03 2014 profile

8751439 function calls (8641082 primitive calls) in 15.873 seconds

Ordered by: primitive call count
List reduced from 1264 to 12 due to restriction <'paper'>

ncalls tottime percall cumtime percall filename:lineno(function)
4870707 3.298 0.000 3.298 0.000 lib/paper_network.py:226()
1013225 2.303 0.000 2.303 0.000 lib/paper_network.py:261()
26472 0.036 0.000 0.057 0.000 lib/paper_network.py:212()
3387 0.002 0.000 0.002 0.000 lib/paper_network.py:123()
3172 0.004 0.000 0.006 0.000 lib/paper_network.py:153()
1536 0.002 0.000 0.002 0.000 lib/paper_network.py:196()
753 0.001 0.000 0.002 0.000 lib/paper_network.py:108()
26 0.000 0.000 0.000 0.000 lib/paper_network.py:127()
3 0.001 0.000 0.001 0.000 lib/paper_network.py:29(_get_reference_mapping)
3 0.981 0.327 15.545 5.182 lib/paper_network.py:178(get_papernetwork)
3 0.094 0.031 3.219 1.073 lib/paper_network.py:67(augment_graph_data)
1 0.001 0.001 0.222 0.222 lib/paper_network.py:5()

4. made lambda do less work

(python)rchyla@argo:/dvt/workspace/vis-services$ python -c "import pstats;ps=pstats.Stats('profile').sort_stats('pcalls').print_stats('paper')"
Tue Dec 30 21:25:38 2014 profile

8729990 function calls (8617574 primitive calls) in 17.723 seconds

Ordered by: primitive call count
List reduced from 1074 to 12 due to restriction <'paper'>

ncalls tottime percall cumtime percall filename:lineno(function)
4881669 3.218 0.000 3.218 0.000 lib/paper_network.py:227()
976683 1.359 0.000 1.359 0.000 lib/paper_network.py:272()
26096 0.034 0.000 0.052 0.000 lib/paper_network.py:212()
3393 0.002 0.000 0.002 0.000 lib/paper_network.py:123()
3027 0.004 0.000 0.006 0.000 lib/paper_network.py:153()
1536 0.001 0.000 0.001 0.000 lib/paper_network.py:196()
766 0.001 0.000 0.002 0.000 lib/paper_network.py:108()
29 0.000 0.000 0.000 0.000 lib/paper_network.py:127()
3 0.880 0.293 17.469 5.823 lib/paper_network.py:178(get_papernetwork)
3 0.001 0.000 0.001 0.000 lib/paper_network.py:29(_get_reference_mapping)
3 0.057 0.019 2.955 0.985 lib/paper_network.py:67(augment_graph_data)
1 0.001 0.001 0.156 0.156 lib/paper_network.py:5()

5. changed the way how weights are computed (there is noticeable improvement ~20%)

(python)rchyla@argo:/dvt/workspace/vis-services$ python -m cProfile -o profile tests/run_benchmark.py 512 3 513
running test with size: 512
size: 512 num rounds: 3 finished in: 10.5986680984
size	avg_time
512	3.53138502439
(python)rchyla@argo:/dvt/workspace/vis-services$ python -c "import pstats;ps=pstats.Stats('profile').sort_stats('pcalls').print_stats('paper')"
Tue Dec 30 21:53:32 2014 profile

4062763 function calls (3953885 primitive calls) in 10.794 seconds

Ordered by: primitive call count
List reduced from 1072 to 11 due to restriction <'paper'>

ncalls tottime percall cumtime percall filename:lineno(function)
941034 1.315 0.000 1.315 0.000 lib/paper_network.py:272()
24944 0.033 0.000 0.051 0.000 lib/paper_network.py:213()
3337 0.002 0.000 0.002 0.000 lib/paper_network.py:124()
3121 0.004 0.000 0.006 0.000 lib/paper_network.py:154()
1536 0.001 0.000 0.001 0.000 lib/paper_network.py:197()
743 0.001 0.000 0.002 0.000 lib/paper_network.py:109()
26 0.000 0.000 0.000 0.000 lib/paper_network.py:128()
3 0.055 0.018 2.826 0.942 lib/paper_network.py:68(augment_graph_data)
3 1.149 0.383 10.573 3.524 lib/paper_network.py:179(get_papernetwork)
3 0.001 0.000 0.001 0.000 lib/paper_network.py:30(_get_reference_mapping)
1 0.001 0.001 0.156 0.156 lib/paper_network.py:5()

6. changed the datastructure that keeps references (bicodes) - from list to sets, which allows for fast intersections

(python)rchyla@argo:/dvt/workspace/vis-services$ python -c "import pstats;ps=pstats.Stats('profile').sort_stats('pcalls').print_stats('paper')"
Tue Dec 30 22:03:53 2014 profile

3376459 function calls (3245334 primitive calls) in 10.027 seconds

Ordered by: primitive call count
List reduced from 1071 to 10 due to restriction <'paper'>

ncalls tottime percall cumtime percall filename:lineno(function)
26199 0.034 0.000 0.054 0.000 lib/paper_network.py:213()
3313 0.002 0.000 0.002 0.000 lib/paper_network.py:124()
3228 0.004 0.000 0.006 0.000 lib/paper_network.py:154()
1536 0.001 0.000 0.001 0.000 lib/paper_network.py:197()
747 0.001 0.000 0.002 0.000 lib/paper_network.py:109()
24 0.000 0.000 0.000 0.000 lib/paper_network.py:128()
3 0.053 0.018 3.222 1.074 lib/paper_network.py:68(augment_graph_data)
3 1.154 0.385 9.801 3.267 lib/paper_network.py:179(get_papernetwork)
3 0.002 0.001 0.002 0.001 lib/paper_network.py:30(_get_reference_mapping)
1 0.001 0.001 0.155 0.155 lib/paper_network.py:5()

Final count, the first run is the optimized version, the second is the original - I'm not
randomly shuffling data; so there is >6s improvement over the original; unfortunately,
in nature it is still O(n^2)

(python)rchyla@argo:/dvt/workspace/vis-services$ python tests/run_benchmark.py 999 10 1001
running test with size: 999
size: 999 num rounds: 10 finished in: 112.054285049
size	avg_time
999	11.2054265499

(python)rchyla@argo:/dvt/workspace/vis-services$ python tests/run_benchmark.py 999 10 1001
running test with size: 999
size: 999 num rounds: 10 finished in: 175.483947039
size	avg_time
999	17.5483926535

this is the latest profiling, there is lot of time spent in the dot product - I'd be curioius
if that weighting can be removed or simplified; that would shave some work...

(python)rchyla@argo:/dvt/workspace/vis-services$ python -c "import pstats;ps=pstats.Stats('profile').sort_stats('tottime').print_stats( 20)"
Tue Dec 30 22:30:56 2014 profile

11668389 function calls (11184208 primitive calls) in 58.950 seconds

Ordered by: internal time
List reduced from 1069 to 20 due to restriction <20>

ncalls tottime percall cumtime percall filename:lineno(function)
31182 37.640 0.001 37.714 0.001 {numpy.core.multiarray.dot}
3 3.823 1.274 58.681 19.560 lib/paper_network.py:179(get_papernetwork)
4118006 2.717 0.000 2.717 0.000 {method 'get' of 'dict' objects}
2579965/2579714 1.617 0.000 1.617 0.000 {len}
412935/3 1.421 0.000 4.074 1.358 /usr/lib/python2.7/copy.py:145(deepcopy)
19872 1.383 0.000 2.534 0.000 /dvt/workspace/vis-services/python/local/lib/python2.7/site-packages/community/__init__.py:475(__neighcom)
4 1.283 0.321 2.568 0.642 lib/tf_idf.py:40(get_tf_idf_vals)
397977 1.110 0.000 1.653 0.000 /dvt/workspace/vis-services/python/local/lib/python2.7/site-packages/numpy/matrixlib/defmatrix.py:312(__getitem__)
31220 0.685 0.000 0.685 0.000 {numpy.core.multiarray.array}
687157 0.561 0.000 0.561 0.000 {isinstance}
428970 0.511 0.000 0.547 0.000 /dvt/workspace/vis-services/python/local/lib/python2.7/site-packages/networkx/classes/graph.py:1052(edges_iter)
708147 0.442 0.000 0.442 0.000 {id}
160542 0.342 0.000 0.547 0.000 /usr/lib/python2.7/copy.py:267(_keep_alive)
132570 0.339 0.000 0.527 0.000 /dvt/workspace/vis-services/python/local/lib/python2.7/site-packages/networkx/classes/graph.py:648(add_edge)
35898/3 0.333 0.000 4.074 1.358 /usr/lib/python2.7/copy.py:253(_deepcopy_dict)
12 0.302 0.025 3.304 0.275 /dvt/workspace/vis-services/python/local/lib/python2.7/site-packages/community/__init__.py:364(__one_level)
155913 0.283 0.000 0.384 0.000 /dvt/workspace/vis-services/python/local/lib/python2.7/site-packages/numpy/matrixlib/defmatrix.py:290(__array_finalize__)
12 0.272 0.023 0.740 0.062 /dvt/workspace/vis-services/python/local/lib/python2.7/site-packages/community/__init__.py:274(induced_graph)
3 0.264 0.088 12.615 4.205 lib/paper_network.py:68(augment_graph_data)
360354 0.236 0.000 0.236 0.000 {method 'append' of 'list' objects}

```