Danke... (Solle man eigentlich in's Wiki mal schreiben!)Eindeutige ID erzeugen aus zwei Interger-Werten
-
Gast
Wow... Danke für die toll Hilfe!... Vorallem von modelnine... Das Forum ist echt super...!
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)))
-
BlackJack
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.
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...?
-
modelnine
- User
- Beiträge: 670
- Registriert: Sonntag 15. Januar 2006, 18:42
- Wohnort: Celle
- Kontaktdaten:
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.
Zuletzt geändert von modelnine am Dienstag 7. März 2006, 23:58, insgesamt 1-mal geändert.
--- Heiko.
-
modelnine
- User
- Beiträge: 670
- Registriert: Sonntag 15. Januar 2006, 18:42
- Wohnort: Celle
- Kontaktdaten:
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...
--- Heiko.
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
-
modelnine
- User
- Beiträge: 670
- Registriert: Sonntag 15. Januar 2006, 18:42
- Wohnort: Celle
- Kontaktdaten:
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.
--- Heiko.