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(<lambda>)
   881834    1.925    0.000    1.925    0.000 lib/paper_network.py:254(<lambda>)
    26214    0.039    0.000    3.140    0.000 lib/paper_network.py:210(<lambda>)
     3162    0.004    0.000    0.007    0.000 lib/paper_network.py:153(<lambda>)
     3068    0.002    0.000    0.002    0.000 lib/paper_network.py:123(<lambda>)
     1536    0.001    0.000    0.001    0.000 lib/paper_network.py:196(<lambda>)
      755    0.001    0.000    0.002    0.000 lib/paper_network.py:108(<lambda>)
       28    0.000    0.000    0.000    0.000 lib/paper_network.py:127(<lambda>)
        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(<module>)


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(<lambda>)
  1033175    2.235    0.000    2.235    0.000 lib/paper_network.py:253(<lambda>)
    27136    0.040    0.000    3.343    0.000 lib/paper_network.py:209(<lambda>)
     3465    0.002    0.000    0.002    0.000 lib/paper_network.py:123(<lambda>)
     3355    0.004    0.000    0.007    0.000 lib/paper_network.py:153(<lambda>)
     1536    0.001    0.000    0.001    0.000 lib/paper_network.py:196(<lambda>)
      797    0.001    0.000    0.002    0.000 lib/paper_network.py:108(<lambda>)
       27    0.000    0.000    0.000    0.000 lib/paper_network.py:127(<lambda>)
        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(<module>)


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(<lambda>)
   919705    1.947    0.000    1.947    0.000 lib/paper_network.py:256(<lambda>)
    25243    0.034    0.000    0.053    0.000 lib/paper_network.py:212(<lambda>)
     3457    0.002    0.000    0.002    0.000 lib/paper_network.py:123(<lambda>)
     3036    0.004    0.000    0.006    0.000 lib/paper_network.py:153(<lambda>)
     1536    0.001    0.000    0.001    0.000 lib/paper_network.py:196(<lambda>)
      768    0.001    0.000    0.002    0.000 lib/paper_network.py:108(<lambda>)
       29    0.000    0.000    0.000    0.000 lib/paper_network.py:127(<lambda>)
        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(<module>)

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(<lambda>)
  1013225    2.303    0.000    2.303    0.000 lib/paper_network.py:261(<lambda>)
    26472    0.036    0.000    0.057    0.000 lib/paper_network.py:212(<lambda>)
     3387    0.002    0.000    0.002    0.000 lib/paper_network.py:123(<lambda>)
     3172    0.004    0.000    0.006    0.000 lib/paper_network.py:153(<lambda>)
     1536    0.002    0.000    0.002    0.000 lib/paper_network.py:196(<lambda>)
      753    0.001    0.000    0.002    0.000 lib/paper_network.py:108(<lambda>)
       26    0.000    0.000    0.000    0.000 lib/paper_network.py:127(<lambda>)
        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(<module>)


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(<lambda>)
   976683    1.359    0.000    1.359    0.000 lib/paper_network.py:272(<lambda>)
    26096    0.034    0.000    0.052    0.000 lib/paper_network.py:212(<lambda>)
     3393    0.002    0.000    0.002    0.000 lib/paper_network.py:123(<lambda>)
     3027    0.004    0.000    0.006    0.000 lib/paper_network.py:153(<lambda>)
     1536    0.001    0.000    0.001    0.000 lib/paper_network.py:196(<lambda>)
      766    0.001    0.000    0.002    0.000 lib/paper_network.py:108(<lambda>)
       29    0.000    0.000    0.000    0.000 lib/paper_network.py:127(<lambda>)
        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(<module>)


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(<lambda>)
    24944    0.033    0.000    0.051    0.000 lib/paper_network.py:213(<lambda>)
     3337    0.002    0.000    0.002    0.000 lib/paper_network.py:124(<lambda>)
     3121    0.004    0.000    0.006    0.000 lib/paper_network.py:154(<lambda>)
     1536    0.001    0.000    0.001    0.000 lib/paper_network.py:197(<lambda>)
      743    0.001    0.000    0.002    0.000 lib/paper_network.py:109(<lambda>)
       26    0.000    0.000    0.000    0.000 lib/paper_network.py:128(<lambda>)
        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(<module>)

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(<lambda>)
     3313    0.002    0.000    0.002    0.000 lib/paper_network.py:124(<lambda>)
     3228    0.004    0.000    0.006    0.000 lib/paper_network.py:154(<lambda>)
     1536    0.001    0.000    0.001    0.000 lib/paper_network.py:197(<lambda>)
      747    0.001    0.000    0.002    0.000 lib/paper_network.py:109(<lambda>)
       24    0.000    0.000    0.000    0.000 lib/paper_network.py:128(<lambda>)
        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(<module>)



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}

```
this is the place that i'm suspicious of - Edwin, can you check it pls?