Como me afasto da escola de pensamento “for-loop”?

Essa é uma pergunta bastante conceitual, mas eu esperava conseguir alguns bons conselhos sobre isso. Muita da programação que faço é com matrizes ( NumPy ); Frequentemente, tenho que combinar itens em duas ou mais matrizes de tamanhos diferentes e a primeira coisa a que vou é um loop for ou, pior ainda, um loop for aninhado. Eu quero evitar os loops, tanto quanto possível, porque eles são lentos (pelo menos em Python).

Eu sei que para muitas coisas com o NumPy existem comandos predefinidos que eu só preciso pesquisar, mas você (como programadores mais experientes) tem um processo de pensamento geral que vem à mente quando você precisa iterar algo?

Então, muitas vezes tenho algo assim, o que é horrível e quero evitá-lo:

small_array = np.array(["one", "two"])
big_array = np.array(["one", "two", "three", "one"])

for i in range(len(small_array)):
    for p in range(len(big_array)):
        if small_array[i] == big_array[p]:
            print "This item is matched: ", small_array[i]

Eu sei que existem várias maneiras diferentes de conseguir isso em particular, mas estou interessado em um método geral de pensamento, se existir.

Essa é uma dificuldade conceitual comum ao aprender a usar o NumPy com eficiência. Normalmente, o processamento de dados no Python é melhor expresso em termos de iteradores , para manter baixo o uso de memória, maximizar oportunidades de paralelismo com o sistema de E / S e fornecer reutilização e combinação de partes de algoritmos.

Mas o NumPy inverte tudo isso: a melhor abordagem é expressar o algoritmo como uma sequência de operações de toda a matriz , para minimizar a quantidade de tempo gasto no interpretador lento do Python e maximizar a quantidade de tempo gasto nas rotinas NumPy compiladas rapidamente.

Aqui está a abordagem geral que tomo:

1. Mantenha a versão original da função (que você acredita estar correta) para poder testá-la em relação às versões aprimoradas, tanto quanto à correção e à velocidade.

2. Trabalhe de dentro para fora: ou seja, comece com o loop mais interno e veja se pode ser vetorizado; quando você tiver feito isso, saia de um nível e continue.

3. Gaste muito tempo lendo a documentação do NumPy . Existem muitas funções e operações lá e elas nem sempre são nomeadas de maneira brilhante, por isso vale a pena conhecê-las. Em particular, se você estiver pensando, "se houvesse uma função que fizesse isso e aquilo", vale a pena gastar dez minutos procurando por ela. Geralmente está lá em algum lugar.

Não há substituto para a prática, então vou dar alguns exemplos de problemas. A meta para cada problema é reescrever a função para que ele é totalmente vectorizada : isto é, de modo que consiste em uma sequência de operações Numpy em matrizes de inteiros, sem alças nativas Python (nenhum forou whiledemonstrações, não há iterators ou comprehensions).

Problema 1

def sumproducts(x, y):
    """Return the sum of x[i] * y[j] for all pairs of indices i, j.

    >>> sumproducts(np.arange(3000), np.arange(3000))
    20236502250000

    """
    result = 0
    for i in range(len(x)):
        for j in range(len(y)):
            result += x[i] * y[j]
    return result

Problema 2

def countlower(x, y):
    """Return the number of pairs i, j such that x[i] < y[j].

    >>> countlower(np.arange(0, 200, 2), np.arange(40, 140))
    4500

    """
    result = 0
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] < y[j]:
                result += 1
    return result

Problema 3

def cleanup(x, missing=-1, value=0):
    """Return an array that's the same as x, except that where x ==
    missing, it has value instead.

    >>> cleanup(np.arange(-3, 3), value=10)
    ... # doctest: +NORMALIZE_WHITESPACE
    array([-3, -2, 10, 0, 1, 2])

    """
    result = []
    for i in range(len(x)):
        if x[i] == missing:
            result.append(value)
        else:
            result.append(x[i])
    return np.array(result)

Spoilers abaixo. Você obterá os melhores resultados se tentar antes de olhar para as minhas soluções!

resposta 1

np.sum (x) * np.sum (y)

Resposta 2

np.sum (np.searchsorted (np.sort (x), y))

Resposta 3

np.where (x == ausente, valor, x)

Para tornar as coisas mais rápidas, você precisa ler suas estruturas de dados e usar as apropriadas.

Para tamanhos não triviais de matriz pequena e matriz grande (digamos, pequeno = 100 elementos e grande = 10.000 elementos), uma maneira de fazer isso é classificar a matriz pequena, iterar sobre a matriz grande e usar uma pesquisa binária para encontrar elementos correspondentes na pequena matriz.

Isso tornaria a complexidade de tempo máxima, O (N log N) (e para pequenas matrizes pequenas e muito grandes) é mais próxima de O (N)) onde sua solução de loop aninhado é O (N ^ 2)

Contudo. quais estruturas de dados são mais eficientes depende muito do problema real.

Você pode usar um dicionário para otimizar significativamente o desempenho

Este é outro exemplo:

locations = {}
for i in range(len(airports)):
    locations[airports["abb"][i][1:-1]] = (airports["height"][i], airports["width"][i])

for i in range(len(uniqueData)):
    h, w = locations[uniqueData["dept_apt"][i]]
    uniqueData["dept_apt_height"][i] = h
    uniqueData["dept_apt_width"][i] = w