Мне нужен алгоритм сокращения массива для графика

Question

Я пытаюсь отобразить некоторые точки данных с помощью графиков Google, но, к сожалению, для длины URL-адреса, который я могу использовать, существует ограничение в 2000 символов, что соответствует примерно 200 предел точек данных, который я могу использовать для отображения графика. У меня около 800 точек данных и растет, поэтому мне нужно сократить их до 200 для графика. Сейчас я просто вырезаю X = (800/200) -1 балла, а затем пропускаю один (и повторяю), чтобы добраться до 200.

Однако большинство точек данных расположены в начале массива, позиции на графиках расширяются несколько экспоненциально (около 1,2 экспоненты). Также наиболее важными являются самые последние (в конце массива). Поэтому мне нужен способ уменьшить массив точек таким образом, чтобы оставить большинство точек в конце массива и удалить большинство (но не всех) в начале.

Это будет использоваться каждый раз, когда будет создан граф, поэтому он должен быть детерминированным (то есть случайным образом не задействован). Если бы кто-то мог указать мне в правильном направлении, я бы очень это оценил.

Answer 1

Как насчет этого? Не имея PHP для работы, я использовал Python, но я надеюсь, что это понятно. Спросите, нет ли.

Пусть ℓ - количество значений, с которых вы должны начать, и n - номер, который вы хотите сократить. Тогда идея найти наибольшую экспоненту х таким образом, что п^х меньше, то л. Тогда мы можем выбрать элементы с индексами, которые являются ближайшими целыми к

л - (п - 1) ^х - 1, л - (п - 2) ^х - 1, ..., ℓ - 1 ^х - 1, ℓ - 0 ^х - 1

, которые расположены на расстоянии друг от друга с уклоном в сторону конца списка.

import math 
def select_with_bias(s, n): 
    """Select n values from the list s if possible, with bias to later values.""" 
    l = len(s) 
    if l <= n: 
     return s[:]   # List is short: return copy of whole list. 
    if n < 2: 
     return s[-n:]  # If n is 1, last item only; if n is 0, empty list. 
    x = math.log(l - 1, n) # Shorthand for log(l - 1)/log(n) 
    result = [] 
    for i in xrange(n - 1, -1, -1): # Loop from n-1 down to 0. 
     result.append(s[l - int(i ** x) - 1]) 
    return result 

(Для специалистов Python: это не самый идиоматических способ сделать это в Python, но я хотел бы сделать это так ясно, как я могу программист, который не знает Python.)

Например:

>>> select_with_bias(range(100), 10) 
[19, 36, 51, 64, 75, 84, 91, 96, 98, 99] 
>>> select_with_bias(range(100), 20) 
[8, 15, 22, 29, 36, 42, 48, 54, 60, 65, 70, 75, 80, 84, 88, 91, 94, 97, 98, 99] 

это легко попробовать вариации этого подхода: идея заключается в том, чтобы выбрать кривую правильной формы и масштабировать его, чтобы соответствовать длине списка, так что вы можете попробовать разные кривые. Я выбрал полиномиальную кривую, но если это не сработает для вас, вы можете выбрать другую, например экспоненциальную.