Eindeutige ID erzeugen aus zwei Interger-Werten

[elLobo]

Hi!

Ich stehe mal wieder voll auf dem Schlauch... brauche eine Funktion die mir eine eindeutige ID (Integerwert), aus zwei Integer-Werten erzeugt!? Gibt es da was einfaches?

mfg elLobo

[gerold]

brauche eine Funktion die mir eine eindeutige ID (Integerwert), aus zwei Integer-Werten erzeugt!?

Hi!

Wie macht man aus einer Dezimalstelle eine Nummer? Da fällt mir jetzt auch nichts mehr dazu ein. Vielleicht wissen die im Forum, wie so etwas geht.

mfg
Gerold

[Python 47]

Code: Alles auswählen

x=2
y=3
z=45
id(x)
9787044
id(y)
9787032
id(z)
9786528

Wie wäre es damit Gerold?

[Mad-Marty]

Hi!

Ich stehe mal wieder voll auf dem Schlauch... brauche eine Funktion die mir eine eindeutige ID (Integerwert), aus zwei Integer-Werten erzeugt!? Gibt es da was einfaches?

mfg elLobo

Ich würde behaupten das geht nicht.
Jedenfalls nicht, wenn die 2 input-integers jeweils jeder mögliche integer sein kann.

Wenn du eventuell die aktuelle time hinzunimmst, dann dürfte das klappen.

Eventuell verstehe ich auch nicht ganz die Frage ....


edit:

x = 3 y = 4
id (x+y)

funktioniert auch nicht, weil bei x =2 und y=5 wieder dieselbe id kommt

[modelnine]

Also sprich: aus zwei Integern mach einen? Du suchst also im Endeffekt eine Funktion mit zwei Argumenten die genau einen Rückgabewert hat, und am besten eine bijektive Abbildung ist, da dann jeder Funktionswert eindeutig ist für eine bestimmte Kombination (idx,idy).

<edit>

Die Funktion die ich gepostet habe war keine Bijektion.

Jetzt aber eine die es ist (war 'ne schwere Geburt... ):

Code: Alles auswählen

def f(x,y):
    x, y = bin(x), bin(y)
    rv = 0L
    for i in range(max(len(x),len(y))-1,-1,-1):
        if len(x) > i:
            rv += x[i]
        rv <<= 1
        if len(y) > i:
            rv += y[i]
        rv <<= 1
    rv >>= 1
    return rv

def bin(n):
    rv = []
    while n:
        rv.append(n&1)
        n >>= 1
    return rv

</edit>

Auf jeden Fall: Ohne dass Du ein bissel genauer darauf eingehst was Du hier machen willst habe ich absolut keine Chance da was genaueres rauszulesen.

PS: Laut Mengenlehre ist das für eine beliebige Anzahl von Integers möglich, da das Produkt einer endlichen Zahl an abzählbar undendlichen Mengen wiederum eine abzählbar unendliche Menge bildet, und deswegen eine bijektive Abbildung aus der einen in die andere existieren muß. Und die obige Funktion ist leicht erweiterbar dass sie wirklich eine beliebige Menge an Integers akzeptier.

--- Heiko.

[gerold]

Wie wäre es damit Gerold?

Hi Python Master 47!

Mit "id()" wird ja nur die Adresse eines Objektes ausgegeben. Beim nächsten Start des Programmes hat sich das schon wieder geändert. Außer um herauszufinden, ob es sich um ein und das selbe Objekt handelt, gibt es kaum einen Verwendungszweck dafür. Außerdem amüsierte mich die Fragestellung. Das klang so wie "Ich habe hier zwei Zahlen -- die brauche ich jetzt eindeutig." So etwas wie "1+2=<eindeutige Zahl>".

lg
Gerold

[modelnine]

Ich wurde gerade im IRC darauf aufmerksam gemacht dass ich mir eine tierisch schwierige Funktion ausgedacht habe um das zu machen, dass es auch noch andere gäbe. Kann ich nur sagen: Ja, das tuts. Zum Beispiel:

Code: Alles auswählen

2**x*3**y

die Primzahleigenschaften ausnutzen.

Aber die erste Transformation braucht maximal log2(x)+log2(y) bits, wobei die in diesem Post erheblich mehr braucht, und zum anderen ist sie auch so gut wie gar nicht rückgängig zu machen (außer man faktorisiert den integer)...

Bei vielen anderen Paarungsfunktionen ist es ähnlich (dass sie nicht einfach rückgängig zu machen sind).

--- Heiko.

[gerold]

Code: Alles auswählen

def f(x,y):
    x, y = bin(x), bin(y)
    rv = 0L
    for i in range(max(len(x),len(y))-1,-1,-1):
        if len(x) > i:
            rv += x[i]
        rv <<= 1
        if len(y) > i:
            rv += y[i]
        rv <<= 1
    rv >>= 1
    return rv

def bin(n):
    rv = []
    while n:
        rv.append(n&1)
        n >>= 1
    return rv

Hi Heiko!

Und ich dachte, das wäre eine Scherzfrage... Obwohl ich immer noch nicht glaube/verstehe, dass man aus zwei Zahlen eine eindeutige Zahl machen kann, wenn man den Bereich nicht eingrenzt. Dafür reicht meine Logik wohl nicht aus.

Bitte versuche es mir nicht zu erklären. Ich möchte in den nächsten Tagen noch schlafen können.

lg
Gerold

[mitsuhiko]

@gerold: http://de.wikipedia.org/wiki/Cantorsche ... gsfunktion

[Python 47]

@gerold

Ich hab wohl die Frage falsch verstanden

[gerold]

@gerold: http://de.wikipedia.org/wiki/Cantorsche ... gsfunktion

Hi blackbird!

Danke. Mit dieser Erklärung kann ich leben (und schlafen ).

lg
Gerold

[modelnine]

Soo...

Hier das ganze noch mal als unleserlicher Einzeiler. Macht im Prinzip das selbe wie meine erste Funktion, baut das nur auf der Dezimalrepräsentation auf und nicht auf der Binärrepräsentation.

Code: Alles auswählen

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

Das ganze benötigt (wie immer) itertools und sieht dann z.B. so aus:

Code: Alles auswählen

>>> joinint(100,200)
120000
>>> joinint(100,20)
100200
>>> joinint(103,204)
120034

Ich denke damit ist auch klar wie das ganze funktioniert. Es noch soweit auszubauen dass es eine beliebige Anzahl an Integers akzeptiert bleibt dem Leser überlassen.

Das ganze funktioniert wie immer nicht für negative Zahlen (haben alle meine Beispiele nicht). Das tut das Cantorsche Verfahren aber (soweit ich weiß) schon, nur ist das nicht mehr so ganz einfach zu verallgemeinern für eine beliebige Anzahl von Zahlen...

<edit>
Hab gerade nachgelesen: das Cantorsche Verfahren ist auch nur für natürliche Zahlen definiert, das macht aber eigentlich gar nix, denn zur Not kann man die ganzen Zahlen (also auch die negativen) in die natürlichen bijektiv abbilden...
</edit>

--- Heiko.

[jens]

Warum nicht einfach so:

Code: Alles auswählen

x=3
y=5
id = int("%s%s" % (x, y))

Aber woher kommen die beiden Zahlen??? Kommen doppelte vor? In dem Fall würde ich aus den beiden + time.time() eine MD5 Summe bilden

[modelnine]

Das geht eben nicht.

Denn:

Code: Alles auswählen

x, y = 11, 1
print "%s%s"%(x,y)
x, y = 1, 11
print "%s%s"%(x,y)

Gibt beide male 111 aus. Wenn Du joinint() darüber laufen lässt gibt er beim ersten mal 1011 aus, beim zweiten mal 111 (also unterschiedliche Zahlen).

Und: eine MD5-Summe bilden ist das Problem von der falschen Seite erschlagen. Die Mengenlehre sagt dass es eben eine bijektive Abbildung geben muß (sogar eine ganze Menge injektive, siehe meine Primzahlabbildung), warum die dann nicht nutzen und _bewiesenermaßen_ sicher sein dass man nie doppelte Zahlen rauskriegt? Wer garantiert Dir dass MD5 keine Kollision hat bei den digests die rauskommen?

--- Heiko.

[jens]

OK, dann eben einfach:

Code: Alles auswählen

print "%s_%s" % (x,y)

Das brint also entweder 1_11 oder 11_1

Im Eingangposting stand:

eine Funktion die mir eine eindeutige ID (Integerwert), aus zwei Integer-Werten erzeugt

Die Frage ist, wie/woher kommen überhaupt die zwei gegebenen Integer-Werten??? Sind die immer eindeutig?

Kollisionen kann man bei md5 nicht ausschließen, vom Prinzip geht das mit keinem hash-Algo. weil es dann ein super guter Komprimierer wäre

Nur, man muß auch den Aufwand zur ID Erzeugung im Verhältniss setzten... In einer Webapp, kann man zur eindeutigen Identifizierung eine ID vergeben und diese aus folgenen Sachen bilden:

• -Zeitpunkt des Login (möglichst genau)
  -IP des Client
  -UserAgent des Client

Natürlich kann man die IP und den Agent beliebig fälschen, aber irgendwo muß man ja ansetzten... Man sollte natürlich beim vergeben der ID prüfen, ob diese nicht schon vergeben ist...
Das Problem beim Session-Klau ist, einfach eine gültige ID (per Cookie) vorzuschwindeln, in der Hoffnung, das diese ID schon vergeben ist und sich damit Zugang zu verschaffen... Der normale MD5 ist 128Bit lang, oder? Das sind schon einige Kombinationen... Mit einem Brute-Force braucht man wahrscheinlich schon recht lang, um eine vergebene ID zu erhalten...

In PyLucid wird bei jedem Request nachgeprüft, ob die IP immer noch die selbe ist...

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

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

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

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

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