Tri des nombres de 10 ** 6 chiffres dans Python 2 efficacement

Question

J'ai utilisé le type long pour stocker des nombres et trier en utilisant la méthode de tri normale, mais ce n'était pas assez efficace. Je pense que long(raw_input()) prend trop de temps. Quelqu'un peut-il penser à une manière efficace de le résoudre?

n = int(raw_input().strip()) 
unsorted = [] 
for i in xrange(n): 
    term = long(raw_input()) 
    unsorted.append(term) 

for i in sorted(unsorted): 
    print i 

Answer 1

Puisque vous avez dit qu'il est une question de programmation compétitive cette solution fonctionnerait autrement il ne fonctionnera jamais car il a besoin beaucoup trop de mémoire et briserait dans les mauvais cas. Mais dans la programmation compétitive, les contraintes ne sont pas tellement et cela devrait fonctionner.

Nous ajoutons simplement le comparateur ie gt et lt méthodes qui décident de la comparaison entre les 2 objets.

class VeryBigNumber(object): 
    def __init__(self,number_string): 
     self.number = number_string 


def __gt__(self,other): 
    if len(self.number)>len(other.number): 
     return True 
    elif len(self.number)<len(other.number): 
     return False 

    for i in xrange(min(len(self.number),len(other.number))): 
     if int(self.number[i])>int(other.number[i]): 
      return True 
     elif int(self.number[i])<int(other.number[i]): 
      return False 
    return False 

def __eq__(self,other): 
    return self.number == other.number 

def __lt__(self,other): 
    return not (self.__eq__(other) or self.__gt__(other)) 

arr = [] 
for i in xrange(n): 
    arr.append(VeryBigNumber(raw_input().strip()) 

arr = sorted(arr) 
for a in arr: 
    print a.number, 

Big Explication:

1. Dans les commentaires que vous avez dit qu'il est pour une compétition de codage. Cela nous assure que la mémoire est suffisamment petite pour que nous puissions lire en moins d'une seconde.

2. Nous ne convertissons pas une chaîne trop grande en nombre car cela serait inutile. Au lieu de cela, nous gardons la chaîne telle quelle.

3. Comment le trions-nous alors? Nous faisons notre propre classe et utilisons des comparaisons de chaînes.

4. Ils fonctionnent en comparant les chiffres de caractères entre les chaînes et ainsi, un seul caractère est converti en int à un moment très efficace.

5. J'ai testé le code ci-dessus et il fonctionne correctement