Tri d'une liste: nombres en croissant, lettres en ordre décroissant

Question

Cette question est actuellement adaptée de one previously asked by Mat.S (image). Bien qu'il ait été supprimé, j'ai pensé que c'était une bonne question, alors je le repositionne avec des exigences plus claires et ma propre solution.

---

Étant donné une liste de lettres et de chiffres, disent

['a', 2, 'b', 1, 'c', 3] 

L'exigence est de trier les nombres par ordre croissant et des lettres en ordre descendant, sans modifier la position relative des lettres et des chiffres. Par là, je veux dire que si la liste non triée est:

[L, D, L, L, D] # L -> letter; # D -> digit 

Ensuite, la liste triée doit également être

[L, D, L, L, D] 

1. Les lettres et les chiffres ne pas nécessairement alternent dans un schéma régulier - ils peuvent apparaître dans n'importe quel ordre arbitraire

2. Après le tri - les nombres sont ascendants, les lettres sont descendantes.

Pour l'exemple ci-dessus, la sortie est

['c', 1, 'b', 2, 'a', 3] 

Un autre exemple:

In[]: [5, 'a', 'x', 3, 6, 'b'] 
Out[]: [3, 'x', 'b', 5, 6, 'a'] 

Quelle serait une bonne façon de le faire?

Answer 1

Voici une approche optimisée en utilisant defaultdict() et bisect():

In [14]: lst = [5, 'a', 'x', 3, 6, 'b'] 
In [15]: from collections import defaultdict  
In [16]: import bisect 

In [17]: def use_dict_with_bisect(lst): 
      d = defaultdict(list) 
      for i in lst: 
       bisect.insort(d[type(i)], i) 
      # since bisect doesn't accept key we need to reverse the sorted integers 
      d[int].sort(reverse=True) 
      return [d[type(i)].pop() for i in lst] 
    .....: 

Démo:

In [18]: lst 
Out[18]: [5, 'a', 'x', 3, 6, 'b'] 

In [19]: use_dict_with_bisect(lst) 
Out[19]: [3, 'x', 'b', 5, 6, 'a'] 

Si vous avez affaire à des listes plus grandes, il est plus optimisé pour déposer à l'aide bisect qui a une complexité à propos de O (n) et il suffit d'utiliser python intégré sort() fonction avec Nlog (n) complexité.

In [26]: def use_dict(lst): 
      d = defaultdict(list) 
      for i in lst: 
       d[type(i)].append(i) 
      d[int].sort(reverse=True); d[str].sort() 
      return [d[type(i)].pop() for i in lst] 

Benchmark avec d'autres réponses qui montre la dernière approche en utilisant dict et intégré sort est presque 1ms plus vite que les autres approches:

In [29]: def use_sorted1(lst): 
       letters = sorted(let for let in lst if isinstance(let,str)) 
       numbers = sorted((num for num in lst if not isinstance(num,str)), reverse = True) 
       return [letters.pop() if isinstance(elt,str) else numbers.pop() for elt in lst] 
    .....: 

In [31]: def use_sorted2(lst): 
       f1 = iter(sorted(filter(lambda x: isinstance(x, str), lst), reverse=True)) 
       f2 = iter(sorted(filter(lambda x: not isinstance(x, str), lst))) 
       return [next(f1) if isinstance(x, str) else next(f2) for x in lst] 
    .....: 

In [32]: %timeit use_sorted1(lst * 1000) 
100 loops, best of 3: 3.05 ms per loop 

In [33]: %timeit use_sorted2(lst * 1000) 
100 loops, best of 3: 3.63 ms per loop 

In [34]: %timeit use_dict(lst * 1000) # <-- WINNER 
100 loops, best of 3: 2.15 ms per loop 

Voici une référence qui montre comment l'utilisation bisect peut ralentir le processus pour de longues listes:

In [37]: %timeit use_dict_with_bisect(lst * 1000) 
100 loops, best of 3: 4.46 ms per loop 

Answer 2

Regardez ma, pas iter:

lst = ['a', 2, 'b', 1, 'c', 3] 
letters = sorted(let for let in lst if isinstance(let,str)) 
numbers = sorted((num for num in lst if not isinstance(num,str)), reverse = True) 
lst = [(letters if isinstance(elt,str) else numbers).pop()for elt in lst] 

Je suis à la recherche d'un moyen de transformer cela en un (affreux) en une ligne, mais pas de chance jusqu'à présent - suggestions sont les bienvenus!

Answer 3

Je pris une fissure à cela en créant deux générateurs et leur ôtant certaines conditions:

In [116]: f1 = iter(sorted(filter(lambda x: isinstance(x, str), lst), reverse=True)) 

In [117]: f2 = iter(sorted(filter(lambda x: not isinstance(x, str), lst))) 

In [118]: [next(f1) if isinstance(x, str) else next(f2) for x in lst] 
Out[118]: ['c', 1, 'b', 2, 'a', 3] 

Answer 4

en une ligne:

list(map(list, sorted(zip(lst[::2], lst[1::2]), key=lambda x: x[1] if hasattr(x[0], '__iter__') else x[0]))) 

Answer 5

Pour déconseillé, mais je me suis amusé à le coder.

from collections import deque 
from operator import itemgetter 

lst = ['a', 2, 'b', 1, 'c', 3] 
is_str = [isinstance(e, str) for e in lst] 
two_heads = deque(map(itemgetter(1), sorted(zip(is_str, lst)))) 
[two_heads.pop() if a_str else two_heads.popleft() for a_str in is_str] 

Answer 6

Pourquoi ne pas nous trions simplement la liste dans l'ordre croissant, mais assurez-vous que les chiffres précèdent les lettres:

[D, D, L, L, L] # L -> letter; # D -> digit 

Nous pouvons atteindre cet objectif de manière à:

>>> lst = [5, 'a', 'x', 3, 6, 'b'] 
>>> sorted(lst, key=lambda el: (isinstance(el, str), el)) 
[3, 5, 6, 'a', 'b', 'x'] 

Ensuite, nous regardons le tableau original de gauche à droite et si nous rencontrons un nombre, nous choisissons l'élément depuis le début du tableau trié, sinon à partir de la fin. La solution verbeux complète sera alors:

def one_sort(lst): 
    s = sorted(lst, key=lambda el: (isinstance(el, str), el)) 
    res = [] 
    i, j = 0, len(s) 
    for el in lst: 
     if isinstance(el, str): 
      j -= 1 
      res.append(s[j]) 
     else: 
      res.append(s[i]) 
      i += 1 
    return res 

lst = [5, 'a', 'x', 3, 6, 'b'] 
print(one_sort(lst)) # [3, 'x', 'b', 5, 6, 'a'] 

Beaucoup plus court, mais la solution cryptique sera:

def one_sort_cryptic(lst): 
    s = sorted(lst, key=lambda el: (isinstance(el, str), el)) 
    return [s.pop(-isinstance(el, str)) for el in lst] 

lst = [5, 'a', 'x', 3, 6, 'b'] 
print(one_sort_cryptic(lst)) # [3, 'x', 'b', 5, 6, 'a']