Supongamos que tenemos un vector entero que suma S1. Me gustaría tomar este vector y producir otro vector que sume a S2<S1. Me gustaría hacer esto restando el (primer) elemento máximo uno por uno hasta que la suma sea inferior a 4.

P.ej. clip_by_sum([1,4,8,3], total=10) == [1, 3, 3, 3].

Un código fácil que hace esto es:

def clip_to_sum(vec, total):
    new_vec = np.array(vec)  
    current_total = np.sum(vec)
    while current_total > total:
        i = np.argmax(new_vec)
        new_vec[i] -= 1
        current_total -= 1
    return new_vec

Sin embargo, obviamente es terriblemente ineficiente, porque solo restamos un elemento a la vez, sin importar cuánto esté conduciendo el vector de plomo.

¿Alguien tiene un ingenioso truco para hacer esto de manera eficiente?

Editar : un vector de entrada que ya suma menos de S1 puede dejarse sin cambios, por lo que, por ejemplo, clip_to_sum([1,4,8,3], 20) debe ser [1,4,8,3]

Editar Para aquellos que se preguntan para qué es, ¡es para la tarea mundana de determinar los anchos de columna en una tabla de ancho fijo!

-1
Peter 31 oct. 2017 a las 21:38

4 respuestas

La mejor respuesta

Aquí hay dos funciones que calculan la matriz recortada. El primero, limit_sum1, no dará exactamente el mismo resultado que su función, ya que, en efecto, hace diferentes elecciones de qué "max" disminuir cuando el máximo ocurre varias veces en el vector de entrada. Es decir, si vec = [4, 4, 4] y total = 11, hay tres resultados posibles: [3, 4, 4], [4, 3, 4] y [4, 4, 3]. Su función da [3, 4, 4], mientras que limit_sum1 da [4, 4, 3].

Para vectores de entrada muy pequeños, como los ejemplos en la pregunta, limit_sum2 es generalmente más rápido que limit_sum1, pero ninguno es más rápido que su clip_to_sum. Para vectores de entrada algo más largos con un rango de entrada más variado, ambos son más rápidos que clip_to_sum, y para vectores de entrada muy largos, limit_sum1 es mucho más rápido. Los ejemplos con tiempo están a continuación.

def limit_sum1(vec, total):
    x = np.asarray(vec)
    delta = x.sum() - total
    if delta <= 0:
        return x

    i = np.argsort(x)

    # j is the inverse of the sorting permutation i.
    j = np.empty_like(i)
    j[i] = np.arange(len(x))[::-1]

    y = np.zeros(len(x)+1, dtype=int)
    y[1:] = x[i]

    d = np.diff(y)[::-1]
    y = y[::-1]

    wd = d * np.arange(1, len(d)+1)
    cs = wd.cumsum()

    k = np.searchsorted(cs, delta, side='right')
    if k > 0:
        y[:k] -= d[:k][::-1].cumsum()[::-1]
        delta = delta - cs[k-1]

    q, r = divmod(delta, k+1)

    y[:k+1] -= q
    y[:r] -= 1

    x2 = y[j]
    return x2


def limit_sum2(vec, total):
    a = np.array(vec)
    while a.sum() > total:
        amax = a.max()
        i = np.where(a == amax)[0]
        if len(i) < len(a):
            nextmax = a[a < amax].max()
        else:
            nextmax = 0
        clip_to_nextmax_delta = len(i)*(amax - nextmax)
        diff = a.sum() - total
        if clip_to_nextmax_delta > diff:
            q, r = divmod(diff, len(i))
            a[i] -= q
            a[i[:r]] -= 1
            break
        else:
            # Clip all the current max values to nextmax.
            a[i] = nextmax
    return a

Ejemplos

In [1388]: vec = np.array([1, 4, 8, 3])

limit_sum1, limit_sum2 y clip_to_sum dan el mismo resultado:

In [1389]: limit_sum1(vec, total=10)
Out[1389]: array([1, 3, 3, 3])

In [1390]: limit_sum2(vec, total=10)
Out[1390]: array([1, 3, 3, 3])

In [1391]: clip_to_sum(vec, total=10)
Out[1391]: array([1, 3, 3, 3])

clip_to_sum es más rápido con este pequeño vector.

In [1392]: %timeit limit_sum1(vec, total=10)
33.1 µs ± 272 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [1393]: %timeit limit_sum2(vec, total=10)
24.6 µs ± 138 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [1394]: %timeit clip_to_sum(vec, total=10)
15.6 µs ± 44.8 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Probemos con un vector más largo que contenga valores más grandes.

In [1405]: np.random.seed(1729)

In [1406]: vec = np.random.randint(0, 100, size=50)

In [1407]: vec
Out[1407]: 
array([13, 37, 21, 67, 13, 89, 59, 35, 65, 91, 36, 73, 93, 83, 43, 86, 44,
       19, 51, 76, 12, 26, 43,  0, 42, 53, 30, 65,  3, 65, 37, 68, 64, 87,
       91,  4, 70, 10, 50, 40, 34, 32, 13,  7, 93, 79, 16, 98,  1, 35])

In [1408]: vec.sum()
Out[1408]: 2362

Encuentre un resultado usando cada función:

In [1409]: limit_sum1(vec, total=1500)
Out[1409]: 
array([13, 37, 21, 38, 13, 38, 38, 35, 38, 38, 36, 38, 38, 38, 38, 38, 38,
       19, 38, 38, 12, 26, 38,  0, 39, 38, 30, 38,  3, 38, 37, 38, 38, 38,
       38,  4, 38, 10, 38, 39, 34, 32, 13,  7, 38, 38, 16, 38,  1, 35])

In [1410]: limit_sum2(vec, total=1500)
Out[1410]: 
array([13, 37, 21, 38, 13, 38, 38, 35, 38, 38, 36, 38, 38, 38, 38, 38, 38,
       19, 38, 38, 12, 26, 38,  0, 38, 38, 30, 38,  3, 38, 37, 38, 38, 38,
       38,  4, 38, 10, 38, 38, 34, 32, 13,  7, 38, 39, 16, 39,  1, 35])

In [1411]: clip_to_sum(vec, total=1500)
Out[1411]: 
array([13, 37, 21, 38, 13, 38, 38, 35, 38, 38, 36, 38, 38, 38, 38, 38, 38,
       19, 38, 38, 12, 26, 38,  0, 38, 38, 30, 38,  3, 38, 37, 38, 38, 38,
       38,  4, 38, 10, 38, 38, 34, 32, 13,  7, 38, 39, 16, 39,  1, 35])

Esta vez, limit_sum1 es la más rápida por un amplio margen:

In [1413]: %timeit limit_sum1(vec, total=1500)
34.9 µs ± 257 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [1414]: %timeit limit_sum2(vec, total=1500)
272 µs ± 2.12 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [1415]: %timeit clip_to_sum(vec, total=1500)
1.74 ms ± 7.08 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
2
Warren Weckesser 1 nov. 2017 a las 08:52

Desafortunadamente, no es realmente obvio en qué tipo de resultado está interesado. Pero supongamos que tiene una matriz de cierta longitud y desea sacar los primeros elementos A [0: ix] para que la suma sea (de alguna manera cercana) S1, puedes hacer:

S1 = 5
A = np.array([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,])

B = np.cumsum(A)
ix = np.argmax(B>=S1)+1
C = A[0:ix]
print("C = ", C); print("sum C = ", np.sum(C))

Que da

C =  [1 1 1 1 1]
sum C =  5

Puedes escribir la misma en 1 linea

C = A[0:np.argmax(np.cumsum(A)>=S1)+1]
-1
pyano 31 oct. 2017 a las 19:30

Puede modificar su función para incluir una diferencia entre los elementos max y second max. Esto utilizará recursos informáticos adicionales por ciclo, pero debería reducir significativamente el número total de ciclos.

He probado esto en comparación con su función original y da los mismos resultados. Aunque, es cierto, estoy teniendo dificultades para ver una velocidad real entre los dos.

def clip_to_sum(vec, total):
    current_total = np.sum(vec)
    new_vec = np.array(vec)
    while current_total > total:
        i = np.argmax(new_vec)
        d = np.partition(new_vec.flatten(), -2)[-2]
        diff = new_vec[i] - d
        if not (new_vec[i] == diff) and diff > 0:
          new_vec[i] -= diff
          current_total -= diff
        else:
          new_vec[i] -= 1
          current_total -= 1
    return new_vec
2
BHawk 31 oct. 2017 a las 19:53

Básicamente vas a Robin Hood allí y recortas los valores que están por encima del promedio global w.r.t. total, hasta que la suma global alcance un umbral. Usando esa teoría, comenzaremos con un número de referencia y luego recorreremos, así:

def clip_until_sum(vec, total):
    # Get array version
    a = np.asarray(vec)  

    if a.sum() <= total: 
        return a

    # Baseline number
    b = int(total/float(len(a)))

    # Setup output
    out = np.where(a > b, b, a)
    s = out.sum()

    # Loop to shift up values starting from baseline
    while s<total:
        idx = np.flatnonzero(a > out)
        dss = total - s
        out[idx[max(0,len(idx)-dss):]] += 1
        s = out.sum()
    return out

Ejecuciones de muestra:

Serie 1 :

In [868]: clip_until_sum([1,4,8,3], 10)
Out[868]: array([1, 3, 3, 3])

In [869]: clip_until_sum([1,4,8,3], 11)
Out[869]: array([1, 3, 4, 3])

In [870]: clip_until_sum([1,4,8,3], 12)
Out[870]: array([1, 4, 4, 3])

In [871]: clip_until_sum([1,4,8,3], 13)
Out[871]: array([1, 4, 5, 3])

In [872]: clip_until_sum([1,4,8,3], 14)
Out[872]: array([1, 4, 6, 3])

In [873]: clip_until_sum([1,4,8,3], 15)
Out[873]: array([1, 4, 7, 3])

In [874]: clip_until_sum([1,4,8,3], 16)
Out[874]: array([1, 4, 8, 3])

Conjunto # 2:

In [875]: clip_until_sum([1,4,8,3,5,6], 12)
Out[875]: array([1, 2, 2, 2, 2, 3])

Prueba de tiempo de ejecución y verificación -

In [164]: np.random.seed(0)

# Assuming 10000 elems with max of 1000 and total as half of sum
In [165]: vec = np.random.randint(0, 1000, size=10000)

In [167]: total = vec.sum()//2

In [168]: np.allclose(clip_to_sum(vec, total), clip_until_sum(vec, total))
Out[168]: True

In [169]: %timeit clip_to_sum(vec, total)
1 loop, best of 3: 19.1 s per loop

In [170]: %timeit clip_until_sum(vec, total)
100 loops, best of 3: 2.8 ms per loop

# @Warren Weckesser's soln
In [171]: %timeit limit_sum1(vec, total)
1000 loops, best of 3: 733 µs per loop
3
Divakar 1 nov. 2017 a las 10:42