vector oder liste



  • Hallo, ich weiß es wurden tausende themen über vectoren oder listen gepostet doch ich habe da eine andere Frage. Ich habe ein vector in den ich lottozahlen einlese. Z.B. bei 22 zahlen habe ich ca.38000 reihen sechserkombinationen. Diese schreibe ich in einen vector. Wenn ich dann mit einen filter die reihen bearbeiten möchte und eine reihe dem kriterium nicht entspricht soll diese reihe dann gelöscht werden. Da aber das löschen mittendrin in einem vector bei so großer reihezahlen töglich werden kann setze ich einfach diese reihe auf NULL. Dann lese ich bei der auswertung einfach nur die reihe die nicht null sind aus. Ist das auch eine gute methode sowas zu lösen oder sollte ich liebe die reihen doch löschen und dafür eine liste nehmen? Verschwende ich nicht dadurch den speicher?



  • Hem, das löschen innerhalb eines vectors ist tatsächlich sehr langsam. Notfalls kannst du das richtige löschen (nachdem du entprechende Elemente auf NULL gesetzt hast) auch zu einem unkritischen Zeitpunkt machen? Wenn du Threads einsetzt, wäre das z.B. eine Lösung.

    Eine std::list wäre wirklich für deine Aufgabe nicht falsch, dann wäre das löschen nicht mehr so langsam. Ich benutze normalerweise auch für alles Mögliche den vector, aber wenn oft gelöscht wird, lohnt sich eine list.

    Eine list braucht aber tatsächlich mehr Speicher, nämlich zwei Pointer mehr pro list-Element. Kommt jetzt darauf an, in welcher Umgebung deine Anwendung läuft, ob du diesen Mehrspeicher "riskieren" kannst.



  • Hallo, danke für die antwort. An speicher liegt mir eigentlich nicht viel. Das ist mir relativ egal. Was für micht zählt ist die geschwindigkeit. wie gesgat wenn ich vecotor benutze und anfange zu löschen dann dauert das fast 15min. Wenn ich die reihen aber auf null setze dann geht es super schnell. So habe ich das auch anfangs mit array gemacht doch die waren ungeeignet für mich da ich dynamisch arbeite. Was für mich noch wichtig ist, ist denn eine Liste mit löschen von reihen genauso oder noch schneller als die methode die ich jetzt mit dem vector auf null setzen mache? Wenn ja dann würde ich auf liste setzen an sonsten bleibe ich beim alten.



  • Hallo, danke für die antwort. An speicher liegt mir eigentlich nicht viel. Das ist mir relativ egal. Was für micht zählt ist die geschwindigkeit. wie gesgat wenn ich vecotor benutze und anfange zu löschen dann dauert das fast 15min. Wenn ich die reihen aber auf null setze dann geht es super schnell. So habe ich das auch anfangs mit array gemacht doch die waren ungeeignet für mich da ich dynamisch arbeite. Was für mich noch wichtig ist, ist denn eine Liste mit löschen von reihen genauso oder noch schneller als die methode die ich jetzt mit dem vector auf null setzen mache? Wenn ja dann würde ich auf liste setzen an sonsten bleibe ich beim alten.



  • Also "einfach auf NULL setzen" ist natürlich das schnellste was du haben kannst (ich hoffe du machst ein delete auf das Object und dann setzt du es auf null?). Du setzt halt einfach nur einen Pointer-Wert neu - fertig.

    Ansonst verhält sich das löschen eines list-Elements so, das erstmal das Element deleted wird, und dann die Pointer des vorherigen und des nachherigen Elements auch neu gesetzt werden. Das sind also zwei Pointer mehr die neu gesetzt werden - mehr nicht (darum mußt du dich aber nicht kümmern, macht ja list für dich). Man kann da nicht gerade von langsam reden, außer du brauchst jeden fitzeligen Taktzyklos. 😃

    Es ist auf jeden Fall ein guter Kompromiss zwischen Performance und Speicherverbrauch! Und das würde ich vorziehen, als wahrscheinlich unendlich Datenmüll im Vector anzusammeln. Falls dir list doch nicht zusagt, kannste ja den vector wieder einsetzen. Performance-Research ist also wohl hier das Stichwort. 😉



  • Danke Artchi für deine Hilfe. Da hätte ich aber eine frage. Was meinst du mit delete auf das Object und dann auf null setzen. Mein Vectro sieht so aus.

    struct zahlen{
     int z1;
     int z2;
     int z3;
     int z4;
     int z5;
     int z6;
    };
    
    std::vector<zahlen> syszahlen;
    

    Wenn ich dann eine reihe nicht brauche dann mache ich folgendes;

    if(.....) // wenn diese reihe nicht im spiel...
       syszahlen.z1=0;
    

    Somit weiß ich dann beim auslesen welche reihe nicht mehr dabei ist, wenn halt die erste zahl z1==0 ist.
    Oder gibt es da eine bessere Lösung

    Vieleicht verlange ich viel aber könntest du mir sagen wie das mit einer Liste aussehen würde?



  • (Edit, Original war Nonsens 😉 )

    Nimm doch remove_if() aus <algorithm>, das dürfte maximal eine Zuweisung pro Element verursachen (wohingegen vector::erase bei steigender Elementanzahl _ziemlich_ schnell langsam wird).



  • Wieso testest du die Bedingung nicht gleich beim generieren der Würfe?

    Wenn das nicht geht:

    Kommt ein bißchen drauf an, wie oft du das array durchläufst, und wieviele einträge dann endlich rausfallen.

    Ein Array hat schon einen Vorteil: keinen Speicher-Overhead pro Element, und beim linearen durchrennen geht's auch linear durch den Speicher - da freut sich der Cache.

    andere Möglichkeit wäre: du merkst dir eine Lese- und Schreibposition im Array, und setzt die Schreibposition nicht weiter, wenn ein Satz rausfallen soll. Wenn ein Satz drinbleibt (und Schreibposition != Leseposition) verschiebst du ihn auf die schreibposition.



  • Und was spricht gegen eine Liste?
    uU reicht sogar eine einfach verkettete Liste, dann halbiert sich der Overhead...



  • Gegen eine Liste spricht nur das, dass ich mittendring löschen müßte und das kostet zeit. Mit kommt es halt auf die Geschwindigkeit und nicht so auf den speicher an. Anfangs hatte ich auch ein array. Es lief alles excellent. Einfach nur genial schnell. Doch leideer habe ich das problem dass ich das array global haben muß nud vorher nicht weiß wie groß das wird. Und ein array will ja konstante werde von mir haben. Oder kann mir jemand eine lösung geben wie ich das global und dynamisch mit einem array machen kann?



  • Was spricht gegen eine Liste? Die ist fuer Loeschen in der Mitte perfekt.

    Ein vector IST ein dynamisches Array - es wird dir also kaum gelingen ein eigenes dynamisches Array zu schreiben, das schneller ist.

    Mittels new kannst du aber ein Array dynamisch erzeugen.

    Verwende doch einfach eine Liste.



  • yo, wenn er seine Liste nur in einer Richtung durchläuft, würde sich eine einfach-verkettete Liste lohnen. Für erste Tests kann er aber std::list nehmen, später noch ersetzen wenn es ihm nicht gefällt.

    BlackDragon! Hätte gedacht du hast Pointer drin, und dein "zahlen" per new instanziert. Weil du meintest, du setzt es dann auf null. Und wenn du es nicht mehr brauchst, machste auf deinen vector:

    delete syszahlen[i];
    syszahlen[i] = NULL;
    

    Ok, ansonst kannst du std::list wie vector instanzieren und benutzen, ausgenommen den []-Operator. Es gibt zum list dann passende remove-Methoden und somit hätte sich dein Problem gelöst.



  • wenn man nicht nachlässig programmiert kann man sich das = NULL auch sparen 🙂



  • BlackDragon schrieb:

    Gegen eine Liste spricht nur das, dass ich mittendring löschen müßte und das kostet zeit. Mit kommt es halt auf die Geschwindigkeit und nicht so auf den speicher an. Anfangs hatte ich auch ein array. Es lief alles excellent. Einfach nur genial schnell. Doch leideer habe ich das problem dass ich das array global haben muß nud vorher nicht weiß wie groß das wird. Und ein array will ja konstante werde von mir haben. Oder kann mir jemand eine lösung geben wie ich das global und dynamisch mit einem array machen kann?

    Ich glaub da haste was durcheinander gebracht. vector ist intern ein normales Array, nur siehst du das halt nicht. Wenn du dann mehr Elemente einfügst oder löschst, macht vector alles für dich was du vorher in Kleinarbeit hättest machen müssen.

    std::list dagegen arbeitet anders. Du solltest dir vielleicht mal ein Buch über die STL kaufen? Es gibt nämlich ganze Bücher die allein diese ganzen Container der STL behandeln, und sogar Performance-Formeln dazu angeben. So kann man sich das raussuchen, was am besten für die eigene Aufgabe passt.

    list ist eine verkettete Liste, d.h. pro Element wir ein neues Object mit new angelegt, das für dich widerrum das Element "zahl" enthält. Eigentlich müsste ich jetzt das Prinzip "verkettete Liste" (Linked List) erklären. Aber schau mal bei google nach oder in ein STL-Buch rein.

    list ist beim richtigen Löschen in der "Mitte" am schnellsten bzw. der beste Kompromiss.



  • Hallo, danke an alle für die Hilfe. Vor allem danke an Artchi. Ich werde mir mal ein tutorial über Liste reinziehen und das ganze mit Listen lösen.


Log in to reply