| Autor |
Beitrag |
    
Kay Schönberger (kay_s)
Erfahrenes Mitglied
Benutzername: kay_s
Nummer des Beitrags: 113
Registriert: 01-2001
| | Veröffentlicht am Sonntag, den 04. Mai, 2003 - 12:37: | 
|
Hallo,
Folgendes Problem: Ich habe Vektoren mit 24 Einträgen, davon besitzen genau 12 den Wert "0" und genau 12 den Wert "1". Laut Kombinatorik gibt es also 24!/12!2 = 2704156 solcher Vektoren.
Jedem dieser Vektoren möchte ich nun ein-eindeutig eine Zahl zwischen 1 und 2704156 (oder auch zwischen 0 und 2704155) zuordnen (z. B. für die Speicherung in einem Array).
Dazu benötige ich eine möglichst rechenzeitschonende Funktion. Ich habe mir zwar schon eine Lösung zurechtgebastelt, doch diese benötigt sämtliche Fakultäten bis 24! (selbst mit 64-Bit-Integer nicht darstellbar) und führt zig Multiplikationen/Divisionen aus.
Kennt da jemand vielleicht eine bessere/schnellere Methode?
Kay S.
|
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 202
Registriert: 10-2001
| | Veröffentlicht am Montag, den 05. Mai, 2003 - 09:02: |
|
Hmmm, warum nimmst Du keine Binärkodierung?
Jede Zahl im Computer ist aus Bits zusammengestzt, welche 0 oder 1 sind (das klingt doch sehr nach Deinen Vektoren).
Deine Zahlen bestehen aus 24 bit und erlauben daher 16777216 (2^24) Kombinationen (maximal) 
z.B. ist 0101 = 0*2^3+1*2^2+0*2^1+1*2^0 = 5
Du brauchst also nur die Werte deines Vektors auf einen 32bit-Zahl (üblich Integer) 1:1 übertragen und wieder zurück, falls Du wieder den Vektor brauchst. Du könntest auch auch 3 Byte (a 8 Bit) aufteilen, das spart ein Byte Platz.
Rechenen wir mal:
Es gibt 2704156 Vektoren, also 2704156 IntegerZahlen (a 4 Byte) = 10816624 entspricht etwa 10,3 MB Speicher für alle Kombinationen
- mit 3 Byte verbrauchst Du ca. 8 MB.
Es kommt nun darauf an, welche Sprache Du verwendest, aber viele haben BitOperationen.
Onkel Murray |
Kay Schönberger (kay_s)
Erfahrenes Mitglied
Benutzername: kay_s
Nummer des Beitrags: 114
Registriert: 01-2001
| | Veröffentlicht am Montag, den 05. Mai, 2003 - 20:25: |
|
Hallo Murray,
Es geht ja um eine effiziente Kodierung. Wenn ich einfach die Bitwerte übernehme, bekomme ich Zahlen zwischen 1 und 16777216, d. h. ich müßte ein Array mit 16,7 Mio. Einträgen anlegen, obwohl nur 2,7 Mio. benötigt werden.
Hintergrund ist ja die Vermeidung der "Redundanz" (also Zahlen, denen kein Vektor zugeordnet ist), da mehrere dieser Arrays im Speicher gehalten werden sollen.
Ich hab' vergessen zu erwähnen, daß ich ja nicht die Vektoren selbst abspeichern möchte, sondern mit ihnen verknüpfte Informationen. Aus einem Vektor berechne ich also eine Zahl 1 <= N <= 2704156 und hole/speichere dann diese Information an Position N im Array.
Kay S.
(Beitrag nachträglich am 05., Mai. 2003 von kay_s editiert) |
|
