6
\$\begingroup\$

Original problem: Given \$x\$ number of tests that should run in \$y\$ number of seconds shift the time per test so that each test takes a little longer than the next.

Example: If running 10 tests over 10 seconds, the equal time per test would be 1 second each. Instead, have the first test take .5 seconds and the last test take 1.5 seconds while each subsequent test take a progressively longer duration. We shift the time per test around while still maintaining the original duration of 10 seconds for the 10 tests.

I am slightly ignorant of what math principles are occurring. I knew how I wanted to solve the problem but I can't describe the problem. I've made it possible to adjust how much shifting can be done. Since the array of times is linear (and we can't really have negative times) I put a limit on that 'shifting' value.

  1. How do you describe this function / math problem? (which would hopefully result in a better name for it).
  2. What should the pct variable be called? I originally thought it to be a percentage of each second, but as I developed the function I realized this was inaccurate; since after the first value, the percentage of shifting per time slice goes down then back up again.
def duration_spread(tests: float, seconds: float, pct: float = .75):
    assert -1 <= pct <= 1, "pct must be within +/-100% otherwise it will push times into negative"
    pct *= 2
    original_velocity = seconds/tests
    seconds_per_tests = original_velocity  # couldn't decide on naming convention
    average_velocity = original_velocity
    diff_average_velocity = pct * average_velocity
    acceleration = diff_average_velocity/tests

    multiplier_list = get_multipliers(tests)
    results = []
    for i, multiplier in enumerate(multiplier_list):
        newadjustment = (multiplier * acceleration)
        newtime = original_velocity + newadjustment
        print(f"{original_velocity} -> {newtime} :: {abs(newadjustment)}")
        results.append(newtime)

    return results


def get_multipliers(tests: float):
    odd = int(tests % 2)
    half_tests = int(tests // 2)
    result = list(range(-half_tests, half_tests+1))
    if not odd:
        result.pop(half_tests)
    return result
\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

This first, superficial refactor does the following:

  • Rearrange functions in order of dependency
  • Represent the return value of get_multipliers as a range and not a list for greater efficiency
  • You're accepting a fraction, not a percentage; your inputs are -1 through 1, not -100 through 100
  • some minor variable name abbreviations
  • convert duration_spread to a generator
  • delete some unused variables
  • do not debug-print within your routine
  • show the results in a test method

This gets us to

from typing import Iterable, Sequence


def get_multipliers(n_tests: int) -> Sequence[float]:
    odd = int(n_tests % 2)
    half_tests = int(n_tests // 2)
    if odd:
        yield from range(-half_tests, half_tests+1)
    else:
        yield from range(-half_tests, 0)
        yield from range(1, half_tests + 1)


def duration_spread(n_tests: int, seconds: float, frac: float = .75) -> Iterable[float]:
    assert -1 <= frac <= 1, "frac must be within +/-100%"
    orig_velocity = seconds / n_tests
    diff_avg_velocity = frac * 2 * orig_velocity
    accel = diff_avg_velocity / n_tests

    multipliers = get_multipliers(n_tests)
    for multiplier in multipliers:
        adj = multiplier * accel
        new_time = orig_velocity + adj
        yield new_time


def test():
    new_times = tuple(duration_spread(10, 10, .5))
    print(new_times)
    print(sum(new_times))


test()

Do some math and you'll see that for a series of \$n\$ integers, the total is:

\$ \sigma = \sum _1 ^n i = \frac {n(n+1)} 2 \$

If you introduce a spacing parameter \$\alpha\$ and base offset \$\delta\$, this becomes

\$ \sigma = \sum _1 ^n \left(\alpha i + \delta\right) = \frac {\alpha n(n+1)} 2 + n\delta \$

Since your \$\alpha\$ and \$n\$ are fixed, you need to solve for \$\delta\$:

\$ \delta = \frac \sigma n - \frac {\alpha(n+1)} 2 \$

Applying this to some simplified code yields the correct results:

from math import isclose
from typing import Iterable


def duration_spread(n_tests: int, seconds: float, alpha: float) -> Iterable[float]:
    delta = seconds/n_tests - alpha*(n_tests - 1)/2
    for i in range(n_tests):
        yield delta + i*alpha


def test():
    times = tuple(duration_spread(10, 20, .3))
    total = sum(times)
    print(' + '.join(f'{x:.1f}' for x in times), f'= {total:.1f}')

    assert isclose(total, 20)
    for i in range(1, 10):
        assert isclose(.3, times[i] - times[i-1])


test()
 0.7 + 1.0 + 1.2 + 1.6 + 1.9 + 2.1 + 2.5 + 2.8 + 3.0 + 3.4 = 20.0

As an exercise to you: to re-introduce validation now that we're using a spacing parameter instead of a fraction, what would be an upper bound on the spacing parameter? You were in the right direction in chat; the criterion boils down to verifying that delta > 0.

\$\endgroup\$
8
  • \$\begingroup\$ this should output 10 but actually outputs 9.5. Right, but OP's original code outputs 10. \$\endgroup\$
    – Marc
    Commented Jan 14, 2021 at 6:41
  • \$\begingroup\$ @Marc Good catch; I've fixed that regression. Thanks. \$\endgroup\$
    – Reinderien
    Commented Jan 14, 2021 at 14:40
  • \$\begingroup\$ This is thoughtfully considered. A new problem arises in your refactored version whereby the returned durations contain negative values when the number of tests exceeds the number of seconds. If I plug in 10 seconds for 20 tests with an alpha of .3, the first 9 values returned are negative. It was this problem alone caused me to realize I didn't know what the argument pct actually was. \$\endgroup\$ Commented Jan 14, 2021 at 15:44
  • \$\begingroup\$ That's why I've included my last sentence about upper bounds :) \$\endgroup\$
    – Reinderien
    Commented Jan 14, 2021 at 15:45
  • \$\begingroup\$ Try duration_spread(20, 10, .02). The number of tests exceeds the number of seconds and the output is correct. \$\endgroup\$
    – Reinderien
    Commented Jan 14, 2021 at 15:49
2
\$\begingroup\$

How do you describe this function / math problem?

The input is a list of tests with the same duration. For example, \$input=[2,2,2,2]\$. Given the indexes from 0 to 3, we can see it in a graph:

enter image description here

So we can define the input as a (discrete) function \$f(x)=2\$, or in general \$f(x) = seconds/tests\$. Where \$0<=x<=tests,x∈Z\$.

The function \$durationSpread\$ can be described as \$durationSpread = g(x) * f(x)\$. Where \$g(x)\$ is a function that depends on \$pct\$ and \$tests\$. In the following I am going to refer it as \$g(pct,tests)\$.

Function analysis

For pct=0 the input remains the same: \$g(pct,tests) * input = g(0,4) * [2,2,2,2] = [2, 2, 2, 2]\$. Meaning that all elements of the input are multiplied by 1. So \$g\$ should look like this: enter image description here

For pct=-1 the result "should be": \$g(-1,4) * [2,2,2,2] = [4.0, 2.67, 1.33, 0.0]\$. The first element of of the input is multiplied by 2, the last one by 0, and the elements in between by a descending factor.

I said "should be" because your code outputs \$[4.0,3.0,1.0,0.0]\$, which is not possible if we consider a constant factor (the gap betweenn 4.0 and 3.0 is 1, but between 3.0 and 1.0 is 2).

So \$g\$ should look like this: enter image description here For pct=1 the result is: \$g(1,4) * [2,2,2,2] = [0.0, 1.33, 2.67, 4.0]\$. In this case, the first element is multiplied by 0 and the last one by 2. So the function \$g\$ is: enter image description here

How to find \$g\$? From the three examples, we know that \$g\$ is a linear function. A linear function can be represented as y = mx + b. How to find m and b? They can be found given two points.

Let's choose the first point (x0,y0) in the origin. x0 is always 0. While y0 depends on pct. Looking at the examples, we can tell that it's equal to abs(pct - 1). Explanation:

  • In the first example pct=0 and y0=1. In fact, y0 = abs(0 - 1) = 1
  • In the second example pct=-1 and y0=2. In fact, y0 = abs(- 1 - 1) = abs(-2) = 2
  • In the third example pct=1 and y0=0. In fact, y0 = abs(1 - 1) = abs(0) = 0

For the second point (x1,y1), we can choose the center. Where y1 is always 1. While x1 can be found as x1 = (tests-1)/2. (You can double-check in the three examples).

Given two points we can find the slope m as m = (y1 - y0) / (x1 - x0). Once we have m, we calculate the constant b as b = y0 - (m * x0).

Now that we found \$g\$, we can multiply the input by \$g\$.

def duration_spread(tests, seconds, pct):
    x0, y0 = 0, abs(pct - 1)
    x1, y1 = (tests - 1) / 2, 1
    m = (y1 - y0) / (x1 - x0)
    b = y0 - (m * x0)
    unit_time = seconds / tests
    return [unit_time * (m * x + b) for x in range(tests)]

Some tests:

times = duration_spread(4, 8, 1)
print(' '.join(f'{x:.1f}' for x in times))
# output: 0.0 1.3 2.7 4.0

times = duration_spread(5, 10, -1)
print(' '.join(f'{x:.1f}' for x in times))
# output: 4.0 3.0 2.0 1.0 0.0

times = duration_spread(5, 10, .5)
print(' '.join(f'{x:.1f}' for x in times))
# output: 1.0 1.5 2.0 2.5 3.0

Code review

Very short since @Reinderien covered most of the ground.

  • Input type: tests represents the number of tests, so I am not sure why it's a float. It should be an integer.
  • Missing return type hint: the return type hint is missing in both functions.
\$\endgroup\$
2
  • \$\begingroup\$ It took me a while to get there, but @Reinderien 's explanation of the formula for sum of integers with a spacing parameter got me to understand where my solution was insufficient. You point it out as well, I used the trick of dividing the range in half which doesn't allow the resulting slope to remain linear. I knew what needed to be done for the first and last elements in the array and extrapolated (incorrectly) for the rest of the array. Looking back; I didn't know what I didn't know -- which was the proper math behind this type of problem. \$\endgroup\$ Commented Jan 15, 2021 at 17:40
  • \$\begingroup\$ @MarcelWilson sure, this is just another way of solving the same problem. It keeps the original parameter pct and uses simpler math, but maybe it's less elegant than Reinderien's solution. I tried to make it as simple as possible. When you are satisfied, don't forget to accept an answer ;) \$\endgroup\$
    – Marc
    Commented Jan 16, 2021 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.