Tankis: pamatuota, ne argumentuota

Antroje pamokoje suskaičiavai, kad 206 875 griežinių antraštės kainuotų transit beveik penkis megabaitus vien rodyklėms. Ir tos pamokos spąstai pasakė tiesiai:

Tai projektavimo pastaba, ne matavimas. Antro žingsnio lentelė yra matavimas, ši pastraipa — argumentas. Abu naudingi; įrodymas tik vienas iš jų.

Dabar turi grafą ir gali tą klausimą pamatuoti.

$ algo dense
nodes 1000, edges 744

                                  bytes            cells           used
  adjacency list                  29952                -              -
  adjacency matrix               125000          1000000        0.1488%

  the matrix is 4.2x larger

  visiting every neighbour of every node:
  adjacency list                   1488           0s
  adjacency matrix              1000000        527µs

Matrica čia sudėta į bitus, ne baitus — kitaip lyginimas būtų nesąžiningas jos nenaudai. Ir vis tiek: 1 000 000 langelių 1 488 tikroms briaunoms. Užpildyta 0.1488 %.

Ir tai ne pastovus skirtumas

$ for n in 1000 10000 100000; do algo gen -n $n -seed 3; algo dense; done

       n    edges     list bytes   matrix bytes      ratio         used
    1000      744          29952         125000       4.2x      0.1488%
   10000     7497         299976       12500000      41.7x      0.0150%
  100000    74998        2999984     1250000000     416.7x      0.0015%

Kiekvienas n padidinimas dešimt kartų padidina skirtumą irgi dešimt kartų. Ir tai ne atsitiktinumas: sąrašas auga kaip O(V + E), matrica — kaip O(V²).

Prie 100 000 knygų matrica užimtų 1.25 GB ten, kur sąrašui užtenka 3 MB.

Ir peržiūros kaina

Paskutinės eilutės svarbesnės už atmintį. Kad apeitum grafą, reikia kiekvienos viršūnės kaimynų:

  adjacency list                   1488
  adjacency matrix              1000000

672 kartus daugiau žingsnių, iš kurių 998 512 pasakys „briaunos nėra". Matricai kiekviena viršūnė turi V galimų kaimynų, ir juos visus reikia patikrinti — nesvarbu, kad realiai jų pusantro.

Būtent todėl BFS ir DFS matricoje kainuoja O(V²), o ne O(V + E). Antrame žingsnyje užrašyta kaina galioja tik sąrašui.

Kada matrica vis dėlto teisinga

Ne niekada. Matrica laimi, kai:

• grafas tankus — briaunų tiek, kad E artėja prie V², ir tada matrica nieko nešvaisto;
• dažniausias klausimas yra „ar yra briauna A–B?" — matricai tai vienas žingsnis, o sąraše reikia peržiūrėti A kaimynus;
• V mažas ir fiksuotas — 50 miestų maršrutų lentelė yra 2 500 langelių, ir jokio klausimo čia nėra.

Tavo tinklo vidutinis laipsnis — 1.49. Tankiam grafui prie V = 1000 reikėtų kelių šimtų. Skirtumas ne kiekybinis.

Reprezentaciją renkasi ne grafas, o klausimas ir tankis. Ir abu galima pamatuoti — ką tik ir padarei.