search

SEL-Columbia / sequencer

Python library for sequencing the output of Network Planner csv's and shape file outputs
Other
4 stars 4 forks source link

DistanceMatrix consumes too much memory #42

Closed chrisnatali closed 9 years ago

chrisnatali commented 9 years ago

Copying from https://github.com/SEL-Columbia/modelrunner/issues/23

From @Naigege

When kedco-all zip file run on model runner, it gives a memory error shown as below. The uploaded zip file is 10mb.

reading input from /home/mr/model_runner/worker_data/011a8c4b-2f0a-439d-bffb-1faa030b5b60/input discarding /home/mr/miniconda/envs/model_runner/bin from PATH prepending /home/mr/miniconda/envs/sequencer/bin to PATH 2015-04-30 20:40:38,011 : NetworkPlan [INFO] : Asserting Input Projections Match 2015-04-30 20:40:41,108 : NetworkPlan [INFO] : Aligning Network Nodes With Input Metrics /home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/Utils.py:61: SettingWithCopyWarning: A value is trying to be set on a copy of a slice from a DataFrame. Try using .loc[row_indexer,col_indexer] = value instead

See the the caveats in the documentation: http://pandas.pydata.org/pandas-docs/stable/indexing.html#indexing-view-versus-copy fake_nodes['m_coords'] = fake_nodes['m_coords'].apply(lambda x: ()) 2015-04-30 20:41:02,613 : NetworkPlan [INFO] : Computing Pairwise Distances 2015-04-30 20:41:02,613 : NetworkPlan [INFO] : Using haversine Distance Traceback (most recent call last): File "/home/mr/model_runner/scripts/mvmax_sequencer.py", line 19, in nwp = NetworkPlan(shp_file, csv_file, prioritize='Population') File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/NetworkPlan.py", line 58, in init self.distance_matrix = self._distance_matrix() File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/NetworkPlan.py", line 97, in _distance_matrix return np.vstack(map(haversine, coords)) File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/numpy/core/shape_base.py", line 228, in vstack return _nx.concatenate([atleast_2d(_m) for _m in tup], 0) MemoryError

chrisnatali commented 9 years ago

If this is a priority, we can probably reduce memory consumption by using a kdtree for nearest neighbor lookup rather than a distance matrix.

chrisnatali commented 9 years ago

fixed in release 0.0.3

chrisnatali commented 9 years ago

Still an issue with large input networks. Need to reproduce. May want to re-implement nearest-neighbor lookup via kdtree as suggested above.

Traceback from run on modelrunner:

2015-08-04 12:47:32,737 : Sequencer [INFO] : Traversing The Input Network and Computing Decision Frontier Traceback (most recent call last): File "/home/mr/modelrunner/models/mvmax_sequencer.py", line 27, in results = model.sequence() File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/Models.py", line 13, in sequence super(EnergyMaximizeReturn, self).sequence() File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/Sequencer.py", line 139, in sequence self.results = pd.DataFrame(self._sequence()).set_index('Sequence..Far.sighted.sequence') File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/pandas/core/frame.py", line 248, in init data = list(data) File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/Sequencer.py", line 81, in _sequence accum_dict = self.accumulate(node) File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/Sequencer.py", line 33, in memoizedFunction cache[args] = f(_args, _kwargs) File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/Sequencer.py", line 171, in accumulate downstream_vars = [self.accumulate(child, adj_matrix=adj_matrix) for child, edge in enumerate(adj_matrix[n, :]) if edge] File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/Sequencer.py", line 33, in memoizedFunction cache[args] = f(_args, _kwargs) File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/Sequencer.py", line 164, in accumulate cost = self.upstream_distance(n) File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/Sequencer.py", line 133, in upstream_distance parent = self.parent(node) File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/Sequencer.py", line 253, in parent parent = (parent for parent, edge in enumerate(self.networkplan.adj_matrix[:, n]) if edge) File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/sequencer/NetworkPlan.py", line 256, in adj_matrix return nx.adj_matrix(self.network).toarray() File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/scipy/sparse/compressed.py", line 940, in toarray return self.tocoo(copy=False).toarray(order=order, out=out) File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/scipy/sparse/coo.py", line 274, in toarray B = self._process_toarray_args(order, out) File "/home/mr/miniconda/envs/sequencer/lib/python2.7/site-packages/scipy/sparse/base.py", line 793, in _process_toarray_args return np.zeros(self.shape, dtype=self.dtype, order=order) MemoryError

chrisnatali commented 9 years ago

The culprit appears to be here:

https://github.com/SEL-Columbia/Sequencer/blob/e68a8f1688ebcc8e0ede6bf9ca04f5c4105d02fd/sequencer/NetworkPlan.py#L256

Expanding the adjacency matrix from sparse to a dense numpy ndarray consumes too much memory. This is hit quite often and likely also represents a performance hit.

chrisnatali commented 9 years ago

fixed in v0.0.5