proggen.org

Verfasst: **Do Nov 11, 2010 11:31 pm**

Tag zusammen

Ich schreibe einen RadixSort für die Uni (das schnellste Sortierverfahren gewinnt einen Preis

) und erweitere diesen nun auf negative Zahlen.
Das ist soweit kein Problem (das MSB muss einfach nur genau andersherum betrachtet werden, ich kann den Code ja bei Gelegenheit , also nach Abgabetermin, offenlegen)
Zumindest, wenn die Darstellung negativer Integer bei Java einheitlich ist.

Zuerst stellt sich noch die andere Frage: Sind "int" bei Java IMMER 32 Bit lang?
Dann die Frage an euch:

Ergibt der folgende Code die gleiche Ausgabe - egal auf welcher Maschine/Betriebssystem/JavaVM ?

Code: Alles auswählen

public static void printBinary(int n)
  {
    System.out.print("" + n + " = 0b");
    for(int i = 31; i >= 0; i--)
    {
      System.out.print("" + ( ((n&(1<<i)) == 0) ? "0" : "1")   );
    }
    System.out.println("");
  }

Code: Alles auswählen

    printBinary(0x7FFFFFFF);
    printBinary(2);
    printBinary(1);
    printBinary(0);
    printBinary(-1);
    printBinary(-2);
    printBinary(0x80000000);

2147483647 = 0b01111111111111111111111111111111
2 = 0b00000000000000000000000000000010
1 = 0b00000000000000000000000000000001
0 = 0b00000000000000000000000000000000
-1 = 0b11111111111111111111111111111111
-2 = 0b11111111111111111111111111111110
-2147483648 = 0b10000000000000000000000000000000

Wäre cool, wenn das jemand wüsste.
Oder auch, wenn ihr es bei euch testen könntet (mit Angabe des Betriebssystems, der JavaVM, 32/64Bit, Prozessorarchitektur)

Verfasst: **Fr Nov 12, 2010 3:19 pm**

Dirty Oerti hat geschrieben:Zuerst stellt sich noch die andere Frage: Sind "int" bei Java IMMER 32 Bit lang?

Mein Java Buch sagt ja. Bin mir aber selbst nicht sicher. Denke das hängt bei Java ausschließlich von der VM ab.

Dirty Oerti hat geschrieben: Dann die Frage an euch:

Ergibt der folgende Code die gleiche Ausgabe - egal auf welcher Maschine/Betriebssystem/JavaVM ?

Maschine und Betriebssystem: Ja, müsste.
JavaVM: Ich nicht wissen. Tut mir Leid.

Dirty Oerti hat geschrieben:Oder auch, wenn ihr es bei euch testen könntet (mit Angabe des Betriebssystems, der JavaVM, 32/64Bit, Prozessorarchitektur)

Code: Alles auswählen

2147483647 = 0b01111111111111111111111111111111
2 = 0b00000000000000000000000000000010
1 = 0b00000000000000000000000000000001
0 = 0b00000000000000000000000000000000
-1 = 0b11111111111111111111111111111111
-2 = 0b11111111111111111111111111111110
-2147483648 = 0b10000000000000000000000000000000

Windows 7,Version 6 Update 22 VM, 64Bit, Duo Core mit 2,66 GHz und 2,67 GHz Intel powered.

Hoffe das hilft dir.

Verfasst: **So Nov 14, 2010 2:14 pm**

Habe mal eben nachgeguckt und int ist in Java wohl grundsätzlich 32 Bit.

Ich habe das ganze mal in Quelltext gegossen, weil es irgendwo auch blöd ist, wenn sich das jeder selbst zusammenfrickeln muss.

Code: Alles auswählen

class DirtyOerti
{
  public static void printBinary(int n)
  {
    System.out.print("" + n + " = 0b");
    for(int i = 31; i >= 0; i--)
    {
      System.out.print("" + ( ((n&(1<<i)) == 0) ? "0" : "1")   );
    }
    System.out.println("");
  }

  public static void main( String [] bla )
  {
    printBinary(0x7FFFFFFF);
    printBinary(2);
    printBinary(1);
    printBinary(0);
    printBinary(-1);
    printBinary(-2);
    printBinary(0x80000000);
  }
}

Debian 64 Bit auf Intel i7, OpenJDK
Dann:

Code: Alles auswählen

xin@trinity:~/Documents$ java -version
java version "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8.2) (6b18-1.8.2-4)
OpenJDK 64-Bit Server VM (build 16.0-b13, mixed mode)
xin@trinity:~/Documents$ javac -version
javac 1.6.0_18
xin@trinity:~/Documents$ javac dirtyoerti.java
xin@trinity:~/Documents$ java DirtyOerti
2147483647 = 0b01111111111111111111111111111111
2 = 0b00000000000000000000000000000010
1 = 0b00000000000000000000000000000001
0 = 0b00000000000000000000000000000000
-1 = 0b11111111111111111111111111111111
-2 = 0b11111111111111111111111111111110
-2147483648 = 0b10000000000000000000000000000000
xin@trinity:~/Documents$ uname -a
Linux trinity 2.6.35.3 #1 SMP Sun Aug 22 12:36:51 CEST 2010 x86_64 GNU/Linux

Ubuntu 10.04 32 Bit auf Sempron 2400, OpenJDK

Code: Alles auswählen

xin@faculty:~$ javac -version
javac 1.6.0_18
xin@faculty:~$ javac dirtyoerti.java 
xin@faculty:~$ java DirtyOerti
2147483647 = 0b01111111111111111111111111111111
2 = 0b00000000000000000000000000000010
1 = 0b00000000000000000000000000000001
0 = 0b00000000000000000000000000000000
-1 = 0b11111111111111111111111111111111
-2 = 0b11111111111111111111111111111110
-2147483648 = 0b10000000000000000000000000000000
xin@faculty:~$ uname -a
Linux faculty 2.6.32-25-generic #45-Ubuntu SMP Sat Oct 16 19:48:22 UTC 2010 i686 GNU/Linux

MacOS 10.6 Core2Duo, Java
Der Mac läuft - wenn ich das richtig sehe - im 32 Bit Modus.

Code: Alles auswählen

Neo:~ xin$ java -version
java version "1.6.0_22"
Java(TM) SE Runtime Environment (build 1.6.0_22-b04-307-10M3261)
Java HotSpot(TM) 64-Bit Server VM (build 17.1-b03-307, mixed mode)
Neo:~ xin$ javac -version
javac 1.6.0_22
Neo:~ xin$ javac dirtyoerti.java 
Neo:~ xin$ java DirtyOerti
2147483647 = 0b01111111111111111111111111111111
2 = 0b00000000000000000000000000000010
1 = 0b00000000000000000000000000000001
0 = 0b00000000000000000000000000000000
-1 = 0b11111111111111111111111111111111
-2 = 0b11111111111111111111111111111110
-2147483648 = 0b10000000000000000000000000000000
Neo:~ xin$ uname -a
Darwin Neo.local 10.4.0 Darwin Kernel Version 10.4.0: Fri Apr 23 18:28:53 PDT 2010; root:xnu-1504.7.4~1/RELEASE_I386 i386

Verfasst: **So Nov 14, 2010 3:08 pm**

Gut, danke euch zweien

Daraus schließe ich mal, dass die Darstellung wohl zu einer großen Wahrscheinlichkeit einheitlich ist.

(Code folgt am 1.12. Sollte ich es vergessen, dann schreibt mich an. Ist nämlich ein super linearer Algorithmus zum Sortieren beliebiger Zahlen. Derweil mal der Link mit Informationen dazu: http://codercorner.com/RadixSortRevisited.htm)

Verfasst: **Do Dez 09, 2010 10:49 pm**

Tag

Also der Code hat gewonnen.
^^
Allerdings hab ich den Code stark vereinfacht abgegeben. Die Aufgabe war es, 10 Mio positive Integer zu sortieren.
Der Algorithmus kann aber auch leicht erweitert werden, um so z.B. auch floats etc zu sortieren.
Mit Hilfe einer Liste geschieht das ganze sogar ohne zusätzlichen Speicheraufwand, dafür natürlich etwas langsamer.
In einer Liste kann man auch Objekte speichern, die dann nach best. Attributen sortiert werden.
Da der Algorithmus stabil ist, kann man so auch durch mehrmaliges Sortieren eine Permutation erzeugen, die auf erster Ebene nach einem, auf niedrigerer Ebene nach einem anderen Attribut sortiert ist.

Code: Alles auswählen

public static void radixBasic(int [] a)
  {
    int[] counter = new int[256];
    int[] buffer = new int[a.length];
    for(char pass = 0; pass < 4; pass++)
    {
      for(int it = 0; it < 256; it++)
      {
        counter[it] = 0;
      }
      for (int it = 0; it < a.length; it++)
      {
        counter[(  (a[it]>>(pass<<3))&(0xFF)  )]++;
      }
      for (int it = 0; it < 255; it++)
      {
       counter[it+1] += counter[it];
      }
      for (int it = (a.length-1); it >= 0; it--)
      {
        buffer[--counter[(a[it]>>(pass<<3))&(0xFF)]] = a[it];
      }
      for (int it = 0; it < a.length; it++)
      {
        a[it] = buffer[it];
      }
    }
  }

Außerdem sind 3 (anstatt von hier 4) Passes wohl noch ein Stück optimaler.
Richtig zum Tragen kommt das aber erst, wenn auch negative Werte betrachtet werden, da dann der letzte Fall ein Sonderfall ist und dann sowieso getrennt betrachtet werden muss.

*Edit*
Hier eine Version, die auch negative Zahlen berücksichtigt. Auf deren Basis habe ich angefangen.
Mit floats funktioniert das im Übrigen genauso.

Code: Alles auswählen

public static void FIRSTradixSort(int[] A)
  {
    int feldlaenge = A.length;
    int[] zero = new int[feldlaenge];
    int[] one = new int[feldlaenge];
    int z,o,i,z_it,o_it;
    // Standard RadixSort
    for( int b = 0; b < 31; b++)
    {
      z = 0;
      o = 0;
      for( i = 0; i < feldlaenge; i++)
      {
        if( (A[i] & (1<<b)) == 0 )
        {
          zero[z] = A[i];
          z++;
        }
        else
        {
          one[o] = A[i];
          o++;
        }
      }
      i = 0;
      for( z_it = 0; z_it < z; z_it++,i++)
      {
        A[i]=zero[z_it];
      }
      for( o_it = 0; o_it < o; o_it++,i++)
      {
        A[i]=one[o_it];
      }
    }
    // MSB gibt Vorzeichen an, 1 -> negativ, damit kleiner, also umgekehrt zu
    // oben verfahren. Da Leadbits bei negativen Zahlen 1 und nicht 0 sind, 
    // werden groessere Absolutwerte automatisch zu kleineren negativen Werten.
    z = 0;
    o = 0;
    for ( i = 0; i < feldlaenge; i++)
    {
      if( (A[i] & (0x80000000)) == 0 )
      {
        zero[z] = A[i];
        z++;
      }
      else
      {
        one[o] = A[i];
        o++;
      }
    }
    i = 0;
    for( o_it = 0; o_it < o; o_it++,i++)
    {
      A[i]=one[o_it];
    }
    for( z_it = 0; z_it < z; z_it++,i++)
    {
      A[i]=zero[z_it];
    }
  }

proggen.org

Darstellung negativer Integer

Darstellung negativer Integer

Re: Darstellung negativer Integer

Re: Darstellung negativer Integer

Re: Darstellung negativer Integer

Re: Darstellung negativer Integer