Bitwise 작업을 사용하여 n = 2 ** x의 지수 찾기 [N의 기본 2의 로그
https://stackoverflow.com/questions/2255177
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
비트 연산 만 사용하여 2의 전력에서 지수를 추출하는 간단한 방법이 있습니까?
편집하다: 질문은 원래 Bittoy 작업에 관한 것이었지만, 궁금한 점이 있으면 스레드도 잘 읽습니다. "y = 2가 주어진 X를 찾는 가장 빠른 방법은 무엇입니까?엑스 파이썬에서?"**
나는 현재 루틴을 최적화하려고 노력하고 있습니다 (라빈 밀러 원시 테스트)) 우수 n 형식으로 2**s * d. 나는 얻을 수있다 2**s 부품 :
two_power_s = N & -N
그러나 나는 단지 추출하는 방법을 찾을 수 없다 "에스"약간의 작동으로. 해결 방법은 현재 너무 많은 만족없이 테스트하고 있습니다 (모두 거의 느립니다).
- 로그 기능 사용
- 2 ** s의 이진 표현 조작 (즉, 후행 제로 계산)
- 결과가 1이 될 때까지 부서에서 2 명으로 반복
나는 Python을 사용하고 있지만이 질문에 대한 답은 언어 불가지론이어야한다고 생각합니다.
해결책 2
짧은 대답
파이썬에 관한 한 :
- 그만큼 가장 빠른 방법 2 ** x의 지수를 찾는 것은 해시가 2의 힘 인 사전을 바라 보는 것입니다 (참조 "해시 루프"코드에서)
- 그만큼 가장 빠른 비트 방법 ""라는 것입니다.Unrolled_bitwise".
- 두 이전 방법 모두 잘 정의되지 않았지만 확장 가능한 상한이 있습니다. 그만큼 하드 코딩 된 상한이없는 가장 빠른 방법 (파이썬이 숫자를 처리 할 수있는 한 확장) "log_e".
예비 메모
- 아래의 모든 속도 측정은 통해 얻어졌습니다
timeit.Timer.repeat(testn, cycles)어디testn3으로 설정되었습니다cycles스크립트에 의해 자동으로 조정되어 초 범위 내에서 시간을 얻었습니다 (노트: 이 자동 조정 메커니즘에는 2010 년 2 월 18 일에 고정 된 버그가있었습니다). - 모든 방법이 확장 할 수있는 것은 아닙니다, 이것이 내가 2의 다양한 힘에 대한 모든 기능을 테스트하지 않은 이유입니다.
- 나는 제안 된 방법 중 일부를 얻지 못했습니다. (함수는 잘못된 결과를 반환합니다). 아직 단계별 디버깅 세션을 수행 할 Tiem이 아직 없었습니다. 누군가가 검사를 통해 실수를 발견하거나 디버그를 수행하려는 경우에 대비하여 코드를 포함 시켰습니다 (댓글).
결과
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%
암호
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
다른 팁
"언어 불가지론 적"과 성능에 대한 걱정은 거의 양립 할 수없는 개념입니다.
대부분의 현대 프로세서에는 CLZ 명령이 "수준의 높이기"가 있습니다. GCC에서는 __builtin_clz (x)로 얻을 수 있습니다 (CLZ가없는 대상에 대한 가장 빠른 대상 코드도 합리적으로 생성). 이 CLZ는 0으로 정의되지 않으므로 응용 프로그램에서 중요한 경우 해당 케이스를 잡으려면 추가 지점이 필요합니다.
CELT에서 ( http://celt-codec.org ) CLZ가없는 압수 자에게 사용하는 Branchless CLZ는 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;
}
(의견은 이것이 분기 버전과 조회 테이블 기반 버전보다 빠른 것으로 밝혀 졌음을 나타냅니다)
그러나 성능이 중요하다면 Python에서 코드 의이 부분을 구현해서는 안됩니다.
이러한 유형의 트릭과 해킹이 많은 페이지가 있습니다. C를 위해 작성되었지만 많은 사람들이 파이썬에서도 작동해야합니다 (성능은 분명히 다를 것입니다). 당신이 원하는 비트는입니다 여기 그리고 이후.
당신은 시도 할 수 있습니다 이것 예를 들어:
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];
}
}
그것은 파이썬으로 쉽게 변환 될 수있는 것처럼 보입니다.
binsearch를 사용하여 임의의 길이 정수를 위해 O (lg s) 시간으로 할 수 있습니다.
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
고정 된 크기 정수의 경우 조회 테이블이 가장 빠른 솔루션이어야하며 전체적으로 가장 좋습니다.
범위가 알려진 것 같습니다. 더 흥미롭게 만들기 위해 최대 1 << 20까지 올라간다 고 가정 해 봅시다.
max_log2=20
따라서 (사실상) 정수를 기본 2 로그에 매핑하는 목록을 만드십시오. 다음은 트릭을 수행합니다.
log2s_table=[0]*((1<<max_log2)+1)
for i in range(max_log2+1):
log2s_table[1<<i]=i
(이것은 두 가지의 힘이 아닌 숫자에 유용한 일을하지 않습니다. 문제 진술은 그들이 처리 할 필요가 없다고 제안합니다. 그래도 그것을 고칠 수있을 정도로 쉽습니다.)
로그를 얻는 기능은 매우 간단하며 쉽게 내릴 수 있습니다.
def table(v):
return log2s_table[v]
내가 쓴 테스트 코드가 예제 타이밍을 얻는 데 사용되는 테스트 코드와 정확히 동일하다는 것을 보장 할 수는 없지만 이것은보다 훨씬 빠릅니다. stringcount 암호:
stringcount: 0.43 s.
table: 0.16 s.
테이블의 모든 값은 256보다 작기 때문에 목록 대신 문자열을 사용하는 것이 더 빠르거나 아마도 array.array 바이트의하지만 주사위는 없다 :
string: 0.25 s.
arr: 0.21 s.
사용 a dict 조회를하는 것은 또 다른 가능성이며, 두 가지의 힘 만 확인하는 방식을 활용합니다.
log2s_map=dict([(1<<x,x) for x in range(max_log2+1)])
def map(v):
return log2s_map[v]
그러나 이것의 결과는 좋지 않았습니다.
map: 0.20 s.
그리고 단지 재미를 위해 하나도 사용할 수도 있습니다 hex 플로트 객체의 메소드 숫자의 기본 2 지수를 포함하는 문자열을 가져옵니다. 이것은 일반적으로 추출하는 데 약간 느리지 만 지수가 한 자릿수 만 있으면 간단하게 수행 할 수 있습니다.
def floathex(v):
return ord(float(v).hex()[-1])-48
이것은 순전히 엔터테인먼트 가치를위한 것이지만 비경쟁 적 이었지만 놀랍게도 여전히 비트 방식보다 더 빠릅니다.
따라서 목록을 사용하는 것이가는 길인 것 같습니다.
(이 접근법은 메모리가 제한되어 있기 때문에 무기한으로 확장되지 않지만 실행 속도는 max_log2, 파이썬 코드를 실행할 때 알 수있는 어떤 방식 으로든 입력 값. 메모리 소비와 관련하여, 내 파이썬 내부를 올바르게 기억한다면, 테이블은 (1<<max_log2)*4 내용은 통역사가 자동으로 인턴하는 작은 정수이기 때문에 바이트. 그렇게 할 때 max_log2 20 세, 그것은 약 4MB입니다.)
이것은 실제로 Mac이 게시 한 성능 테스트에 대한 의견입니다. 나는 이것을 적절한 코드 서식 및 들여 쓰기를 위해 답으로 게시합니다.
Mac, Mark Byers가 제안한 Bitseach의 구현 된 구현을 시도해 볼 수 있습니까? 어쩌면 그것은 더 느려지는 배열 액세스 일 것입니다. 이론적 으로이 접근법은 다른 접근법보다 빠릅니다.
형식이 파이썬에 적합한 지 확실하지 않지만 이와 같이 보일 것입니다. 그러나 그것이 무엇을 해야하는지 볼 수 있다고 생각합니다.
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 );
Python이 Java의 흡수되지 않은 정수 부족을 공유하면 다음과 같은 것이 필요합니다.
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 );
파티에 늦었지만 어떻습니까? int.bit_length(n) - 1? 당신은 간단하게 요청했고, 그것은 나에게 가장 단순한 것 같습니다. CPYTHON 구현은 합리적으로 수행됩니다.
