python bisect, ¿es posible trabajar con listas ordenadas descendentes?

Question

¿Cómo puedo usar el módulo bisect en las listas que se ordenan descendentemente? por ej.

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 

Los únicos métodos son insort (insort_right) o insort_left - ninguno de los cuales el trabajo para mí. ¿Alguna sugerencia? gracias

Answer 1

Probablemente, lo más fácil es pedir el código de la biblioteca y hacer su propia versión

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

Nunca me he acostumbrado al paquete bisecado. Pero si solo funciona en orden ascendente y usted siempre mantiene su lista ordenada (ya sea ascendente o descendente), entonces puede ordenarla de antemano y luego invertirla (si desea mantenerla descendente).

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

Obviamente, más un truco que una solución real, pero al menos funcionaría.

Answer 3

De la documentación:

A diferencia de la función sorted(), no no hace sentido para las funciones de bisección() para tener argumentos clave o invertidos porque eso llevaría a un diseño ineficaz (llamadas sucesivas para bisectar funciones n ot "recuerde" todas las búsquedas de la clave anterior ).

Por lo tanto, si tiene una lista con orden inverso, entonces no tiene suerte.

El principal uso de bisect es la actualización eficiente de una lista ya ordenada.
Es posible que desee cambiar el formato de datos de su lista (por ejemplo, mantenerlo en orden directo tanto como sea posible y luego invertirlo al final), ya sea para implementar su propia versión de bisect.
O, si no está en el uso principal, puede optar por no usarlo en absoluto, p. insertando todos los elementos y luego ordenándolos al final.

Answer 4

Tuve el mismo problema y desde cuando utilicé la lista ordenada.

Terminé con una solución en la que mantenía la lista original siempre en orden ascendente y solo usaba el iterador invertido cuando necesitaba valores de orden descendente.

Esto podría no funcionar con su problema ...

Answer 5

Con suerte se añadirá el argumento "clave" para dividir en dos funciones del módulo de un día (ver: http://bugs.python.org/issue4356). Lamentablemente, no es posible sin algún tipo de solución en este momento (Python versión < 3.4).

Una posible solución es utilizar un envoltorio como:

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) 

Uso:

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

Answer 6

ligeramente modificada código bisect biblioteca:

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