- LiTime Speicher und Akkus         
Ergebnis 1 bis 10 von 10

Thema: Bubblesort: für beliebige Datentypen nur 1 Algorithmus ?

  1. #1
    HaWe
    Gast

    Bubblesort: für beliebige Datentypen nur 1 Algorithmus ?

    Anzeige

    Powerstation Test
    hallo,
    für einfache Sortierzwecke kurzer Arrays verwende ich gern den Bubblesort (ansonsten Shellsort oder Quicksort).
    Nun brauche ich bislang immer 2 getrennte Funktionen, eine für int32, eine für double.
    Wie macht man es "schöner" mit C oder C++, dass man für beliebige (!) Datentypen im selben (!) Programm nur 1 Algorithmus braucht, evtl. auch für char*, int16_t* und float* ? (Ich arbeite mit der Arduino IDE auf 8-bit AVR und 32-bit ARM/ESP-Plattformen.)

    Code:
    void bubblesortn(int32_t *array, int length) {
      int32_t tmp;
    
      for (int i=0; i<length-1; i++)     {
        for (int j=0; j<length-i-1; j++)  {
          if (array[j] > array[j+1])       {
            tmp = array[j];
            array[j] = array[j+1];
            array[j+1] = tmp;
          }
        }
      }
    }
    
    void bubblesortd(double *array, int length) {
      double  tmp;
    
      for (int i=0; i<length-1; i++)     {
        for (int j=0; j<length-i-1; j++)  {
          if (array[j] > array[j+1])       {
            tmp = array[j];
            array[j] = array[j+1];
            array[j+1] = tmp;
          }
        }
      }
    }
    Erste "Ideen" wären mit overloading oder mit void *array, ersteres habe ich aber noch nie gemacht und letzteres könnte zu kompliziert in der Programmierung werden, fürchte ich, etwa z.B.
    void bubblesort (void *array , size_a length, size_a varsize, f_compare) // wie bei Quicksort-Implementierung
    - nur die zusätzlich nötigen f_compare() Funktionen für alle Var-Typen machen es dann unterm Strich sicher auch nicht einfacher....

    Auch von "Prototypen" habe ich mal was gelesen - wäre das besser und einfacher?

    - - - Aktualisiert - - -

    update:

    habe mal ganz ohne Hoffnung, dass es klappen könnte, beide Funktionen mit unterschiedlichen Datentypen unter demselben Funktionsnamen deklariert -
    überraschenderweise meckert der Compiler gar nicht und er scheint das völlig automatisch zu overloaden... das wär ja ungeahnt simpel...!
    Code:
    void bubblesort(int32_t *array, int length) {
      int32_t tmp;
    
      for (int i=0; i<length-1; i++)     {
        for (int j=0; j<length-i-1; j++)  {
          if (array[j] > array[j+1])       {
            tmp = array[j];
            array[j] = array[j+1];
            array[j+1] = tmp;
          }
        }
      }
    }
    
    void bubblesort(double *array, int length) {
      double  tmp;
    
      for (int i=0; i<length-1; i++)     {
        for (int j=0; j<length-i-1; j++)  {
          if (array[j] > array[j+1])       {
            tmp = array[j];
            array[j] = array[j+1];
            array[j+1] = tmp;
          }
        }
      }
    }

  2. #2
    Erfahrener Benutzer Roboter Experte
    Registriert seit
    04.09.2011
    Ort
    Hessen
    Beiträge
    707
    Wenn eine zweite Datei erlaubt ist, die Arduino IDE ist da sonst etwas eigen, braucht man die Funktion nicht zweimal hinschreiben.

    Beispiel, getestet mit Arduino 1.8.5 und Arduino Uno:

    Datei "TemplateTest.h"
    Code:
    template<typename T>
    void bubblesort(T *array, int length) {
      T tmp;
    
      for (int i=0; i<length-1; i++)     {
        for (int j=0; j<length-i-1; j++)  {
          if (array[j] > array[j+1])       {
            tmp = array[j];
            array[j] = array[j+1];
            array[j+1] = tmp;
          }
        }
      }
    }
    Sketch "TemplateTest.ino"
    Code:
    #include "TemplateTest.h"
    
    int Test1[] = { 4, 2, 9 };
    double Test2[] = { 8.2, 7.1, 5.4, 9.6, 1.3 };
    
    void setup() {
      // put your setup code here, to run once:
      Serial.begin(9600);
    
      bubblesort(Test1, 3);
    
      for(auto& n : Test1) {
        Serial.println(n);
      }
    
      Serial.println();
      bubblesort(Test2, 5);
    
      for(auto& n : Test2) {
        Serial.println(n);
      }
    }
    
    void loop() {
      // put your main code here, to run repeatedly:
    
    }
    Die sortierte Ausgabe sieht man im seriellen Monitor.

  3. #3
    HaWe
    Gast
    klasse, danke, das ist ja noch viel schicker!
    - und wow, die Ausgabe ist ja auch sehr "sophisticated"

    - - - Aktualisiert - - -

    Anschlussfrage...:

    Ich verwende den bubblesort z.B. für versch. Medianfilter:
    kann man das ähnlich schick ebenfalls "overloaden" ?
    Code:
    // FiFo-Arrays für Median, nur für Gebrauch von FiFo-push und Medianfilter
    
    static int16_t  fifoi[8][3];
    static int32_t  fifon[8][3];
    static double   fifod[8][3];
    
    //---------------------------------------------------------
    // FiFo-push
    
    void fifopush(int16_t  col,  int16_t _new) {
      fifoi[col][2] = fifoi[col][1];
      fifoi[col][1] = fifoi[col][0];
      fifoi[col][0] = _new;
    }
    
    void fifopush(int16_t  col,  int32_t _new) {
      fifon[col][2] = fifon[col][1];
      fifon[col][1] = fifon[col][0];
      fifon[col][0] = _new;
    }
    
    void fifopush(int16_t  col, double _new) {
      fifod[col][2] = fifod[col][1];
      fifod[col][1] = fifod[col][0];
      fifod[col][0] = _new;
    }
    
    //---------------------------------------------------------
    // Medianfilter
    
    int16_t  medianOf3i(int col) {
      int16_t temp[3];
      
      memset ( temp, 0, 3 );
      for ( int i = 0; i < 3; i++)  temp[i] = fifoi[col][i];
      bubblesort( temp, 3 );
      return temp[1];
    }
    
    int32_t  medianOf3n(int col) {
      int32_t temp[3];
      
      memset ( temp, 0, 3 );
      for ( int i = 0; i < 3; i++)  temp[i] = fifon[col][i];
      bubblesort( temp, 3 );
      return temp[1];
    }
    
    double medianOf3d(int col) {
      double  temp[3];
    
      memset ( temp, 0, 3 );
      for (int i = 0; i < 3; i++)  temp[i] = fifod[col][i];
      bubblesort( temp, 3 );
      return temp[1];
    }
    Die Zuordnung von ggf. übergebenen Variablentypen auf die entspr. FiFo-Arrays fifoi[][], fifon[][] und fifod[][] muss dazu funktionieren; deren Namen sind aber nicht "öffentlich", sondern werden nur von Median- und FiFo-push-Funktionen "privat" verwendet.

  4. #4
    Erfahrener Benutzer Roboter Experte
    Registriert seit
    04.09.2011
    Ort
    Hessen
    Beiträge
    707
    Also eigentlich ist das Prinzip bei Templates einfach. Man ersetzt die "beliebigen" Datentypen quasi durch Typvariablen. Das man die T usw. nennt ist nur eine Konvention.

    Damit sollte man eigentlich aus den fifopush folgendes machen können (ungetestet)
    Code:
    template<typename T>
    void fifopush(int16_t  col,  T _new) {
    [Edit2]
    Sorry, nein, jetzt sehe ich erst die unterschiedlichen Arrays. Die müsste man wohl zu Parametern befördern, sonst macht das keinen Sinn.

    [Edit]
    Die medianOf3 würden komplizierter, da werden ja abhängig vom Typ andere Arrays verwendet.

  5. #5
    HaWe
    Gast
    kann man in den Funktionen selber die Art der übergebenen template<typename T> abfragen?
    In der Art
    if(T==double) ... tudies
    else
    if(T==int32_t) ... tudas
    else
    if(T==int16_t) ... tuanderes

  6. #6
    Erfahrener Benutzer Roboter Experte
    Registriert seit
    04.09.2011
    Ort
    Hessen
    Beiträge
    707
    Zur Erläuterung der Edits:

    Ja, man könnte Template Code schreiben in der Form "Wenn T ein int ist dann nimm dieses Array", aber das wird wohl nicht kürzer als die jetzigen Funktionen. Man bräuchte dafür std::enable_if (ab C++11) oder constexpr if (ab C++17).


    Hier mal als Beispiel, die Arduino "map" Funktion, die beim Teensy in C++14 geschrieben ist:
    Code:
    // when the input number is an integer type, do all math as 32 bit signed long
    template <class T, class A, class B, class C, class D>
    long map(T _x, A _in_min, B _in_max, C _out_min, D _out_max, typename std::enable_if<std::is_integral<T>::value >::type* = 0)
    {
    	long x = _x, in_min = _in_min, in_max = _in_max, out_min = _out_min, out_max = _out_max;
    	// Arduino's traditional algorithm
    	//return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min;
    	// st42's suggestion: https://github.com/arduino/Arduino/issues/2466#issuecomment-69873889
    	// more conversation:
    	// https://forum.pjrc.com/threads/44503-map()-function-improvements
    	if ((in_max - in_min) > (out_max - out_min)) {
    		return (x - in_min) * (out_max - out_min+1) / (in_max - in_min+1) + out_min;
    	} else {
    		return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min;
    	}
    }
    // when the input is a float or double, do all math using the input's type
    template <class T, class A, class B, class C, class D>
    T map(T x, A in_min, B in_max, C out_min, D out_max, typename std::enable_if<std::is_floating_point<T>::value >::type* = 0)
    {
    	return (x - (T)in_min) * ((T)out_max - (T)out_min) / ((T)in_max - (T)in_min) + (T)out_min;
    }

  7. #7
    HaWe
    Gast
    aja, stimmt, sieht nicht einfacher aus

  8. #8
    Erfahrener Benutzer Roboter Experte
    Registriert seit
    04.09.2011
    Ort
    Hessen
    Beiträge
    707
    Man muss dabei bedenken, das sind Berechnungen die der Compiler zur Übersetzungszeit ausführen muss. Es handelt sich dabei um "Metaprogrammierung".
    https://de.wikipedia.org/wiki/C%2B%2...programmierung

    Der Knackpunkt in obigen Code ist aber eigentlich sichtbar, es handelt sich um diese zwei Stellen
    Code:
    long map( /* weggelassene Parameter */ , typename std::enable_if<std::is_integral<T>  /* ... */)
    
    T map(/* weggelassene Parameter */ , typename std::enable_if<std::is_floating_point<T>::value >/* ... */)
    Zwei Funktionen namens map, die Parameter der ersten passen nur (enable_if) wenn T ein Integertyp ist (is_integral). Bei der zweiten muss T ein "floating_point" sein. Der Mechanismus der dann greift ist der gleiche wie bei zwei normalen Funktionen, die eine mit int die andere mit double Parameter.

  9. #9
    HaWe
    Gast
    ja, danke, jetzt sehe ich auch das Prinzip! Interessant, was da alles so geht...!

  10. #10
    HaWe
    Gast
    so, habe meine ardumath lib fertig, anscheinend zumindest ohne erkennbare Bugs!

    Man kann einfach bubblesort für einen beliebigen Array nutzen,
    dann medianofX mit Angabe von Var.-Nr und der Array-Tiefe (median of 3 oder median of 5 z.B.)
    und schließlich auch medianNewOfX unter zusätzlicher Übergabe eines neuen Messwertes, der sodann erst in den FiFo Puffer eingespeist wird.

    Edit:
    Als Zugabe noch ein Shellsort und ein Lowpass-Filter mit beliebigem Variablentyp.

    vlt kanns ja jemand brauchen - Bug Reports willkommen!

    Code:
    // ardumath.h
    
    #ifndef _ARDUMATH_H
    #define _ARDUMATH_H
    
    
    //---------------------------------------------------------
    // Bubble Sort
    //---------------------------------------------------------
    
    template<typename VTYPE>
    void bubblesort(VTYPE *array, int length) {
      VTYPE tmp;
    
      for (int i=0; i<length-1; i++)     {
        for (int j=0; j<length-i-1; j++)  {
          if (array[j] > array[j+1])       {
            tmp = array[j];
            array[j] = array[j+1];
            array[j+1] = tmp;
          }
        }
      }
    }
    
    
    //---------------------------------------------------------
    // Shell Sort
    //---------------------------------------------------------
    
    template<typename VTYPE>
    void shellsort(VTYPE *array, int length) {
      int   i, j, increment;   
      VTYPE temp;
    
      increment = length / 2;
      while (increment > 0) {
        for (i = increment; i < length; i++) {
          j = i;
          temp = array[i];
          while ((j >= increment) && (array[j-increment] > temp)) {
            array[j] = array[j - increment];
            j = j - increment;
          }
          array[j] = temp;
        }
        if (increment == 2)
           increment = 1;
        else
           increment = (unsigned int) (increment / 2.2);
      }
    }
    
    
    //---------------------------------------------------------
    // Median Filter
    //---------------------------------------------------------
    
    #define MEDMAX 5  // Median depth: 5 each (MEDMAX default)
    
    // private FiFo Buffers: 8 variants, Median depth: 5 each (MEDMAX default)
    static int16_t  fifoi[8][MEDMAX];
    static int32_t  fifon[8][MEDMAX];
    static double   fifod[8][MEDMAX];
    
    
    
    void fifopush(int16_t _new, int varnr) {
      for (int i=MEDMAX-1; i>=1; i--) {
         fifoi[varnr][i] = fifoi[varnr][i-1];
      }
      fifoi[varnr][0] = _new;
    }
    
    void fifopush(int32_t _new, int varnr) {
      for (int i=MEDMAX-1; i>=1; i--) {
         fifon[varnr][i] = fifon[varnr][i-1];
      }
      fifon[varnr][0] = _new;
    }
    
    void fifopush(double _new, int varnr) {
      for (int i=MEDMAX-1; i>=1; i--) {
         fifod[varnr][i] = fifod[varnr][i-1];
      }
      fifod[varnr][0] = _new;
    }
    
    //---------------------------------------------------------
    
    int16_t  medianOfi(int varnr, int depth) {
      int16_t temp[depth];  
      for (int i=0; i<depth; i++)  temp[i] = fifoi[varnr][i];
      bubblesort( temp, depth );  
      return temp[depth/2];
    }
    
    int32_t  medianOfn(int varnr, int depth) {
      int32_t temp[depth];  
      for (int i=0; i<depth; i++)  temp[i] = fifon[varnr][i];
      bubblesort( temp, depth );  
      return temp[depth/2];
    }
    
    double  medianOfd(int varnr, int depth) {
      double  temp[depth];
      for (int i=0; i<depth; i++)  temp[i] = fifod[varnr][i];
      bubblesort( temp, depth );
      return temp[depth/2];
    }
    
    //---------------------------------------------------------
    
    int16_t medianNewOfi(int16_t _new, int varnr, int depth) {
      fifopush(_new, varnr);
      return medianOfi(varnr, depth);
    }
    
    int32_t medianNewOfn(int32_t _new, int varnr, int depth) {
      fifopush(_new, varnr);
      return medianOfn(varnr, depth);
    }
    
    double medianNewOfd(double _new, int varnr, int depth) {
      fifopush(_new, varnr);
      return medianOfd(varnr, depth);
    }
    
     
    //---------------------------------------------------------
    //  Tiefpass = lowpassFilter
    //---------------------------------------------------------
    
    template<typename VTYPE>
    double lowpassFilt(VTYPE NewVal, VTYPE Avrg, double FF) {
       
       return (double)(NewVal*FF + Avrg*(1.0-FF)) ;
    }
     
    
    //---------------------------------------------------------
    
    #endif
    
    //---------------------------------------------------------
    //---------------------------------------------------------
    Geändert von HaWe (25.06.2018 um 11:46 Uhr)

Ähnliche Themen

  1. Nach ISR in beliebige Funktion springen? Wie? Inline-Asm?
    Von Manu_91 im Forum C - Programmierung (GCC u.a.)
    Antworten: 15
    Letzter Beitrag: 17.09.2015, 09:56
  2. Beliebige Pins für I2C (SDA & SCL) ...? (ATmega168)
    Von Willa im Forum Basic-Programmierung (Bascom-Compiler)
    Antworten: 6
    Letzter Beitrag: 25.10.2009, 22:18
  3. Datentypen
    Von Thomas$ im Forum Basic-Programmierung (Bascom-Compiler)
    Antworten: 31
    Letzter Beitrag: 30.07.2009, 23:15
  4. AVR-GCC: Floating Point Datentypen
    Von Dirk im Forum C - Programmierung (GCC u.a.)
    Antworten: 6
    Letzter Beitrag: 17.07.2009, 10:53
  5. Programm zur Simulation von boolschen und fließk. Datentypen
    Von izaseba im Forum Konstruktion/CAD/3D-Druck/Sketchup und Platinenlayout Eagle & Fritzing u.a.
    Antworten: 0
    Letzter Beitrag: 25.06.2005, 23:18

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •  

LiTime Speicher und Akkus