Optimierte Bereich Überprüfung und Rückgabe eines Wertes

Question

Ich habe unter Funktion, die einen Wert auf der Grundlage der Eingabe zurückgibt. Ich muss diesen Code so schnell wie möglich machen, ohne Divison oder Modulo-Operator oder Schleifen zu verwenden. Jeder aufeinanderfolgende Wert von Betrag getrennt ist fast gleich 6553.

int GetScalingFactor(int input) 
{ 
    unsigned int factor = 0; 

    if(input < 13107) factor = 72816; 
    else if(input < 19660) factor = 81918; 
    else if(input < 26214) factor = 93621; 
    else if(input < 32767) factor = 109225; 
    else if(input < 39321) factor = 131070; 
    else if(input < 45874) factor = 163837; 
    else if(input < 52428) factor = 218450; 
    else if(input < 58981) factor = 327675; 

    return factor; 
} 

Answer 1

Sie einen Tisch vorbereiten konnte enthält 7281613107 mal wiederholt, wiederholt 8191819660-13107 mal, und so weiter und prüft gerade obere Schranke (58981). Wenn innerhalb der Grenzen, einfach table[input] zurückgeben sonst geben 0, wie Sie derzeit (sollten) tun.

Keine Division, kein Modulo, nur einige zugewiesenen Speicher (deutlich unter 1 Megabyte) und vorberechnete Tabelle.

Proof-of-Concept:

#include <stdio.h> 
#include <stdint.h> 

int32_t table[58981]; 

void prepare_table() 
{ 
    int32_t input,factor; 
    for (input=0;input<sizeof(table)/sizeof(table[0]);input++) 
    { 
    // just reusing your code as-is, but only to create the table 

    if(input < 13107) factor = 72816; 
    else if(input < 19660) factor = 81918; 
    else if(input < 26214) factor = 93621; 
    else if(input < 32767) factor = 109225; 
    else if(input < 39321) factor = 131070; 
    else if(input < 45874) factor = 163837; 
    else if(input < 52428) factor = 218450; 
    else if(input < 58981) factor = 327675; 

    table[input] = factor; 
    } 

} 
int GetScalingFactor(int input) 
{ 
    return input < sizeof(table)/sizeof(table[0]) ? table[input] : 0; 
} 

int main() { 

    prepare_table(); 

    printf("%d => %d\n",19600,GetScalingFactor(19600)); 
    printf("%d => %d\n",26200,GetScalingFactor(26200)); 
    printf("%d => %d\n",58000,GetScalingFactor(58000)); 
    printf("%d => %d\n",60000,GetScalingFactor(60000)); 

} 

so ist es Speicher vs Berechnung Kompromisses. Wenn Sie sich den Cache-Fehler nicht leisten können, haben Sie keine andere Wahl als Division oder mehrere Tests.

Answer 2

Der lokale variable Faktor ist nicht sehr nützlich.

Ich denke, Sie können nicht wirklich eine Sequenz von "wenn sonst" optimieren, aber Sie können denken, , was der häufigere Fall sind und testen sie zuerst. Die meiste Zeit wird also nur die erste Bedingung bearbeitet.

int GetScalingFactor(int input) { 

     if(input < 13107) return 72816; // most common case 
     else if(input < 19660) return 81918; // second common case 
     else if(input < 26214) return 93621; // ... 
     else if(input < 32767) return 109225; 
     else if(input < 39321) return 131070; 
     else if(input < 45874) return 163837; 
     else if(input < 52428) return 218450; 
     else if(input < 58981) return 327675; 
     else return 0; 
    } 

Answer 3

Mit std::lower_bound von in C++:

int GetScalingFactor(int input) 
{ 
    const unsigned int inputs[] = {13107, 19660, 26214, 32767, 39321, 45874, 52428, 58981}; 
    const int factors[] = {72816, 81918, 93621, 109225, 131070, 163837, 218450, 327675, 0}; 

    auto it = std::lower_bound(std::begin(inputs), std::end(inputs), input + 1); 
    return factors[std::distance(std::begin(inputs), it)]; 
} 

Demo

Answer 4

Wenn der Compiler schnelle Division durch eine Konstante (unter Verwendung von Multiplikation und Verschiebungen) implementiert, wird die folgende Funktion arbeiten:

int GetScalingFactor(int input) 
{ 
    static const int factors[] = 
    { 
     72816, 72816, 81918, 93621, 109225, 131070, 163837, 218450, 327675 
    }; 

    if (input < 0) 
    { 
     input = 0; 
    } 
    else 
    { 
     input = (input * 2 + 1)/13107; 
     if (input >= sizeof(factors)/sizeof(factors[0])) 
     { 
      return 0; 
     } 
    } 
    return factors[input]; 
} 

Answer 5

Vorausgesetzt, dass die Eingabe ist völlig arbitra ry und es gibt keinen Fall, dass eher als die andere ist, dann können Sie die Schecks als hartcodierte binäre Suche neu zu schreiben, wo Sie die gesuchten Daten Abstände in zwei Teilen mit jedem geteilt if-Anweisung:

if(input < 32767ul) 
{ 
    if(input < 19660ul) 
    { 
    ... 
    } 
    ... 
} 
else if(input < 45874ul) 
{ 
    ... 
} 

Und so weiter (zeichne es vor der Kodierung als binären Suchbaum auf Papier, wenn das hilft). Dies reduziert die Anzahl der Vergleiche mit "O log (n)" und ist das Beste, was Sie erreichen können, wenn Sie eine riesige Nachschlagetabelle von 58981 Artikeln erstellen, wobei input der Index ist - was die beste Lösung in Bezug auf Ausführungsgeschwindigkeit.

Auch Sie Code ist abgehört, sollten Sie nicht vorzeichenbehaftete Variablen mit int mischen. Wechseln Sie den Datentyp auf uint_fast32_t.

Answer 6

Warum Daten verwenden, wenn wir eine Binärsuche zur Kompilierzeit mit Vorlagenerweiterung berechnen können?

Synopsis: Dieser Code generiert eine benutzerdefinierte lower_bound-Implementierung für jede Indexsequenz.

Voraussetzungen: Jeder Index muss im Tupel in aufsteigender Reihenfolge erscheinen.

Ergebnisse: bei Clang 3.9.1 wird kein Eingabearray generiert. Der Compiler vergleicht lediglich jede Grenze in der effizientesten Reihenfolge. GCC entscheidet ein Array zu erstellen und effektiv implementieren lower_bound selbst (wow!)

Code:

#include <utility> 
#include <tuple> 

// turn values into types 
template<std::size_t I> using index = std::integral_constant<std::size_t, I>; 

// termination case  
template<class T, class Tuple, std::size_t it> 
std::size_t iteration(T value, Tuple&&, index<it>, index<0>) 
{ 
    return it; 
} 

// end of search 'else' path which will not be taken but there must 
// be code available at compile time 
template<class T, class Tuple, std::size_t first, std::size_t count, std::enable_if_t<(first >= count)>* = nullptr> 
std::size_t iteration(T value, Tuple&& tuple, index<first>, index<count>) 
{ 
    return count-1; 
} 

// normal iteration of the lower_bound loop  
template<class T, class Tuple, std::size_t first, std::size_t count, std::enable_if_t<(first < count)>* = nullptr> 
std::size_t iteration(T value, Tuple&& tuple, index<first>, index<count>) 
{ 
    constexpr auto step = count/2; 
    constexpr auto it = first + step; 
    if(std::get<it>(tuple) < value) 
    { 
     return iteration(value, std::forward<Tuple>(tuple), index<it>(), index<step + 1>()); 
    } 
    else { 
     return iteration(value, std::forward<Tuple>(tuple), index<first>(), index<step>()); 
    } 
} 

// expand out a lower-bound algorithm from a tuple of bounds 
template<class Tuple, class T> 
constexpr std::size_t tuple_lower_bound(Tuple&& tuple, const T& value) 
{ 
    constexpr auto count = index<std::tuple_size<std::decay_t<Tuple>>::value>(); 
    constexpr auto first = index<0>(); 
    return iteration(value, std::forward<Tuple>(tuple), first, count); 
} 


int GetScalingFactor(int input) 
{ 
    static constexpr auto indexes = std::make_tuple(13107, 19660, 26214, 32767, 39321, 45874, 52428, 58981); 
    static constexpr std::array<int, std::tuple_size<std::decay_t<decltype(indexes)>>::value + 1> factors = 
    {{ 
     72816, 81918, 93621, 109225, 131070, 163837, 218450, 327675, 0 
     }}; 

    auto i = tuple_lower_bound(indexes, input + 1); 
    return factors[i]; 
} 


int main() 
{ 
    extern int get_input(); 
    auto s1 = GetScalingFactor(get_input()); 
    return s1; 
}