🐍 Benchmark entre IN, IN + SLICING e FIND + OFFSET: qual é mais eficiente?

in-slicing-vs-find-offset.py

"""
Dado uma sequência enorme, você deve descobrir se um
item específico se encontra nela, e você sabe que ele
só pode estar entre o meio e o fim da sequência.

Mas o que seria mais rápido?

1) Percorrer ela inteira: `item in sequence`.
2) Fatiar no meio: `item in sequence[middle:]`.
3) Percorrer da metade: `sequence.find(item, middle)`

====================================================
                  RESULTADOS
====================================================
IN                  13.20 s     0.26 MB
IN + SLICING        11.51 s     29.99 MB
FIND + OFFSET       6.76  s     0.04 MB
====================================================

Como esperado, `FIND + OFFSET` é muito mais eficiente
tanto em performance quanto em consumo de memória.

Ao fatiar você estará realizando uma cópia,
e isto ocupa espaço sem necessidade, além de levar
tempo até copiar os itens dependendo da quantidade.

----------------------------------------------------
1.95x mais rápido que `IN`
1.70x mais rápido que `IN + SLICING`
----------------------------------------------------
6.50x menos espaço que um simples `IN`
749.75x menos espaço que `IN + SLICING`
----------------------------------------------------

Considerando que `FIND + OFFSET` usa aproximadamente
uma complexidade de espaço constante O(1) e
`IN + SLICING` linear O(n), acaba perdendo o sentido
comparar a economia de espaćo de ambos, pois quanto
mais itens houver maior será a diferença esmagadora
de economia.

Mas é claro que em cópias pequenas é quase imperceptível
a diferença.
"""

import tracemalloc
from timeit import timeit

# Quantidade de itens.
length = 8_000_000
# Gerando sequencia de itens.
numbers = list(map(str, range(length)))
# Transformando em uma string grande.
string = ' '.join(numbers)
# Meio da string.
middle = len(string) // 2 - 1
# Último número da string.
last_number = numbers[-1]
# Quantidade de vezes que vai rodar.
times = 150

def run(title: str, code: str) -> None:
  # Inicia rastreio de alocação de memória.
  tracemalloc.start()
  # Executa o código varias vezes.
  time = timeit(code, number=times, globals=globals())
  # Obtém o maior pico de memória.
  _, memory_peak = tracemalloc.get_traced_memory()
  # Encerra o rastreio de alocação de memória.
  tracemalloc.stop()
  # Exibe resultados.
  print('{title:<20}{time:<6.2f}s\t{memory_peak:.2f} MB'.format(
   title=title,
   time=time,
   memory_peak=memory_peak / 1024 / 1024
  ))

# Sei que o item que procuro não está no começo
# da string, mas vou percorrer a string inteira
# mesmo assim.
run('IN', 'last_number in string')

# Decidimos pegar um atalho pra encontrar ele mais rápido,
# porém isto vai copiar metade da string pra memoria,
# o que torna o processo mais lento e ineficiente.
run('IN + SLICING', 'last_number in string[middle:]')

# O método find() não realiza cópias, portanto não faz
# uso absurdo de memória, o que torna o processo ainda
# mais rápido.
run('FIND + OFFSET', 'string.find(last_number, middle) != -1')