Binary Search on Keys of SortedList <K, V>

Question

Necesito escribir un código para la interpolación lineal y estoy tratando de encontrar la manera más eficiente de buscar las claves de un SortedList<K, V> para las teclas superior e inferior que rodean mi tecla objetivo.

SortedList<int, double> xyTable = new SortedList<int, double>() 
{ 
    {1, 10}, {2, 20}, {3, 30}, {4,40} 
}; 

double targetX = 3.5; 

¿Cuál es la forma más eficiente de buscar en la lista y determinar que 3.5 está entre 3 y 4? Tengo un método/truco que funciona para enteros (inserte temporalmente la clave objetivo en la lista y luego encuentre el índice) pero pensé que podría preguntar a los profesionales para poder producir un código de calidad.

Gracias.

Answer 1

Una búsqueda binaria le ofrece un rendimiento decente en una lista. Sin embargo, la propiedad Keys en SortedList es de tipo IList, mientras que BinarySearch se define en List. Afortunadamente, se puede encontrar una aplicación de búsqueda binaria para IList en esta pregunta relacionada:

How to perform a binary search on IList<T>?

Answer 2

public class Bounds 
{ 
    int lower; 
    int upper; 

    public Bounds(int lower, int upper) 
    { 
     this.lower = lower; 
     this.upper = upper; 
    } 
} 

public Bounds BinarySearch(List<int> keys, double target) 
{ 
    // lower boundary case returns the smallest key as the lower and upper bounds 
    if (target < keys[0]) 
     return new Bounds(0, 0); 

    else if (target < keys[1]) 
     return new Bounds(0, 1); 

    // upper boundary case returns the largest key as the lower and upper bounds 
    else if (target > keys[keys.Length - 1]) 
     return new Bounds(keys.Length - 1, keys.Length - 1); 

    else if (target > keys[keys.Length - 2]) 
     return new Bounds(keys.Length - 2, keys.Length - 1); 

    else 
     return BinarySearch(keys, target, 0, keys.Length - 1); 

} 

// 'keys' is a List storing all of the keys from your SortedList. 
public Bounds BinarySearch(List<int> keys, double target, int lower, int upper) 
{ 
    int middle = (upper + lower)/2; 

    // target is equal to one of the keys 
    if (keys[middle] == target) 
     return new Bounds(middle - 1, middle + 1); 

    else if (keys[middle] < target && keys[middle + 1] > target) 
     return new Bounds(middle, middle + 1); 

    else if (keys[middle] > target && keys[middle - 1] < target) 
     return new Bounds(middle - 1, middle); 

    if (list[middle] < target) 
     return BinarySearch(list, target, lower, upper/2 - 1); 

    if (list[middle] > target) 
     return BinarySearch(list, target, upper/2 + 1, upper); 
} 

Esto podría work..I no probarlo. Si no, con suerte está lo suficientemente cerca como para poder usarlo con ajustes menores. Este es un problema extraño, así que manejé todos los casos límite así que no tuve que pensar sobre qué haría el algoritmo cuando el alcance fuera a 2 elementos o menos.

Answer 3

En mi caso, la fuente SortedList no cambia mucho, ya que se usa como una tabla de búsqueda. Entonces, en este caso, tiene sentido convertir el SortedList a List<T> una vez. Después de que es muy fácil de usar la incorporada en el método de BinarySearch List<T> ...

double targetX = 3.5; 

// Assume keys are doubles, may need to convert to doubles if required here. 
// The below line should only be performed sparingly as it is an O(n) operation. 
// In my case I only do this once, as the list is unchanging. 
List<double> keys = xyTable.Keys.ToList(); 

int ipos = keys.BinarySearch(targetX); 

if (ipos >= 0) 
{ 
    // exact target found at position "ipos" 
} 
else 
{ 
    // Exact key not found: BinarySearch returns negative when the 
    // exact target is not found, which is the bitwise complement 
    // of the next index in the list larger than the target. 
    ipos = ~ipos; 
    if (ipos >= 0 && ipos < keys.Count) 
    { 
     if (ipos > 0) 
     { 
      // target is between positions "ipos-1" and "ipos" 
     } 
     else 
     { 
      // target is below position "ipos" 
     } 
    } 
    else 
    { 
     // target is above position "ipos" 
    } 
} 

Answer 4

De MSDN,

Los elementos de un objeto SortedList están ordenadas según cualquiera de las teclas de acuerdo con un IComparer específica implementación especificada cuando se crea SortedList, o de acuerdo con la implementación IComparable proporcionada por las claves mismas. La secuencia de índice se basa en la secuencia de clasificación. Cuando se agrega un elemento, se inserta en SortedList en el orden correcto, y la indexación se ajusta en consecuencia. Cuando se elimina un elemento, la indexación también se ajusta en consecuencia. Por lo tanto, el índice de un par clave/valor específico puede cambiar a medida que se agregan o eliminan elementos de SortedList.

***** Este método utiliza un algoritmo de búsqueda binario; por lo tanto, este método es una operación O (log n), donde n es Count. *****

Comenzando con .NET Framework 2.0, este método utiliza los métodos Equal y CompareTo de los objetos de la colección en el elemento para determinar si el artículo existe En las versiones anteriores de .NET Framework, esta determinación se realizó utilizando los métodos Equals y CompareTo del parámetro item en los objetos en la colección.

En otras palabras, el método IndexOfKey en SortedList ya usa un algoritmo binarySearch, por lo que no es necesario convertir SortedList en List en su caso.

creo que sirve ..