resueltos - lenguaje c++ ejemplos

Algoritmo limpio y eficiente para envolver enteros en C++

Question

/**
* Returns a number between kLowerBound and kUpperBound
* e.g.: Wrap(-1, 0, 4); // Returns 4
* e.g.: Wrap(5, 0, 4); // Returns 0
*/
int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
// Suggest an implementation?
}

Answer 1

¿Por qué no usar métodos de extensión?

public static class IntExtensions
{
public static int Wrap(this int kX, int kLowerBound, int kUpperBound)
{
int range_size = kUpperBound - kLowerBound + 1;
if (kX < kLowerBound)
kX += range_size * ((kLowerBound - kX) / range_size + 1);
return kLowerBound + (kX - kLowerBound) % range_size;
}
}

Uso: currentInt = (++currentInt).Wrap(0, 2);

Answer 2

Daría un punto de entrada al caso más común lowerBound = 0, upperBound = N-1. Y llamar a esta función en el caso general. No se realiza ningún cálculo de mod cuando I ya está en el rango. Se supone superior> = inferior, o n> 0.

int wrapN(int i,int n)
{
if (i<0) return (n-1)-(-1-i)%n; // -1-i is >=0
if (i>=n) return i%n;
return i; // In range, no mod
}
int wrapLU(int i,int lower,int upper)
{
return lower+wrapN(i-lower,1+upper-lower);
}

Answer 3

El signo de a % b solo se define si a y b son no negativos.

int Wrap(int kX, int const kLowerBound, int const kUpperBound)
{
int range_size = kUpperBound - kLowerBound + 1;
if (kX < kLowerBound)
kX += range_size * ((kLowerBound - kX) / range_size + 1);
return kLowerBound + (kX - kLowerBound) % range_size;
}

Answer 4

En realidad, como -1% 4 devuelve -1 en todos los sistemas en los que he estado, la simple solución de mod no funciona. Lo intentaré:

int range = kUpperBound - kLowerBound +1;
kx = ((kx - kLowerBound) % range) + range;
return (kx % range) + kLowerBound;

si kx es positivo, modificas, agregas rango y modificas de nuevo, deshaciendo el complemento. Si kx es negativo, mod, agrega rango que lo hace positivo, luego mod nuevamente, lo que no hace nada.

Answer 5

Lo siguiente debería funcionar independientemente de la implementación del operador mod:

int range = kUpperBound - kLowerBound + 1;
kx = ((kx-kLowerBound) % range);
if (kx<0)
return kUpperBound + 1 + kx;
else
return kLowerBound + kx;

Una ventaja sobre otras soluciones es que utiliza un solo% (es decir, división), lo que lo hace bastante eficiente.

Nota (Off Topic):

Es un buen ejemplo, por eso a veces es aconsejable definir intervalos con el límite superior siendo el primer elemento que no está en el rango (como en los iteradores STL ...). En este caso, ambos "+1" desaparecerían.

Answer 6

Mi otra publicación se volvió desagradable, toda esa multiplicación y división ''correctivas'' se me fueron de las manos. Después de ver la publicación de Martin Stettner y mis propias condiciones iniciales de (NL)%H+L , se me ocurrió esto:

int Wrap(N,L,H){
H=H-L+1; N=(N-L)%H+L; if(N<L)N+=H; return N;
}

En el extremo negativo extremo del rango entero, se rompe como lo haría mi otro, pero será más rápido, es mucho más fácil de leer y evita las otras asquerosas cosas que se deslizaron en él.

Cuervo.

Answer 7

Para kX negativo, puede agregar:

int temp = kUpperBound - kLowerBound + 1;
while (kX < 0) kX += temp;
return kX%temp + kLowerBound;

Answer 8

Personalmente, he encontrado que las soluciones para este tipo de funciones son más limpias si el rango es exclusivo y el divisor está restringido a valores positivos.

int ifloordiv(int x, int y)
{
if (x > 0)
return x / y;
if (x < 0)
return (x + 1) / y - 1;
return 0
}
int iwrap(int x, int y)
{ return x - y * ifloordiv(x, y);
}

Integrado.

int iwrap(int x, int y)
{
if (x > 0)
return x % y;
if (x < 0)
return (x + 1) % y + y - 1;
return 0;
}

La misma familia. Por qué no?

int ireflect(int x, int y)
{
int z = iwrap(x, y*2);
if (z < y)
return z;
return y*2-1 - z;
}
int ibandy(int x, int y)
{
if (y != 1)
return ireflect(abs(x + x / (y - 1)), y);
return 0;
}

La funcionalidad a distancia se puede implementar para todas las funciones con,

// output is in the range [min, max).
int func2(int x, int min, int max)
{
// increment max for inclusive behavior.
assert(min < max);
return func(x - min, max - min) + min;
}

Answer 9

Por favor, no pase por alto esta publicación. :)

¿Esto es bueno?

int Wrap(N,L,H){
H=H-L+1; return (N-L+(N<L)*H)%H+L;
}

Esto funciona para entradas negativas, y todos los argumentos pueden ser negativos siempre que L sea menor que H.

Fondo ... (Tenga en cuenta que H aquí es la variable reutilizada, establecida en H-L+1 ).

Había estado usando (NL)%H+L al aumentar, pero a diferencia de Lua, que usé antes de comenzar a aprender C hace unos meses, esto NO funcionaría si usara entradas por debajo del límite inferior, sin importar las entradas negativas. (Lua está construido en C, pero no sé qué está haciendo, y probablemente no sea rápido ...)

Decidí agregar +(N<L)*H para hacer (N-L+(N<L)*H)%H+L , ya que C parece estar definido de manera tal que verdadero = 1 y falso = 0. Funciona lo suficientemente bien para mí y parece responder a la pregunta original de manera clara. Si alguien sabe cómo hacerlo sin el operador MOD% para hacerlo deslumbrantemente rápido, hágalo. No necesito velocidad en este momento, pero alguna vez lo haré, sin duda.

EDITAR:

Esa función falla si N es inferior a L en más de H-L+1 pero esto no:

int Wrap(N,L,H){
H-=L; return (N-L+(N<L)*((L-N)/H+1)*++H)%H+L;
}

Creo que se rompería en el extremo negativo del rango de enteros en cualquier sistema, pero debería funcionar para la mayoría de las situaciones prácticas. Agrega una multiplicación extra y una división, pero aún es bastante compacta.

(Esta edición es solo para completar, porque se me ocurrió una manera mucho mejor, en una publicación más reciente en este hilo).

Cuervo.

Answer 10

Sugeriría esta solución:

int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
int d = kUpperBound - kLowerBound + 1;
return kLowerBound + (kX >= 0 ? kX % d : -kX % d ? d - (-kX % d) : 0);
}

La lógica if-then-else del operador ?: asegura de que ambos operandos de % no sean negativos.

Answer 11

También he enfrentado este problema. Esta es mi solución.

template <> int mod(const int &x, const int &y) {
return x % y;
}
template <class T> T mod(const T &x, const T &y) {
return ::fmod((T)x, (T)y);
}
template <class T> T wrap(const T &x, const T &max, const T &min = 0) {
if(max < min)
return x;
if(x > max)
return min + mod(x - min, max - min + 1);
if(x < min)
return max - mod(min - x, max - min + 1);
return x;
}

No sé si es bueno, pero pensé que lo compartiría desde que me dirigí aquí cuando hice una búsqueda en Google sobre este problema y encontré las soluciones anteriores que no se ajustaban a mis necesidades. =)

Answer 12

Una respuesta que tiene cierta simetría y también hace obvio que cuando kX está dentro del rango, se devuelve sin modificaciones.

int Wrap(int const kX, int const kLowerBound, int const kUpperBound)
{
int range_size = kUpperBound - kLowerBound + 1;
if (kX < kLowerBound)
return kX + range_size * ((kLowerBound - kX) / range_size + 1);
if (kX > kUpperBound)
return kX - range_size * ((kX - kUpperBound) / range_size + 1);
return kX;
}

Answer 13

La solución más rápida y menos flexible: aproveche los tipos de datos nativos que integrarán el hardware.

El método más rápido para envolver los enteros sería asegurarse de que sus datos se escalan a int8 / int16 / int32 o al tipo de datos nativo. Luego, cuando necesite que sus datos se ajusten, el tipo de datos nativo se realizará en hardware. Muy indoloro y órdenes de magnitud más rápido que cualquier implementación de ajuste de software que se ve aquí.

Como ejemplo de un caso de estudio:

He encontrado que esto es muy útil cuando necesito una implementación rápida de sin / cos implementada usando una tabla de consulta para una implementación sin / cos. Básicamente, hace que la escala de sus datos sea tal que INT16_MAX es pi y INT16_MIN es -pi. Entonces tienes listo para ir

Como nota al margen, la escala de sus datos agregará un costo de cómputo finito por adelantado que generalmente se ve algo así como:

int fixedPoint = (int)( floatingPoint * SCALING_FACTOR + 0.5 )

No dude en intercambiar int por otra cosa que desee como int8_t / int16_t / int32_t.

La siguiente solución más rápida, más flexible: la operación de modificación es lenta. En su lugar, si es posible, ¡intente usar máscaras de bits!

La mayoría de las soluciones que analicé son funcionalmente correctas ... pero dependen de la operación de modificación.

La operación de modulación es muy lenta porque esencialmente está haciendo una división de hardware . La explicación laica de por qué mod y división son lentas es equiparar la operación de división a algún pseudocódigo for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; } for(quotient = 0;inputNum> 0;inputNum -= divisor) { quotient++; } (def de cociente y divisor ). Como puede ver, la división de hardware puede ser rápida si es un número bajo en relación con el divisor ... pero la división también puede ser terriblemente lenta si es mucho mayor que el divisor .

Si puede escalar sus datos a una potencia de dos, entonces puede usar una máscara de bits que se ejecutará en un ciclo (en el 99% de todas las plataformas) y su mejora de velocidad será de aproximadamente un orden de magnitud (al menos 2 o 3 veces más rápido) .

Código C para implementar el envoltorio:

#define BIT_MASK (0xFFFF)
int wrappedAddition(int a, int b) {
return ( a + b ) & BIT_MASK;
}
int wrappedSubtraction(int a, int b) {
return ( a - b ) & BIT_MASK;
}

Siéntase libre de hacer #define algo que es tiempo de ejecución. Y siéntase libre de ajustar la máscara de bits para obtener la potencia de dos que necesite. Al igual que 0xFFFFFFFF o potencia de dos, decides implementar.

ps. Recomiendo encarecidamente leer sobre el procesamiento de puntos fijos al jugar con condiciones de envoltura / desbordamiento. Sugiero leer:

Aritmética de punto fijo: una introducción por Randy Yates 23 de agosto de 2007