Lūžio taškas: keturi atsakymai

Dabar palygink savo spėjimą su matavimu.

$ algo sweep -ints
key: int32   layout: contiguous

     n |   lin cmps   bin cmps |    lin ns/op    bin ns/op | winner by CLOCK
-------|-----------------------|---------------------------|----------------
     2 |          2          2 |            2            3 | LINEAR
     4 |          3          2 |            3            3 | binary
     8 |          5          3 |            3            3 | binary
    16 |          9          4 |            4            4 | binary
    32 |         17          5 |            5            4 | binary
   127 |         65          7 |           22            7 | binary
  1024 |        513         10 |          112            5 | binary
  2254 |       1128         11 |          265            6 | binary

Skaitiklis ir laikrodis nesutaria

Pažiūrėk į n = 4: 3 palyginimai prieš 2, o laikas vienodas. Prie n = 8 skaitiklis sako, kad dvejetainė 1,7 karto pranašesnė; laikrodis rodo lygiąsias. Skirtumas atsiveria tik kur kas vėliau.

Pagal palyginimus dvejetainė laimi praktiškai nuo pat pradžių. Pagal laikrodį — tik nuo n ≈ 6.

Nė vienas nemeluoja. Jie matuoja skirtingus dalykus:

• palyginimas yra vienetas, kurį skaičiuoja Big-O;
• laikas priklauso ir nuo to, kiek vienas palyginimas kainuoja, ir nuo to, ar duomenys jau procesoriaus atmintinėje, ir nuo to, ar procesorius geba atspėti, kur nueis šuolis.

Tiesinė paieška eina per masyvą iš eilės. Procesorius tokį skaitymą numato ir duomenis parsineša iš anksto. Dvejetainė šokinėja: n/2, n/4, 3n/4 — kiekvienas šuolis nenuspėjamas.

Todėl 65 nuspėjami palyginimai gali trukti trumpiau nei 7 nenuspėjami.

Ir tai dar ne vienas atsakymas

Paleisk tą patį su kitokia išdėstymo ir rakto forma:

konfigūracija	kur lūžis
-ints, gretimai (šis puslapis)	n ≈ 6
-ints -scattered (per map, kaip tikras indeksas)	n ≈ 6, bet abu ~2× lėtesni
be -ints (eilutės, brangus palyginimas)	n ≈ 3

Eilučių atveju vienas palyginimas — funkcijos iškvietimas, galintis peržiūrėti kelis baitus. Kai palyginimas brangsta, tiesinė paieška, daranti jų n/2, pralaimi anksčiau.

Trys mechanizmai, ir kiekvienas stumia lūžio tašką: atminties išdėstymas, palyginimo kaina ir procesoriaus gebėjimas nuspėti šuolius.

Keturi atsakymai į vieną klausimą

transit tą patį klausimą matavo dviem būdais ir gavo du atsakymus. Mes išmatavome trečią kartą ir gavome trečią:

matavimas	lūžio taškas
transit, sintetinis gretimas masyvas	≈ 50
transit, tikras tvarkaraštis, jų kompiuteris	> 127 (tiesinė vis dar laimi)
transit matavimas, mūsų kompiuteris	< 127 (dvejetainė laimi)
ši pamoka, mūsų kompiuteris	≈ 6

Nuo 6 iki daugiau nei 127. Dvidešimtkartis skirtumas tam pačiam algoritmui.

transit sintetinis matavimas naudojo šviežią gretimą []int32, gulintį procesoriaus atmintinėje; tikrasis indeksas tą patį masyvą pasiekia per 1 514 įrašų map. Išdėstymas nulėmė nugalėtoją, ne algoritmas.

Tavo skaičius bus penktas

Paleisk algo sweep savo kompiuteryje. Beveik neabejotinai gausi dar kitą skaičių.

Tai nėra klaida. Tai ir yra atsakymas.

Jei gavai kitą lūžio tašką negu čia parašyta — nieko nesuklydai, o pakartojai patį rezultatą: lūžio taškas nėra algoritmo savybė. Jis yra tavo duomenų, tavo išdėstymo ir tavo procesoriaus savybė.

Įgūdis, kurio siekia ši pamoka, yra ne skaičius 50 ar 127, o gebėjimas pačiam jį rasti.