Array defenieren

[snafu]

Wenn ich's richtig verstanden habe, implementiert numpy.ndarray das gewünschte Verhalten.

Eine Erklärung zu den Hintergründen findet sich hier.

[Pekh]

Okay, jetzt ist mir auch klar, was mit dem Durchlaufen der Elemente gemeint war.

Aber meines Wissens hat man über all das in Python keine Kontrolle, da Python eben nur die Liste anbietet. Von daher dürfte es, wie schon gesagt wurde, relativ sinnfrei sein, eine Liste mit vorbestimmter Länge zu initialisieren.

Das stimmt im Großen und Ganzen. Ich weiß ehrlich gesagt nicth einmal, welche Implementierung CPython für die Liste tatsächlich verwendet. So lange man nicht tatsächlich an Grenzen stößt, ist es eigentlich auch egal. Es gibt aber Module, die auch in Python Arrays zur Verfügung stellen. Nur braucht man diese halt eher selten.

Edit: Ich habe doch tatsächlich einen Anwendungsfall gefunden. Beim TDD testet man ja, ob ein Test fehlschlägt, bevor man sich an eine Implementierung macht. Ist der (erwartete) Rückgabewert aber eine Sequenz fester Länge (z.B. 12 (Monate) ), dann fliegt einem der Test mit einem KeyError um die Ohren, wenn man einfach nur den Funktionskopf implementiert hat. Manchmal ist es schöner, wenn er feststellt, daß an der richtigen Stelle das falsche (oder kein) Objekt steht. Dann könnte man in der zu testenden Funktion einen "künstlichen" Rückgabewert mit 12 Elementen erzeugen.

[snafu]

Man kann aber auch einfach testen, ob die Länge des Rückgabewerts 12 ist.

[Pekh]

Wenn ich davon ausgehe, daß die Länge des Rückgabewerts *immer* 12 ist (das klappt ja meistens), und ich nur gucken will, ob ein bestimmtes Objekt an einer bestimmten Stelle eingetragen ist, ist ein Test auf Länge 12 ziemlich sinnfrei.

[Defnull]

Bei einer Liste mit Zeigern enthält jedes Element einen Zeiger auf seinen Nachfolger und evtl. auch auf seinen Vorgänger. Die Elemente können so faktisch bunt über den Speicher gestreut sein. Das Hinzufügen und Löschen ist hier in konstanter Zeit möglich, da ich "nur" ein paar Zeiger umbiegen muß. Will ich aber auf das i-te Element zugreifen, muß ich mich vom ersten Element durchhangeln und bei jedem Element nachfragen, wo denn nun sein Nachfolger steckt. Solche Strukturen verwendet man, wenn sich oft Änderungen ergeben, oder wenn man eigentlich nur sequentiell darauf zugreifen will. Arrays (oder mit Arrays implementierte Listen) bieten schnelleren Zugriff, sind aber eher für statische Datenmengen geeignet.

Die von dir beschriebene Struktur macht eher wenig Sinn. Inserts und deletes müssen bei dir nämlich erst einmal die richtige Stelle finden, um die Pointer zu aktualisieren. Damit sind alle selects, inserts und deletes auf so einer Liste O(n), solange sie nicht am Anfang der Liste statt finden.

CPython macht das zum Glück nicht so. Wie gesagt, Listen sind im Grunde Pointer-Arrays mit eingebauter Speicherverwaltung. Wird die Liste zu groß, wird sie dynamisch auch im Speicher verlängert. Ist das nicht möglich, wird ein neuer Speicherbereich reserviert und die Pointer dort hin kopiert. Wird sie signifikant kleiner als ihr reservierter Speicher, wird der hintere Speicherbereich auch wieder frei gegeben. CPython kümmert sich um eine sinnvolle Vorgehensweise.

Daraus ergibt sich folgende Laufzeit:
SELECT kosten immer O(1), da die Adresse des Pointers mit index*sizeof(pointer)+start_adresse berechnet werden kann und ein Pointer-Lookup bei der Laufzeit nicht ins Gewicht fällt (da ebenfalls O(1)).
DELETE kostet O(n), da alle folgenden Pointer verschoben werden müssen. Ein TAIL_DELETE ist aber mit O(1) vergleichsweise schnell.
INSERT verhält sich analog zu DELETE. Die Kosten für die Speicherverwaltung bei überlaufenden Listen sind zu vernachlässigen, da sie nur gelegentlich auf treten und eh nicht vorhersagbar sind.

Warum hat NumPy nun eigene Klassen für Arrays? Weil ein Array (im unterschied zu Pythons Listen) keine Objekt-Pointer, sondern C-native Primitive (Integer, Float) enthält und man sich somit den Pointer Lookup sparen kann.

Macht es Sinn, eine Liste mit einer gewissen Zahl an Elementen zu initiieren? Jain. Wenn man 100%ig sicher, das man gleich x Elemente der Reihe nach in die Liste einpflegen möchte, könnte ein "l=x*[None]" bei stark fragmentieren Speicher ein paar allocs sparen. Vorausgesetzt, CPython optimiert das x*[None] anständig.

[Leonidas]

In C gibt es ja keine komfortable Implementierung von dynamischen Datenstrukturen im ANSI Sprachumfang (oder irre ich hier?). Daher ist es dort bei angenommener bekannter maximaler Größe oft einfacher, ein statisches Array anzulegen.

Nein, gibt es nicht, da müsste man auf GLib ausweichen, ich denke auch das APR da einige brauchbare Datenstrukturen mitbringt. Das ist auch der Punkt, ab dem C wirklich unangenehm wird: Datenstrukturen variabler Größe.

[snafu]

In C gibt es ja keine komfortable Implementierung von dynamischen Datenstrukturen im ANSI Sprachumfang (oder irre ich hier?).

Naja, man könnte `realloc()` verwenden, oder nicht? Ob das jetzt das Optimum an Komfort ist, sei mal dahingestellt.

@Defnull: Was ist ein `TAIL_DELETE`?

[BlackJack]

@snafu: Wenn ich raten müsste, ist mit TAIL_DELETE ein DELETE im hinteren Bereich gemeint. Da ist es halt nicht so teuer, weil nicht viele Elemente umgesetzt werden müssen.

[Leonidas]

In C gibt es ja keine komfortable Implementierung von dynamischen Datenstrukturen im ANSI Sprachumfang (oder irre ich hier?).

Naja, man könnte `realloc()` verwenden, oder nicht? Ob das jetzt das Optimum an Komfort ist, sei mal dahingestellt.

Naja, wenn du eine Datenstruktur erweiterst indem du hinten mittels ``realloc()`` immer ein Element einfügst hast du eine Menge Kopiervorgänge. ``realloc()`` ist nämlich nur dann O(1), wenn hinter dem allokierten Speicherbereich noch Platz ist, sonst ist es eher ``O(n)``.

[snafu]

Ich meinte jetzt schon, dass man - wie im fiktiven Beispiel - eine bestimmte Größe anfordert und dann bei Bedarf ein `realloc()` ausführt. Im Grunde halte ich das aber auch für nebensächlich. Ich kenne mich mit C nicht gut genug aus, um jetzt Aussagen über das optimale Vorgehen treffen zu können. Hauptsächlich wollte ich sagen, dass dynamisch wachsende (Pointer-)Arrays auch mit wenigen Zeilen implementierbar sein dürften, ohne dass man die GLib installieren muss. Haarig wird's dann aber wohl beim Entfernen von Elementen.

[Leonidas]

Oder beim testen auf korrektheit. Und eigentlich mag man dann nicht in jedem Projekt das Rad neu erfinden, daher ist die Verwendung von GLib schon eher DRY. Zudem man sowieso gleich noch eine Menge weiterer Goodies mit dazubekommt.

[snafu]

Naja, wenn man denn sowas regelmäßig braucht. Es bedeutet ja immerhin eine weitere Abhängigkeit. Ich denke da vor allem an Windows-Benutzer.

[Leonidas]

Die sinds gewöhnt, tonnenweise DLLs zu haben.

[Hyperion]

Wenn man natürlich die Glib "mitschleppt", dann könnte man natürlich auch statt C zu Vala greifen - und hat es gleich wesentlich komfortabler

[mit]

Vielen Dank für die Zahlreichen antworten.

Ich habe folgenden Perl Code der ein dynamisches 2 D Array verwendet

Code: Alles auswählen

#!/usr/bin/perl
use strict;

my @s;  
my @c;  
        
my %bonds = (GU=>1,UG=>1,AU=>2,UA=>2,CG=>3,GC=>3);
    

sub max {
    my ($x,$y) = @_;
    if ($x>$y) { return $x; } else { return $y};
}

sub foldRna {
    my ($s) = @_; 
    my $slen = length $s;
    @s = ('X', split(//, $s));
    print @s;
    for (my $len = 5; $len <= $slen; $len++) {
	for (my $i=1; $i<=$slen-$len+1; $i++) {
	    my $j = $i+$len-1;
	    $c[$i][$j] = max($c[$i+1][$j],
			     $bonds{$s[$i].$s[$j]}+$c[$i+1][$j-1]);
	    
	    for (my $k=$i+1; $k<$j; $k++) {
		$c[$i][$j] = max($c[$i][$j], 
                                 $c[$i][$k]+$c[$k+1][$j]);
	    }
	}
    }
}

sub traceBack {
    my ($i,$j) = @_;  
    my $cij = $c[$i][$j];

    return ("."  x ($j-$i+1)) if ($cij==0);
    return "." . traceBack($i+1,$j) 
        if ($cij == $c[$i+1][$j]);
    return "(" . traceBack($i+1,$j-1) . ")" 
	if ($cij == $bonds{$s[$i].$s[$j]}+ $c[$i+1][$j-1]);
    for (my $k = $i+1; $k < $j; $k++) {
	return traceBack($i,$k) . traceBack($k+1,$j)
	    if ($cij == ($c[$i][$k]+$c[$k+1][$j]));
    }
}

Ich habe alles in den Python umgeschrieben (siehe unten), aber ich weiss nicht wie man am besten (effizientesten) das 2 D Array erzeugt.

Code: Alles auswählen

def max(x, y):
  if x >y: 
    return x 
  else: 
    return y

def foldRNA(s, bonds):

  sLen = len(s)
  s = 'X' + s
  print s

  for Len in range(5, sLen+1):
    for i in range(1, (sLen - Len + 1)+1):
      j = i + Len - 1
      c[i][j] = max(c[i+1][j],
                    bonds[s[i] + s[j]] + c[i+1][j-1])
      for k in range(i+1, j):
        c[i][j] = max(c[i][j],
                      c[i][k]+c[k+1][j])

def traceBack(i,j, bonds):
  cij = c[i][j]

  if cij == 0:
    return '.' * (j-i+1)
  if cij == c[i+1][j]:
    return '.' * traceBack(i+1,j, bonds)
  if (cij == bonds[s[i].s[j]]+ c[i+1][j-1]):
    return "(" + traceBack(i+1,j-1, bonds) + ")"

  for k in range(i+1, j):
    if (cij == (c[i][k]+c[k+1][j])):
      return traceBack(i,k, bonds) + traceBack(k+1,j, bonds)
    

if __name__ == "__main__":
  bonds = {'GU': 1, 'UG': 1, 'AU': 2,
           'UA': 2, 'CG': 3, 'GC': 3,}
  basestring = "CUCUCGGUAGCCAAGUUGGUUUUAAGGCGCAAGACUGAAUUUACCACUACGAAACUUGAGAUCGGGCGUUCGACUCGCCCCCGGGAGACCA";

  foldRNA(basestring, bonds)
  print "basestring\n", traceBack(1, len(basestring), bonds)

Der Perl Code liefert als Ergebnis:

Code: Alles auswählen

.((((((...))(((((((((((..(...))))))(((...)..)))(...))))))))))(((((.(..((...)).)))))((...)))

Wie erzeugt man am Besten ein 2 D Array für den Python code und ohne globale Variable?

[BlackJack]

@mit: Ich würde hier ein Dictionary, das ein Tupel von zwei Zahlen auf einen Wert abbildet, verwenden. Falls auf Indexpaare zugegriffen wird, die vorher nicht gesetzt wurden, bietet sich ein `collections.defaultdict()` an.

Die Funktion `max()` brauchst Du bei Python übrigens nicht neu erfinden, die gibt es schon.

[mit]

Wie würde dies in der Praxis aussehen?

[snafu]

Wenn man natürlich die Glib "mitschleppt", dann könnte man natürlich auch statt C zu Vala greifen - und hat es gleich wesentlich komfortabler

Du kannst aber nicht zufällig dies* beantworten, oder?

EDIT: *erledigt

[BlackJack]

@mit: Was genau hast Du denn bei der Dokumentation zum `defaultdict` und mit ein bisschen herumprobieren in der Python-Shell nicht verstanden?

Code: Alles auswählen

In [4]: c = collections.defaultdict(int)

In [5]: c[42, 23] = 4711

In [6]: c[42, 23]
Out[6]: 4711

In [7]: c[0, 0]
Out[7]: 0

[mit]

Ops, Ich meine eigentlich an welcher Stelle man

Code: Alles auswählen

c = collections.defaultdict(int) 

platzieren sollte.