Oddział Multiway - Multiway branch

Gałąź typu Multiway to zmiana w przepływie kontroli programu na podstawie wartości pasującej do wybranych kryteriów. Jest to forma instrukcji warunkowej . Odgałęzienie wielodrogowe jest często najbardziej wydajną metodą przekazywania kontroli do jednego z zestawu etykiet programu , zwłaszcza jeśli wcześniej utworzono indeks z surowych danych .

Przykłady

Alternatywy

Wielodrożną gałąź można często zastąpić wydajnym przeszukiwaniem tabeli indeksowanej (przy użyciu samej wartości danych lub obliczonej pochodnej wartości danych jako indeksu tablicy )

„ … implementacja instrukcji switch została zrównana z implementacją instrukcji switch z wieloma ścieżkami. Jednak w przypadku wielu zastosowań instrukcji switch w rzeczywistym kodzie można całkowicie uniknąć rozgałęzień i zastąpić przełącznik jednym lub kilkoma wyglądami tabeli -ups. Na przykład Has30Daysprzykład [przedstawiony wcześniej] można zaimplementować w następujący sposób: [C przykład] "

„A Superoptimizer Analysis of Multiway Branch Code Generation” autorstwa Rogera Anthony'ego Sayle'a 

 switch (x) {                     /* x is month no */
   case 4:                        /* April         */                             
   case 6:                        /* June          */
   case 9:                        /* September     */
   case 11:                       /* November      */
   return true;
 }

można zastąpić przy użyciu techniki „bezpiecznego mieszania” - 

 unsigned int t = x | 2;
 switch (t) {
   case 6:
   case 11:
   return true;
 }

lub można go zastąpić, używając wyszukiwania tabeli mapowania indeksu , z - 

 x %= 12;                                           /* to ensure x is in range 0-11*/                                                 
 static const int T[12] ={0,0,0,0,1,0,1,0,0,1,0,1}; /* 0-based table 'if 30 days =1,else 0'  */
 return T[x];                                       /* return with boolean 1 = true, 0=false */

(ze względu na prostotę tego drugiego przypadku byłoby lepiej zaimplementować go w linii, ponieważ narzut używania wywołania funkcji może być większy niż samo wyszukiwanie indeksowane).

Cytaty

Wielokierunkowe rozgałęzianie to ważna technika programowania, która zbyt często jest zastępowana nieefektywną sekwencją testów if. Peter Naur niedawno napisał mi, że uważa użycie tabel do sterowania przepływem programów za podstawową ideę informatyki, która została prawie zapomniana; ale spodziewa się, że lada dzień będzie gotowy do ponownego odkrycia. Jest to klucz do wydajności wszystkich najlepszych kompilatorów, które studiowałem.

-  Donald Knuth , Structured Programming, przejdź do instrukcji

Zobacz też

Bibliografia

Linki zewnętrzne