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

Question

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

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

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

Answer 1

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

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

ℓ - ( n - 1) ^x - 1, ℓ - ( n - 2) ^x - 1, ..., ℓ - 1 ^x - 1, ℓ - 0 ^x - 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]

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