1

Possuo uma lista com aproximadamente 1,5 milhões de valores e preciso definir qual é a mediana deste conjunto. Os valores estão armazenados em um arquivo, como string, entre aspas simples (ex.: '155').

Quais as formas de eu calcular a mediana deste montante de valores?

Obs.: Não posso utilizar as funções prontas, tal como min, max, etc.

5
  • 1.5mi são 1500 ou um milhão e meio?
    – Woss
    Commented 9/08/2018 às 19:01
  • São aproximadamente 1 milhão e meio de linhas.
    – daaug
    Commented 9/08/2018 às 19:44
  • Daniel, tomei a liberdade para editar sua pergunta e deixá-la um pouco mais direta. Poderia confirmar para mim se por acaso não errei na interpretação e alterei a pergunta?
    – Woss
    Commented 9/08/2018 às 20:08
  • 1
    @AndersonCarlosWoss não errou na interpretação e ficou muito melhor. Obrigado!
    – daaug
    Commented 9/08/2018 às 20:16
  • Veja este código Commented 15/08/2018 às 14:23

3 Respostas 3

1

Neste tipo de problema temos que ter muito cuidado com tempo de execução e memória. Trabalhar com listas pode ser um problema. Por enquanto sugiro essa solução.

1) Ler o arquivo linha a linha e, enquanto lê, já adiciona os números em uma lista de maneira ordenada

Para isso, vamos usar esta função que coloca um numero em uma lista na posição ordenada.

def adiciona_na_ordem(lista, tamanho_lista, numero):
    for i in range(0, tamanho_lista):
        if numero < lista[i]:
            break
    else:
        i+=1
    return lista[:i]+[numero]+lista[i:]

>>> lista = [0,1,2,3]
>>> print (adiciona_na_ordem(lista, len(lista), 10))
[0, 1, 2, 3, 10]

E ler o arquivo linha a linha:

entrada = open('dados.txt', 'r')

lista_ordenada = [int(entrada.readline())] #Para não inicializar a lista vazia
num_lidos = 1 #Evita usar len(lista_ordenada)
for linha in entrada:
    numero = int(linha)
    lista_ordenada = adiciona_na_ordem(lista_ordenada, num_lidos, numero)
    num_lidos += 1

entrada.close()

Um exemplo seria:

para uma entrada:
7
7
1
4
4
5
6
7

>>> print (lista_ordenada)
[1, 4, 4, 5, 6, 7, 7, 7]

2) Pegar a mediana

if num_lidos % 2 == 1:
    mediana = lista_ordenada[num_lidos//2]
else:
    mediana = (lista_ordenada[num_lidos//2 -1]+lista_ordenada[num_lidos//2]) / 2
1

Bom, as informações estão meio vagas e também não se sabe o formato do arquivo onde estão esses dados, com isso, posso te passar apenas uma ideia do que fazer.

1) Ler o arquivo e botar os valores numa lista(se o arquivo for .csv vai facilitar muito).

2) Transforma-los em intergers usando o int().

3) Usar a função sorted() para ordenar a lista, exemplo aqui.

4) Calcular o tamanho total da lista usando a função len().

5) Pegar o tamanho total da lista e calcula o resto da divisão desse número por 2 usando o sinal de %.

6) Se for par, você faz a média dos elementos centrais, se for impar a mediana é o elemento central da sua lista.

2
  • 1
    E fazer isso com 1,5 milhões de números? Parece inviável para mim.
    – Woss
    Commented 9/08/2018 às 23:53
  • 1
    Fica realmente pesado, concordo, mas na ausência de alternativa... Há maneiras de processar esse arquivo separadamente, tipo dividi-lo em X partes, ordenar, contar a ocorrência de casos e posteriormente tirar a conclusão... Mas aí já seria outro processo... Commented 10/08/2018 às 0:05
1

Gostaria de sugerir outra abordagem. Se os números forem inteiros ou com poucas casas decimais, muitos deles podem se repetir, então podemos contar o numero de ocorrências de cada número um com um dicionário. Assim, não usamos tanta memória.

1) Lemos o arquivo linha a linha e fazemos um dicionário com as ocorrências ao mesmo tempo que mantemos uma lista com as chaves ordenadas (usaremos futuramente)

Função que coloca um numero em uma lista na posição ordenada:

def adiciona_na_ordem(lista, tamanho_lista, numero):
    for i in range(0, tamanho_lista):
        if numero < lista[i]:
            break
    else:
        i+=1
    return lista[:i]+[numero]+lista[i:]

Lemos linha a linha:

entrada = open('dados.txt', 'r')

primeiro_valor = int(entrada.readline())
ocorrencias = {primeiro_valor:1}
lista_chaves_ordenadas = [primeiro_valor]
num_linhas = 1

for linha in entrada:
    numero = int(linha)
    if numero in ocorrencias: #Se o numero ja esta no dicionario
        ocorrencias[numero] += 1
    else: #Se não está, adiciono em ocorrencias
        ocorrencias[numero] = 1
        #OU ocorrencias.update({numero:1})
        lista_chaves_ordenadas = adiciona_na_ordem(lista_chaves_ordenadas, len(lista_chaves_ordenadas), numero)

    num_linhas += 1

entrada.close()

Exemplo de como ficariam as variaveis:

para uma entrada:
7
7
1
4
4
5
6
7

>>> print (ocorrencias)
{7: 3, 1: 1, 4: 2, 5: 1, 6: 1}
>>> print (lista_chaves_ordenadas)
[1, 4, 5, 6, 7]

2) Agora calculamos a mediana percorrendo o dicionário na ordem das chaves ordenadas até que a soma das ocorrências chegue na metade

if num_linhas % 2 == 1: #Buscamos o elemento central
    num_elementos = 0
    for key in lista_chaves_ordenadas:
        num_elementos += ocorrencias[key]
        if num_elementos >= num_linhas/2:
            print (key)
            break

else: #media dos dois elementos centrais
    num_elementos = 0
    mediana = None
    for key in lista_chaves_ordenadas:
        num_elementos += ocorrencias[key]
        #Prox 2 ifs se os valores medianos forem chaves diferentes, ex: 5 e 6
        if num_elementos == num_linhas/2:
            mediana = key
        if num_elementos > num_linhas/2 and mediana != None:
            mediana += key
            print(mediana/2)
            break
        #Prox if se os valores medianos forem a mesma chave, ex: 6 e 6
        if num_elementos > num_linhas/2 and mediana == None:
            mediana = key
            print(key)
            break

Edit: Se você utilizar pytho2.7, acho que o dicionário já fica ordenado, então não precisa da lista_chaves_ordenadas, basta fazer for key, value in ocorrencias.iteritems(): em vez de for key in lista_chaves_ordenadas:. Mas tome cuidado com as divisões. Faça /2.0 para não arredondar para inteiro

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .