verschiedene Anfängerfragen

[JimPanse]

Hallo

Ich habe heute neu mit Python angefangen, weil ich nach einer Sprache gesucht habe, mit der man unter Linux mit möglichst wenig Aufwand viel machen kann, und das bieten mir C(++) und Pascal nicht wirklich.

Jetzt hab ich gerade zum test ein kleines Programm geschrieben, welches den Algorithmus von Bellman und Ford darstellen soll.
Mein erstes Problem war, wie ich vernünftig ein Dictionary in einem Dictionary machen kann. Also wenn man das schon vorher definiert ist das ja einfach. Da macht man einfach so z.B.:
dict = {'a': {'b': 3}}

Aber wenn das dict am Anfang leer ist, und man die entsprechenden Elemente erst dynamisch einfügt, dann wird das schon schwieriger. Ich hab das so gelöst:

Code: Alles auswählen

Verbindungen = {}
##Verbindungen auf unendlich setzen:
for x in Knoten:
        for y in Knoten:
                if x in Verbindungen:
                        Verbindungen[x][y] = unendlich
                else:
                        Verbindungen[x] = {y: unendlich}

Aber wir man sieht ist das ein ziemlich umständlicher Weg. Ich kann mir vorstellen das das auch irgendwie einfacher geht.


Meine zweite Frage: Gibt es sowas wie Konstanten in Python? Also wenn man ne Konstante Liste haben will, benutzt man ja einfach ein Tupel, aber wie ist das mit anderen Datentypen?


Mehr Fragen fallen mir jetzt gerade nichtmehr ein

Edit (Leonidas): Code in Python-Tags gesetzt.

[henning]

Aber wenn das dict am Anfang leer ist, und man die entsprechenden Elemente erst dynamisch einfügt, dann wird das schon schwieriger. Ich hab das so gelöst:

Code: Alles auswählen

Verbindungen = {}
##Verbindungen auf unendlich setzen:
for x in Knoten:
        for y in Knoten:
                if x in Verbindungen:
                        Verbindungen[x][y] = unendlich
                else:
                        Verbindungen[x] = {y: unendlich}

Also mal langsam mit den jungen Pferden bitte!
Kennt sicher nicht jeder diese beiden Herren und ihren Algorithmus (ich zähle mich selbst dazu).

Also du hast das dict "Verbindungen".
Wenn ich deinen Code richtig verstanden habe, sollen in diesem dict jedem Knoten ein weiteres dict zugeordnet sein, dass allen anderen Knoten "unendlich" zuordnet.

Also sowas:

Code: Alles auswählen

verbindungen = {
 Knoten1 : { Knoten1: unendlich, Knoten2: undendlich, Knoten3: unendlich },
 Knoten2 : ...
 ...
}

Da das aber bei allen der selbe Wert ist, würde ich bald dazu übergehen, den Wert unendlich beim Auslesen als default zu nehmen also:

Code: Alles auswählen

verb_von_1_zu_2 = verbindungen.get(Knoten1, {}).get(Knoten2, unendlich)

Das 2. Argument von get() gibt dabei den Wert an, den get zurückgeben soll, wenn der Schlüssel in dem dict nicht gefunden wurde.

Meine zweite Frage: Gibt es sowas wie Konstanten in Python? Also wenn man ne Konstante Liste haben will, benutzt man ja einfach ein Tupel, aber wie ist das mit anderen Datentypen?

Nein die gibt es nicht, ich muss aber sagen, dass ich sie nicht vermisse.
Wenn du Daten hast, die in keinem Fall geschrieben werden dürfen, weil du deinen "mit-programmieren" nicht traust, kannst du eine Exception beim schreiben auslösen. Dazu gibts ein schönes Rezept:
http://aspn.activestate.com/ASPN/Cookbo ... ipe/414140

[henning]

oh, ich seh gerade, das Receipe zeigt nur eine Möglichkeit, den Typ konstant zu halten, hier ist was für "echte" Konstanten (aber wie schon angedeutet, sowas wie eien Konstante habe ich noch nie gebraucht in Python):
http://www.bigbold.com/snippets/posts/show/737

Ausserdem dürfte für dich eventuell interessant sein, dass man auch tuple's als dict-keys verwenden kann (weil sie immutabel sind):

Code: Alles auswählen

verbindungen = { (2, 4) : 5.0, (1, 3) : -2.3 }

verbindungen[(1, 7)] = 2.8
print verbindungen.get( (5, 6), unendlich )

wird wahrscheinlich schöner zu lesen und zu schreiben sein, sofern es sich um was graphentheoretisches handelt...

[JimPanse]

Erstmal danke für die Hilfe.

Kennt sicher nicht jeder diese beiden Herren und ihren Algorithmus (ich zähle mich selbst dazu).

Der dient dazu in einem Graphen alle kürzesten Wege von einem Startknoten zu allen anderen Knoten auszurechnen. Also sowas wie der Dijkstra Algorithmus, nur für alle Knoten auf einmal.

Da das aber bei allen der selbe Wert ist, würde ich bald dazu übergehen, den Wert unendlich beim Auslesen als default zu nehmen also:

Code: Alles auswählen

verb_von_1_zu_2 = verbindungen.get(Knoten1, {}).get(Knoten2, unendlich)

Jo sorum hät ich es auch machen können. Aber es ging mir mehr um folgendes:
Wie kann ich Python klar machen, dass es da wirklich ne Verbindung zwischen zwei geben soll?
Ich kann zwar Schreiben:
Verbindung = {}
und danach durch Verbindung[Schlüssel] = Wert ganz neue Schlüssel erfinden, aber ich kann nicht mit Verbindung[Schlüssel][Schlüssel2] direkt einen zweiten Schlüssel "erfinden", weil Python ja noch nicht weiß, dass das der Wert von dem ersten Schlüssel wieder ein dict ist.
Deswegen muss ich da erstmal schreiben Verbindung[Schlüssel] = {Schlüssel2: Wert}. Wenn ich dann wiederum dem dict, welches zum Schlüssel1 gehört, einen weiteres Paar hinzufügen will, muss ich das jetzt mit Verbindung[Schlüssel][Schlüssel2] machen. Das führt also dazu das ich eine nervige Unterscheidung machen muss, wie in meinem Codebeispiel ganz oben.


Habs jetzt aber mit den Tupeln so realisiert, weil das auch gut klappt

@Konstanten: OK wenn man die eh nicht braucht, kann ich auch drauf verzichten.

Weitere Frage:
Ich habe so etwas:
Knoten = ('a', 'b', 'c', 'd')
Dieses Tupel soll einfach nur dafür sorgen, dass ich die darin enthaltenen Buchstaben als Schlüssel für ein dict benutzen kann (Genauer gesagt stellen sie die Namen der Knoten da).
Am liebsten würd ich das aber so in der Art machen: range('a', 'd'). Das geht aber nicht mit Strings. Gibt es irgendeine Funktion, die genau sowas macht?

Noch ne Frage:
Was ist eigentlich der Unterschied zwischen einer Liste in Python, und einem Array in anderen Sprachen? Ist das nicht nahezu das selbe?

[JimPanse]

Noch eine Frage: Was lässt sich gegen so eine Melund machen?

DeprecationWarning: Non-ASCII character '\xc3' in file asp.py on line 21, but no encoding declared; see http://www.python.org/peps/pep-0263.html for details

[henning]

Zu den Paaren noch:
Die Paare sind wir gesagt, an sich recht elegant, wie ich finde, mir fällt aber grade ein, dass es Problematisch wird, wenn du z.B. alle Verbindungen haben willst, die von einem bestimmten Knoten ausgehen. (Dann musst du alle dict keys abfragen => schlechte Performance)
Falls das ein Problem ist, kann man den ganzen Verbindungs-Kram auch z.B. in eine Klasse kapseln und intern z.B. mit den dicts realisieren und den ganzen umständlichen Kram gleich in spezielle Funktionen packen, so dass das ganze wieder handhabbar wird.

Hmm... also mit dem range('a', 'd'), das ist ne gute Frage.
Ich wüsste nicht, dass es da was fertiges gibt, ist aber auch leicht zu machen:

Code: Alles auswählen

def strrange(fr, to):
  return tuple(map(chr, range(ord(fr), ord(to))))

Man beachte, dass der letzte Buchstabe wie beim "normalen" range() nicht mitgezählt wird, also:

Code: Alles auswählen

>>> strrange("a", "d")
('a', 'b', 'c')

Liste vs. Array, da hab ich irgendwo schonmal was gelesen (ich glaube in der offiziellen Python FAQ).
Also intern ist die Liste ähnlich realisiert wie ein Array, man hat aber z.B. den Vorteil, dass man sich um die Größe keine Gedanken machen muss, weil Python das erledigt und list ist ja eine ganze Klasse mit allen möglichen nützlichen Funktionen (slices, negativ-indizierung, etc...) die man um ein C-Array halt noch bauen müsste.
Also ich würd spontan mal sagen, dass das der Unterschied ist. Wie gesagt, unter der Haube ists auch nur ein Speicherbereich, er wird halt bloß intelligent verwaltet.

Zum encoding: Einfach

Code: Alles auswählen

# -*- coding: ISO-8859-1 -*-

als erste oder zweile Zeile ins Python-File schreiben (je nach deinem Encoding natürlich).

HTH

[henning]

Hab übrigens grad noch festgestellt: Wenn du tuples als index verwendest, darfst du die Klammern weglassen, also statt

Code: Alles auswählen

mein_dict[(5,7)] = 2.3

auch

Code: Alles auswählen

mein_dict[5, 7] = 2.3

, was noch ein bisschen netter aussieht ,-)

[CM]

Hi

von mir nur ein kurzes Kommentar zum Thema arrays:
Das Modul array dürfte vielleicht von Interesse sein. Zwar sind Listen in Python fast dasselbe wie arrays in manch anderer Sprache, aber eben nicht ganz. Abgesehen davon braucht man manchmal mehr als was Listen bieten. Das bietet dann womöglich scipy.
Ansonsten sind u. U. tatsächlich die FAQ interresant: http://python.org/doc/faq/general.html (dort einfach mal den Browser nach "array" suchen lassen.

Gruß,
Christian

[jens]

Ich habe so etwas:
Knoten = ('a', 'b', 'c', 'd')
Am liebsten würd ich das aber so in der Art machen: range('a', 'd').

Naja, du könntest sowas machen:

Code: Alles auswählen

Knoten =['a', 'b', 'c', 'd', 'e', 'f']
for i in Knoten[Knoten.index("c"):Knoten.index("e")+1]:
    print i,

Ausgaben:

Code: Alles auswählen

c d e

Geht aber nicht mit tuple sondern mit Listen.

[mawe]

Hi!

Hab mal kurz gegoogelt und das gefunden: http://hetland.org/python/bellman_ford.py
Vielleicht hilft Dir das.

Gruß, mawe

[JimPanse]

Danke noch mal an alle. Ihr habt mir sehr geholfen

[BlackJack]

Beim Problem mit dem "Erfinden" von leeren Dictionaries wenn das Element noch nicht existiert kann man auch die `setdefault()` Methode von Dictionaries benutzen:

Code: Alles auswählen

INFINITY = object()

def insert_edge(edges, source, destination):
    source_edge = edges.setdefault(source, dict())
    source_edge[destination] = INFINITY

graph = dict()

for source, destination in (('a', 'b'), ('a', 'c'), ('b', 'c')):
    insert_edge(graph, source, destination)

print graph

Das beantwortet auch Deine Frage noch Konstanten: wenn ein Programmierer einen Namen komplett in Grossbuchstaben sieht, dann wissen die meisten, das es sich um eine Konstante handelt. Das ist übliche Namenskonvention in vielen Programmiersprachen.

Wenn Du Tupel (oder generell "iterables") mit Schlüsseln für ein Dictionary hast, die alle mit dem selben Wert belegt werden sollen, dann ist die `fromkeys()` Methode ganz praktisch:

Code: Alles auswählen

In [14]: dict.fromkeys(('a', 'b', 'c', 'd'), 42)
Out[14]: {'a': 42, 'c': 42, 'b': 42, 'd': 42}

EDIT: Noch ein kleiner Nachtrag: Deine doppelte Schleife verbindet jeden Knoten mit jedem anderen, also ein vollständiger Graph, ist das gewollt?

Und noch der Tip Dich mit Klassen und Objekten auseinander zu setzen. Wenn man erst einmal anfängt Dictionaries und Listen tiefer als eine oder zwei Ebenen zu verschachteln wird es sehr schnell sehr unübersichtlich. Der Quelltext wird wesentlich lesbarer wenn man den Datentypen und deren Komponenten aussagekräftige Namen gibt. Wenn man eine Klasse für die Knoten und eine für den Graphen mit entsprechenden Methoden und Attributen versieht, dann könnte die Initialisierung zum Beispiel so schön aussehen:

Code: Alles auswählen

def init_single_source(graph, source):
    for node in graph:
        node.total_cost = INFINITY
        node.predecessor = None
    source.total_cost = 0

Das ist wesentlich verständlicher als namenlose Dictionaries in Dictionaries oder Listen. Für die obige Funktion dürfte `graph` sogar noch eine ganz normale Liste mit Knoten-Objekten sein. Für den Bellman-Ford wäre aber zum Beispiel eine Methode nützlich, mit der man über alle Kanten im Graph iterieren kann.