3. Array Implementierung - Einfach verkettete Liste

Array Implementierung - Einfach verkettete Liste

  • 3

    Hab ich mich jetzt verlesen, oder sollte das nicht eine verkettete Liste sein. Das hier ist ne Mischung ohne Vorteile.

    0
  • C

    Du hast dich verlesen:

    lu4k schrieb:

    (a)
    Erzeugen Sie eine Datenstruktur Liste1 und verwenden Sie die Array-Implementierung zur Speicherung der verketteten Liste. Hier muss zusätzlich eine Funktion implementiert werden, die abfragt, ob der Speicher leer ist.

    (und der Ausgangsbeitrag sieht eher so aus, als ob er verstehen will/soll/darf, was da im Hintergrund passiert)

    0
  • 3

    Naja, das ist aber keine "Array-Implementierung" sondern eine "Schrott-Implementierung". Irgendwas ist da doch faul.

    0
  • C

    Dann zeig du doch mal, was du dir unter einer Array-Implementation vorstellen würdest 😉

    0
  • 3

    Ich kann mir keine sinnvolle Array-Implementierung einer verketteten Liste vorstellen, die Idee ist einfach schwachsinnig.

    0
  • ?

    "Schwachsinnig" ist ein sehr starkes Wort - zu stark für diesen Zusammenhang. Letztendlich läuft es ja darauf hinaus, der Liste einen lokalen dynamischen Speicher zu verschaffen - das ist ziemlich umständlich, aber unter bestimmten Umständen alles andere als eine schwachsinnige Idee. Insbesondere in stark nebenläufigen Szenarien kann es eine Menge bringen, wenn die verschiedenen Threads sich nicht andauernd um den selben Heap prügeln müssen. Wenn man keinen lokalen Speicher mehr hat, kann man ja immer noch darauf ausweichen.

    Dass alle jemals angeforderten Elemente die gleiche Größe haben, dürfte die Speicherverwaltung deutlich vereinfachen; meine erste Idee wäre, neben der eigentlichen Liste eine Liste gelöschter Elemente vorzuhalten - damit sollte man die Allokation in O(1) hinbekommen können. Das ist allerdings nichts, was ich um diese Zeit noch hinkriege - ich werde mich nach etwas Schlaf mal daransetzen.

    0
  • S

    stimmt. der erste gedanke war bei mir auch: "das ist schwachsinn, das mit eienr festen größe zu machen..." genau wie bei mister PI

    aber stimmt, man muss sich nicht mehr um die speicher allokationen kümmern und das hat seine vorteile...
    aber auch da würde ich die größe dynamisch machen, sprich im constructor angeben lassen, so wäre das nämlich auch praxistauglich...

    0
  • V

    Skym0sh0 schrieb:

    aber auch da würde ich die größe dynamisch machen, sprich im constructor angeben lassen, so wäre das nämlich auch praxistauglich...

    Naja, das Übungsbeispiel muß nicht so ausgereift sein, zumal man das leicht nachrüsten kann.

    Was ich nie nachvollziehen kann, ist, warum man die armen Datenstrukturen immer vergewaltigt. Sortiertes Einfügen darf man einer einfach verketteten Liste einfach nicht antun. Es hätte doch vollig gereicht, sie als Stack ihr Leben fristen zu lassen.

    0
  • 3

    seldon schrieb:

    "Schwachsinnig" ist ein sehr starkes Wort - zu stark für diesen Zusammenhang. Letztendlich läuft es ja darauf hinaus, der Liste einen lokalen dynamischen Speicher zu verschaffen - das ist ziemlich umständlich, aber unter bestimmten Umständen alles andere als eine schwachsinnige Idee. Insbesondere in stark nebenläufigen Szenarien kann es eine Menge bringen, wenn die verschiedenen Threads sich nicht andauernd um den selben Heap prügeln müssen. Wenn man keinen lokalen Speicher mehr hat, kann man ja immer noch darauf ausweichen.

    Dass alle jemals angeforderten Elemente die gleiche Größe haben, dürfte die Speicherverwaltung deutlich vereinfachen; meine erste Idee wäre, neben der eigentlichen Liste eine Liste gelöschter Elemente vorzuhalten - damit sollte man die Allokation in O(1) hinbekommen können. Das ist allerdings nichts, was ich um diese Zeit noch hinkriege - ich werde mich nach etwas Schlaf mal daransetzen.

    Das kapier ich jetzt nicht, kanns mir wer erklären?

    0
  • P

    Ich würde mal vermuten eine Liste die indexe in den Array speichert - umsortiert wird nicht das Element sondern nur der Index. Wenn was rausgelöscht wird den Index woanders speichern um dann bei neuzuweisungen den Platz im Array zu überschreiben. Ist bei bekannter Obergrenze für Anzahl der Elemente in der Liste vermutlich etwas performanter als eine dynamisch reallokierende Struktur zu verwenden - im Rahmen der 2.x GHz Prozzer die in PCs drin stecken macht das aber vermutlich nur wenig Sinn in den meisten Anwendungen.

    0
  • V

    314159265358979 schrieb:

    Das kapier ich jetzt nicht, kanns mir wer erklären?

    Ich kann mal versuchen, andere Worte dafür zu nehmen.

    seldon schrieb:

    Letztendlich läuft es ja darauf hinaus, der Liste einen lokalen dynamischen Speicher zu verschaffen - das ist ziemlich umständlich, aber unter bestimmten Umständen alles andere als eine schwachsinnige Idee. Insbesondere in stark nebenläufigen Szenarien kann es eine Menge bringen, wenn die verschiedenen Threads sich nicht andauernd um den selben Heap prügeln müssen.

    Normalerweise besorgt man sich für jeden Knoten mit new Speicher und gibt jeden mit delete wieder frei. Aber bei 6 Prozessoren und 12 Threads muß sichergestellt werden, daß die vielen gleichzeitig ablaufenden news nicht den Heap aus versehen zerstören, weil sie gleichzeitig wo schreiben. Das verhindert man, indem man dafür sorgt, daß nur einer schreiben kann, aber das bedeutet, daß schlimmstenfalls nur einer arbeitet und elf Threads warten.
    Das ist ganz verhindert, wenn sich ein Thread erste ein fettes Array holt und dadrin eine Liste macht.

    seldon schrieb:

    Wenn man keinen lokalen Speicher mehr hat, kann man ja immer noch darauf ausweichen.

    Ah, eine Kombination aus Speicher, der dem Thread gehört und den 12 gleichzeitigen news, also gerade nicht so richtig gleichzeitigen.

    seldon schrieb:

    Dass alle jemals angeforderten Elemente die gleiche Größe haben, dürfte die Speicherverwaltung deutlich vereinfachen; meine erste Idee wäre, neben der eigentlichen Liste eine Liste gelöschter Elemente vorzuhalten - damit sollte man die Allokation in O(1) hinbekommen können. Das ist allerdings nichts, was ich um diese Zeit noch hinkriege - ich werde mich nach etwas Schlaf mal daransetzen.

    void removeFirst(){
   Node* toDie=anchor;
   anchor=anchor->next;
   delete toDie;
}

    wird zu

    void removeFirst(){
   Node* toDie=anchor;
   anchor=anchor->next;

   toDie->next=freeAnchor;
   freeAnchor=toDie;
}

    und

    void addFirst(double data){
   Node* newNode=new Node;
   newNode->data=data;
   newNode->next=anchor;
   anchor=newNode;
}

    wird zu

    void addFirst(double data){
   Node* newNode;
   if(freeAnchor){
      newNode=freeAnchor;
      freeAnchor=freeAnchor->next;
   }
   else{//Wenn man keinen lokalen Speicher mehr hat, 
      newNode=new Anchor;//kann man ja immer noch darauf ausweichen.
   }
   newNode->data=data;
   newNode->next=anchor;
   anchor=newNode;
}
    0
  • V

    padreigh schrieb:

    im Rahmen der 2.x GHz Prozzer die in PCs drin stecken macht das aber vermutlich nur wenig Sinn in den meisten Anwendungen.

    Das Argument, nur mit anderen Hertz-Zahlen hört man seit 30 Jahren mindestens.
    Aber bis heute hat sich nichts daran geändert, daß der Benutzer auf den Rechner wartet, und daß doppelt so schnell ungefähr doppelt so schnell ist.

    0
  • P

    volkard schrieb:

    Aber bis heute hat sich nichts daran geändert, daß der Benutzer auf den Rechner wartet, und daß doppelt so schnell ungefähr doppelt so schnell ist.

    Stimmt beides, und ersteres Nervt mich laufend (unter Win stärker als unter Linux). Trotzdem behaupte ich das 98.75% der Anwendungen nicht dadurch besser werden das jeder sich was eigenes Strickt. Sowas gehört gekapselt in die Libraries die man benutzt. Wenn du zu den 1.25% gehörst die diese Libraries entwickeln, bitte, nutze jeden Trick der ein Microsekündchen rauskitzelt - ich benutzt die dann vielleicht neben der STL auch mal. Der Rest der Programme ist mit verständlichem und wartbarem Code besser gedient - und als Constraint für eine Übungsaufgabe für angehende InformWasauchimmer ist das ziemlich .... obskur.

    0
  • V

    padreigh schrieb:

    ...

    Die Array-Version (a) ist ja nur Hinführung zur richtigen version (b).
    Das mit dem Array läßt sich besser debuggen.

    Den stl-containern kann man so ein Array auch als Allokator unterschubsen.

    0
  • S

    volkard schrieb:

    Den stl-containern kann man so ein Array auch als Allokator unterschubsen.

    volkard, kannst du mir kurz mal in 1-2 sätzen erklären was ein allokator überhaupt ist?!?

    0
  • 3

    Danke volkard, ich denke ich habe es jetzt verstanden.

    Ein Allokator ist ein Objekt, dass dir deinen Speicher alloziert, auf welche Art auch immer. 😉

    0
  • ?

    Jetzt hat Volkard mir schon einiges vorweggenommen. Ja, genau das ist die Idee - es macht vor allem dann Sinn, wenn man zur Compilezeit grob abschätzen kann, wie viel man zur Laufzeit etwa benötigen kann und trotzdem eine Liste braucht. Ich sehe auch keinen Grund, den ersten Batzen nicht auf den Stack zu legen.

    Dieser Ansatz ist bei kanonischen verketteten Listen etwas weniger sinnvoll als beispielsweise bei Vektoren - man verliert Teile der Listenfunktionalität (Splicing zwischen verschiedenen Containern). Ich kann mir aber vorstellen, dass man ihn beispielsweise auf Kantentänzer (dancing links) erweitern kann. Damit befinden wir uns im Dunstkreis von Backtracking-Algorithmen, mithin wieder bei der Möglichkeit starker Parallelisierung.

    Naja. Ansonsten - Volkard hat schon Code gepostet, der die Idee verdeutlicht, aber ich will euch die Früchte meiner Arbeit auch nicht vorenthalten. Ich stelle mir das etwa so vor:

    #include <cstddef>
#include <new>
#include <tr1/type_traits>
#include <stdexcept>

template<typename T>
class stack_list_node {
public:
  typedef T value_type;

  stack_list_node *prev, *next;
  value_type       &data()       { return *storage(); }
  value_type const &data() const { return *storage(); }

  void init(stack_list_node *pos, value_type const &value) {
    new (storage()) value_type(value);

    prev = pos->prev;
    next = pos;
    pos->prev->next = this;
    pos->prev       = this;
  }

  void destroy(stack_list_node *&head_deleted) {
    data().~value_type();

    prev->next = next;
    next->prev = prev;
    next = head_deleted;
    head_deleted = this;
  }

private:
  value_type       *storage()       { return static_cast<T       *>(static_cast<void       *>(&storage_)); }
  value_type const *storage() const { return static_cast<T const *>(static_cast<void const *>(&storage_)); }
  typename std::tr1::aligned_storage<sizeof(T), std::tr1::alignment_of<T>::value>::type storage_;
};

template<typename T>
struct stack_list_iterator {
  typedef T                                value_type;
  typedef std::ptrdiff_t                   difference_type;
  typedef std::bidirectional_iterator_tag  iterator_category;
  typedef value_type                      *pointer;
  typedef value_type                      &reference;

  stack_list_iterator() : pos_(0) { }
  stack_list_iterator(stack_list_node<value_type> *pos) : pos_(pos) { }

  stack_list_iterator &operator++(   ) { pos_ = pos_->next; return *this; }
  stack_list_iterator  operator++(int) { stack_list_iterator copy(*this); ++*this; return copy; }

  stack_list_iterator &operator--(   ) { pos_ = pos_->prev; return *this; }
  stack_list_iterator  operator--(int) { stack_list_iterator copy(*this); --*this; return copy; }

  reference operator* () const { return  pos_->data(); }
  reference operator->() const { return &pos_->data(); }

  bool operator==(stack_list_iterator const &other) const { return pos_ == other.pos_; }
  bool operator!=(stack_list_iterator const &other) const { return pos_ != other.pos_; }

  stack_list_node<value_type> *pos_;
};

// const_iterator in gleicher Weise

template<typename T, std::size_t N>
class stack_list {
public:

  typedef T                               value_type;
  typedef stack_list_iterator<value_type> iterator;
  static std::size_t const preallocated_size = N;

  stack_list()
    : head_        (local_storage_),
      tail_        (local_storage_ + 1),
      next_unused_ (local_storage_ + 2),
      head_deleted_(0),
      size_        (0)
  {
    // Dummy-Elemente
    head_->prev = tail_->prev = head_;
    head_->next = tail_->next = tail_;
  }

  ~stack_list() {
    while(size_ > 0) {
      erase(begin());
    }
  }

  iterator begin() { return iterator(head_->next); }
  iterator end  () { return iterator(tail_      ); }

  iterator insert(iterator pos, value_type const &val) {
    get_node().init(pos.pos_, val);
    ++size_;
  }

  iterator erase(iterator pos) {
    pos.pos_->destroy(head_deleted_);
    --size_;
  }

private:
  // TODO: Implementieren
  stack_list(stack_list const &);
  stack_list &operator=(stack_list const &);

  typedef stack_list_node<value_type> node_type;

  node_type &get_node() {
    node_type *result;

    if(head_deleted_ != 0) {
      result = head_deleted_;
      head_deleted_ = head_deleted_->next;
    } else if(size_ < preallocated_size) {
      result = next_unused_;
      ++next_unused_;
    } else {
      // Im Zusammenhang hiermit: Sinnvolle Aufräumarbeit ist zu leisten.
      // Wann soll der Speicher wieder freigegeben werden?
      throw std::logic_error("Unimplementiert: Auf den Heap ausweichen");
    }

    return *result;
  }

  node_type    local_storage_[preallocated_size + 2];
  node_type   *head_;
  node_type   *tail_;
  node_type   *next_unused_;
  node_type   *head_deleted_;
  std::size_t  size_;
};

#include <algorithm>
#include <iostream>
#include <iterator>

int main() {
  stack_list<int, 100> ls;

  ls.insert(ls.begin(), 1);
  ls.insert(ls.begin(), 2);
  ls.insert(ls.end  (), 3);

  std::copy(ls.begin(), ls.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;

  stack_list<int, 100>::iterator iter = ls.begin();
  ++iter;
  ls.erase(iter);

  std::copy(ls.begin(), ls.end(), std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
}
    0
Anmelden zum Antworten