kostenloser Webspace werbefrei: lima-city

Fälle unterscheiden

lima-city → Forum → Programmiersprachen → Sonstige Programmiersprachen

1. Autor dieses Themas

   toolz

   

   toolz hat kostenlosen Webspace.

   17:55, 16.2.2012

   Hallo!
   Angenommen, es sind zwei Zahlen von 0 bis n gegeben. Ich möchte diese jetzt so numerisch kombinieren, dass sich eine einzigartige (möglichst kleine) Zahl ergibt, etwa nach folgendem Schema:

   (0 ; 0) => 0
   (0 ; 1) => 1
   (1 ; 0) => 1
   (1 ; 1) => 2
   (0 ; 2) => 3
   (2 ; 0) => 3
   (1 ; 2) => 4
   (2 ; 1) => 4
   (2 ; 2) => 5
   (0 ; 3) => 6
   (3 ; 0) => 6

   Wobei das nicht zwingend so nummeriert sein muss. Die Anforderungen sind also:
   -> Schnelle Laufzeit
   -> Kombinationen der Art (0 ; 3) und (3 ; 0) müssen das selbe Ergebnis liefern
   -> Injektivität (sehr wichtig)
   
   Aufgrund der bequemen Implementation wäre es also auch vorteilhaft, wenn die Resultate nicht den Rahmen der Integervariable sprengt, also (n+1)! wäre angemessen; dabei sei n klein.
   
   Eine gute Funktion ist mir hierzu noch nicht eingefallen. Hat jemand einen Vorschlag?
   
   Beitrag zuletzt geändert: 16.2.2012 18:08:37 von toolz

2. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

3. sektor

   sektor hat kostenlosen Webspace.

   19:18, 16.2.2012

   Soso du willst also eine perfekte Hashfunktion basteln.
   Gibt es denn eine einschränkung bei den Eingabewerten?
   
   Ich kann dir erstmal den Tipp geben, dass die die (x; y) (y; x) invarianz hinbekommst, indem du ein solches Tupel immer sortierst (also natürlich nur intern). Damit wird (1; 0) und (0; 1) schonmal immer zu (0; 1). Auf dieser Basis kannst du dann weiterarbeiten.

4. darkpandemic

   

   darkpandemic hat kostenlosen Webspace.

   21:12, 16.2.2012

   Hallo toolz,
   
   auf die schnelle ist mir das folgende eingefallen:
   

   #include <stdio.h>
   
   int get_required_bit_count(unsigned int max_value)
   {
       int bits;
   
       if(max_value < 1)
           return -1;
   
       bits = 0;
   
       do
       {
           max_value >>= 1;
           bits++;
       }while(max_value);
   
       return bits;
   }
   
   unsigned int get_hash(int bit_count, unsigned int value_1, unsigned int value_2)
   {
       unsigned int hash;
   
       if(bit_count < 0 || bit_count > 16)
           return 0;
   
       if(value_1 > value_2)
           hash = (value_2 << bit_count) | value_1;
       else
           hash = (value_1 << bit_count) | value_2;
   
       return hash;
   }
   
   int main(int argc, char ** argv)
   {
       const unsigned int MAX_VALUE = 10;
       int bit_count;
       unsigned int i, j;
   
       bit_count = get_required_bit_count(MAX_VALUE);
   
       for(i=0;i<=MAX_VALUE;i++)
       for(j=i;j<=MAX_VALUE;j++)
       {
           printf("(%d; %d) -> %u\n", i, j, get_hash(bit_count, i, j));
       }
   
       getchar();
       return 0;
   }

   Es entspricht Deinen Anforderungen so gut wie es halt machbar ist. zumindest halbwegs schnell und injektiv ist es. Der Maximalwert darf aber 65535 nicht überschreiten. Theoretisch könnte man wohl noch kleinere Hashwerte erzeugen, indem man die lücken füllt. Aber das ist dann aufwendig und folglich langsam.

5. sektor

   sektor hat kostenlosen Webspace.

   22:29, 16.2.2012

   Hm nachdem ich nochmal etwas drüber gelesen habe wie wär es damit:
   

   (x, y) -> z
   x, y liegen in [0, N]

   
   dann berechne einfach:
   
   Dazu noch meine vergeschlagene Methode, um das ganze "symmetrisch" zu machen und es sollte deinen anforderungen entsprechen, sofern

6. darkpandemic

   

   darkpandemic hat kostenlosen Webspace.

   23:53, 16.2.2012

   Mir ist noch eine Alternative eingefallen (Bitverschränkung):
   

   unsigned int get_hash2(unsigned short value_1, unsigned short value_2)
   {
       unsigned int i, hash;
   
       hash = 0;
   
       if(value_1 > value_2)
       {
           for(i=0;i<16;i++)
           {
               hash >>= 1;
               if(value_1 & 1)
                   hash |= 0x80000000;
   
               hash >>= 1;
               if(value_2 & 1)
                   hash |= 0x80000000;
   		
               value_1 >>= 1;
               value_2 >>= 1;
           }
       }
       else
       {
           for(i=0;i<16;i++)
           {
               hash >>= 1;
               if(value_2 & 1)
                   hash |= 0x80000000;
   			
               hash >>= 1;
               if(value_1 & 1)
                   hash |= 0x80000000;
   	
               value_1 >>= 1;
               value_2 >>= 1;
           }
       }
   
       return hash;
   }

   
   
   Beitrag zuletzt geändert: 16.2.2012 23:59:38 von darkpandemic

7. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?