Note de curs, clasele 9-10, 6 martie 2014

From Algopedia
Revision as of 09:05, 5 March 2014 by Cata (talk | contribs) (→‎Programare dinamică)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Calculul unor proprietăți ale numerelor pe 32 / 64 de biți

Uneori veți avea nevoie să calculați proprietăți ca

  • numărul de biți 1 din reprezentarea binară a lui x (popcount).
  • logaritmul în baza 2 al lui x (care este totuna cu numărul de ordine al celui mai din stânga bit 1)
  • dacă x este putere al lui 2

Este bine de știut că există metode și metode de a face aceste calcule, din care unele pot fi de 10-20 de ori mai rapide decât celelalte. Dacă aceste calcule sunt o componentă critică a programului vostru, este bine să știți ce merge și ce nu merge. Experimentați din timp.

Includ ca exemplu Media:popcount.cpp, unde am experimentat cu 5 metode de a calcula popcount. Timpii obținuți pentru 100.000.000 de evaluări sunt:

metoda timp (ms)
naiv 5.000
Kernighan 3.265
lookup table 1 355
lookup table 2 460
în paralel 270

Se vede că există diferențe notabile între ultimele trei metode, dar oricare dintre ele mătură pe jos cu metodele naive.

Aceste calcule și multe altele le puteți găsi la http://graphics.stanford.edu/~seander/bithacks.html

Programare dinamică

Vom urma notele de la clasele 11-12, dar vom insista mai mult pe probleme. Vom sta două lecții pe acest subiect și abia spre sfârșitul lecției a doua vom extrage niște principii teoretice.