Verfasst: Donnerstag 19. Januar 2006, 13:04
Sehr Interessant, deine Ausführungen 
Danke... (Solle man eigentlich in's Wiki mal schreiben!)
Danke... (Solle man eigentlich in's Wiki mal schreiben!)Das deutsche Python-Forum
Seit 2002 Diskussionen rund um die Programmiersprache Python
https://www.python-forum.de/
Eindeutige ID erzeugen aus zwei Interger-Werten
Seite 2 von 2
Verfasst: Samstag 21. Januar 2006, 21:14
Wow... Danke für die toll Hilfe!... Vorallem von modelnine... Das Forum ist echt super...!
Verfasst: Dienstag 7. März 2006, 21:10
Frage!
Warum macht folgendes:
nicht das gleiche, wie dieses:
Wo ist der "Trick" beim zweiten?
Warum macht folgendes:
Code: Alles auswählen
def genIDnew(self, x, y):
var_id = ""
for a, b in itertools.izip(("%%0%sd"%max(len(str(x)),len(str(y))))%x,("%%0%sd"%max(len(str(x)),len(str(y))))%y):
var_id = var_id.join(a+b)
return int(var_id)Code: Alles auswählen
def genID(self, x, y):
return int("".join(a+b for a, b in itertools.izip(("%%0%sd"%max(len(str(x)),len(str(y))))%x,("%%0%sd"%max(len(str(x)),len(str(y))))%y)))
Verfasst: Dienstag 7. März 2006, 21:58
Oh Gott! Mir ist schlecht! Für so etwas gehörst Du standrechtlich erschossen. Geh sofort zu Perl zurück!elLobo hat geschrieben:nicht das gleiche, wie dieses:Code: Alles auswählen
def genIDnew(self, x, y): var_id = "" for a, b in itertools.izip(("%%0%sd"%max(len(str(x)),len(str(y))))%x,("%%0%sd"%max(len(str(x)),len(str(y))))%y): var_id = var_id.join(a+b) return int(var_id)
Code: Alles auswählen
def genID(self, x, y): return int("".join(a+b for a, b in itertools.izip(("%%0%sd"%max(len(str(x)),len(str(y))))%x,("%%0%sd"%max(len(str(x)),len(str(y))))%y)))
Im zweiten Fall werden alle ``a+b`` durch eine leere Zeichenkette verbunden. Im ersten Fall ist `var_id` nur im ersten Schleifendurchlauf eine leere Zeichenkette, danach ist es das erste ``a+b`` und das wird dann im nächsten Durchlauf als Verbindung fürs `join()` benutzt und so weiter. Würde ich mal so sagen. Ich habe jetzt nämlich nicht versucht zu verstehen was Du armer kranker Mensch da machen möchtest. Das ist zutiefst unpythonisch.
Verfasst: Dienstag 7. März 2006, 22:19
Tja.. warum antwortest Du dann überhaupt?BlackJack hat geschrieben:Würde ich mal so sagen. Ich habe jetzt nämlich nicht versucht zu verstehen was Du armer kranker Mensch da machen möchtest. Das ist zutiefst unpythonisch.
Verfasst: Dienstag 7. März 2006, 23:00
So bin jetzt dahinter gekommen, was in der zweiten Version genau passiert und habe so die erste Version abändern können...
Der Grund warum ich das mache, ist dass die zweite Version scheinbar bei manchen Python-Versionen Probleme macht... warum auch immer...
mfg elLobo
P.S. @modelnine Kannst Du mir nochmal die mathematische Grundlage für Deine Version nennen...?
Code: Alles auswählen
def genIDnew(self, x, y):
int_one = "%%0%sd"%max(len(str(x)),len(str(y)))%x
int_two = "%%0%sd"%max(len(str(x)),len(str(y)))%y
list_id = []
for a, b in itertools.izip(int_one,int_two):
list_id.append(a+b)
var_id = "".join(list_id)
return int(var_id)mfg elLobo
P.S. @modelnine Kannst Du mir nochmal die mathematische Grundlage für Deine Version nennen...?
Verfasst: Dienstag 7. März 2006, 23:48
Die mathematische Grundlage hinter dem ganzen ist einfach dass es eine Bijektion von einem endlichen Produkt abzählbar unendlicher Mengen in eine abzählbar unendliche Menge gibt.
Im Endeffekt machst Du ja folgendes:
joinint(i,j) -> k
Wenn man das ganze mathematisch schreibt würde man folgendes machen:
joinint: NxN -> N
(N für die Menge der natürlichen Zahlen, x für das kartesische Produkt zweier Mengen, und zwei Mengen sind nun mal eine endliche Anzahl an Mengen
).
Diese Funktion ist für Deine Anwendung nur dann sinnvoll, wenn es eine Injektion ist, in dem Fall haben wir nämlich eine Funktion die eindeutig einem Tupel (i,j) eine Zahl k zuordnet (bzw. für jedes k gibt es entweder kein, oder nur ein Tupel (i,j) was dazu passt, was eine äquivalente Formulierung ist).
Da die Mengenlehre sagt dass eine solche Funktion existieren muß (das ist ein Satz aus der Cantorschen Mengenlehre, siehe ganz am Anfang), und es sogar Bijektionen gibt, musst Du nur noch eine entsprechende Funktion finden, und das was ich da geschrieben hab ist eben eine solche bijektive Funktion.
Ich kenne das was ich da geschrieben habe als "Digit-Intermingling," aber das hier auch angesprochene Cantorsche Verfahren ist im Endeffekt nichts anderes als genau auch eine solche Bijektion (und da jede Bijektion auch eine Injektion ist, hast Du damit eben eine solche Funktion die Du brauchst gefunden).
Es gibt noch diverse andere Möglichkeiten, zum Beispiel 2**i*3**j (aufgrund der Tatsache dass eine Primfaktorzerlegung einer Zahl eindeutig ist, existiert für jedes k aus N entweder eine eindeutige Primfaktorzerlegung mit nur den Primfaktoren 2 und 3, was dann einem eindeutigen Paar (i,j) entspricht, oder aber eine Primfaktorzerlegung mit anderen Primfaktoren, was dann wiederum bedeutet dass kein Paar dieser Zahl entspricht, somit haben wir eine Injektion, was Deiner Anwendung genügt) die auch genau wie das cantorsche Verfahren einfacher mathematisch darzustellen sind, aber eben nicht so schön und sauber rückgängig zu machen, und vor allen Dingen auch nicht mit minimalem Platz auskommen, siehe auch mein Beispiel zu Binär gegen Cantor.
So, ich hoffe das ist genug zur Theorie dahinter.
Im Endeffekt machst Du ja folgendes:
joinint(i,j) -> k
Wenn man das ganze mathematisch schreibt würde man folgendes machen:
joinint: NxN -> N
(N für die Menge der natürlichen Zahlen, x für das kartesische Produkt zweier Mengen, und zwei Mengen sind nun mal eine endliche Anzahl an Mengen
). Diese Funktion ist für Deine Anwendung nur dann sinnvoll, wenn es eine Injektion ist, in dem Fall haben wir nämlich eine Funktion die eindeutig einem Tupel (i,j) eine Zahl k zuordnet (bzw. für jedes k gibt es entweder kein, oder nur ein Tupel (i,j) was dazu passt, was eine äquivalente Formulierung ist).
Da die Mengenlehre sagt dass eine solche Funktion existieren muß (das ist ein Satz aus der Cantorschen Mengenlehre, siehe ganz am Anfang), und es sogar Bijektionen gibt, musst Du nur noch eine entsprechende Funktion finden, und das was ich da geschrieben hab ist eben eine solche bijektive Funktion.
Ich kenne das was ich da geschrieben habe als "Digit-Intermingling," aber das hier auch angesprochene Cantorsche Verfahren ist im Endeffekt nichts anderes als genau auch eine solche Bijektion (und da jede Bijektion auch eine Injektion ist, hast Du damit eben eine solche Funktion die Du brauchst gefunden).
Es gibt noch diverse andere Möglichkeiten, zum Beispiel 2**i*3**j (aufgrund der Tatsache dass eine Primfaktorzerlegung einer Zahl eindeutig ist, existiert für jedes k aus N entweder eine eindeutige Primfaktorzerlegung mit nur den Primfaktoren 2 und 3, was dann einem eindeutigen Paar (i,j) entspricht, oder aber eine Primfaktorzerlegung mit anderen Primfaktoren, was dann wiederum bedeutet dass kein Paar dieser Zahl entspricht, somit haben wir eine Injektion, was Deiner Anwendung genügt) die auch genau wie das cantorsche Verfahren einfacher mathematisch darzustellen sind, aber eben nicht so schön und sauber rückgängig zu machen, und vor allen Dingen auch nicht mit minimalem Platz auskommen, siehe auch mein Beispiel zu Binär gegen Cantor.
So, ich hoffe das ist genug zur Theorie dahinter.
Verfasst: Dienstag 7. März 2006, 23:50
PS: BlackJack, das "Horrorbeispiel" mit itertools.izip stammte von mir. Also nicht elLobo schelten, sondern mich...
Also nicht elLobo schelten, sondern mich... Verfasst: Mittwoch 8. März 2006, 00:04
Hmm... Okay, brauchst Du noch einen Beweis dass meine Funktion eine Bijektion auf:
joinint: NxN -> N
ist? Ich hab nämlich gerade gelesen dass Du gefragt hast was die mathematische Theorie hinter _meiner_ Funktion ist, wenn Du das wirklich wissen willst, dann sag das kurz, dann bau ich einen Beweis zusammen. Den muss ich dann aber TeXen...
joinint: NxN -> N
ist? Ich hab nämlich gerade gelesen dass Du gefragt hast was die mathematische Theorie hinter _meiner_ Funktion ist, wenn Du das wirklich wissen willst, dann sag das kurz, dann bau ich einen Beweis zusammen. Den muss ich dann aber TeXen...
Verfasst: Mittwoch 8. März 2006, 01:09
Nein... Deine Antwort vorher reicht mir voll und ganz...! Danke vielmals!modelnine hat geschrieben:Hmm... Okay, brauchst Du noch einen Beweis dass meine Funktion eine Bijektion auf:
joinint: NxN -> N
ist? Ich hab nämlich gerade gelesen dass Du gefragt hast was die mathematische Theorie hinter _meiner_ Funktion ist, wenn Du das wirklich wissen willst, dann sag das kurz, dann bau ich einen Beweis zusammen. Den muss ich dann aber TeXen...
mfg elLobo
Verfasst: Mittwoch 8. März 2006, 08:53
Achso, als letztes noch, um die Richtung der Beweise in der Cantorschen Mengenlehre klarzumachen (die ich ein wenig durcheinandergewürfelt habe, zwecks Einfachheit):
Es gibt eine Bijektion, die angegeben ist, um aus einem Kartesischen Produkt zweier Mengen von natürlichen Zahlen eine Menge von natürlichen Zahlen zu machen. Hieraus kann ich folgern, dass die Mächtigkeit des Produkts der Mengen gleich der Menge selbst ist, beide sind also abzählbar unendlich (das ist die Definition von Mächtigkeit; damit zwei Mengen gleich-mächtig sind muß es eine Bijektion zwischen ihnen geben, und die Menge der natürlichen Zahlen nennt man abzählbar unendlich).
Wenn das Produkt zweier abzählbar unendlicher Mengen abzählbar unendlich ist, ist es auch das Produkt einer endlichen Anzahl von abzählbar unendlichen Mengen, was sich durch einfache Rekursion zeigen lässt. Da es sich um eine endliche Anzahl von Mengen handelt und bei jedem Rekursionsschritt joinint(i,joinint(j,joinint(k,...))) eine Menge verschwindet, bricht auch die Rekursion auf jeden Fall ab.
Das letztere ist der eigentliche Satz der Mengenlehre, der eben sagt dass zum Beispiel die Mächtigkeit der Menge aller rationalen Zahlen auch nicht mächtiger ist als die Menge aller natürlichen Zahlen. Denn schließlich ist eine rationale Zahl im Endeffekt nichts anderes als ein Tupel von drei natürlichen Zahlen: ({0;-1},Zähler,Nenner), was wiederum bedeutet, dass die Mächtigkeit der rationalen Zahlen auch abzählbar unendlich ist. Die ganzen Zahlen lassen sich genauso auf die natürlichen reduzieren, und sich genausowenig mächtiger.
Nun suchst Du suchst eine Injektion für (i,k) -> k, und kannst dann halt eben sagen dass eine Bijektion die für den Beweis des obigen Satzes benutzt wird genau das ist was Du willst.
So, genug.
Es gibt eine Bijektion, die angegeben ist, um aus einem Kartesischen Produkt zweier Mengen von natürlichen Zahlen eine Menge von natürlichen Zahlen zu machen. Hieraus kann ich folgern, dass die Mächtigkeit des Produkts der Mengen gleich der Menge selbst ist, beide sind also abzählbar unendlich (das ist die Definition von Mächtigkeit; damit zwei Mengen gleich-mächtig sind muß es eine Bijektion zwischen ihnen geben, und die Menge der natürlichen Zahlen nennt man abzählbar unendlich).
Wenn das Produkt zweier abzählbar unendlicher Mengen abzählbar unendlich ist, ist es auch das Produkt einer endlichen Anzahl von abzählbar unendlichen Mengen, was sich durch einfache Rekursion zeigen lässt. Da es sich um eine endliche Anzahl von Mengen handelt und bei jedem Rekursionsschritt joinint(i,joinint(j,joinint(k,...))) eine Menge verschwindet, bricht auch die Rekursion auf jeden Fall ab.
Das letztere ist der eigentliche Satz der Mengenlehre, der eben sagt dass zum Beispiel die Mächtigkeit der Menge aller rationalen Zahlen auch nicht mächtiger ist als die Menge aller natürlichen Zahlen. Denn schließlich ist eine rationale Zahl im Endeffekt nichts anderes als ein Tupel von drei natürlichen Zahlen: ({0;-1},Zähler,Nenner), was wiederum bedeutet, dass die Mächtigkeit der rationalen Zahlen auch abzählbar unendlich ist. Die ganzen Zahlen lassen sich genauso auf die natürlichen reduzieren, und sich genausowenig mächtiger.
Nun suchst Du suchst eine Injektion für (i,k) -> k, und kannst dann halt eben sagen dass eine Bijektion die für den Beweis des obigen Satzes benutzt wird genau das ist was Du willst.
So, genug.