4 ms·

The slowness comes from the interaction of numpy and a Python object "Polygon", which in not numpy. I suspect that a sufficiently clever coder could have optimi

The slowness comes from the interaction of numpy and a Python object "Polygon", which in not numpy. I suspect that a sufficiently clever coder could have optimized the result without resorting to Rust, but at the cost of a substantial increase in complexity of the codebase. The proposed approach keep the Python code simple (and moves the complexity into having another language to deal with).

alex_smart 4y ago
diff --git a/poly_match_v1.py b/poly_match_v1.py index 675c88a..4293a46 100644 --- a/poly_match_v1.py +++ b/poly_match_v1.py @@ -1,4 +1,5 @@ from functools import cached_property +from itertools import compress from typing import List, Tuple import numpy as np from dataclasses import dataclass @@ -56,11 +57,8 @@ def generate_example() -> Tuple[List[Polygon], List[np.array]]: def find_close_polygons( polygon_subset: List[Polygon], point: np.array, max_dist: float ) -> List[Polygon]: - close_polygons = [] - for poly in polygon_subset: - if np.linalg.norm(poly.center - point) < max_dist: - close_polygons.append(poly) - + dist = np.linalg.norm([poly.center for poly in polygon_subset] - point, axis=1) + close_polygons = list(compress(polygon_subset, dist < max_dist)) return close_polygons 10x faster than the original, without resorting to native code, and without substantial increase in complexity of code base.
- mgraupner 4y ago
  I wish the author would take your suggestion (and other recommendations) here and try it out again. Would be a very interesting follow up to read: "How we speed up Python and simplifying our codebase by removing on more dependency".
  - nossid 4y ago
    Focusing on speeding up find_close_polygons instead of realizing that you're matching many points against the same set of polygons is also unfortunate, since that function being slow is a red herring. You can create a scipy.spatial.KDTree for example and just query all the points against that.

alex_smart 4y ago

diff --git a/poly_match_v1.py b/poly_match_v1.py index 675c88a..4293a46 100644 --- a/poly_match_v1.py +++ b/poly_match_v1.py @@ -1,4 +1,5 @@ from functools import cached_property +from itertools import compress from typing import List, Tuple import numpy as np from dataclasses import dataclass @@ -56,11 +57,8 @@ def generate_example() -> Tuple[List[Polygon], List[np.array]]: def find_close_polygons( polygon_subset: List[Polygon], point: np.array, max_dist: float ) -> List[Polygon]: - close_polygons = [] - for poly in polygon_subset: - if np.linalg.norm(poly.center - point) < max_dist: - close_polygons.append(poly) - + dist = np.linalg.norm([poly.center for poly in polygon_subset] - point, axis=1) + close_polygons = list(compress(polygon_subset, dist < max_dist)) return close_polygons 10x faster than the original, without resorting to native code, and without substantial increase in complexity of code base.

mgraupner 4y ago
I wish the author would take your suggestion (and other recommendations) here and try it out again. Would be a very interesting follow up to read: "How we speed up Python and simplifying our codebase by removing on more dependency".
- nossid 4y ago
  Focusing on speeding up find_close_polygons instead of realizing that you're matching many points against the same set of polygons is also unfortunate, since that function being slow is a red herring. You can create a scipy.spatial.KDTree for example and just query all the points against that.