3. unbounded array

unbounded array

  • E

    momentan sieht das ganze so aus: http://www.intertivity.de/share/uarray.h

    jetzt ist die aufgabenstellung die folgende:

    Andern Sie die vorgestellte Datenstruktur unbounded array so ab, dass
    alle Operationen im worst-case in O(1) durchgeführt werden können.
    Beschreiben Sie sowohl die Datenstruktur als auch die darauf definierten Operationen und begründen Sie, warum Sie auch im schlimmsten Fall konstante Laufzeit garantieren können.
    Hinweis: Verwenden Sie bis zu zwei Arrays zum Speichern der Elemente und beginnen Sie mit dem Verschieben der Elemente in ein grösseres Array schon, bevor das kleinere Array vollständig gefüllt ist. Sie dürfen auch bei dieser Aufgabe wieder annehmen, dass Allokationen und Deallokationen in konstanter Zeit ablaufen.

    trotz des hinweises, komm ich nicht drauf, wie das in O(1) gehen soll!!!

    0
  • P

    oh, gute idee, damit gehts!
    also, wir legen initial ein array der laenge n an, und eins der laenge 2n.
    alles, was wir in das erste schreiben, schreiben wir auch in das zweite.
    wenn das erste voll ist (n eintraege), legen wir ein drittes der laenge 4    n an, loeschen das erste.
    und jetzt kopieren wir nicht etwa, sondern beim pushbacken eines elements tun wir dies wieder in beide schreiben und zusaetzlich tun wird das element 2n weiter vorne aus dem zwoten in das dritte array kopieren.
    und das gleiche immer weiter. nicht schlecht die idee. aber braucht 3     soviel speicher wie ein normales array.

    0
  • E

    Original erstellt von PeterTheMaster:
    **oh, gute idee, damit gehts!
    also, wir legen initial ein array der laenge n an, und eins der laenge 2n.
    alles, was wir in das erste schreiben, schreiben wir auch in das zweite.
    wenn das erste voll ist (n eintraege), legen wir ein drittes der laenge 4    n an, loeschen das erste.
    **

    okay... bis hier hin kapier ich es...

    Original erstellt von PeterTheMaster:
    **und jetzt kopieren wir nicht etwa, sondern beim pushbacken eines elements tun wir dies wieder in beide schreiben und zusaetzlich tun wird das element 2*n weiter vorne aus dem zwoten in das dritte array kopieren.
    **

    das kapier ich jedoch nicht... nochmal mit genauer! 😉

    aber schonmal danke!

    0
  • E

    habs kappiert...
    danke...
    sobald ich es fertig hab, poste ich mal den code...

    0
  • P
     

    template<class T>
class LinArray{
public:
    LinArray():pos_(0),size_(1),aCurr_(new T[size_]),aNext_(new T[2*size_]){}
    ~LinArray(){ delete aCurr_; delete aNext_; }

    T get(size_t i)const{ return aCurr_[i]; }
    void set(size_t i, const T&t){ 
        aNext_[i]=aCurr_[i]=t; 
    }
    void pushback(const T&t){
        if(pos_==size_){
            size_*=2;
            delete aCurr_;
            aCurr_=aNext_;
            aNext_=new T[2*size_];
        }
        aNext_[pos_]=aCurr_[pos_]=t;
        aNext_[pos_-size_/2]=aCurr_[pos_-size_/2];
        ++pos_;
    }
private:
    //order of declaration is important b/c of initlist
    size_t pos_; //points after last pushbacked element, must be <=size_
    size_t size_; //memory reserved at aCurr_
    T* aCurr_;
    T* aNext_;
};

    ungetestet.

    0
  • P

    na toll...

    0
  • E

    bis auf variablen namen, sind wir ziemlich gleich...
    hab noch popBack implementiert...

    void popBack()
        {
            if(m_idx) m_idx--;
            if(m_size >= blowup * m_idx && m_idx > 0)
            {
                m_size /= factor;
                delete m_data2;

                T* tmp = new T[m_size];

                m_data2 = m_data1;
                m_data1 = new T[m_size];
            }
        }

    wobei factor == 2 und blowup == factor * factor ist!

    0
  • P

    das geht so nicht. (es sei denn deine implementation weicht stark von meiner ab, zeig mal)

    die praxisrelevante implementation von popback ist wohl

    void popback(){
    --pos_;
}

    denn wenn ein array einmal eine groesse hatte, geht man davon aus, dass es auch wieder so gross wird (empirisch).

    was ist tmp? warum postdecrement? das zwote if sollte mit in den scope des ersten.

    0
  • E

    ok... das tmp war unnoetig... war auch schon spaet... hatte es aber schon vorher entdeckt...

    void popBack()
{
   if(pos_) pos_--;
   if(size_ >= 4 * pos_ && pos_ > 0)
   {
       size_ /= 2;
       delete [] aNext_;

       aNext_ = aCurr_;
       aCurr_ = new T[m_size];
   }
}

    so besser?
    die idee ist, dass man den speicherverbrauch auch wieder minimiert, wenn das array nur noch zu 1/4 gefuellt ist...
    hab es getestet...
    scheint zu klappen!!!

    0
  • P

    ich kann mir nicht vorstellen, wie das gehen soll. zeig mal bitte deine gesamte implementation. ich glaube, wenn du das array auch wieder schrumpfen willst, was praktisch schwachsinn ist, brauchst du 3 arrays in die du parallel schreibst. weil wie kommen denn in dein hier neu allokiertes daten rein? mach mal ein get(0) direkt nach einer verkleinerung.

    0
  • E

    ist ja gut...
    hast ja recht!

    [ Dieser Beitrag wurde am 29.05.2003 um 09:56 Uhr von esskar editiert. ]

    0
Anmelden zum Antworten