Seite 1 von 2

Verfasst: Donnerstag 19. Januar 2006, 12:17
von modelnine
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.

Verfasst: Donnerstag 19. Januar 2006, 12:30
von jens
Stimmt, ich hab ganz übersehen, das daraus am Ende wieder eine Zahl werden soll...

Dennoch würde mich mal interessieren wozu das alles gut ist?!?

Verfasst: Donnerstag 19. Januar 2006, 12:42
von modelnine
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:

Code: Alles auswählen

n = ("%%0%sd"%(((len(str(n))+1)/2)*2))%n
x, y= int(n[::2]), int(n[1::2])
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.

Verfasst: Donnerstag 19. Januar 2006, 12:54
von modelnine
Kurz noch zum Vergleich zwischen Cantorschem Verfahren und Bit-intermingling:

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
Bitintermingling 2x2-bit passen auf jeden Fall in 4-bit

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
--- Heiko.

Verfasst: Donnerstag 19. Januar 2006, 13:02
von modelnine
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):

Code: Alles auswählen

x<<12+y
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.

Verfasst: Donnerstag 19. Januar 2006, 13:04
von jens
Sehr Interessant, deine Ausführungen ;) Danke... (Solle man eigentlich in's Wiki mal schreiben!)

Verfasst: Samstag 21. Januar 2006, 21:14
von Gast
Wow... Danke für die toll Hilfe!... Vorallem von modelnine... Das Forum ist echt super...!

Verfasst: Dienstag 7. März 2006, 21:10
von elLobo
Frage!

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)
nicht das gleiche, wie dieses:

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)))
Wo ist der "Trick" beim zweiten?

Verfasst: Dienstag 7. März 2006, 21:58
von BlackJack
elLobo hat geschrieben:

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)
nicht das gleiche, wie dieses:

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! ;-)

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
von elLobo
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.
Tja.. warum antwortest Du dann überhaupt? :?

Verfasst: Dienstag 7. März 2006, 23:00
von elLobo
So bin jetzt dahinter gekommen, was in der zweiten Version genau passiert und habe so die erste Version abändern können...

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)
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...?

Verfasst: Dienstag 7. März 2006, 23:48
von modelnine
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. ;-)

Verfasst: Dienstag 7. März 2006, 23:50
von modelnine
PS: BlackJack, das "Horrorbeispiel" mit itertools.izip stammte von mir. ;-) Also nicht elLobo schelten, sondern mich... :-)

Verfasst: Mittwoch 8. März 2006, 00:04
von modelnine
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... ;-)

Verfasst: Mittwoch 8. März 2006, 01:09
von elLobo
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... ;-)
Nein... Deine Antwort vorher reicht mir voll und ganz...! Danke vielmals!

mfg elLobo

Verfasst: Mittwoch 8. März 2006, 08:53
von modelnine
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. :-)