Welcher median ist schneller?

knivil

Muss man nicht trotzdem die Werte sortieren? Variante 1 scheint das nicht zu machen. Btw. wenn er schon sortiert ist, kann man bestimmt sehr optimieren. Aber das sehe ich gerade nicht in Variante 1.

Edit: Ok, hab 's verstanden. Einfach messen ...

thenoname

Hi,

also der Vector ändert sich ja fortlaufend. nth element wird ja an Position X, also hier die Mitte, den zugehörigen Wert ablegen, als wäre der Vektor sortiert. Dadurch wird der Datensammel Vektor aber verändert und trägt rechts immer die letzten Median Werte, da links neue Daten reingeschoben werden.
Das Kopieren muss ich natürlich auch bei QSort machen.
Ich suche irgendwas, was den nth Wert evtl. ausgibt, ohne den Vector zu verändern.

Grüße
TheNoName

ps. es nennt sich glaube ich "gleitender Median"?

thenoname

Wobei ich bemerken muss, das ich die Funktionsweise von nth Element nicht verstehe, da ich hier ja auch sortieren muss um den nth Wert zu erhalten???

Variante 1 kommt von:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-199232-and-highlight-is-median.html

knivil

std:nth_element sortiert ... etwas

thenoname

Wenn ich "etwas" sortiere kommt "aestw" heraus.
Was schwebt dir dabei vor den Augen herum?

SeppJ

thenoname schrieb:

Wenn ich "etwas" sortiere kommt "aestw" heraus.
Was schwebt dir dabei vor den Augen herum?

Sagen wirs mal so: Wenn du das kleinste Element in "etwas" suchst, musst du dann "etwas" vollständig sortieren? Und wenn du das zweitkleinste suchst, was würdest du dann machen? Setze den Gedankengang fort. Und denke auch daran, dass man dieselbe Argumentationskette auch mit dem größten Element starten kann.

knivil

Einfach mal google benutzen: http://www.sgi.com/tech/stl/nth_element.html

antialias

Bei nTh Element muss ich wohl wegen meinem laufenden Median zuerst den Vector duplizieren, was auch Zeit kostet.

Hier mal ein (nicht getesteter) Gedanke dazu

Da du einen Vektor definierter Länge hast würde ich das anders lösen:

Das ganze nicht als Vektor sondern als Liste abspeichern und die Liste zu anfangs einmal sortieren.
Wenn jetzt ein Wert abgetrennt wird und einer dazugefügt wird den neu dazugefügten richtig einsortieren.

qSort eines Vektors packt im ungünstigsten Fall alle Werte und kopiert sie (z.B. wenn du am Ende einen Wert einfügst der kleiner ist als alle anderen in einem bereits sortierten Vektor muss dieser nach ganz vorne kopiert werden und alle anderen um eins nach hinten)

Um die richtige Position in der List zu finden bietet sich eine divide&conquer Strategie an und du musst effektiv dann nur noch 2 Zeiger umbiegen (wenn du die STL benutzt dann einfach list.insert(...)).

wie in deinem Beispiel steht der Median dann immer an der Position n = size/2, allerdings musst du nix kopieren (wobei der Zugriff auf das size/2-te Glied einer Liste langsamer ist als auf das size/2-te Glied eines Vektors)

Das kannst du aber auch umgehen indem du dir die Position des letzen Medians über einen iterator (iter) merkst. Denn der neue Median ist dann an folgender Position:

Wenn gelöschtes und neu eingefügtes Element BEIDE größer oder kleiner waren als der Median: Dann zeigt iter bereits auf den Median.

Wenn gelöschtes Element größer war als Median und neu eingefügtes kleiner als Median dann steht der neue Median in iter--.

Wenn gelöschtes Element kleiner war als Median und neu eingefügtes größer als Median dann steht der neue Median in iter++.

Zusätzlicher Aufwand:

a) du musst dir eine zweite Liste mit Chronologie der Listenelement vorhalten (z.b. als deque mit Pointern auf deine sortierte Liste) damit du weisst welches das 'älteste' Element ist das gelöscht werden soll. Aber in der deque brauchst du ja immer nur das letzte auszulesen und das erste anfügen: also kein großer overhead.

b) Du musst aufpassen, dass du deinen Medianzeiger 'rettest' wenn zufällig das Median-element gerade gelöscht werden soll - denn sonst schlägt iter++ / iter-- fehl!

hier gibst dann auch wieder 3 Fälle:
a1) neues Element kommt zufällig an position des gelöschten Elements -> neues Element ist median
a2) neues Element nicht benachbart mit altem Medianelement - aber größer: iter++ bevor man das alte Element löscht
a3) neues Element nicht benachbart mit altem Medianelement - aber kleiner: iter-- bevor man das alte Element löscht

life

Vielleicht mal die folgende Wikipedia Seite anschauen:

http://en.wikipedia.org/wiki/Selection_algorithm

Es gibt jedenfalls durchaus O(n) Algorithmen, die den n-ten Median einer Menge bestimmen können.

In diesem Fall bietet sich aber wohl eher eine Datenstruktur an, die die Menge sortiert hält. Eine multiset sollte es eigentlich tun.

pumuckl

thenoname schrieb:

d.h. 100 mal pro Sekunde wird hinten eine neue Zahl angehängt und vorne eine abgetrennt.

Denkbar ungünstig, da einen vector zu benutzen. Beim vorne abtrennen musst du dann nämlich jedes Element um einen Platz nach vorne kopieren. Eine Liste wäre da deutlich besser.
Zum Median: wenn du vor der Bestimmung des Medians überprüfst, wie das hinzugefügte und das entfernte Element sich zum Median verhalten, kannst du schon eine Menge Medianbildungen verhindern:
Sind beide Elemente größer oder beide kleiner als der Median, dann ändert sich der Median nicht. Andernfalls muss der neue Median erst wieder ermittelt werden.
Wenn die Elemente wenig Speicherplatz benötigen, dann sollte es kein Problem sein, zusätzlich zu der Liste auch noch ein set zu haben und jeweils das Element, was an die Liste angehängt bzw. aus ihr entfernt wird, auch ins set zu packen bzw. daraus zu entfernen. Den median in einem Set zu bestimmen, dürfte O(1) brauchen, wenns als balancierter Baum implementiert ist, sonst O(log n).
Wenn die Elemente viel Platz brauchen, sollte erst recht eine liste benutzt werden (weil das Verschieben der Elemente im vector dann entsprechend mehr Aufwand bedeutet), und da push_back bzw. pop_front einer Liste deren Iteratoren nicht invalidieren, können statt der Kopien der Elemente Iteratoren in die Liste im Set gespeichert werden (der Comparator muss dann entsprechend die Iteratoren dereferenzieren). Der Pseudocode wäre dann in etwa wie folgt:

set.erase(list.front);
list.pop_front();
list.push_back(X);
set.insert(list.back);
medianiter = getmedian(set, set.comparator);
median = *medianiter;

life

Etwa so könnte es funktionieren:

#include <list>
#include <map>
#include <cassert>
#include <iostream>

class MedianComputer
{
public:
	MedianComputer(std::list<int> list); //O(n log(n))

	void removeAndAddElement(int removeElement, int addElement); //O(log(n))	
	int getMedian() const; //O(1)

private:
	void eraseElement(std::map<int, std::size_t>::iterator& it);
	void decrementMedianIt();
	void incrementMedianIt();

	std::map<int, std::size_t> multiset;
	std::map<int, std::size_t>::const_iterator medianIt;
	std::size_t medianOffset; 
};

MedianComputer::MedianComputer(std::list<int> list) {
	for(std::list<int>::const_iterator it = list.begin(); it != list.end(); ++it) {
		++multiset[*it];
	}
	medianIt = multiset.begin();
	std::size_t count = 0;
	std::size_t end = list.size()/2;
	while(count+medianIt->second <= end) {
		count += medianIt->second;
		++medianIt;
	} 
	medianOffset = end - count;	
}

void MedianComputer::removeAndAddElement(int removeElement, int addElement) {
	std::map<int, std::size_t>::iterator removeIt = multiset.find(removeElement);
	assert(removeIt != multiset.end());

	int median = getMedian();

	if(removeElement > median) {
		eraseElement(removeIt);

		++multiset[addElement];		
		if(addElement < median) {
			decrementMedianIt();
		}
	}
	else if(removeElement == median && addElement < median) {
		++multiset[addElement];
		decrementMedianIt();
		eraseElement(removeIt);
	}
	else if(removeElement == median && addElement > median) {
		++multiset[addElement];
		decrementMedianIt();
		eraseElement(removeIt);
		incrementMedianIt();
	}
	else if(removeElement < median) {
		eraseElement(removeIt);

		++multiset[addElement];
		if(addElement >= median) {
			incrementMedianIt();
		}
	}
}

int MedianComputer::getMedian() const {
	return medianIt->first;
}

void MedianComputer::eraseElement(std::map<int, std::size_t>::iterator& it) {
	std::size_t count = it->second;
	if(count == 1) {
		multiset.erase(it);
	} else {
		--(it->second);
	}
}

void MedianComputer::decrementMedianIt() {
	if(medianOffset > 0) {
		--medianOffset;
	} else {
		--medianIt;
		medianOffset = medianIt->second - 1;
	}
}

void MedianComputer::incrementMedianIt() {
	if(medianOffset < medianIt->second - 1) {
		++medianOffset;
	} else {
		++medianIt;
		medianOffset = 0;
	}
}

int main(int argc, char *argv[])
{
	std::list<int> list;
	list.push_back(1);
	list.push_back(2);
	list.push_back(3);
	list.push_back(4);
	list.push_back(5);

	MedianComputer medianComputer(list);
	std::cout << medianComputer.getMedian() << std::endl; //1 2 [3] 4 5

	list.push_back(6);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();	
	std::cout << medianComputer.getMedian() << std::endl; //2 3 [4] 5 6

	list.push_back(6);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();

	list.push_back(6);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();

	list.push_back(6);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();	
	std::cout << medianComputer.getMedian() << std::endl; //5 6 [6] 6 6

	list.push_back(7);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();	
	std::cout << medianComputer.getMedian() << std::endl; //6 6 [6] 6 7

	list.push_back(8);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();	
	std::cout << medianComputer.getMedian() << std::endl; //6 6 [6] 7 8

	list.push_back(9);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();	
	std::cout << medianComputer.getMedian() << std::endl; //6 6 [7] 8 9

	list.push_back(1);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();	
	std::cout << medianComputer.getMedian() << std::endl; //1 6 [7] 8 9

	list.push_back(1);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();	
	std::cout << medianComputer.getMedian() << std::endl; //1 1 [7] 8 9

	list.push_back(1);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();	
	std::cout << medianComputer.getMedian() << std::endl; //1 1 [1] 8 9

	list.push_back(10);
	medianComputer.removeAndAddElement(list.front(),list.back());
	list.pop_front();	
	std::cout << medianComputer.getMedian() << std::endl; //1 1 [1] 9 10
}

unskilled

huch - lesen 4tw

krümelkacker

ich weiß nicht, ob das schon erwähnt wurde (hab's beim Überfliegen nicht gesehen) aber std::nth_element hat eine lineare Komplexität, also O(n), falls n die Zahl der Elemente sind. Eine komplette Sortierung dagegen benötigt im Schnitt O(n log(n)) Zeit.

Wie std::nth_element typischerweise implementiert wird, weiß ich nicht. Aber man kann es jedenfalls über einen halben Quick-Sort machen, wobei er sich nach der Partition nicht 2mal rekursiv (für linke und rechte Hälfte) aufruft sondern nur einmal. Welche "Hälfte" hängt davon ab, wo das Pivot-Element relativ zur gewünschten Position landet.