Classificar uma lista ao juntar ou depois?

5

Eu tenho que ler uma quantidade extremamente grande de dados de rede de vários arquivos de log e compilar informações relevantes sobre esses dados para realizar análises estatísticas (os principais comunicadores, principais endereços IP que enviam em média os maiores pacotes, média tamanho do pacote, etc.) Eu decidi fazer uma matriz onde cada índice na matriz externa corresponde a uma lista ordenada de ips em ordem incremental.

Para ter uma ideia do meu conjunto de dados, eu tenho um arquivo de log que é gerado a cada dia, que contém informações sobre toda a comunicação que ocorreu em uma rede naquele dia. Tenho gerado arquivos de log desde meados de maio e cada arquivo de log tem cerca de 5 milhões de linhas cada, então, quanto mais eficiente for esse programa, melhor.

Minha pergunta é a seguinte:

Quando estou compilando dados de todos os arquivos de log para essa matriz, devo classificar minha camada de matriz externa por IPs enquanto ainda estou reunindo os dados ou apenas acrescentar novos IPs ao final do arquivo? como eu os encontro e depois classifico a lista depois? Existe uma opção melhor aqui que eu não tenha pensado? qual caminho seria o mais eficiente? Eu vou estar usando python 2.7, se isso faz diferença. Além disso, devido a restrições sobre o que eu posso fazer, eu não posso instalar nenhum novo módulo na máquina em que este código será executado, então a menos que eu possa criar um banco de dados com python nativamente, isso não é um disponível opção para mim.

    
por Ben Schwabe 13.11.2015 / 22:56
fonte

2 respostas

5

A ordenação por inserção funciona melhor quando você insere um novo valor em algo que já está classificado. Então, o que eu faria é usar o Quicksort para classificar o conjunto de dados original que você tem e, em seguida, quando entradas de log adicionais entrarem, adicione-as uma a uma no conjunto já classificado.

Com Quicksort sendo O (n * logn) e Insertion Sort sendo O (n) quando usado com um conjunto já classificado, o tempo total para tudo será O (a * log (a) + b), onde a é o tamanho do conjunto de dados original eb são os registros adicionais que você coloca depois.

    
por 13.11.2015 / 22:58
fonte
-1

Inserir tudo não faz comparações, classificá-lo depois é em O (n * log (n)), então inserir e depois ordenar é em O (n * log (n))

Inserir um elemento em uma lista ordenada para manter uma lista ordenada é logarítmico no tamanho da lista, portanto, a inserção de n elementos nessa lista está em O (n * log (n)), já que o tamanho da lista cresce à medida que você continua inserindo elementos.

Portanto, ele tem uma complexidade semelhante em termos de comparações, mas inserir um elemento em python é muito mais caro do que acrescentar (linear com o tamanho da lista em vez de constante). O mais eficiente é, portanto, acrescentar tudo e depois ordenar.

Aqui está um exemplo de código para verificar o desempenho do processamento de números aleatórios de 10000:

import random
import timeit
import bisect


def append_then_sort(data):
    result = []

    for element in data:
        result.append(element)

    result.sort()
    return result


def insert_sorted(data):
    result = []

    for element in data:
        bisect.insort_left(result, element)

    return result

if __name__ == '__main__':
    numbers = [random.randint(0, 3000000) for _ in xrange(10000)]
    print('Append then sort:')
    print(timeit.timeit('append_then_sort(numbers)', setup='from __main__ import append_then_sort, numbers', number=10))
    print('Insert sorted:')
    print(timeit.timeit('insert_sorted(numbers)', setup='from __main__ import insert_sorted, numbers', number=10))

E os resultados na minha máquina:

Append then sort:
0.0509831905365
Insert sorted:
0.27309513092

Você também pode estar interessado em pesquisar no módulo sqlite3 que faz parte da biblioteca Python padrão por isso deve estar disponível em seu sistema. Eu não tenho certeza de como o sqlite lida com bancos de dados grandes, no entanto ...

    
por 14.11.2015 / 14:28
fonte