dynamical list problem
01-02-2019, 04:36 PM (This post was last modified: 01-02-2019 07:22 PM by peacecalc.)
Post: #1
 peacecalc Member Posts: 187 Joined: Dec 2013
dynamical list problem
Hello folks,

I have a problem for you, but no solution. We have a growing list, in every cycle a new element is appended to the list. Let us say, every second a new value is generated and which series of elements have the highest average. The sum of values of such a sequence should obey a certain value:

Here a example: sum value is 5

1 {1}
2 {1 2}
3 {1 2 1}
4 {1 2 1 3} Now the first time for building an averge value: m = (4 + 1)/(3 + 1/3) = 3/2
5 {1 2 1 3 2} m = (3+2)/(1+1) = 5/2. Statically it would be not calculated because the sum value is not 5 (only 2+2). I hope this explain a little bit the problem. A more difficult situation occurs when the not only one but more values in the "past" must be included in the new average caluation.

From where I get this dynamical problem? My fitness watch told me after a jogging tour that was my fastest mile. I've the impression, the watch works statically. It takes the time after the first miles, then after the second mile and so on. And at the end, it tells me, ok your fith mile was my record (= fastest) mile. But what is, when my record milstones lies in between?

Greetings
peacecalc
01-02-2019, 06:08 PM
Post: #2
 grsbanks Senior Member Posts: 1,219 Joined: Jan 2017
RE: dynamical list problem

(01-02-2019 04:36 PM)peacecalc Wrote:  4 {1 2 1 3} Now the first time for building an averge value: m = 4/3 + (3-2)/(1/3) = 13/3

I make the average $$\frac {1+2+1+3} 4 = \frac 7 4$$

(01-02-2019 04:36 PM)peacecalc Wrote:  5 {1 2 1 3 2} m = 3/1 + 2/1 = 5.

Again, your process is not clear. How are you going from a list of 5 numbers to $$m=\frac 3 1 + \frac 2 1 = 5$$ ?

If you can explain in clearer terms exactly what you're trying to achieve, we might be able to help.
01-02-2019, 06:47 PM
Post: #3
 BruceH Senior Member Posts: 417 Joined: Dec 2013
RE: dynamical list problem
I assume he wants to find the fastest mile/km during his run.

So if the running watch samples at a particular rate then n consecutive values will correspond to a mile/km. So find the n consecutive values that have the highest average; and note the starting position, p.

p/n gives the mile/km position of the start of the fastest mile/km.

Or something like that!
01-02-2019, 07:14 PM (This post was last modified: 01-02-2019 07:21 PM by peacecalc.)
Post: #4
 peacecalc Member Posts: 187 Joined: Dec 2013
RE: dynamical list problem
Hello folks,

@grsbanks,

oh, sorry my calclution is wrong! Shame on me. I takes the value 5 for serious, if you take the 3 out of the list and add it to the numbers 1, 2 and 1 you get 7 and not 5, so the program should recognize this and add only 1 from 3 (3-2) and this 1 takes only a third of 1 (cycle), together with the other three cycles I have to divide with 3 and a third of one. That is the way I calculated. And the second calution is wrong, too. I have to take the 3 and the 2 and divide it by 2 (cycles) that gives 5/2. I correct it in the foregoing post.

@BruceH, you get it although my double wrong calculation!
01-03-2019, 11:56 AM
Post: #5
 pier4r Senior Member Posts: 2,190 Joined: Nov 2014
RE: dynamical list problem
I am not sure I understood the problem. Are you with the 50g? (or with RPL ) ?

Wikis are great, Contribute :)
01-03-2019, 12:57 PM (This post was last modified: 01-03-2019 05:58 PM by Albert Chan.)
Post: #6
 Albert Chan Senior Member Posts: 2,099 Joined: Jul 2018
RE: dynamical list problem
Hi pier4r

(01-02-2019 04:36 PM)peacecalc Wrote:  4 {1 2 1 3} Now the first time for building an averge value: m = (4 + 1)/(3 + 1/3) = 3/2

The list are speed numbers, say miles run per hour (mph)
So above translated to 4th hours {1 mph, 2 mph, 1 mph, 3 mph}

5-miles run "dynamic" part:
Miles 0 to 5, time ~ 3+1/3 = 3.333 hr --> speed = 1.500 mph
Miles 1 to 6, time ~ 2+2/3 = 2.667 hr --> speed = 1.875 mph
Miles 2 to 7, time ~ 1.5+1 = 2.500 hr --> speed = 2.000 mph

If above is what we wanted to calculate, it is better to record time for each mile:

time = {0:00, 1:00, 1:30, 2:00, 3:00, 3:20, 3:40, 4:00, 4:30, 5:00}

Assuming 0 based indexing, Miles k to 5+k, speed (mph) = 5/(time[k+5] - time[k])
01-03-2019, 02:11 PM (This post was last modified: 01-03-2019 02:14 PM by peacecalc.)
Post: #7
 peacecalc Member Posts: 187 Joined: Dec 2013
RE: dynamical list problem
Hello Albert,

originally the values in the list are differences of distances walked between to points in time. I reduced this already to a list of distances (let us say in meters) and the values are generated to equal time marks (let us say every second).

To translate it to my way: I want to get the average velocity over 5 meters.

Now the first velocity was v = (1m + 2m + 1m +(3-2)m)/(3s + (1/3)s) = 1,5 m/s,
the second was: v = (2m+3m)/(1s + 1s) = 2,5 m/s.

My watch with it's gps-modules makes it more complicate, because the time marks are not constant (it depends on if the gps-signal can be received as a good signal or not).

But Albert, you gave me the hint for a solution: Every value is a starting point of a new 5m distance, the only difficulty will be then values where are 5m is not arrived exactly (means: it is more then 5m).

@pier4r: Yes, I use the hp50g.
01-03-2019, 03:13 PM (This post was last modified: 01-03-2019 03:16 PM by Albert Chan.)
Post: #8
 Albert Chan Senior Member Posts: 2,099 Joined: Jul 2018
RE: dynamical list problem
(01-03-2019 02:11 PM)peacecalc Wrote:  Now the first velocity was v = (1m + 2m + 1m +(3-2)m)/(3s + (1/3)s) = 1,5 m/s,
the second was: v = (2m+3m)/(1s + 1s) = 2,5 m/s.

I think "the second" meant last 5m speed, from your data: 5 {1 2 1 3 2}

Note: the word velocity included direction. So, if you run in a 5m circle, 5m averaged velocity = 0 m/s
01-03-2019, 04:25 PM
Post: #9
 peacecalc Member Posts: 187 Joined: Dec 2013
RE: dynamical list problem
Hello Albert,

ha, you tease me, lets say speed as the physicist wrote:

$| \vec{v} |$
01-03-2019, 04:44 PM (This post was last modified: 01-03-2019 04:46 PM by Thomas Klemm.)
Post: #10
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: dynamical list problem
(01-02-2019 04:36 PM)peacecalc Wrote:  I have a problem for you, but no solution.

You could create the following list from {1 2 1 3 2}:

$$\left \{ 1 \frac{1}{2} \frac{1}{2} 1 \frac{1}{3} \frac{1}{3} \frac{1}{3} \frac{1}{2} \frac{1}{2} \right \}$$

And then just use a moving window of 5 elements and add them up:

$$\begin{matrix} \left \{ 1+\frac{1}{2}+\frac{1}{2}+1+\frac{1}{3} \right \} & = 3 \frac{1}{3} \\ \left \{ \frac{1}{2}+\frac{1}{2}+1+\frac{1}{3}+\frac{1}{3} \right \} & = 2 \frac{2}{3} \\ \left \{ \frac{1}{2}+1+\frac{1}{3}+\frac{1}{3}+\frac{1}{3} \right \} & = 2 \frac{1}{2} \\ \left \{ 1+\frac{1}{3}+\frac{1}{3}+\frac{1}{3}+\frac{1}{2} \right \} & = 2 \frac{1}{2} \\ \left \{ \frac{1}{3}+\frac{1}{3}+\frac{1}{3}+\frac{1}{2}+\frac{1}{2} \right \} & = 2 \\ \end{matrix}$$

You end up with:

$$\begin{matrix} 5 \div \frac{10}{3} & = \frac{3}{2} & = 1.500\\ 5 \div \frac{8}{3} & = \frac{15}{8} & = 1.875 \\ 5 \div \frac{5}{2} & = 2 & = 2.000 \\ 5 \div \frac{5}{2} & = 2 & = 2.000 \\ 5 \div 2 & = \frac{5}{2} & = 2.500 \end{matrix}$$

Now you have additional intermediate values but they might still be useful for you.

Cheers
Thomas
01-03-2019, 05:18 PM
Post: #11
 Albert Chan Senior Member Posts: 2,099 Joined: Jul 2018
RE: dynamical list problem
(01-03-2019 04:44 PM)Thomas Klemm Wrote:  You could create the following list from {1 2 1 3 2}:

$$\left \{ 1 \frac{1}{2} \frac{1}{2} 1 \frac{1}{3} \frac{1}{3} \frac{1}{3} \frac{1}{2} \frac{1}{2} \right \}$$ ...

This only work with integer speed numbers.
Also, the integers must be relatively small, to prevent "exploded" list.
01-03-2019, 09:15 PM
Post: #12
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: dynamical list problem
(01-03-2019 05:18 PM)Albert Chan Wrote:  This only work with integer speed numbers.

You can scale up a list like { 1 2 1 2.5 2 } to { 2 4 2 5 4 }.

In general you would integrate the velocity $$v(t)$$ and set it equal to 5:

$$\int_t^{t+\Delta t} v(\tau)d\tau=s(\tau)\vert_t^{t+\Delta t}=s(t+\Delta t)-s(t)=5$$

And then for a given $$t$$ solve for $$\Delta t$$.

The average velocity for these 5 meters would then be:

$$\bar{v}(t)=\frac{5}{\Delta t}$$

You could either use linear functions or splines to approximate the velocity.
Or then just use locally constant functions as in the approach I suggested.
This makes solving for $$\Delta t$$ rather easy.

Cheers
Thomas
01-04-2019, 08:51 AM
Post: #13
 peacecalc Member Posts: 187 Joined: Dec 2013
RE: dynamical list problem
Hello all,

I'm not shure if everybody (or more worse for me, that I understand everybody else right) understand right: The numbers in the list are distances between places. Of course it is possible to calculate for every time step (e. g. 1 second) a speed, but I want to have average value of speed let us say for 5 (meters).

{1 2 1 3 2} -> {{1 2 1 1} {2 1 2} {1 3 1} {3 2}} These four lists contain all a way of 5 meters, but with different times of walking:

{1 2 1 1} needs 3 + 1/3 seconds v = 3/2 m/s
{2 1 2} needs 2 + 2/3 seconds v = 15/8 m/s
{1 3 1} needs 2 + 1/2 seconds v = 2 m/s
{3 2} needs 2 seconds v = 5/2 m/s

The fraction of seconds have their reason in the fourth value of the original list is a big one: 3 and that value can be divided in 1 + 2, 2 + 1.

And that might be the solution I looked for: for every new value in the list, must be calculate how far I have to go back in the original list to get 5 m and then how many time steps it affords. Then the now speed value has to be compared with last maximum value.
01-04-2019, 11:57 AM
Post: #14
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: dynamical list problem
(01-04-2019 08:51 AM)peacecalc Wrote:  {1 2 1 1} needs 3 + 1/3 seconds v = 3/2 m/s
{2 1 2} needs 2 + 2/3 seconds v = 15/8 m/s
{1 3 1} needs 2 + 1/2 seconds v = 2 m/s
{3 2} needs 2 seconds v = 5/2 m/s

These values appear to agree with mine:
(01-03-2019 04:44 PM)Thomas Klemm Wrote:  $$\begin{matrix} 5 \div \frac{10}{3} & = \frac{3}{2} & = 1.500\\ 5 \div \frac{8}{3} & = \frac{15}{8} & = 1.875 \\ 5 \div \frac{5}{2} & = 2 & = 2.000 \\ 5 \div \frac{5}{2} & = 2 & = 2.000 \\ 5 \div 2 & = \frac{5}{2} & = 2.500 \end{matrix}$$

Not sure if that helps but here's some Clojure code:

Create a list of lists where each list contains n times $$\frac{1}{n}$$:
Code:
user=> (->> (for [n [1 2 1 3 2]] (repeat n (/ 1 n)))) ((1) (1/2 1/2) (1) (1/3 1/3 1/3) (1/2 1/2))

Flatten the result:
Code:
user=> (->> (for [n [1 2 1 3 2]] (repeat n (/ 1 n))) flatten) (1 1/2 1/2 1 1/3 1/3 1/3 1/2 1/2)

Move a window of length 5 with step 1 over the list:
Code:
user=> (->> (for [n [1 2 1 3 2]] (repeat n (/ 1 n))) flatten (partition 5 1)) ((1 1/2 1/2 1 1/3) (1/2 1/2 1 1/3 1/3) (1/2 1 1/3 1/3 1/3) (1 1/3 1/3 1/3 1/2) (1/3 1/3 1/3 1/2 1/2))

Sum the elements of each list:
Code:
user=> (->> (for [n [1 2 1 3 2]] (repeat n (/ 1 n))) flatten (partition 5 1) (map sum)) (10/3 8/3 5/2 5/2 2N)

Divide 5 by each of the results:
Code:
user=> (->> (for [n [1 2 1 3 2]] (repeat n (/ 1 n))) flatten (partition 5 1) (map sum) (map (partial / 5))) (3/2 15/8 2N 2N 5/2)

The average speed isn't calculated at equal time intervals. But this makes the calculation much easier.

HTH
Thomas

PS: I've used the following definition of sum:
Code:
(defn sum [xs] (reduce + xs))
01-04-2019, 01:21 PM
Post: #15
 BruceH Senior Member Posts: 417 Joined: Dec 2013
RE: dynamical list problem
(01-04-2019 08:51 AM)peacecalc Wrote:  {1 2 1 3 2} -> {{1 2 1 1} {2 1 2} {1 3 1} {3 2}} These four lists contain all a way of 5 meters, but with different times of walking:

Hi Peacecalc,

The following short program produces your sub-lists. Is that enough to enable you to finish it off by adding in the calculation?

Code:
timing({1,2,1,3,2}) --> {{1,2,1,3},{2,1,3},{1,3,2},{3,2}}

PHP Code:
EXPORT timing(a)BEGIN  LOCAL i,j,k,m,res;  res := {};  k := SIZE(a);  FOR i FROM 1 TO k DO    FOR j FROM i TO k DO      m := a({i,j});      IF ΣLIST(m) >= 5 THEN        res := append(res,m);        BREAK;      END;    END;  END;  RETURN res;END;
01-04-2019, 02:34 PM
Post: #16
 Albert Chan Senior Member Posts: 2,099 Joined: Jul 2018
RE: dynamical list problem
(01-04-2019 08:51 AM)peacecalc Wrote:  {1 2 1 3 2} -> {{1 2 1 1} {2 1 2} {1 3 1} {3 2}}
These four lists contain all a way of 5 meters, but with different times of walking:

You missed {1 1 3}. Total distance travelled = 9m, thus should have 5 ways.

It might help calculations if list is travelled (time distance):

{1 2 1 3 2} => {(0 0) (1 1) (2 3) (3 4) (4 7) (5 9)}

For speed of any distance, just interpolate for the time.
Example, above missed {1 1 3}:

Speed(2m to 7m) = (7-2) / (4-1.5) = 5/2.5 = 2 m/s

With (time distance) list, no restrictions for equal time intervals, thus solved lost GPS signal problem.
Also, distance does not restricted to integers.
01-05-2019, 09:48 AM
Post: #17
 peacecalc Member Posts: 187 Joined: Dec 2013
RE: dynamical list problem
Hello Albert, Thomas and Bruce,

thank you for straight forward thinking and helping. @Thomas, now I understand your procedure. You normalized each element of the list the time for one meter distance, so you take always 5 elements, so you get the needed time for every 5 meters. 5 meters divided by this time is the average speed. @Albert, yes another possibility to solöve the problem, thank you. @Bruce, how Albert wrote, there is a missing list {1 1 3}. I don't now wether your algorithm has this problem, too or not.

If I've my RPL program I will share it, of course.
01-05-2019, 12:54 PM (This post was last modified: 01-05-2019 01:03 PM by Thomas Klemm.)
Post: #18
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: dynamical list problem
(01-04-2019 02:34 PM)Albert Chan Wrote:  It might help calculations if list is travelled (time distance):

{1 2 1 3 2} => {(0 0) (1 1) (2 3) (3 4) (4 7) (5 9)}

For speed of any distance, just interpolate for the time.

We can extend this table a bit to make sure that the difference between the travelled distance is 1m:

$$\begin{matrix} \textbf{time } t & \textbf{distance } s(t)\\ 0 & 0 \\ 1 & 1 \\ 1\frac{1}{2} & 2\\ 2 & 3 \\ 3 & 4 \\ 3\frac{1}{3} & 5 \\ 3\frac{2}{3} & 6 \\ 4 & 7 \\ 4\frac{1}{2} & 8 \\ 5 & 9 \end{matrix}$$

And then calculate the difference of the times that are 5 meters apart:

$$\begin{matrix} 3\frac{1}{3} &- & 0 &=& 3\frac{1}{3} \\ 3\frac{2}{3} &- & 1 &=& 2\frac{2}{3} \\ 4 &- & 1\frac{1}{2} &=& 2\frac{1}{2} \\ 4\frac{1}{2} &- & 2 &=& 2\frac{1}{2} \\ 5 &- & 3 &=& 2 \end{matrix}$$

Either calculate the partial sum of the times (as suggested by Albert) and then calculate the difference or then add up 5 time entries (as I suggested).
You will end up with the same result.

Cheers
Thomas
01-05-2019, 05:13 PM
Post: #19
 DavidM Senior Member Posts: 914 Joined: Dec 2013
RE: dynamical list problem
(01-03-2019 02:11 PM)peacecalc Wrote:  But Albert, you gave me the hint for a solution: Every value is a starting point of a new 5m distance, the only difficulty will be then values where are 5m is not arrived exactly (means: it is more then 5m).

@pier4r: Yes, I use the hp50g.

(01-05-2019 12:54 PM)Thomas Klemm Wrote:  Either calculate the partial sum of the times (as suggested by Albert) and then calculate the difference or then add up 5 time entries (as I suggested).
You will end up with the same result.

With the above in mind, DOSUBS could be a key part of your implementation. It "feeds" each contiguous subgroup of list elements to a subroutine for processing, then takes whatever you left on the stack and returns it to you in a new list.

Using a simple list for illustrative purposes, imagine that your data exists as follows:
$$\left \{ \ 1 \ 1 \ 1 \ 1 \ 1 \ 2 \ 2 \ 2 \ 2 \ 2 \ 3 \ 3 \ 3 \ 3 \ 3 \ \right \}$$

DOSUBS could be used to obtain a list of averages of each subgroup of 5 as follows:
Code:
«    5    « + + + + 5 / »    DOSUBS »

DOSUBS operates in a loop to "pre-load" the stack with (in this case) 5 elements from the source list, then runs the provided subroutine. This process is repeated until the final group of elements has been exhausted, and whatever your subroutine left on the stack is gathered into a new list result. If it helps to visualize the process, you can think of it this way:
Code:
1 1 1 1 1             « + + + + 5 / »   1 1 1 1 2           « + + + + 5 / »     1 1 1 2 2         « + + + + 5 / »       1 1 2 2 2       « + + + + 5 / »         1 2 2 2 2     « + + + + 5 / »           2 2 2 2 2   « + + + + 5 / » ... 3 3 3 3 3             « + + + + 5 / » <results count> →LIST

The result of the above code (assuming exact mode) is:
$$\left \{ \ 1 \ \frac {6} {5} \ \frac {7} {5} \ \frac {8} {5} \ \frac {9} {5} \ 2 \ \frac {11} {5} \ \frac {12} {5} \ \frac {13} {5} \ \frac {14} {5} \ 3 \ \right \}$$

...thus allowing you to conveniently perform the averaging using a "sliding window" of values from the source list.

The more challenging part, of course, is in converting your source data into the proper format before determining the averages.
01-05-2019, 07:45 PM
Post: #20
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: dynamical list problem
(01-05-2019 05:13 PM)DavidM Wrote:  With the above in mind, DOSUBS could be a key part of your implementation.

Here's a program for the HP-48G:
Code:
« { } SWAP 1   « DUP INV ROT ROT     1 SWAP     START OVER +     NEXT SWAP DROP   » DOLIST   5   « 5 →LIST ∑LIST 5 SWAP / »   DOSUBS »

Example:

{ 1 2 1 3 2 }

{ 1.5 1.875 2.00000000001 2.00000000001 2.5 }

But I'm sure this can be improved using the HP-50G.

Cheers
Thomas
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)