Bir kod satırı, tamsayı ikili olarak ardışık 1 yargıyı işler!
Yazar | veelion
Baş Editör | Guo Rui
Bayt bit manipülasyonu ile çözülen bir problemle karşılaşıldı, bir tamsayı ikilisinin en az iki ardışık 1'i içerip içermediğine nasıl karar verilir?
Sorunun kendisi karmaşık değildir ve ikili işlem olmadan tamamlanabilir ve birçok yol vardır. Farklı yöntemlerin verimliliği de çok daha kötü, bunları uygulamak ve karşılaştırmak için Python ve C'yi kullanalım.
Yöntem 1: Sürekli bir 1 olup olmadığını öğrenmek için her biti baştan sona yineleyin
Bu yöntem, ilk izlenimde düşünülebilecek en yaygın yöntemdir.Özel uygulamasına bir göz atalım.
Python kodu:
def method_1 (n): last_is_one = Yanlış this_is_one = Yanlış n iken > 0: this_is_one = n% 2 this_is_one ve last_is_one ise: True döndür n = n > > 1 last_is_one = this_is_one dönüş YanlışYukarıdaki uygulamada, kalan işlem tam sayı n (n% 2) için gerçekleştirilir. Kalan 1 ise, n'nin son biti 1'dir, aksi takdirde 0'dır ve this_is_one'yi mevcut biti kaydetmek için kullanın; sonra bu zamanın son bitinin ve son zamanın her ikisinin de 1 olup olmadığına karar verin. Eğer öyleyse, tamsayının iki ardışık 1'e sahip olduğu belirlenebilir, aksi takdirde n'yi bir bit sola hareket ettirin ve döngünün başında kalan işleme devam edin.
Yöntem 2: Her biti geçmeye gerek yok, ancak bit işlemi: bir bit kaydır (sola kaydırma veya sağa kaydırma yapılabilir) ve ardından orijinal numara ile "bit ve"
Bu ilke karmaşık değil, bir düşünün:
- 1 olan iki ardışık bit varsa, orijinal sayı ve kaydırılan sayı "bitsel-AND'lidir", yani bu iki ardışık 1, "bitsel-AND'li" olacaktır ve sonuçta en az bir bit 1 olmalıdır. (11 == 1), sonuç sıfır değil;
- En az iki ardışık bit 1 değilse, 1'in her iki tarafı da 0'dır ve orijinal sayı ve kaydırılan sayı "bitsel-AND'lidir", yani 1, her iki tarafta 0 ile "bitsel-AND'lidir" ve ardından tüm 1'ler Her ikisi de 0 (10 == 0) olur ve sonuç sıfır olmalıdır.
Yukarıdaki mantığa dayanarak, algoritma çok basitleştirilmiştir ve sadece bir satır kod ile yapılabilir.
Python kodu:
def foo2 (n): dönüş (n ve n < < 1) > 0Öyleyse, yukarıdaki iki yöntem arasındaki verimlilik farkı nedir, hadi test edelim:
Python kodu:
def testi (func, döngüler): b = time.time () aralıktaki n için (döngüler): func (n) e = time.time () __name__ == '__ main__' ise print (döngüler, ', zaman maliyeti:', e-b): test (foo1, 10 ** 6) test (foo2, 10 ** 6)Çalışan sonuçlara bir göz atın, 1 milyon kez döngü yapın, ikinci yöntem, birinci yöntemden 4 kat daha hızlıdır:
< 0x7f60de787e18'deki işlev yöntemi_1 > 1000000, zaman maliyeti: 0.6687741279602051 < 0x7f60de75b598'deki işlev yöntemi_2 > 1000000, zaman maliyeti: 0.16364359855651855Ardından, ne kadar verimli olduğunu görmek için bunu C'de uygulayın:
C dil kodu:
#include #include < sys / time.h > int method_1 (int n) {int last_is_one = 0; int this_is_one = 0; while (n > 0) { this_is_one = n% 2; eğer (this_is_one last_is_one) {return 0; } n = n > > 1; last_is_one = this_is_one; } dönüş 1; } int yöntem_2 (int n) {dönüş n ve n > > 1; } void testi (int (* func) (int), int döngüler) {struct timeval b, e; gettimeofday (b, 0); for (int i = 0; i < döngüler; i ++) { (* işlev) (i); } gettimeofday (e, 0); double timecost = (e.tv_sec-b.tv_sec) * 1000.0 + (e.tv_usec-b.tv_usec) /1000.0; printf ("döngüler:% d, zaman maliyeti:% f ms \ n", döngüler, zaman maliyeti); } int main (int argc, char ** argv) { test (yöntem_1, 1000000); test (yöntem_2, 1000000); 0 döndür; }Yukarıdaki C kodunu derleyin ve çalıştırın:
gcc iki ardışık-bit.c ./a.outloops: 1000000, timecost: 50.572000 msloops: 1000000, timecost: 4.253000 msYukarıdaki sonuçlardan, C dili tarafından uygulanan algoritma iki, algoritma birinden on kat daha fazladır.
Derleme ve optimizasyondan sonra çalıştırın:
gcc iki ardışık-bit.c -O3 ./a.outloops: 1000000, timecost: 13.407000 msloops: 1000000, timecost: 3.537000 msDerleyicinin optimize edilmiş sonucu, algoritma iki, algoritma birinden 4 kat daha fazladır, ancak optimize edilmemiş olandan çok daha hızlıdır.
Bu arada, Python'un performansı C'den gerçekten çok daha kötü. Ancak doğru araç, doğru şeyi yapmak için her zaman doğrudur. Şu alıntıyı anlayalım:
Her gün çalıştırılması gereken bir Python programı var.Çalışması yaklaşık 1,5 saniye sürüyor.
Rust'ta yeniden yazmak için altı saat harcadım ve şimdi çalıştırmak için 0.06 saniye sürüyor.
Verimlilikteki artış, harcadığım zamanı geri almam 41 yıl 24 gün sürecek anlamına geliyor ...
Yazar: veelion, geliştirme konusunda uzun yıllara dayanan deneyime sahip, ağırlıklı olarak Python, C ++ dilini kullanıyor, web tarayıcıları, arama motorları, doğal dil işleme alanında araştırma ve geliştirme yapıyor.
Feragatname: Bu makale yazar tarafından sunulmuştur ve telif hakkı karşı tarafa aittir.
