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

Mittwoch 18. Januar 2006, 20:49

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
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5555
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Oberhofen im Inntal (Tirol)
Kontaktdaten:

Mittwoch 18. Januar 2006, 21:03

elLobo hat geschrieben: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. :lol: :lol:

mfg
Gerold
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Python 47
User
Beiträge: 574
Registriert: Samstag 17. September 2005, 21:04

Mittwoch 18. Januar 2006, 21:05

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

Thomas :-)
Mad-Marty
User
Beiträge: 317
Registriert: Mittwoch 18. Januar 2006, 19:46

Mittwoch 18. Januar 2006, 21:07

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

Mittwoch 18. Januar 2006, 21:14

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.
Zuletzt geändert von modelnine am Mittwoch 18. Januar 2006, 21:50, insgesamt 4-mal geändert.
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5555
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Oberhofen im Inntal (Tirol)
Kontaktdaten:

Mittwoch 18. Januar 2006, 21:18

Python Master 47 hat geschrieben: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
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Mittwoch 18. Januar 2006, 22:23

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.
Zuletzt geändert von modelnine am Donnerstag 19. Januar 2006, 00:50, insgesamt 1-mal geändert.
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5555
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Oberhofen im Inntal (Tirol)
Kontaktdaten:

Mittwoch 18. Januar 2006, 22:46

modelnine hat geschrieben:

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
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Mittwoch 18. Januar 2006, 22:48

TUFKAB – the user formerly known as blackbird
Python 47
User
Beiträge: 574
Registriert: Samstag 17. September 2005, 21:04

Mittwoch 18. Januar 2006, 23:00

@gerold

Ich hab wohl die Frage falsch verstanden :lol:
mfg

Thomas :-)
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5555
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Oberhofen im Inntal (Tirol)
Kontaktdaten:

Mittwoch 18. Januar 2006, 23:38

Hi blackbird!

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

lg
Gerold
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
modelnine
User
Beiträge: 670
Registriert: Sonntag 15. Januar 2006, 18:42
Wohnort: Celle
Kontaktdaten:

Donnerstag 19. Januar 2006, 02:01

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

Donnerstag 19. Januar 2006, 07:49

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

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, 11:53

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

Donnerstag 19. Januar 2006, 12:10

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

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