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