Es ging hier aber explizit darum aus zwei Ints einen Integer zu erzeugen. Und das geht wie gesagt. Ohne dass ich daraus eine Zeichenkette machen muss indem ich fremde Zeichen einfüge.
Glaubs mir einfach, MD5 ist "the wrong tool for the job." Es geht einfach darum dass jemand zwei Zahlen bekommt, und daraus eine machen will. Das kann er mit den vorgestellten Algorithmen, weil die Mengenlehre das so vorsieht (naja, eher weil das eine inhärente Eigenschaft von abzählbar unendlichen Mengen ist). Dass es auch anders geht: keine Frage. Aber das ist dann trotzdem (IMHO) nicht "das richtige."
--- Heiko.
Eindeutige ID erzeugen aus zwei Interger-Werten
-
- User
- Beiträge: 670
- Registriert: Sonntag 15. Januar 2006, 18:42
- Wohnort: Celle
- Kontaktdaten:
Das ist zum Beispiel gut wenn ich eine Kunden-ID und eine Orts-ID habe (wie in der Fibu) und dann eine "Aggregate"-ID erzeugen will die sowohl den Kunden als auch den Ort enthält, und diesen eindeutig identifiziert, und zwar bewiesenermaßen eindeutig identifiziert, was mir MD5 eben nicht garantieren kann.
Warum ich wie gesagt nicht das Cantorsche Verfahren vorgeschlagen habe ist schlicht und ergreifend dass es einfach ist aus den beiden einen aggregate zu erzeugen, aber nicht einfach ist aus den beiden wieder einzelne Zahlen zu machen. Indem ich die Stellen aber wechselnd in die Ausgabe schreibe, genau das was joinint macht, und auch vorher meine Funktion, nur dass die auf binärstellen operierte (aneinanderhängen geht eben nicht), kann ich aber einfach die ursprünglichen IDs schnell und schmerzlos zurückholen:
Ich brauch dafür nicht mal eine separat berechnete, nicht trivial zu berechnende, j()-Funktion wie bei dem Cantorschen Verfahren, sondern kann wieder einfach die dezimalstellen spalten.
Das dieses Verfahren einfachst auf eine größere Menge an Integers erweiterbar ist (nicht wie das Cantorsche Verfahren, was resursiv definiert ist) und eben auch rückgängig zu machen ist, ist eben nur noch ein schöner Nebeneffekt.
Zusätzlich ist es aber auch noch interessant, dass nämlich das Binärverfahren was ich mit dieser umständlichen Routine angedeutet hatte, bewiesenermaßen die geringste Anzahl an binär Stellen für das aggregate braucht, nämlich maximal 2*(max(log2(x),log2(y))+1). Das ist beim Dezimalverfahren nicht mehr so, beim Cantorschen Verfahren auch nicht. Die Idee dahinter ist dass wenn wir zum Beispiel zwei 12-bittige Zahlen haben um Kunde und Ort darzustellen, dass wir dann sicher sein können dass das aggregieren uns einen Wert liefert der in 24-bit, also auf jeden Fall in einen Integer, passt. Für Python egal, für Datenbanken nicht.
--- Heiko.
Warum ich wie gesagt nicht das Cantorsche Verfahren vorgeschlagen habe ist schlicht und ergreifend dass es einfach ist aus den beiden einen aggregate zu erzeugen, aber nicht einfach ist aus den beiden wieder einzelne Zahlen zu machen. Indem ich die Stellen aber wechselnd in die Ausgabe schreibe, genau das was joinint macht, und auch vorher meine Funktion, nur dass die auf binärstellen operierte (aneinanderhängen geht eben nicht), kann ich aber einfach die ursprünglichen IDs schnell und schmerzlos zurückholen:
Code: Alles auswählen
n = ("%%0%sd"%(((len(str(n))+1)/2)*2))%n
x, y= int(n[::2]), int(n[1::2])
Das dieses Verfahren einfachst auf eine größere Menge an Integers erweiterbar ist (nicht wie das Cantorsche Verfahren, was resursiv definiert ist) und eben auch rückgängig zu machen ist, ist eben nur noch ein schöner Nebeneffekt.
Zusätzlich ist es aber auch noch interessant, dass nämlich das Binärverfahren was ich mit dieser umständlichen Routine angedeutet hatte, bewiesenermaßen die geringste Anzahl an binär Stellen für das aggregate braucht, nämlich maximal 2*(max(log2(x),log2(y))+1). Das ist beim Dezimalverfahren nicht mehr so, beim Cantorschen Verfahren auch nicht. Die Idee dahinter ist dass wenn wir zum Beispiel zwei 12-bittige Zahlen haben um Kunde und Ort darzustellen, dass wir dann sicher sein können dass das aggregieren uns einen Wert liefert der in 24-bit, also auf jeden Fall in einen Integer, passt. Für Python egal, für Datenbanken nicht.
--- Heiko.
Zuletzt geändert von modelnine am Donnerstag 19. Januar 2006, 12:55, insgesamt 2-mal geändert.
-
- User
- Beiträge: 670
- Registriert: Sonntag 15. Januar 2006, 18:42
- Wohnort: Celle
- Kontaktdaten:
Kurz noch zum Vergleich zwischen Cantorschem Verfahren und Bit-intermingling:
Cantor 2x2-bit passen nicht in 4-bit
Bitintermingling 2x2-bit passen auf jeden Fall in 4-bit
--- Heiko.
Cantor 2x2-bit passen nicht in 4-bit
Code: Alles auswählen
y x0 1 2 3
0 0 2 5 9
1 1 4 8 13
2 3 7 12 18
3 6 11 17 24
Code: Alles auswählen
y x0 1 2 3
0 0 1 4 5
1 2 3 6 7
2 8 9 12 13
3 10 11 14 15
Zuletzt geändert von modelnine am Donnerstag 19. Januar 2006, 13:06, insgesamt 1-mal geändert.
-
- User
- Beiträge: 670
- Registriert: Sonntag 15. Januar 2006, 18:42
- Wohnort: Celle
- Kontaktdaten:
Bit-Intermingling ist natürlich auch dann interessant wenn wir eben nicht garantieren können dass zwei Integer eine gewisse Länge maximal haben. Im Obigen Fall wäre nämlich, wenn wir zwei maximal 12-bittige Zahlen x, y, haben, es sinnvoller folgendes Aggregate zu bilden (weil schneller):
Das geht aber wie gesagt nur wenn wir die feste Breite garantieren können; sonst überschreibt ein Teil von y x, und wir verlieren in der Ausgabe wieder Informationen, was wir bei den anderen vorgestellten Verfahren nicht tun.
--- Heiko.
Code: Alles auswählen
x<<12+y
--- Heiko.
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)))
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...?
-
- 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.
-
- 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
-
- 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.