Encontrar el exponente de n = 2**x el uso de las operaciones bit a bit [logaritmo en base 2 de n]
https://stackoverflow.com/questions/2255177
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Hay una manera sencilla de extraer el exponente de una potencia de 2 con operaciones a nivel de bit sólo?
EDITAR: Aunque la pregunta era originalmente acerca de las operaciones bit a bit, el hilo es una buena lectura también si usted se está preguntando "¿Cuál es la forma más rápida de encontrar X dado Y = 2X en Python?"**
Actualmente estoy tratando de optimizar una rutina (Rabin-Miller de la prueba de primalidad) que reduce una incluso el número de N en las formas 2**s * d.Puedo obtener la 2**s parte por:
two_power_s = N & -N
pero no puedo encontrar una manera de extraer "s"con una operación bit a bit.Soluciones actualmente estoy probando sin demasiada satisfacción (todos ellos son bastante lentos) son:
- utilizando el logaritmo de la función de
- la manipulación de la representación binaria de 2**s (es decir,contando los ceros finales)
- bucle en una división por 2 hasta que el resultado es 1
Estoy usando python, pero la respuesta a esta pregunta debe ser independiente del idioma, supongo.
Solución 2
Respuesta corta
Tan lejos como python es que se trate:
- El método más rápido de todos para encontrar el exponente de 2**x está buscando en un diccionario cuyos valores hash son las potencias de 2 (ver "hashlookup"en el código)
- El más rápido bit a bit método es el llamado "unrolled_bitwise".
- Ambos métodos anteriores tienen bien definida (pero extensible) límites superiores.El método más rápido sin rígida límites superiores (que escala hasta tan lejos como python puede manejar números) es "log_e".
Nota preliminar
- Todas las mediciones de la velocidad a continuación han sido obtenidos a través de la
timeit.Timer.repeat(testn, cycles)dondetestnestaba a 3 ycyclesse ajusta automáticamente por el script para obtener los tiempos en el rango de segundos (nota: hubo un error en esta auto-mecanismo de ajuste que se ha fijado en 18/02/2010). - No todos los métodos pueden escala, este es por qué no probar todas las funciones de las diversas potencias de 2
- No pude conseguir algunos de los métodos propuestos para el trabajo (la función devuelve un resultado incorrecto).Yo aún no tenía tiempo para hacer un paso a paso de la sesión de depuración:He incluido el código (comentado) sólo en caso de que alguien ve el error por la inspección (o desea realizar la depuración de sí mismos)
Resultados
func(25)**
hashlookup: 0.13s 100%
lookup: 0.15s 109%
stringcount: 0.29s 220%
unrolled_bitwise: 0.36s 272%
log_e: 0.60s 450%
bitcounter: 0.64s 479%
log_2: 0.69s 515%
ilog: 0.81s 609%
bitwise: 1.10s 821%
olgn: 1.42s 1065%
func(231)**
hashlookup: 0.11s 100%
unrolled_bitwise: 0.26s 229%
log_e: 0.30s 268%
stringcount: 0.30s 270%
log_2: 0.34s 301%
ilog: 0.41s 363%
bitwise: 0.87s 778%
olgn: 1.02s 912%
bitcounter: 1.42s 1264%
func(2128)**
hashlookup: 0.01s 100%
stringcount: 0.03s 264%
log_e: 0.04s 315%
log_2: 0.04s 383%
olgn: 0.18s 1585%
bitcounter: 1.41s 12393%
func(21024)**
log_e: 0.00s 100%
log_2: 0.01s 118%
stringcount: 0.02s 354%
olgn: 0.03s 707%
bitcounter: 1.73s 37695%
Código
import math, sys
def stringcount(v):
"""mac"""
return len(bin(v)) - 3
def log_2(v):
"""mac"""
return int(round(math.log(v, 2), 0)) # 2**101 generates 100.999999999
def log_e(v):
"""bp on mac"""
return int(round(math.log(v)/0.69314718055994529, 0)) # 0.69 == log(2)
def bitcounter(v):
"""John Y on mac"""
r = 0
while v > 1 :
v >>= 1
r += 1
return r
def olgn(n) :
"""outis"""
if n < 1:
return -1
low = 0
high = sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
while True:
mid = (low+high)//2
i = n >> mid
if i == 1:
return mid
if i == 0:
high = mid-1
else:
low = mid+1
def hashlookup(v):
"""mac on brone -- limit: v < 2**131"""
# def prepareTable(max_log2=130) :
# hash_table = {}
# for p in range(1, max_log2) :
# hash_table[2**p] = p
# return hash_table
global hash_table
return hash_table[v]
def lookup(v):
"""brone -- limit: v < 2**11"""
# def prepareTable(max_log2=10) :
# log2s_table=[0]*((1<<max_log2)+1)
# for i in range(max_log2+1):
# log2s_table[1<<i]=i
# return tuple(log2s_table)
global log2s_table
return log2s_table[v]
def bitwise(v):
"""Mark Byers -- limit: v < 2**32"""
b = (0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000)
S = (1, 2, 4, 8, 16)
r = 0
for i in range(4, -1, -1) :
if (v & b[i]) :
v >>= S[i];
r |= S[i];
return r
def unrolled_bitwise(v):
"""x4u on Mark Byers -- limit: v < 2**33"""
r = 0;
if v > 0xffff :
v >>= 16
r = 16;
if v > 0x00ff :
v >>= 8
r += 8;
if v > 0x000f :
v >>= 4
r += 4;
if v > 0x0003 :
v >>= 2
r += 2;
return r + (v >> 1)
def ilog(v):
"""Gregory Maxwell - (Original code: B. Terriberry) -- limit: v < 2**32"""
ret = 1
m = (not not v & 0xFFFF0000) << 4;
v >>= m;
ret |= m;
m = (not not v & 0xFF00) << 3;
v >>= m;
ret |= m;
m = (not not v & 0xF0) << 2;
v >>= m;
ret |= m;
m = (not not v & 0xC) << 1;
v >>= m;
ret |= m;
ret += (not not v & 0x2);
return ret - 1;
# following table is equal to "return hashlookup.prepareTable()"
hash_table = {...} # numbers have been cut out to avoid cluttering the post
# following table is equal to "return lookup.prepareTable()" - cached for speed
log2s_table = (...) # numbers have been cut out to avoid cluttering the post
Otros consejos
"lenguaje agnóstico" y preocuparse por el rendimiento son más o menos los conceptos incompatibles.
La mayoría de los procesadores modernos tienen una instrucción de CLZ, "contar con ceros a la izquierda". En GCC se puede llegar a ella con __builtin_clz (x) (que también produce razonable, si no el más rápido, el código para los objetivos que carecen de CLZ). Tenga en cuenta que esta no está definida para CLZ cero, por lo que tendrá una rama adicional para coger ese caso, si es importante en la aplicación.
En CELT ( http://celt-codec.org ) del CLZ sin sucursales que utilizamos para los cumplidores que carecen de una CLZ fue escrito por Timothy B. Terriberry:
int ilog(uint32 _v){
int ret;
int m;
ret=!!_v;
m=!!(_v&0xFFFF0000)<<4;
_v>>=m;
ret|=m;
m=!!(_v&0xFF00)<<3;
_v>>=m;
ret|=m;
m=!!(_v&0xF0)<<2;
_v>>=m;
ret|=m;
m=!!(_v&0xC)<<1;
_v>>=m;
ret|=m;
ret+=!!(_v&0x2);
return ret;
}
(Los comentarios indican que este se encontró que era más rápido que una versión de ramificación y una versión basada en la tabla de consulta)
Pero si el rendimiento es crítico que es probable que no debe ser la aplicación de esta parte de su código en Python.
Hay una página con una gran cantidad de este tipo de trucos y hacks. Está escrito para C, pero muchos de ellos debería funcionar en Python también (aunque el rendimiento será obviamente diferente). El bit que desea es aquí y en adelante.
Usted podría intentar este por ejemplo:
register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i--) // unroll for speed...
{
if (v & b[i])
{
v >>= S[i];
r |= S[i];
}
}
Esto parece que podría ser convertido en Python con bastante facilidad.
Puede hacerlo en un tiempo O (lg s) para los enteros de longitud arbitraria utilizando un binsearch.
import sys
def floorlg(n):
if n < 1:
return -1
low=0
high=sys.getsizeof(n)*8 # not the best upper-bound guesstimate, but...
while True:
mid = (low+high)//2
i = n >> mid
if i == 1:
return mid
if i == 0:
high = mid-1
else:
low = mid+1
Para enteros de tamaño fijo, una tabla de consulta debe ser la solución más rápida, y probablemente el mejor en general.
Parece que se conoce la gama. Vamos a suponer que sube 1 << 20, sólo para que sea más interesante:
max_log2=20
Así que hacer una lista que (en efecto) asigna un entero a su logaritmo de base 2. A continuación se hará el truco:
log2s_table=[0]*((1<<max_log2)+1)
for i in range(max_log2+1):
log2s_table[1<<i]=i
(Esto no hace nada útil para números que no son potencias de dos;.. El enunciado del problema sugiere que no necesitan ser manejados sería bastante fácil de arreglar eso sin embargo)
La función para obtener el logaritmo es muy simple, y podría ser fácilmente inlined:
def table(v):
return log2s_table[v]
No puedo garantizar que el código de prueba que escribí es exactamente el mismo que el que está utilizando para obtener los tiempos de ejemplo, pero esto es más rápido que el código stringcount:
stringcount: 0.43 s.
table: 0.16 s.
Dado que todos los valores de la tabla son menos de 256, que se preguntaron si el uso de una cadena en lugar de una lista sería más rápido, o tal vez una array.array de bytes, pero no dice:
string: 0.25 s.
arr: 0.21 s.
El uso de un dict hacer las operaciones de búsqueda es otra posibilidad, aprovechando la forma en que se están comprobando sólo potencias de dos:
log2s_map=dict([(1<<x,x) for x in range(max_log2+1)])
def map(v):
return log2s_map[v]
Los resultados de este no fueron tan buenos, sin embargo:
map: 0.20 s.
Y sólo por diversión también se podría utilizar el método hex sobre objetos flotantes para obtener una cadena que incluye (como su última parte) de la base 2 exponente de la serie. Esto es un poco lento para extraer en general, pero si el exponente única es cada vez va a ser un dígito que se podía hacer lo suficiente sin rodeos:
def floathex(v):
return ord(float(v).hex()[-1])-48
Esto es puramente para el valor de entretenimiento, ya que era uncompetetive - aunque, sorprendentemente, todavía más rápido que el enfoque a nivel de bits
.Así que parece que el uso de una lista es el camino a seguir.
(Este enfoque no se escala de forma indefinida, debido a la memoria limitada, pero para compensar que la velocidad de ejecución no dependerá de max_log2, o los valores de entrada, de cualquier manera que usted notará cuando se ejecuta el código Python . en relación con el consumo de memoria, si no recuerdo mis partes internas pitón correctamente, la tabla ocupará unos bytes (1<<max_log2)*4, ya que los contenidos son todos enteros pequeños que el intérprete pasante de forma automática. Así que, cuando max_log2 es 20, que es alrededor de 4 MB.)
Esto es en realidad un comentario a la prueba de rendimiento Publicado por MAC. Puedo publicar esto como una respuesta a tener el formato de código apropiado y sangría
mac, ¿podría intentar una aplicación desenrollado de la bitseach sugerido por Mark Byers? Tal vez sea sólo el acceso a la matriz que lo frena. En teoría, este enfoque debe ser más rápido que los demás.
Se vería algo como esto, aunque no estoy seguro de si el formato es el adecuado para Python, pero supongo que se puede ver lo que tiene que hacer.
def bitwise(v):
r = 0;
if( v > 0xffff ) : v >>= 16; r = 16;
if( v > 0x00ff ) : v >>= 8; r += 8;
if( v > 0x000f ) : v >>= 4; r += 4;
if( v > 0x0003 ) : v >>= 2; r += 2;
return r + ( v >> 1 );
Si la falta de números enteros unsingned acciones pitón de java que tendría que ser algo como esto:
def bitwise(v):
r = 0;
if( v & 0xffff0000 ) : v >>>= 16; r = 16;
if( v > 0x00ff ) : v >>= 8; r += 8;
if( v > 0x000f ) : v >>= 4; r += 4;
if( v > 0x0003 ) : v >>= 2; r += 2;
return r + ( v >> 1 );
tarde a la fiesta, pero ¿qué hay int.bit_length(n) - 1? Usted pidió sencillo, y que parece el más simple para mí. La aplicación CPython parece razonable performant.
