Как найти минимальный интервал времени

Find the “median timestamp range” which has minimal summary difference for given “arbitrary number of timestamps”.

If the amount of “arbitrary timestamps” is odd then this is the median timestamp. Take the timestamp equal to this median. If such timestamp not exists then take any timestamp within the range of the timestamps adjacent to the median timestamp or, if no such timestamp, take the timestamp closest to this range.

If the amount of “arbitrary timestamps” is even then this is a range between two median timestamps. Take any timestamp within this range or, if no such timestamp, take the timestamp closest to this range.

In both variants “closest timestamp” means “the timestamp which has minimal amount of arbitrary timestamps between self and closest range border, if there are a couple of such timestamp then take closest by the difference”.

We need not formula/theory but practical solution. Steps:

1. We have an array of “data timestamps”. Let’s say it is DTS[1..X], it contains X timestamps.
2. We have an array of “arbitrary timestamps”. Let’s say it is ATS[1..N], it contains N timestamps.
3. Calculate the indices of two median elements in ATS (for odd-amount array this will be the same element). N₁ = (N+1) MOD 2 ; N₂ = (N+2) MOD 2.
4. In DTS – find the timestamp DTS[K₁] closest but not above ATS[N₂] and the timestamp DTS[K₂] closest but not below ATS[N₁].
5. Calculate “summary distance” for DTS[K₁] and DTS[K₂].

If the sums are equal then both elements and all elements between them (yes, they may be not adjacent in this case!) are the solution.

If they differs then the element with least sum is a solution. It seems that in this case cannot be a couple of solutions (but you may test its neighbors for to ensure).

Why this must work?

Imagine that AST contains 2 ts only. Take one DST between them, it has some difference sum. Move it 1s left. The distance to left ATS decreases by 1s, to right – increases by 1s, and total sum is unchanged. Move one more, and again… and the sum is constant until we reach left ATS. When we cross it the sum will increase by 2 for each 1s move.

Now imagine that we have 3-element ATS. Again take one DST and put it over the middle AST. Move to left or to right by 1s – partial sum to left/right ASTs will not change, distance to middle will increase by 1s, total sum will increase by 1s. Move more – when we cross the extreme ATS the sum will increase by 3 for each step…

Expand this to 4, 5, … element in ATS. The timestamp which has minimal sum matches the median timestamp or median timestamps range. Moving away from it increases the sum, crossing a timestamp increases increasing rate.

Есть таблица (Время, Цена, Объем)

Необходимо найти в заданном промежутке времени по определенному интервалу значения:

• цена у минимального времени интервала, (не сделано)

• цена у максимального времени интервала, (не сделано)

• максимальная цена,
• минимальная цена,
• объем.

Что сделал: интервал в примере 3 дня, может быть хоть год или пару секунд и т.д.

SELECT 
    FLOOR(UNIX_TIMESTAMP(t1.TimeAdded)/(60 * 60 * 24 * 3)) AS timekey, 
    min(t1.TimeAdded), max(t1.TimeAdded),   
    min(t1.Price) as min_price, max(t1.Price) as max_price,
    SUM(t1.Quantity) as volume
FROM TradeFill as t1
WHERE t1.TimeAdded >= "2018-01-01 00:00:00" AND t1.TimeAdded <= "2018-08-10 23:59:59"
GROUP BY timekey;


SELECT VERSION()
5.5.56-MariaDB

CREATE TABLE `TradeFill` (
  `Id` bigint(20) NOT NULL AUTO_INCREMENT,
  `Price` decimal(32,20) NOT NULL,
  `Quantity` decimal(32,20) NOT NULL,
  `TimeAdded` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP,
  PRIMARY KEY (`Id`)
) ENGINE=InnoDB AUTO_INCREMENT=10370 DEFAULT CHARSET=utf8

Таблица

ID-----Price-----Quantity-----TimeAdded
1------2000------10-----------2018-08-09 00:01:00
2------5000------10-----------2018-08-09 00:02:00
3------1000------10-----------2018-08-09 00:03:00
4------7000------10-----------2018-08-09 00:05:00
5------3000------10-----------2018-08-09 00:04:00
6------2500------15-----------2018-08-10 00:00:00

Хочу видеть

min(t1.TimeAdded)-------max(t1.TimeAdded)-----PriceStart-----PriceFinish-----min_price-----max_price-----volume
2018-08-09 00:01:00-----2018-08-09 00:05:00---2000-----------3000------------1000----------7000----------50----
2018-08-10 00:00:00-----2018-08-10 00:00:00---2500-----------2500------------2500----------2500----------15----