List, Deque oder Vector?

Con*n

Hallo,

wenn Dein Array doch jedesmal sortiert wird, warum hängst Du dann hinten einen Wert ran und löschst den vorne? Du kannst ja auch einfach den ersten Wert durch den neuen ersetzen. Das wird auf jeden Fall schneller sein.

grüße Con@n

[ Dieser Beitrag wurde am 17.06.2003 um 17:47 Uhr von Con@n editiert. ]

Winzler

Hallo,

zuerst hab ich gedacht, das geht nicht, weil ja immer der älteste Wert verworfen werden muss. Aber wenn ich beim ersten mal den ersten Wert durch den neuen ersetze und beim nächsten mal den zweiten usw. dann geht's natürlich!

Ist bestimmt schneller!

Vielen Dank

Stefan

Con*n

Hi,

Nu bin ich aber mal Neugierig. Wie stellst Du eigentlich fest, welcher der älteste Wert ist? Weil, wenn Du das durchsortierst, kann man ja ger nicht mehr so einfach feststellen, welcher Wert jetzt weg muß.

grüße Con@n

[ Dieser Beitrag wurde am 17.06.2003 um 21:43 Uhr von Con@n editiert. ]

Bashar

Original erstellt von Con@n:
Weil, wenn Du das durchsortierst, kann man ja ger nicht mehr so einfach feststellen, welcher Wert jetzt weg muß.

um nicht zu sagen, gar nicht

volkard

also nimm ein array fester größe und den linearen median-algo, würd ich sagen tun.
genaueres hängt von den daten ab, die vermutlich kommen werden. und davon, wie schnell es werden muss.

[ Dieser Beitrag wurde am 17.06.2003 um 22:26 Uhr von volkard editiert. ]

volkard

bei 31 messwerten kommts mir doch.
kann man nicht nen vollen max-heap mit den 15 kleineren und nen vollen min-keap mit den 15 größeren und dem dedian dazwischen machen?

void insert(int x)
{
  * hau den alten raus.
  * tu den alten median in den heap, wo der alte grad ausflog
  if(x<groessterDerKleinen)
     median=groessterDerKleinen
  *   tu x in den heap der kleinen rein
  else if(x<groessterDerKleinen)
     median=kleinsterDerGrossen
  *   tu x in heap der grossen rein
  else
     median=x
}

die zeilen mit * davor haben O(log(n)), die anderen haben O(1) mit n==arraygröße für den median. das riecht also nach ner O(log(n))-Implemetierung für nen median-filter und toppt sogar die O(n)-Version und die sortierversion eh.

kann aber sein, daß bei nur 31 werten ne schlichte variante schneller ist. zum bleistift, wenn man ein sortiertes array hat und nach ersetzung des ältesten durch den neuen den neuen hoch/bzw runterblubbert, bis er passt.

Winzler

Hi Leute!

Ich weiß, welcher der älteste ist, indem ich nicht das Originalarray sortiere, immer nur eine Kopie davon.

Was ist denn der lineare Median? Sowas wie ein gleitender Mittelwert? Ich will grobe Ausreißer aus meinen Messdaten entfernen, da sollte was nichtlineares eigentlich besser sein. Schnell sollte es auch werden, denn da kommen seeehr viele Daten aus dem AD-Wandler

Winzler

Puh, jetzt wird's kompliziert!

Also, das muss ich jetzt mal in aller ruhe durchdenken.

volkard

Original erstellt von Winzler:
Hi Leute!
Ich weiß, welcher der älteste ist, indem ich nicht das Originalarray sortiere, immer nur eine Kopie davon.
Was ist denn der lineare Median? Sowas wie ein gleitender Mittelwert? Ich will grobe Ausreißer aus meinen Messdaten entfernen, da sollte was nichtlineares eigentlich besser sein. Schnell sollte es auch werden, denn da kommen seeehr viele Daten aus dem AD-Wandler

meinte den linearen algo, um nen median zu bestimmen. aka median-der-mediane-algo. ist bestimmt schneller, als sortieren von 31 werten, aber vermutlich nicht gerade einfach zu implemetieren, daß er sich bei 31 weren wohl fühlt.

volkard

Original erstellt von Winzler:
kommen seeehr viele Daten aus dem AD-Wandler

unsigned 16-bit? ists gut, wenn der wandler 1mb/s davon schafft?

und vor allem, was weiß man über die daten? ändern sie sich selten? dann natürlich nen hoch/runter-bubbler, der immer bei der letzten zielposition ansetzt. wohl doppelt verkettet liste in nem array, das machts einfügen und löschen fein. uih, wäre das schnell.

[ Dieser Beitrag wurde am 17.06.2003 um 22:58 Uhr von volkard editiert. ]