Map from integer ranges to arbitrary single integers

Question

Trabajando en C++ en un entorno Linux, tengo una situación en la que se definen varios rangos enteros, y las entradas enteras se asignan a diferentes enteros arbitrarios en función del rango en el que caen. Ninguno de los rangos se superpone, y no siempre son contiguos.

La forma "más simple" de resolver este problema es con un montón de sentencias if para cada rango, pero el número de rangos, sus límites y los valores objetivo pueden variar, por lo que las sentencias if no son mantenibles .

Por ejemplo, los rangos pueden ser [0, 70], llamados r_a, [101, 150], llámalo r_b y [201, 400], llámalo r_c. Las entradas en r_a se asignan a 1, en r_b asignan a 2 y r_c asignan a 3. Cualquier cosa que no esté en r_a, r_b, r_c se asigna a 0.

Puedo encontrar una estructura de datos & algoritmo que almacena tuplas de (límites, objetivo de mapa) y los itera a través de ellos, por lo que encontrar el valor objetivo requiere tiempo lineal en el número de pares de límites. También puedo imaginarme un esquema que mantiene los pares ordenados y utiliza un algoritmo binario sort-ish contra todos los límites inferiores (o límites superiores), encuentra el más cercano a la entrada y luego se compara con el límite opuesto.

¿Hay una mejor manera de realizar la asignación que un algoritmo basado en búsqueda binaria? Mejor aún, ¿hay alguna biblioteca de C++ que ya lo haga?

Answer 1

me gustaría utilizar una cosa muy simple: una std::map.

class Range 
{ 
public: 
    explicit Range(int item); // [item,item] 
    Range(int low, int high); // [low,high] 

    bool operator<(const Range& rhs) const 
    { 
    if (mLow < rhs.mLow) 
    { 
     assert(mHigh < rhs.mLow); // sanity check 
     return true; 
    } 
    return false; 
    } // operator< 

    int low() const { return mLow; } 
    int high() const { return mHigh; } 

private: 
    int mLow; 
    int mHigh; 
}; // class Range 

A continuación, vamos a tener un mapa:

typedef std::map<Range, int> ranges_type; 

y escribir una función que buscar en este mapa:

int find(int item, const ranges_type& ranges) 
{ 
    ranges_type::const_iterator it = ranges.lower_bound(Range(item)); 
    if (it != ranges.end() && it->first.low() <= item) 
    return it->second; 
    else 
    return 0; // No mapping ? 
} 

beneficios principales:

• comprobará que los rangos efectivamente no se superponen durante la inserción en el s y (que puede hacerlo de modo que es sólo en el modo de depuración)
• Soporta edición de los rangos sobre la marcha
• hallazgo es rápido (búsqueda binaria)

Si se congelan los rangos (aunque su los valores no lo son), es posible que desee utilizar Loki::AssocVector para reducir la sobrecarga de memoria y mejorar el rendimiento un poco (básicamente, es un vector ordenado con la interfaz de un mapa).

Answer 2

Una lista de enlaces simple que contiene las entradas del rango debe ser lo suficientemente rápida, incluso para, digamos, 50-100 rangos. Además, podría implementar un Skip List, por ejemplo, los límites superiores, para acelerar estas consultas de rango. Todavía otra posibilidad es un Interval Tree.

Al final elegiría la más simple: búsqueda binaria.

Answer 3

Su ejemplo se superpone, pero la pregunta dice que no. Asumiré que el rango es un error tipográfico. Podría, podría, almacenar los destinos en una matriz y usar los índices como rangos. Es bastante fácil, pero feo y no muy fácil de mantener. Debería inicializar la matriz en 0, luego para cada rango, iterar sobre esos índices y establecer cada índice en el valor de destino. Muy feo, pero el tiempo de búsqueda constante por lo que puede ser útil si los números no son demasiado altos y los rangos no cambian muy a menudo.

Answer 4

Registre los límites en set (o map). Cuando llame al insert, tendrá un valor de retorno que es un par. Un iterador y un booleano. Si el valor booleano es verdadero, se crea un nuevo elemento que debe eliminar más adelante. Después de ese paso uno con el iterador y mira lo que has encontrado.

http://www.cplusplus.com/reference/stl/set/insert/ Ver Valor de retorno

Answer 5

No sería una simple matriz será suficiente? No está diciendo cuántos elementos tiene, pero con mucho, la estructura de datos más rápida es una matriz simple.

Si los rangos son:

• 0..9 -> 25
• 10..19 -> 42

entonces la matriz sería simplemente como esto:

[25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42] 

Answer 6

Puede tener dos matrices ordenadas: una para los límites inferiores, una para los límites superiores.Use std::lower_bound(lower_bound_array, value) y std::upper_bound(upper_bound_array, value). Si el índice de ambos resultados es el mismo, return index + 1. De lo contrario, return 0.

Si los índices devueltos coinciden, significa que el valor es >= el límite inferior y < el límite superior. Si no lo hacen, entonces estás entre rangos.

Answer 7

Es un índice espacial de 1 dimensión. Árbol binario estilo Quadtree, por ejemplo, y hay muchos otros métodos ampliamente utilizados.

Answer 8

El mejor enfoque aquí es de hecho una búsqueda binaria, pero cualquier búsqueda basada en órdenes eficiente lo hará perfectamente bien. Realmente no tiene que implementar la búsqueda y la estructura de datos explícitamente. Puede usarlo indirectamente empleando un contenedor asociativo estándar en su lugar.

Dado que sus rangos no se superponen, la solución es muy simple. Puede utilizar inmediatamente un std::map para resolver este problema en unas pocas líneas de código.

Por ejemplo, este es un posible enfoque. Supongamos que estamos asignando un rango [ int, int ] a un valor de int. Representemos nuestros rangos como rangos de apertura cerrada, es decir, si el rango original es [0, 70], consideremos un rango [0, 71) en su lugar. Además, vamos a utilizar el valor de 0 como un valor "reservado" que significa "sin asignación" (como usted pidió en su pregunta)

const int EMPTY = 0; 

Todo lo que necesita hacer es declarar un mapa de int a int:

typedef std::map<int, int> Map; 
Map map; 

y llénelo con cada extremo de sus gamas abiertas. El extremo izquierdo (cerrado) debe asignarse al valor deseado en el que está asignado todo el rango, mientras que el extremo derecho (abierto) debe asignarse a nuestro valor EMPTY. Por su ejemplo, que se verá de la siguiente manera

map[0] = r_a; 
map[71] = EMPTY; 

map[101] = r_b; 
map[251] = EMPTY; 

map[260] = r_c; // 260 adjusted from 201 
map[401] = EMPTY; 

(ajusté su última gama, ya que en el ejemplo original, que se superponía la gama anterior, y usted dijo que sus rangos no se superponen).

Eso es todo para la inicialización.

Ahora, con el fin de determinar dónde un valor dado de i se asigna a todo lo que tiene que hacer es

Map::iterator it = map.upper_bound(i); 

Si it == map.begin(), entonces no es i en cualquier rango. De lo contrario, haga

--it; 

Si el it->second (para el it decrementa) es EMPTY, entonces no es i en cualquier rango.

La "miss" cheque combinada podría tener el siguiente

Map::iterator it = map.upper_bound(i); 
if (it == map.begin() || (--it)->second == EMPTY) 
    /* Missed all ranges */; 

De lo contrario, it->second (para el decremento it) es el valor asignado

int mapped_to = it->second; 

Tenga en cuenta que si los rangos originales eran "tocar ", como en [40, 60] y [61, 100], a continuación, los rangos cerrados abierta se verá tan [40, 61) y [61, 101) lo que significa que el valor de 61 se ser mapeado dos veces durante la inicialización del mapa. En este caso, es importante asegurarse de que el valor de 61 se asigna al valor de destino correspondiente y no al valor de EMPTY. Si mapea los rangos como se muestra arriba en el orden de izquierda a derecha (es decir, aumentando), funcionará correctamente por sí mismo.

Tenga en cuenta que solo los puntos finales de los rangos se insertan en el mapa, lo que significa que el consumo de memoria y el rendimiento de la búsqueda dependen únicamente del rango total y de su longitud total.

---

Si se desea, se puede añadir un elemento de "guardia" para el mapa durante la inicialización

map[INT_MIN] = EMPTY; 

(que corresponde a "infinito negativo") y la "miss" cheque será más sencillo

Map::iterator it = map.upper_bound(i); 

assert(it != map.begin()); 
if ((--it)->second == EMPTY) 
    /* Missed all ranges */; 

pero eso es solo una cuestión de preferencia personal.

Por supuesto, si solo desea devolver 0 para valores no mapeados, no es necesario que realice ninguna comprobación en absoluto. Simplemente tome el it->second desde el iterador decrementado y listo.

Answer 9

El ideal es un interval tree (árbol binario especializado). Wikipedia describe el método por completo. Mejor que yo. No obtendrá mucho más óptimo que esto, sin sacrificar espacio para el rendimiento.

Answer 10

Usted puede encontrar Mínimo Función Hashing Perfecto útil, http://cmph.sourceforge.net/.