median algo

Fytch

beantworte bitte erst einmal die frage, ob du es nachimplementieren MUSS (als inhalt einer übung o.ä.) oder ob du einfach das ergebnis möchtest. es gibt in der stl nämlich - wie volkard schon sagte - std::nth_element, welches für diesen zweck geschaffen wurde.

das was du da gepostet hast sieht nach müll aus:
uneindeutige variablennamen
fixe typen
hantieren mit containern statt mit iteratoren
relikte wie return 0;
unnötige endl
undefined behaviour wenn i > k (kein return-statement)
postinkrement obwohl das präinkrement gewünscht ist

ich moechte es nachimplementieren, ist vorbereitung fuer job interview...

algo wurde im mit kurs so beschrieben:
http://www.youtube.com/watch?v=mR_RUjsJnV8

warum gibt es undefined behaviour?

ok den fehler gefunden, aber mein algo liefert (6) noch immer ein unterchiedliches ergebnis im vergleich zu nth_element (5)....warum? bitte um improvements fuer code...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int rand_partition(vector<int> &A, int l, int r) {
	int pivot = A[l + rand() % r];
    int i = l; 
    int j = r+1;

	while(i < j) {
    	while(A[i] <= pivot) i++;
   		while(A[j] > pivot) j--;

   		swap(A[i], A[j]);
   	}

   	return j;
}

int rand_select(vector<int> &A, int p, int q, int i) {
	// ith smallest in A[p..q]
	if(p == q) {
		return A[p];
	}

	int r = rand_partition(A, p, q);
	int k = r - p + 1; // k = rank(A[r]) in A[q...q]

	if(i == k) {
		return A[r];
	}
	else if(i < k) {
		return rand_select(A, p, r - 1, i);
	}
	else {
		return rand_select(A, r + 1, q, i);
	}
}

int get_median2(vector<int> &vec) {
	int n = vec.size()/2;

	nth_element(vec.begin(), vec.begin() + n, vec.end());
	return vec[n];
}

int main() {
	// your code goes here

	//1 2 3 4 5 6 7 8 9
	vector<int> numbers = {9,2,4,3,8,5,7,6,1};
	cout << rand_select(numbers, 0, numbers.size() - 1, numbers.size()/2) << endl;

	vector<int> numbers2 = {9,2,4,3,8,5,7,6,1};
	cout << get_median2(numbers) << endl;

	return 0;
}

volkard

Und nimm einen Container oder Zugriffsfunktionen, die bei Arraygrenzenüberschreitung lautstark weinen.

Schreib Dir die 9 Zahlen in Kronkorken, nimme zwei Leuchtmarker als i und j und male Array-Kästchen auf ein Blatt Papier und simuliere es per Hand.

Als pivot beim Simulieren nimm erstmal den echten Median. Und wenn das ein Weilchen klappt, die Zufallszahl.

Wenn Du tatsächlich nicht siehst, wo Du den median-of-5 einbauen sollst, will ich auch nicht weiter helfen. Dann ist dert Code zu stümperhaft zusammenkopiert und ich vermisse die Eigenleistung.

@Container oder Zugriffsfunktionen, die bei Arraygrenzenüberschreitung lautstark weinen....

vector.at() ?

andere vorschlaege?

SeppJ

c++coder11 schrieb:

@Container oder Zugriffsfunktionen, die bei Arraygrenzenüberschreitung lautstark weinen....

vector.at() ?

andere vorschlaege?

Beispielsweise. Aber geschickter ist einfach ein normaler operator[], denn normalerweise bieten STL-Implementierungen einen optionalen Debugmodus an. Die benutzt man dann bei der Fehlersuche und im Release schaltet man sie ab und muss nix am Programm ändern für volle Performance.

Bei GCC zum Beispiel mittels Makro _GLIBCXX_DEBUG.

@SeppJ ich habe doch gerade von random access operator [] auf .at() umgestellt...seit wann hat ein normaler [] operator eine index pruefung?

SeppJ

c++coder11 schrieb:

@SeppJ ich habe doch gerade von random access operator [] auf .at() umgestellt...seit wann hat ein normaler [] operator eine index pruefung?

SeppJ schrieb:

normalerweise bieten STL-Implementierungen einen optionalen Debugmodus an. Die benutzt man dann bei der Fehlersuche und im Release schaltet man sie ab und muss nix am Programm ändern für volle Performance.

Bei GCC zum Beispiel mittels Makro _GLIBCXX_DEBUG.

Nathan

c++coder11 schrieb:

@SeppJ ich habe doch gerade von random access operator [] auf .at() umgestellt...seit wann hat ein normaler [] operator eine index pruefung?

Der Standard sagt, es ist UB wenn man mit falschem Index rangeht.
Der GCC macht keinen Check, es sei denn _GLIBCXX_DEBUG ist aktiviert.
Dann checkt der.

Nexus

Stell wieder auf operator[] zurück. Die von at() zur Laufzeit geworfene Exception zu behandeln macht in den meisten Fällen keinen Sinn, da es sich um Logikfehler (Bugs) handelt. Bei operator[] hast du im Debug-Modus ebenso eine Prüfung, aber im Release-Modus, wo dein Programm funktioniert, verschwendest du keine Performance für gültige Indizes.

bug gefixed...folgender algo funktioniert:

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;

int rand_partition(vector<int> &a, int left, int right) { 
  int pivotIndex = left + (rand() % (right - left));
  //int m = left + (right - left) / 2; //... to test the algo...no rand at this point
  int pivot = a[pivotIndex];
  int i = left;
  int j = right;

  do {
    while(a[i] < pivot) i++; // find left element > pivot
    while(a[j] > pivot) j--; // find right element < pivot

    // if i and j not already overlapped, we can swap
    if(i < j) {
      swap(a[i], a[j]);
    }
  } while(i < j);

  return i;
}

// Returns the n-th smallest element of list within left..right inclusive (i.e. n is zero-based).
int rand_select(vector<int> &a, int left, int right, int n) {
  if(left == right) {        // If the list contains only one element
    return a[left];  // Return that element
  }

  int pivotIndex = rand_partition(a, left, right);

  // The pivot is in its final sorted position
  if(n == pivotIndex) {
    return a[n];
  }
  else if(n < pivotIndex) {
    return rand_select(a, left, pivotIndex - 1, n);
  }   
  else {
    return rand_select(a, pivotIndex + 1, right, n);
  }
}

int get_median(vector<int> vec) {
  int n = vec.size() / 2;
  return rand_select(vec, 0, vec.size() - 1, n);
}

int get_median2(vector<int> vec) {
  int n = vec.size() / 2;

  nth_element(vec.begin(), vec.begin() + n, vec.end());
  return vec.at(n);
}

int main() {
  // your code goes here

  srand( time(0));

  vector<int> numbers = {9,2,4,3,8,5,7,6,1};
  cout << get_median(numbers) << endl;
  cout << get_median2(numbers) << '\n' << endl;

  vector<int> numbers2 = {6,8,2};
  cout << get_median(numbers2) << endl;
  cout << get_median2(numbers2) << '\n' << endl;

  vector<int> numbers3 = {1, 10, 5, 7};
  cout << get_median(numbers3) << endl;
  cout << get_median2(numbers3) << '\n' << endl;

  vector<int> numbers4 = {11, 3, 7, 8};
  cout << get_median(numbers4) << endl;
  cout << get_median2(numbers4) << '\n' << endl;

  vector<int> numbers5 = {3, 1};
  cout << get_median(numbers5) << endl;
  cout << get_median2(numbers5) << endl;

  return 0;
}