bisect python, è possibile lavorare con elenchi ordinati discendenti?

Question

Come posso utilizzare il modulo bisect su liste che vengono ordinate in ordine decrescente? es.

import bisect 

x = [1.0,2.0,3.0,4.0] # normal, ascending 
bisect.insort(x,2.5) # --> x is [1.0, 2.0, 2.5, 3.0, 4.0]  ok, works fine for ascending list 

# however 
x = [1.0,2.0,3.0,4.0] 
x.reverse()   # --> x is [4.0, 3.0, 2.0, 1.0]   descending list 
bisect.insort(x,2.5) # --> x is [4.0, 3.0, 2.0, 1.0, 2.5]  2.5 at end, not what I want really 

Gli unici metodi sono insort (insort_right) o insort_left - nessuno dei quali lavoro per me. Qualche suggerimento? grazie

Answer 1

Probabilmente la cosa più semplice è di prendere in prestito il codice dalla libreria e rendere la propria versione

def reverse_insort(a, x, lo=0, hi=None): 
    """Insert item x in list a, and keep it reverse-sorted assuming a 
    is reverse-sorted. 

    If x is already in a, insert it to the right of the rightmost x. 

    Optional args lo (default 0) and hi (default len(a)) bound the 
    slice of a to be searched. 
    """ 
    if lo < 0: 
     raise ValueError('lo must be non-negative') 
    if hi is None: 
     hi = len(a) 
    while lo < hi: 
     mid = (lo+hi)//2 
     if x > a[mid]: hi = mid 
     else: lo = mid+1 
    a.insert(lo, x) 

Answer 2

Non ho mai usato il pacchetto di bisect. Ma se funziona solo in ordine ascendente e tu stai sempre tenendo in ordine la lista (sia in ordine ascendente che discendente), puoi semplicemente ordinare in anticipo e poi invertirla (se vuoi mantenerla decrescente).

x.sort() 
bisect.insort(x,2.5) 
x.reverse() 

Ovviamente più un hack quindi una soluzione reale ma almeno funzionerebbe.

Answer 3

Dalla documentazione:

A differenza della funzione ordinato(), non non rende senso per le funzioni bisect() per avere argomenti chiave o invertiti perché ciò porterebbe a un design inefficente (chiamate successive a funzioni di bisect sarebbe n ot "ricorda" tutte le precedenti chiavi ricerche).

Pertanto, se si dispone di un elenco con ordine inverso, quindi si è fuori di fortuna.

L'uso principale di bisect è l'aggiornamento efficiente di una lista già ordinata.
È possibile modificare il formato dei dati dell'elenco (ad esempio mantenendolo il più possibile in ordine diretto e quindi invertendolo alla fine), sia per implementare la propria versione di bisect.
Oppure, se non si utilizza l'opzione principale, è possibile scegliere di non utilizzarlo affatto, ad es. inserendo tutti gli elementi e poi ordinandoli alla fine.

Answer 4

Ho avuto lo stesso problema e da quando ho usato l'elenco ordinato.

Mi sono ritrovato con una soluzione in cui ho mantenuto l'elenco originale sempre in ordine crescente e ho utilizzato l'iteratore invertito solo quando avevo bisogno di avere valori di ordine decrescenti.

Questo potrebbe non funzionare con il tuo problema ...

Answer 5

Speriamo che l'argomento "chiave" sarà aggiunto alla bisettrice funzioni del modulo di un giorno (si veda: http://bugs.python.org/issue4356). Sfortunatamente non è possibile senza una qualche soluzione al momento (versione Python < 3.4).

Una possibile soluzione è quella di utilizzare un wrapper come:

class ReversedSequenceView(collections.MutableSequence): 
    def __init__(self, seq): 
     self._seq = seq 

    def __getitem__(self, i): 
     return self._seq[-1 - i] 

    def __setitem__(self, i, v): 
     self._seq[-1 - i] = v 

    def __delitem__(self, i): 
     del self._seq[-1 - i] 

    def __len__(self): 
     return len(self._seq) 

    def insert(self, i, v): 
     return self._seq.insert(len(self._seq) - i, v) 

Usage:

>>> x = [4., 3., 2., 1.] 
>>> bisect.insort(ReversedSequenceView(x), 2.5) 
>>> x 
[4.0, 3.0, 2.5, 2.0, 1.0] 

Answer 6

leggermente aggiornata codice bisect libreria:

def reverse_bisect_right(a, x, lo=0, hi=None): 
    """Return the index where to insert item x in list a, assuming a is sorted in descending order. 

    The return value i is such that all e in a[:i] have e >= x, and all e in 
    a[i:] have e < x. So if x already appears in the list, a.insert(x) will 
    insert just after the rightmost x already there. 

    Optional args lo (default 0) and hi (default len(a)) bound the 
    slice of a to be searched. 

    Essentially, the function returns number of elements in a which are >= than x. 
    >>> a = [8, 6, 5, 4, 2] 
    >>> reverse_bisect_right(a, 5) 
    3 
    >>> a[:reverse_bisect_right(a, 5)] 
    [8, 6, 5] 
    """ 
    if lo < 0: 
     raise ValueError('lo must be non-negative') 
    if hi is None: 
     hi = len(a) 
    while lo < hi: 
     mid = (lo+hi)//2 
     if x > a[mid]: hi = mid 
     else: lo = mid+1 
    return lo