إيجاد أس n = 2**x باستخدام عمليات البت [اللوغاريتم في الأساس 2 لـ n]
https://stackoverflow.com/questions/2255177
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
هل هناك طريقة مباشرة لاستخراج الأس من قوة 2 باستخدام عمليات البت فقط؟
يحرر: على الرغم من أن السؤال كان في الأصل يتعلق بعمليات البت، إلا أن الموضوع جيد القراءة أيضًا إذا كنت تتساءل "ما هي أسرع طريقة للعثور على X إذا كانت Y = 2X في بايثون?"**
أحاول حاليًا تحسين الروتين (اختبار رابين ميلر للأولوية) الذي يقلل من رقم زوجي ن في الأشكال 2**s * d.يمكنني الحصول على 2**s جزء من:
two_power_s = N & -N
لكن لا يمكنني العثور على طريقة لاستخراجها فقط "س"مع عملية bitwise.الحلول البديلة التي أختبرها حاليًا دون الكثير من الرضا (جميعها بطيئة جدًا) هي:
- باستخدام الدالة اللوغاريتمية
- معالجة التمثيل الثنائي لـ 2**s (أيحساب الأصفار الزائدة)
- تكرار القسمة على 2 حتى تكون النتيجة 1
أنا أستخدم لغة بايثون، ولكن أعتقد أن الإجابة على هذا السؤال يجب أن تكون محايدة للغة.
المحلول 2
اجابة قصيرة
بقدر ما يتعلق الأمر بيثون:
- ال أسرع طريقة على الإطلاق للعثور على أس 2**x يتم ذلك من خلال البحث في القاموس الذي تكون تجزئاته هي قوى الرقم 2 (انظر "com.hashlookup"" في الكود)"
- ال أسرع طريقة bitwise هو الذي يسمى "unrolled_bitwise".
- كلتا الطريقتين السابقتين لهما حدود عليا محددة جيدًا (ولكنها قابلة للتوسيع).ال أسرع طريقة بدون حدود عليا مرمزة (والذي يصل إلى حد قدرة بايثون على التعامل مع الأرقام) هو "log_e".
ملاحظات أولية
- تم الحصول على جميع قياسات السرعة أدناه عبر
timeit.Timer.repeat(testn, cycles)أينtestnتم ضبطه على 3 وcyclesتم ضبطه تلقائيًا بواسطة البرنامج النصي للحصول على أوقات في نطاق الثواني (ملحوظة: كان هناك خطأ في آلية الضبط التلقائي هذه وتم إصلاحه بتاريخ 18/02/2010). - لا يمكن لجميع الأساليب التوسع, ولهذا السبب لم أختبر جميع الوظائف لمختلف صلاحيات 2
- لم أتمكن من تفعيل بعض الطرق المقترحة (ترجع الدالة نتيجة خاطئة).لم يكن لدي بعد Tiem للقيام بجلسة تصحيح الأخطاء خطوة بخطوة:لقد قمت بتضمين الكود (تم التعليق عليه) فقط في حالة اكتشاف شخص ما للخطأ عن طريق الفحص (أو الرغبة في إجراء التصحيح بنفسه)
نتائج
وظيفة(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%
وظيفة(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%
وظيفة(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%
وظيفة(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، "عد الأصفار البادئة".في دول مجلس التعاون الخليجي، يمكنك الوصول إليها باستخدام __builtin_clz(x) (الذي ينتج أيضًا كودًا معقولًا، إن لم يكن الأسرع، للأهداف التي تفتقر إلى clz).لاحظ أن CLZ غير محدد للصفر، لذا ستحتاج إلى فرع إضافي لالتقاط هذه الحالة إذا كان الأمر مهمًا في تطبيقك.
في سيلت ( http://celt-codec.org ) تم كتابة CLZ بدون فروع التي نستخدمها للممتثلين الذين يفتقرون إلى CLZ بواسطة Timothy B.تيريبيري:
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;
}
(تشير التعليقات إلى أنه تم اكتشاف أن هذا أسرع من الإصدار المتفرع والإصدار المستند إلى جدول البحث)
ولكن إذا كان الأداء بهذه الأهمية، فربما لا ينبغي عليك تنفيذ هذا الجزء من التعليمات البرمجية الخاصة بك في بايثون.
هناك صفحة تحتوي على الكثير من هذه الأنواع من الحيل والاختراقات.إنها مكتوبة للغة C، لكن العديد منها يجب أن تعمل في Python أيضًا (على الرغم من أن الأداء سيكون مختلفًا بشكل واضح).الشيء الذي تريده هو هنا وما بعده.
بامكانك ان تحاول هذا على سبيل المثال:
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];
}
}
يبدو أنه يمكن تحويله إلى Python بسهولة تامة.
يمكنك القيام بذلك في وقت O(lg s) للأعداد الصحيحة ذات الطول العشوائي باستخدام 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
بالنسبة للأعداد الصحيحة ذات الحجم الثابت، يجب أن يكون جدول البحث هو الحل الأسرع، وربما الأفضل بشكل عام.
ويبدو أن النطاق معروف.لنفترض أنها تصل إلى 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.
باستخدام أ 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 الطريقة على الكائنات العائمة للحصول على سلسلة تتضمن (كجزء أخير) الأس الأساسي للرقم.يعد استخراج هذا الأمر بطيئًا بعض الشيء بشكل عام، ولكن إذا كان الأس سيتكون من رقم واحد فقط، فيمكن القيام بذلك بشكل مباشر بما فيه الكفاية:
def floathex(v):
return ord(float(v).hex()[-1])-48
هذا فقط من أجل قيمة ترفيهية على الرغم من أنه لم يكن قادرًا على المنافسة - على الرغم من أنه من المثير للدهشة أنه لا يزال أسرع من النهج الثنائي.
لذلك يبدو أن استخدام القائمة هو الحل الأمثل.
(لن يتم توسيع هذا النهج إلى أجل غير مسمى، بسبب محدودية الذاكرة، ولكن للتعويض عن ذلك، لن تعتمد سرعة التنفيذ على max_log2, أو قيم الإدخال بأي طريقة ستلاحظها عند تشغيل كود بايثون.فيما يتعلق باستهلاك الذاكرة، إذا كنت أتذكر الأجزاء الداخلية من لغة بايثون الخاصة بي بشكل صحيح، فسوف يستغرق الجدول حوالي (1<<max_log2)*4 بايت، لأن المحتويات كلها عبارة عن أعداد صحيحة صغيرة سيقوم المترجم بتدريبها تلقائيًا.اذن متى max_log2 هو 20، وهذا حوالي 4 ميغابايت.)
هذا في الواقع تعليق على اختبار الأداء الذي نشرته شركة Mac.أقوم بنشر هذا كإجابة للحصول على تنسيق التعليمات البرمجية والمسافة البادئة المناسبة
mac، هل يمكنك تجربة تنفيذ غير مسجل لـ 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 );
إذا كانت بايثون تشترك في افتقار جافا إلى الأعداد الصحيحة غير المسجلة، فيجب أن تكون شيئًا مثل هذا:
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 ذو أداء معقول.
