Eindeutige ID erzeugen aus zwei Interger-Werten

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Donnerstag 19. Januar 2006, 12:17

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.
Zuletzt geändert von modelnine am Donnerstag 19. Januar 2006, 12:31, insgesamt 1-mal geändert.
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Donnerstag 19. Januar 2006, 12:30

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?!?

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Donnerstag 19. Januar 2006, 12:42

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.
Zuletzt geändert von modelnine am Donnerstag 19. Januar 2006, 12:55, insgesamt 2-mal geändert.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Donnerstag 19. Januar 2006, 12:54

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.
Zuletzt geändert von modelnine am Donnerstag 19. Januar 2006, 13:06, insgesamt 1-mal geändert.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Donnerstag 19. Januar 2006, 13:02

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.
Benutzeravatar
jens
Moderator
Beiträge: 8461
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Donnerstag 19. Januar 2006, 13:04

Sehr Interessant, deine Ausführungen ;) Danke... (Solle man eigentlich in's Wiki mal schreiben!)

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
Gast

Samstag 21. Januar 2006, 21:14

Wow... Danke für die toll Hilfe!... Vorallem von modelnine... Das Forum ist echt super...!
elLobo
User
Beiträge: 4
Registriert: Dienstag 7. März 2006, 20:56

Dienstag 7. März 2006, 21:10

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?
BlackJack

Dienstag 7. März 2006, 21:58

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.
elLobo
User
Beiträge: 4
Registriert: Dienstag 7. März 2006, 20:56

Dienstag 7. März 2006, 22:19

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? :?
elLobo
User
Beiträge: 4
Registriert: Dienstag 7. März 2006, 20:56

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

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...?
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

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. ;-)
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:

Dienstag 7. März 2006, 23:50

PS: BlackJack, das "Horrorbeispiel" mit itertools.izip stammte von mir. ;-) Also nicht elLobo schelten, sondern mich... :-)
--- Heiko.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

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... ;-)
--- Heiko.
elLobo
User
Beiträge: 4
Registriert: Dienstag 7. März 2006, 20:56

Mittwoch 8. März 2006, 01:09

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
Antworten