[
https://issues.apache.org/jira/browse/BEAM-4858?focusedWorklogId=148690&page=com.atlassian.jira.plugin.system.issuetabpanels:worklog-tabpanel#worklog-148690
]
ASF GitHub Bot logged work on BEAM-4858:
----------------------------------------
Author: ASF GitHub Bot
Created on: 27/Sep/18 11:16
Start Date: 27/Sep/18 11:16
Worklog Time Spent: 10m
Work Description: robertwb commented on a change in pull request #6375:
[BEAM-4858] Clean up division in batch size estimator.
URL: https://github.com/apache/beam/pull/6375#discussion_r220883853
##########
File path: sdks/python/apache_beam/transforms/util.py
##########
@@ -269,23 +270,60 @@ def record_time(self, batch_size):
self._thin_data()
def _thin_data(self):
- sorted_data = sorted(self._data)
- odd_one_out = [sorted_data[-1]] if len(sorted_data) % 2 == 1 else []
- # Sort the pairs by how different they are.
-
- def div_keys(kv1_kv2):
- (x1, _), (x2, _) = kv1_kv2
- return old_div(x2, x1) # TODO(BEAM-4858)
-
- pairs = sorted(zip(sorted_data[::2], sorted_data[1::2]),
- key=div_keys)
- # Keep the top 1/3 most different pairs, average the top 2/3 most similar.
- threshold = 2 * len(pairs) // 3
- self._data = (
- list(sum(pairs[threshold:], ()))
- + [((x1 + x2) / 2.0, (t1 + t2) / 2.0)
- for (x1, t1), (x2, t2) in pairs[:threshold]]
- + odd_one_out)
+ # Make sure we don't change the parity of len(self._data)
+ # As it's used below to alternate jitter.
+ self._data.pop(random.randrange(len(self._data) // 4))
+ self._data.pop(random.randrange(len(self._data) // 2))
+
+ @staticmethod
+ def linear_regression_no_numpy(xs, ys):
+ # Least squares fit for y = a*x + b over all points.
+ n = float(len(xs))
+ xbar = sum(xs) / n
+ ybar = sum(ys) / n
+ b = (sum([(x - xbar) * (y - ybar) for x, y in zip(xs, ys)])
+ / sum([(x - xbar)**2 for x in xs]))
+ a = ybar - b * xbar
+ return a, b
+
+ @staticmethod
+ def linear_regression_numpy(xs, ys):
+ # pylint: disable=wrong-import-order, wrong-import-position
+ import numpy as np
+ from numpy import sum
+ xs = np.asarray(xs, dtype=float)
+ ys = np.asarray(ys, dtype=float)
+
+ # First do a simple least squares fit for y = a*x + b over all points.
+ b, a = np.polyfit(xs, ys, 1)
+
+ n = len(xs)
+ if n < 10:
+ return a, b
+ else:
+ # Refine this by throwing out outliers, according to Cook's distance.
+ # https://en.wikipedia.org/wiki/Cook%27s_distance
+ sum_x = sum(xs)
+ sum_x2 = sum(xs**2)
+ errs = a * xs + b - ys
+ s2 = sum(errs**2) / (n - 2)
Review comment:
The typical definition takes into account the number of degrees of freedom.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
Issue Time Tracking
-------------------
Worklog Id: (was: 148690)
Time Spent: 4h (was: 3h 50m)
> Clean up _BatchSizeEstimator in element-batching transform.
> -----------------------------------------------------------
>
> Key: BEAM-4858
> URL: https://issues.apache.org/jira/browse/BEAM-4858
> Project: Beam
> Issue Type: Bug
> Components: sdk-py-core
> Reporter: Valentyn Tymofieiev
> Assignee: Robert Bradshaw
> Priority: Minor
> Time Spent: 4h
> Remaining Estimate: 0h
>
> Beam Python 3 conversion [exposed|https://github.com/apache/beam/pull/5729]
> non-trivial performance-sensitive logic in element-batching transform. Let's
> take a look at
> [util.py#L271|https://github.com/apache/beam/blob/e98ff7c96afa2f72b3a98426dc1e9a47224da5c8/sdks/python/apache_beam/transforms/util.py#L271].
>
> Due to Python 2 language semantics, the result of {{x2 / x1}} will depend on
> the type of the keys - whether they are integers or floats.
> The keys of key-value pairs contained in {{self._data}} are added as integers
> [here|https://github.com/apache/beam/blob/d2ac08da2dccce8930432fae1ec7c30953880b69/sdks/python/apache_beam/transforms/util.py#L260],
> however, when we 'thin' the collected entries
> [here|https://github.com/apache/beam/blob/d2ac08da2dccce8930432fae1ec7c30953880b69/sdks/python/apache_beam/transforms/util.py#L279],
> the keys will become floats. Surprisingly, using either integer or float
> division consistently [in the
> comparator|https://github.com/apache/beam/blob/e98ff7c96afa2f72b3a98426dc1e9a47224da5c8/sdks/python/apache_beam/transforms/util.py#L271]
> negatively affects the performance of a custom pipeline I was using to
> benchmark these changes. The performance impact likely comes from changes in
> the logic that depends on how division is evaluated, not from the
> performance of division operation itself.
> In terms of Python 3 conversion the best course of action that avoids
> regression seems to be to preserve the existing Python 2 behavior using
> {{old_div}} from {{past.utils.division}}, in the medium term we should clean
> up the logic. We may want to add a targeted microbenchmark to evaluate
> performance of this code, and maybe cythonize the code, since it seems to be
> performance-sensitive.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
