[jabu]

Ich mach das neu.

Ein freier Kopf, verstanden.

Dieses abwandeln, würde nur dazu führen, dass das andere nicht mehr läuft. Das wäre zwar nicht mehr notwendig. Aber es ist ja auch ein lauffähiger Algorithmus, den ich eigentlich erhalten will.

Du könntest doch auf einer Kopie (des Projektes) weiterarbeiten. Aber du hast dich entschieden, alles gut.

Naja, er schaut ja nicht wirklich nach. Ich hole da nur die x,y werte. Das die Stellen 0 sind, ist ja klar. Das wird ja vorher einmal ermittelt.

Wenn einer von "Liste" redet, dann denke ich zuerst an eine reine Liste. Dabei hängt der Aufwand für den Zugriff davon ab, wo sich das Element innerhalb der Liste befindet, entsprechend O(n). Ein Element an vierzigster Stelle abzufragen, ist also vierzigmal so aufwendig, wie eines an erster Stelle abzufragen, wenn du hundert Elemente hast, nur zum Beispiel. Das wäre hier kontraproduktiv.

Natürlich vermute ich, dass du nicht eine reine Liste meinst, sondern eine mit einer zusätzlichen Verwaltungsstruktur, welche im Optimalfall einen Zugriff mit konstantem Aufwand (O(1)) ermöglicht. Dieses impliziert jedoch notwendig (weil die Elemente einer Liste nicht direkt aufeinanderfolgend im Speicher abgelegt sind) mindestens eine weitere Indirektionsebene (z. B. ein dynamisches Array) mit Verweisen auf die Elemente, was bedeutet, dass ein vorangehender, zusätzlicher, Speicherzugriff erfolgt (teuer) und dass die endgültige Adresse ausgerechnet werden muss (billig). Zusammen ist das teuer.

Ob deine Liste unter der Haube als Array implementiert ist, weiß ich nicht. Allerdings wäre in dem Fall (den ich nicht absprechen will) eine Bezeichnung als Liste schon etwas irreführend. Aber auch in dem Fall glaube ich nicht an das Entfallen einer Indirektionsebene, denn irgendwann ist das Array mal ausgeschöpft, was bedeutet, dass neuer Speicher alloziiert werden muss, der dann eben nicht nahtlos anknüpft. Dann wäre das ungefähr dasselbe wie eine optimierte Liste mit zwangsweiser Preallokation (was eine cachefreundliche Auslegung ermöglicht), aber was ungefähr denselben Aufwand für die Indirektion benötigt, denn es kann nicht vorab garantiert werden, dass die Zeiger gültig bleiben.

Es ist bereits eine Indirektion, die Adresse eines Arrays oder einer Liste nachzugucken, um den Zeiger für den Zugriff auszurechnen, bevor überhaupt ein Zugriff erfolgt, was man bereits deutlich merkt (wenn die Adresse nicht gerade in einem Register vorgehalten wird). Jede weitere Indirektion ist natürlich Gift, weswegen es bei einem echten Array bleiben sollte, wenn man eine dementsprechende Struktur braucht.

Das meiste von deinen Vorschlägen konnte ich umsetzen und es wird nachvollziehbar schneller. Und der Code wird sogar deutlicher.

Den Zustand des geringstmöglichen Aufwandes möchte man als Voraussetzung für das anschließende Optimieren anstreben. Letzteres macht den einfachstmöglichen Code (den man erst mal haben muss, was gar nicht so einfach ist) dann wieder etwas komplizierter (auf andere Weise).

Lediglich das Prüfen läuft so nicht. Für die andere Methode brauche ich ein anderes prüfen.

Das war nicht wörtlich gemeint, sondern als ein Wink, du mögest die Voraussetzung für die Notwendigkeit des Aktualisierens eliminieren...

Aber mal sehen, wie es funktioniert im reinen Brute Force bei mir. Hab schon was entwickelt, was die Prüfzeiten deutlich reduzieren wird. Mal sehen, was bei rauskommt.

Reines Brute-Force? Das ließe sich unterschiedlich interpretieren. Ich bin gespannt.

Das war ein Bestandteil meines Winks (ausgenommen die 0, die dort anstelle von get_matrix(x,y) steht, falls möglich):

matrix[x][y]=0;
aktualisieren_neu(x,y,get_matrix(x,y));

Ist leider bei mir notwendig.
Das Problem ist halt, dass er die Spalten, Zeilen und Matrizen aus der großen Matrix zieht und anschließend wird geprüft. Das geht sicherlich viel besser. Aber wenn ich das hier ändere, läuft der ganze Rest nicht mehr. Deshalb mache ich das komplett neu und brauch mich nicht mehr um andere Zöpfe zu kümmern.

Viel Spaß dabei!

[Stiller Leser]

Wenn einer von "Liste" redet, dann denke ich zuerst an eine reine Liste. Dabei hängt der Aufwand für den Zugriff davon ab, wo sich das Element innerhalb der Liste befindet, entsprechend O(n). Ein Element an vierzigster Stelle abzufragen, ist also vierzigmal so aufwendig, wie eines an erster Stelle abzufragen, wenn du hundert Elemente hast, nur zum Beispiel. Das wäre hier kontraproduktiv.

Natürlich vermute ich, dass du nicht eine reine Liste meinst, sondern eine mit einer zusätzlichen Verwaltungsstruktur, welche im Optimalfall einen Zugriff mit konstantem Aufwand (O(1)) ermöglicht. Dieses impliziert jedoch notwendig (weil die Elemente einer Liste nicht direkt aufeinanderfolgend im Speicher abgelegt sind) mindestens eine weitere Indirektionsebene (z. B. ein dynamisches Array) mit Verweisen auf die Elemente, was bedeutet, dass ein vorangehender, zusätzlicher, Speicherzugriff erfolgt (teuer) und dass die endgültige Adresse ausgerechnet werden muss (billig). Zusammen ist das teuer.

Ob deine Liste unter der Haube als Array implementiert ist, weiß ich nicht. Allerdings wäre in dem Fall (den ich nicht absprechen will) eine Bezeichnung als Liste schon etwas irreführend. Aber auch in dem Fall glaube ich nicht an das Entfallen einer Indirektionsebene, denn irgendwann ist das Array mal ausgeschöpft, was bedeutet, dass neuer Speicher alloziiert werden muss, der dann eben nicht nahtlos anknüpft. Dann wäre das ungefähr dasselbe wie eine optimierte Liste mit zwangsweiser Preallokation (was eine cachefreundliche Auslegung ermöglicht), aber was ungefähr denselben Aufwand für die Indirektion benötigt, denn es kann nicht vorab garantiert werden, dass die Zeiger gültig bleiben.

Es ist bereits eine Indirektion, die Adresse eines Arrays oder einer Liste nachzugucken, um den Zeiger für den Zugriff auszurechnen, bevor überhaupt ein Zugriff erfolgt, was man bereits deutlich merkt (wenn die Adresse nicht gerade in einem Register vorgehalten wird). Jede weitere Indirektion ist natürlich Gift, weswegen es bei einem echten Array bleiben sollte, wenn man eine dementsprechende Struktur braucht.

Also eigentlich muss gar nichts gesucht werden. Das ist ja gerade das tolle.
Die Nullstellen werden gleich beim Initialisieren der Matrix abgespeichert. Das ganze ist in einer eigenen Klasse. Hätte dafür eigentlich auch gleich Point nehmen können. Aber letztendlich hab ich mir da was eigenes erstellt. Eine Set-Funktion zum Setzen einer Koordinate und zwei Get-Funktionen zum Bekommen des x und y -wertes.

Daraus erstelle ich dann in der Hauptklasse eine Liste. Also List<Koordinaten> nullstellen= new ArrayList<Koordinaten>();
In der Schleife dann, wo initialisiert wird, ist zur eigentlichen Zuweisung dann halt noch eine Zeile mit if(Matrix[i][j]==0)nullstellen.add(new Koordinaten(i,j));

Die könnte ich jetzt noch sortieren oder es sein lassen. Aber wenn ich es so lasse, sind halt nur einfach alle Nullstellen drin und es braucht eigentlich gar nicht gesucht werden, da immer das nächste Nullelement aufgerufen wird bis zum Schluss, ich die Nullstellen also per Indizes aufrufe.

Oder dauert das auch so lange?

[Stiller Leser]

Auf deine Zeit komme ich zwar noch nicht, aber immerhin bin ich jetzt nahe dran. 5.5 ms pro Durchgang in etwa. Wobei ich sagen muss, dass ich fast geflucht hätte.
Denn: Ich habe die ganze Zeit immer nur einen Durchgang geprüft. Da kam ich auf etwa 60 ms. Ich wollte dann mal testen, wie es ist mit 1000 Durchgängen und siehe da. da wurde er bedeutend schneller.

Leider konnte ich meine Idee nicht verwirklichen, so dass das neue Tempo alleine daran liegt, dass ich die Klassen neu geschrieben habe und den ganzen Ballast weg habe.

So sieht jetzt mein Primus aus.

boolean primus(int pos) {		final int x=nullstellen.get(pos).get_x(),y=nullstellen.get(pos).get_y();
		final int m=Tools.get_kl_matrix_aus_Matrix(3, 3, 9, 9, x+1, y+1);
		final int kx=Tools.get_x_aus_kl_matrix_aus_Matrix(3, 3, 9, 9, x+1);
		final int ky=Tools.get_y_aus_kl_matrix_aus_Matrix(3, 3, 9, 9, y+1);
		int zahl=0;
		aufrufe++;
		do {
				do {
					zahl++;
					if(zahl>9) {
						kl_matrix[m].set_matrix(kx, ky, 0);
						zeile[x].set_reihe(y, 0);
						spalte[y].set_reihe(x, 0);
						return false;
					}
				}while(prüfe_zahl(x,y,m,zahl));
				
			aktualisieren_neu(x,y,m,zahl, kx, ky);
				
			if(pos==nullstellen.size()-1) {
				return true;
			}
		}while(!primus(pos+1));
		
		return true;
	}

Mit meiner Idee gestaltet es sich komplexer, als ich dachte.

Mal anhand meiner zeilen und spalten erklärt:

class Reihen{		private List<Integer>reihe=new ArrayList<Integer>();


		Reihen(){
			for(int i=0;i<9;i++)reihe.add(0);
		}


		int get_reihe(int x) {
			return reihe.get(x);
		}
		
		void set_reihe(int x, int zahl) {
			reihe.set(x, zahl);
		}
		
		boolean prüfen_doppelt(int zahl){
			for (int i=0;i<9;i++)
			            if(reihe.get(i)==zahl)return true;
			return false;
			}
	}

Die ganze Arbeit läuft ja in prüfen doppelt ab. Er prüft soweit, bis er das erste Mal die Zahl findet. Bei über 40000 Aufrufe muss er oft durch die Schleife durch.
Meine Idee ist, dass er keine Schleife durchlaufen muss, sondern einfach die Zahl prüft. Und zwar dergestalt, dass ich eine zweite Liste oder ein Array stelle, welches 9 Felder in Boolean bereitstellt. Die Zahlen werden dann einfach mit den Indizes angesprochen. Also zahlen[5] wäre beispielsweise die 5. Dazu muss ich lediglich beim set_reihe(int x, int zahl) noch die Zeile zahlen[zahl]=true einfügen. Beim Prüfen auf doppelt wäre dann statt der Schleife nur noch if(zahlen[zahl]) zu prüfen.
Das funktioniert solange, bis ich zurücksetzen muss. Denn ich kann jetzt nicht einfach die letzte geänderte Zahl nehmen und auf false setzen. Das Problem dabei ist, dass dann für die nächste Vorwärtsprüfung der Wert wieder frei ist und zwar so, als ob der in der ganzen Zeile gar nicht vorhanden wäre. Es gibt also am Ende eine falsche Lösung und Primus endet mit false. Ich glaube, dass es eine einfache Lösung für das Problem gibt. Aber ich komme im Moment nicht drauf.

[Stiller Leser]

Mit der Idee bin ich immer noch nicht weiter gekommen. Dafür hatte ich eine andere fruchtbare Idee. Diese ganzen Klassen Reihe, Kleine Matrizen braucht es eigentlich gar nicht. Jedenfalls nicht, wenn man nur schnell durchzählen will.
Ich hab die jetzt auch alle raus genommen und siehe da, jetzt bin ich bei 3,2 ms. Aber beim Einzelaufruf bin ich bei 30 bis 50 ms. Irgendwie ist das komisch.

package Haupt;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;


import Fenster.Fenster;
import Tools.Tools;
import Zeitmesser.Zeitmesser;


public class Sudoku {
    
    List<Koordinaten>nullstellen=new ArrayList<Koordinaten>();
    
    int [][]matrix; //Hauptmatrix
    int zeilen,spalten;//Größe Hauptmatrix
    static int aufrufe=0;
    List<Integer> letzte_zahl=new ArrayList<Integer>();
    
    Sudoku(int [][]matrix){
        this.matrix=new int[9][9];
        zeilen=9;spalten=9;
        
        for(int i=0;i<zeilen;i++)
            for(int j=0;j<spalten;j++){
                this.matrix[i][j]=matrix[i][j];
                if(this.matrix[i][j]==0)nullstellen.add(new Koordinaten(i,j));
            }
    }
    
    boolean primus(int pos) {
        final int x=nullstellen.get(pos).get_x(),y=nullstellen.get(pos).get_y();
        final int m=Tools.get_kl_matrix_aus_Matrix(3, 3, 9, 9, x+1, y+1);
        final int start_kx=Tools.get_zeile_aus_Matrix(3, 3, 1, 1, m+1, 9, 9);
        final int start_ky=Tools.get_spalte_aus_Matrix(3, 3, 1, 1, m+1, 9, 9);
        int zahl=0;
        aufrufe++;
        do {
                do {
                    zahl++;
                    if(zahl>9) {
                        matrix[x][y]=0;
                        return false;
                    }
                }while(prüfe_zahl(x,y,m,zahl, start_kx, start_ky));
                
            matrix[x][y]=zahl;
                
            if(pos==nullstellen.size()-1) {
                return true;
            }
        }while(!primus(pos+1));
        
        return true;
    }
    
    boolean prüfe_zahl(int x, int y, int m, int zahl, int start_kx, int start_ky) {
            if (prüfen_zeile(zahl,x))return true;
            if(prüfen_spalte(zahl,y))return true;
            if(prüfen_matrix(zahl, start_kx, start_ky))return true;
            return false;
    }
    
    boolean prüfen_zeile(int zahl, int x){
        for (int i=0;i<9;i++)
                    if(matrix[x][i]==zahl)return true;
        return false;
    }
    
    boolean prüfen_spalte(int zahl, int y){
        for (int i=0;i<9;i++)
                    if(matrix[i][y]==zahl)return true;
        return false;
    }


    boolean prüfen_matrix(int zahl, int kx, int ky){
        for (int i=kx;i<3+kx;i++)
            for(int j=ky;j<3+ky;j++)
                    if(matrix[i][j]==zahl)return true;


        return false; 
        }




    /*
     * gibt den wert der Hauptmatrix an Stelle zeile, spalte zurück
     */
    int get_matrix(int zeile, int spalte){
        return matrix[zeile][spalte];
    }
    
    class Koordinaten{
        int x=0;
        int y=0;


        Koordinaten(int x, int y){
            set_Koordinaten(x,y);
        }


        int get_x() {
            return x;
        }


        int get_y() {
            return y;
        }


        boolean gleich(Koordinaten a) {
            if(this.x==a.get_x()&&this.y==a.get_y())return true;
            else return false;
        }


        void set_Koordinaten(int x, int y) {
            this.x=x;
            this.y=y;
        }


        }


}






class Mainframe{
    public static void main(String[] args) {
        
        int [][]matrix={{0,0,2,0,7,0,9,4,0},
                        {9,0,1,0,0,0,0,0,0},
                        {0,7,3,9,8,0,0,0,6},
                        {0,0,4,5,0,7,0,0,8},
                        {6,3,0,0,9,0,0,0,0},
                        {0,0,0,1,0,0,3,0,0},
                        {0,9,0,4,5,6,0,7,3},
                        {0,0,0,0,0,0,0,8,1},
                        {0,0,0,0,1,3,0,0,0}};


        Fenster b=new Fenster();
        
        boolean initialisiert=false, laden=false, gelöst=false;
        int x=0, y=0, y1=0;
        
        b.set_text();
        
        while(!initialisiert&&!laden){
            initialisiert=b.get_fertig();
            laden=b.get_laden();
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        
        if(initialisiert){
        for(int i=0;i<9;i++){
            switch(i){
            case 0:case 1:case 2:
                switch(i){
                    case 0:
                        x=0;y=0;y1=y;
                        break;
                    case 1:
                        x=0;
                        y=3;y1=y;
                        break;
                    case 2:
                        x=0;
                        y=6;y1=y;
                        break;
                }
            break;
            case 3:case 4: case 5:
                switch(i){
                case 3:
                    x=3;
                    y=0;y1=y;
                    break;
                case 4:
                    x=3;
                    y=3;y1=y;
                    break;
                case 5:
                    x=3;
                    y=6;y1=y;
                    break;
                }


                break;
            case 6: case 7: case 8:
                switch(i){
                case 6:
                    x=6;
                    y=0;y1=y;
                    break;
                case 7:
                    x=6;
                    y=3;y1=y;
                    break;
                case 8:
                    x=6;
                    y=6;y1=y;
                    break;
                }
                break;
        }
            for(int j=0;j<3;j++){
                for (int k=0;k<3;k++){
                    matrix[x][y1++]=b.get_matrix(i, j, k);
                }
                x++;y1=y;
            }
        }
        
        FileWriter writer;
        File datei=new File("Sodoku.txt");
        
        try {
            writer=new FileWriter(datei);
            
            for(int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    writer.write(Integer.toString(matrix[i][j]));
                }
                writer.write(System.getProperty("line.separator"));
            }
            
            writer.flush();
            writer.close();
            
            
        } catch (IOException e) {
            e.printStackTrace();
            System.out.println("Fehler beim Speichern");
        }
    }//end initialisiert -> Zahlen vom Eingabefenster
        
        if(laden){
                //System.out.println("Versuche zu laden");
        FileReader reader;
        File datei=new File("Sodoku.txt");
        int zahl;
        int i=0;int j=0;
        
        
        try {
              reader=new FileReader(datei);
              
              try {
                while( (zahl=reader.read()) != -1 ){
                    if((char)zahl!=13 &&(char)zahl!=10){//13=return 10=neue Zeile
                        matrix[i][j++]=Character.getNumericValue((char)zahl);
                        if(j==9){
                            i++;
                            j=0;
                        }
                        if(i==9)i=0;
                    }
                }    
                reader.close();
                //System.out.println("Laden ok");
            } catch (IOException e) {
                e.printStackTrace();
                System.out.println("Fehler beim Datei auslesen");
            }
              
              
            } catch (FileNotFoundException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
                System.out.println("Datei nicht gefunden.");
            }
        
        
        x=0;y=-1;
        int xg,yg;
        for(i=0;i<9;i++) {
            for(j=0;j<9;j++) {
                y++;
                if(y==3) {
                    x++;
                    y=0;
                }
                xg=Tools.get_zeile_aus_Matrix(3, 3, x+1, y+1, i+1, 9, 9);
                yg=Tools.get_spalte_aus_Matrix(3, 3, x+1, y+1, i+1, 9, 9);
                b.set_button(i, j, Integer.toString(matrix[xg][yg]));
            }
            x=0;
            y=-1;
        }


        }//end laden -> Zahlen aus Datei


        Sudoku a=new Sudoku(matrix);
        Zeitmesser.startZeitmessung(1,2);
        for(int i=0; i<1000; i++) {
        a=new Sudoku(matrix);
        
        gelöst=a.primus(0);}
        long zeit=Zeitmesser.getZeitmessung(1)/1000;
        Zeitmesser.stopZeitmessung(1);
        
        System.out.println();System.out.println();
        for (int i=0;i<a.zeilen;i++)
        {
            for (int j=0;j<a.spalten;j++)System.out.print(a.get_matrix(i, j)+" ");
            System.out.println();
        }    
        System.out.println();
        
        x=0;y=-1;
        int xg,yg;
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                y++;
                if(y==3) {
                    x++;
                    y=0;
                }
                xg=Tools.get_zeile_aus_Matrix(3, 3, x+1, y+1, i+1, 9, 9);
                yg=Tools.get_spalte_aus_Matrix(3, 3, x+1, y+1, i+1, 9, 9);
                b.set_button(i, j, Integer.toString(a.get_matrix(xg,yg)));
            }
            x=0;
            y=-1;
        }
        
        System.out.println();
        System.out.println("Aufrufe = "+a.aufrufe);
        System.out.println("Primus liefert = "+gelöst);
        System.out.println("Gebraucht: "+zeit/1000.+ " Microsekunden");


    }
    
}

[jabu]

Mit der Idee bin ich immer noch nicht weiter gekommen. Dafür hatte ich eine andere fruchtbare Idee. Diese ganzen Klassen Reihe, Kleine Matrizen braucht es eigentlich gar nicht. Jedenfalls nicht, wenn man nur schnell durchzählen will.

Aber ja, Speicherzugriffe sind bekanntermaßen teuer (selbst auf optimierte Listen (ArrayList) noch teurer als auf richtige Arrays und u. U. selbst auf Arrays (siehe unten!)...).

Ich hab die jetzt auch alle raus genommen und siehe da, jetzt bin ich bei 3,2 ms. Aber beim Einzelaufruf bin ich bei 30 bis 50 ms. Irgendwie ist das komisch.

Weil ich mir deinen Code noch nicht anschauen konnte, von allgemeinen Voraussetzungen ausgehend:

• Beim ersten Durchgang hat der JIT-Compiler noch nichts oder nicht viel optimiert. Es gibt nämlich Schwellwerte, damit das Optimieren nicht bei Code, der nur selten ausgeführt wird, einen zu großen Overhead bedeutet. Nur häufig ausgeführter Code lohnt den Aufwand. Du kannst aber beim Start über Parameter die Schwellen verändern, sodass mehr vorauskompiliert wird, was ich empfehlen würde, falls es hilft (die größere Verzögerung beim Anwendungsstart dürfte nicht stören).
• Der JIT-Compiler selber hackt dir da rein (passiert und stört eher bei mehreren, aber wenigen, Durchgängen).
• Wenn jeder Durchgang zum selben Ergebnis führt, also sonst keine Effekte hat, dann darf der Compiler ihn durch einen einzigen Durchgang ersetzen. Deswegen sorge ich bei meinen Benchmarks für einen Nebeneffekt, dessen Ergebnis der Compiler nicht so leicht vorausberechnen kann, denn ich möchte n Durchgänge messen und nicht nur einen. Ich gehe zwar nicht davon aus, dass das hier passiert, aber manchmal ist ein Compiler so clever, dass man die Zeit für einen einzigen Durchgang misst, weil es nur noch diesen einen gibt (oder nicht mal den, wenn das Ergebnis allzu offensichtlich ist, was hier aber nicht sein kann)...

Deine 3,2 ms kann aber gut hinkommen, denn meine Hardware ist steinalt und zudem niedrig getaktet, wie du weißt. Bei mir müsste das langsamer laufen bzw. bei dir noch schneller (rechne etwa mit Faktor 3). Es wäre also noch ein Weg zu gehen. Aber die Zeit ist schon mal gut, wenn sonst alles stimmt. Wenn ich mir das Brett günstiger hindrehe und es nachher zurückdrehe (bisher nur manuell gemacht, ohne das Optimum zu ermitteln), bin ich jedoch bei knapp 400 us. Wenn das automatische Analysieren und Verdrehen hinzukommt (was noch fehlt), sollte es schlechtestenfalls 500 us sein. Dann teilst du das wegen der Hardware etwa durch drei. Wenn du also bei ungefähr 200 us ankommst, dann kannst du dir ein Pfeifchen rauchen.

Eine Antwort, die vielleicht von Interesse sein könnte, liegt bei mir schon länger herum, ich will sie nicht vorenthalten:

Also eigentlich muss gar nichts gesucht werden. Das ist ja gerade das tolle.
Die Nullstellen werden gleich beim Initialisieren der Matrix abgespeichert. Das ganze ist in einer eigenen Klasse. Hätte dafür eigentlich auch gleich Point nehmen können. Aber letztendlich hab ich mir da was eigenes erstellt. Eine Set-Funktion zum Setzen einer Koordinate und zwei Get-Funktionen zum Bekommen des x und y -wertes.
[...]
Oder dauert das auch so lange?

Beim Zugriff muss der Zeiger für das angefragte Element gesucht werden. Bei einer reinen verketteten Liste ist das noch eine richtige Suche, weil die eben leider elementweise durchgegangen werden muss. Bei diesen heutzutage weitverbreiteten zugriffsoptimierten Listen (mit Speicher-Overhead gegenüber reinen Listen) beschränkt sich die "Suche" bestenfalls auf das Nachschlagen und Ausrechnen des endgültigen Zeigers, was schon ein enormer Vorteil ist. Dass das nötig bleibt, liegt einfach daran, dass sich ein echtes Array nicht beliebig erweitern lässt. Auch wenn viel Speicher im Voraus angefordert wird, kann er nicht für ewig ausreichen. Neuer Speicher bedeutet aber neue Adressen, die irgendwo nachgeschlagen werden müssen. Deswegen ist mindestens eine weitere Indirektion drin, auch wenn du sie nicht brauchen würdest, weil deine Länge fix ist.

Demnach sind keine fixen Zeiger auf die Elemente möglich, denn dass die Elemente immer direkt hintereinander liegen, kann bei Erweiterbarkeit nur durch das Erkaufen anderer Nachteile (Umkopieren von allem) garantiert werden, wobei der neu alloziierte Speicher nicht unbedingt an derselben Adresse beginnen muss. Solches wäre niemals garantierbar. Deswegen kannst du schon von vornherein nicht mit direkten Elementzeigern zugreifen (es sei denn, die VM tauscht sie unter'm Hintern gegen aktualisierte aus, was aber auch nicht so naiv gewinnbringend funktionieren kann, alles hat seinen Preis). Theoretisch kann eine VM aber viel optimieren, wenn garantiert ist, dass der Programmierer nicht direkt auf Zeiger zugreifen kann (wie bei Java), aber irgendwann würde das zu komplex und daher selbst zum Problem werden. In realen komplexen Anwendungen (Spiele) scheitert fast alles, was solche Sprachen versprechen. Bei Programmen, die immer dasselbe tun (Webserver, Datenbanken, dein wiederholter Algorithmus), kann die Rechnung aufgehen, wenn die Hardware entsprechend dimensioniert ist.

Es kann zur Vermeidung des Umkopierens allzu großer Blöcke beim Erweitern einen ganzen Baum an Adressen geben, der beim Zugriff durchsucht werden muss, um den jeweiligen Anfang eines Blockes zu finden. Im Idealfall existiert nur ein einziger Block, wodurch der Zugriff streng mit O(1) und in kürzestmöglicher Zeit geschieht, indem sich die Suche auf den Zugriff und die Auswertung des ersten Baumknotens beschränkt. Davon, dass er Aufwand nicht oder nicht viel größer ist (oder vllt. sogar etwas kleiner ist, weil die VM trickst), ist bei dir auszugehen, aber es ist eben nicht nichts. Und manchmal liegen Elemente verstreut auf dem Heap und manchmal dichter nacheinander, was enorme Auswirkungen auf das Caching haben kann.

Weil dich der Aufwand bei ArrayList interessierte, habe ich mal gemessen:

 Ermittle Zugriffszeiten, bitte warten...
|------------------------------------------|------------|--------------|
|  Datenstruktur (wird immer int gelesen)  |  Zugriffe  |     Zeit     |
|------------------------------------------|------------|--------------|
| Vector mit Point                         | 1000000000 | 50921,591 ms |
| LinkedList mit Point                     | 1000000000 | 48111,207 ms |
| Ein zweidimensionales Array [100][2]     | 1000000000 |  1653,860 ms |
| ArrayList mit Point                      | 1000000000 |  1565,029 ms |
| Ein lineares Array mit Point             | 1000000000 |  1137,475 ms |
| Alternierender Zugriff auf lin. Array    | 1000000000 |   841,819 ms |
| Zwei separate lineare Arrays abwechselnd | 1000000000 |   780,776 ms |
| Linearer Zugriff auf lineares Array      | 1000000000 |   806,007 ms |
|------------------------------------------|------------|--------------|
 Compiler anti cheat accumulator: 6284966960
 Fertig. Zum Beenden bitte die Eingabetaste betätigen.

Der Code:

package zugriffszeiten;

import java.awt.Point;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Vector;

final class Watch {
    private static final long ns_per_us = 1000;
    private static final long us_per_ms = 1000;
    private static final long ns_per_ms = ns_per_us * us_per_ms;
    private static long starttime_ns = 0;
    private static long stoptime_ns = 0;
    private static long timespan_ns = 0;
    
    // Compiler should keep (not optimize away) the two separate accesses... 
    public static volatile long anticheat = 3761;

    private Watch() {
    }

    static void Start() {
        stoptime_ns = 0;
        starttime_ns = System.nanoTime();
    }

    static void Stop() {
        timespan_ns = System.nanoTime() - starttime_ns;
        starttime_ns = 0;
    }

    static void PrintResult(String name, long sum1, long sum2) {
        final double fspan_ms = (double)timespan_ns / (double)ns_per_ms;
        System.out.format("| %-41s|%11d |%10.3f ms |%n", name, sum1 + (sum2/2) - anticheat, fspan_ms);
        // ...so we make cheating nearly impossible:
        if (((timespan_ns - sum1) % 11) != 5471) {
            if (sum1 != 0) {
                anticheat += timespan_ns % sum1;
            }
        }
        timespan_ns = 0;
    }
}

public final class Zugriffszeiten {

    public static void main(String[] args) throws IOException, InterruptedException {
        
        System.out.println(" Ermittle Zugriffszeiten, bitte warten...");
        System.out.println("|------------------------------------------|------------|--------------|");
        System.out.println("|  Datenstruktur (wird immer int gelesen)  |  Zugriffe  |     Zeit     |");
        System.out.println("|------------------------------------------|------------|--------------|");

        long sum1;
        long sum2;      
        {
            sum1 = Watch.anticheat;
            sum2 = 0;
            Vector<Point> vector = new Vector<Point>();
            for (int i = 0; i < 100; i++) {
                vector.add(new Point(1, 2));
            }
            Watch.Start();      
            for (int i = 0; i < 5000000; i++) {
                for (int j = 0; j < 100; j++) {
                    sum1 += vector.get(j).x;
                    sum2 += vector.get(j).y;
                }
            }
            Watch.Stop();
            Watch.PrintResult("Vector mit Point", sum1, sum2);
        }
        {
            sum1 = Watch.anticheat;
            sum2 = 0;
            List<Point> linkedlist = new LinkedList<Point>();
            for (int i = 0; i < 100; i++) {
                linkedlist.add(new Point(1, 2));
            }
            Watch.Start();
            for (int i = 0; i < 5000000; i++) {
                for (int j = 0; j < 100; j++) {
                    sum1 += linkedlist.get(j).x;
                    sum2 += linkedlist.get(j).y;
                }
            }
            Watch.Stop();
            Watch.PrintResult("LinkedList mit Point", sum1, sum2);
        }
        {
            sum1 = Watch.anticheat;
            sum2 = 0;
            int[][] twoDimArray = new int[100][2];
            for (int i = 0; i < 100; i++) {
                twoDimArray[i][0] = 1;
                twoDimArray[i][1] = 2;
            }
            Watch.Start();
            for (int i = 0; i < 5000000; i++) {
                for (int j = 0; j < 100; j++) {
                    sum1 += twoDimArray[j][0];
                    sum2 += twoDimArray[j][1];
                }
            }
            Watch.Stop();
            Watch.PrintResult("Ein zweidimensionales Array [100][2]", sum1, sum2);
        }
        {
            sum1 = Watch.anticheat;
            sum2 = 0;
            List<Point> arraylist = new ArrayList<Point>();
            for (int i = 0; i < 100; i++) {
                arraylist.add(new Point(1, 2));
            }
            Watch.Start();
            for (int i = 0; i < 5000000; i++) {
                for (int j = 0; j < 100; j++) {
                    sum1 += arraylist.get(j).x;
                    sum2 += arraylist.get(j).y;
                }
            }
            Watch.Stop();
            Watch.PrintResult("ArrayList mit Point", sum1, sum2);
        }
        {
            sum1 = Watch.anticheat;
            sum2 = 0;
            Point[] pointArray = new Point[100];
            for (int i = 0; i < 100; i++) {
                pointArray[i] = new Point(1, 2);
            }
            Watch.Start();
            for (int i = 0; i < 5000000; i++) {
                for (int j = 0; j < 100; j++) {
                    sum1 += pointArray[j].x;
                    sum2 += pointArray[j].y;
                }
            }
            Watch.Stop();
            Watch.PrintResult("Ein lineares Array mit Point", sum1, sum2);
        }
        {
            sum1 = Watch.anticheat;
            sum2 = 0;
            int[] dblAcc = new int[200];

            for (int i = 0; i < 5000000; i++) {
                for (int j = 0; j < 200; j += 2) {
                    dblAcc[j] = 1;
                    dblAcc[j+1] = 2;                    
                }
            }
            Watch.Start();
            for (int i = 0; i < 5000000; i++) {
                for (int j = 0; j < 200; j += 2) {
                    sum1 += dblAcc[j];
                    sum2 += dblAcc[j+1];
                }
            }
            Watch.Stop();
            Watch.PrintResult("Alternierender Zugriff auf lin. Array", sum1, sum2);
        }
        {
            sum1 = Watch.anticheat;
            sum2 = 0;
            int[] trueArrayX = new int[100];
            int[] trueArrayY = new int[100];

            for (int i = 0; i < 100; i++) {
                trueArrayX[i] = 1;
                trueArrayY[i] = 2;
            }
            Watch.Start();
            for (int i = 0; i < 5000000; i++) {
                for (int j = 0; j < 100; j++) {
                    sum1 += trueArrayX[j];
                    sum2 += trueArrayY[j];
                }
            }
            Watch.Stop();
            Watch.PrintResult("Zwei separate lineare Arrays abwechselnd", sum1, sum2);
        }
        {
            sum1 = Watch.anticheat;
            sum2 = 0;
            int[] linArray = new int[200];

            for (int i = 0; i < 200; i++) {
                linArray[i] = 1;
            }
            Watch.Start();
            for (int i = 0; i < 5000000; i++) {
                for (int j = 0; j < 200; j++) {
                    sum1 += linArray[j];
                }
            }
            Watch.Stop();
            Watch.PrintResult("Linearer Zugriff auf lineares Array", sum1, sum2);
        }

        System.out.println("|------------------------------------------|------------|--------------|");
        System.out.format(" Compiler anti cheat accumulator: %d%n", Watch.anticheat);
        System.out.println(" Fertig. Zum Beenden bitte die Eingabetaste betätigen.");
        System.in.read();

    }

}

Das stur lineare Abhandeln eines linearen Arrays (ganz unten), ist nur zu Vergleichszwecken aufgeführt, wobei ausnahmsweise immer nur ein Wert gelesen und in einem Ziel gespeichert wird (1:1). Alle anderen liefern zwei (wie Point) und speichern zwei (2:2), wie du es brauchst.

Du kannst dir ja mal deinen Teil dazu denken, wie es zu den Ergebnissen kommt. Warum speziell dieses zweidimensionale Array so schlecht abschneidet, sollte auf der Hand liegen, aber man rechnet nicht unbedingt damit. Es geht natürlich um eine weitere Indirektion, ähnlich wie bei ArrayList. Dass zwei Arrays schneller als eines sind, ist auch interessant.

[Stiller Leser]

Ob ich für die Nullstellen ein Array nehme oder eine Liste ist eigentlich nicht so relevant. Dazu ist der Aufruf viel zu selten. Hab das jetzt mal getestet. Es brachte 0,01 Millisekunden.
Denke, dass ist bei anderen Aufgaben vermutlich wichtiger. Wobei die ArrayList hier auch von der Bequemlichkeit keinen Vorteil bietet. Hier kommt bei beiden Versionen jeweils die nächste Position der Nullstelle, die ja nacheinander gespeichert sind. Also kommt bei beiden Versionen einfach nur Pos rein und dann rufe ich getx und gety auf.

Aber ist schon interessant zu sehen, was da für Unterschiede lauern.

Von der alten Version weiß ich, dass es besser ist, die Spalten zu nehmen, am besten noch sortiert.

Und lach, ich hab das gerade mal probiert. Brauchte bei der Initialisierung der Nullstellen ja nur y mit x tauschen.

Unglaublich, was dabei rauskommt -> Ein Durchgang 0,154 Millisekunden. 151600 Aufrufe. Bei x y sind es 4.015.800 Aufrufe. (Also jeweils bei 1000 Durchgängen)
D,h. es dürfte sich lohnen, zu ermitteln, wo die Nullstellen am besten stehen. Das ist dann zwar langsamer, als wenn ich das ganze per Augenschein mache. Es dürfte aber schneller sein, als wenn ich tatsächlich grundsätzlich von links nach rechts gehe und das ganze Zeilenweise bearbeite.

[Stiller Leser]

 Ermittle Zugriffszeiten, bitte warten...
|------------------------------------------|------------|--------------|
|  Datenstruktur (wird immer int gelesen)  |  Zugriffe  |     Zeit     |
|------------------------------------------|------------|--------------|
| Vector mit Point                         | 1000000000 | 50921,591 ms |
| LinkedList mit Point                     | 1000000000 | 48111,207 ms |
| Ein zweidimensionales Array [100][2]     | 1000000000 |  1653,860 ms |
| ArrayList mit Point                      | 1000000000 |  1565,029 ms |
| Ein lineares Array mit Point             | 1000000000 |  1137,475 ms |
| Alternierender Zugriff auf lin. Array    | 1000000000 |   841,819 ms |
| Zwei separate lineare Arrays abwechselnd | 1000000000 |   780,776 ms |
| Linearer Zugriff auf lineares Array      | 1000000000 |   806,007 ms |
|------------------------------------------|------------|--------------|
 Compiler anti cheat accumulator: 6284966960
 Fertig. Zum Beenden bitte die Eingabetaste betätigen.

 Ermittle Zugriffszeiten, bitte warten...|------------------------------------------|------------|--------------|
|  Datenstruktur (wird immer int gelesen)  |  Zugriffe  |     Zeit     |
|------------------------------------------|------------|--------------|
| Vector mit Point                         | 1000000000 | 20180,526 ms |
| LinkedList mit Point                     | 1000000000 | 15919,421 ms |
| Ein zweidimensionales Array [100][2]     | 1000000000 |   453,763 ms |
| ArrayList mit Point                      | 1000000000 |   494,899 ms |
| Ein lineares Array mit Point             | 1000000000 |   311,092 ms |
| Alternierender Zugriff auf lin. Array    | 1000000000 |   200,145 ms |
| Zwei separate lineare Arrays abwechselnd | 1000000000 |   359,482 ms |
| Linearer Zugriff auf lineares Array      | 1000000000 |   277,691 ms |
|------------------------------------------|------------|--------------|
 Compiler anti cheat accumulator: 2548143784
 Fertig. Zum Beenden bitte die Eingabetaste betätigen.

Das ist sehr interessant. Vor allem, dass die Verhältnisse untereinander so unterschiedlich sind. Z.B. Point mit ArrayList und Point mit eindimensionalen Array. Bei mir ist die Liste 59 Prozent langsamer, bei dir waren das um die 30, Zahl weiß ich nicht mehr, aber eben deutlich besseres Verhältnis, als bei mir. Bei dir sind die zwei separaten die schnellsten, bei mir der alternierende Zugriff.

[Whiz-zarD]

Die ArrayList ist im Grunde eine Neuimplementierung von Vector. Mit dem Unterschied, dass Vector threadsicher ist und ArrayList hingegen nicht.

Eine ArrayList verwendet intern ein Array und beim Hinzufügen neuer Elemente wird schaut, ob es noch groß genug ist und wenn nicht, wird ein neues Array erzeugt und die Elemente in das neue Array rüberkopiert und das alte gelöscht. Somit ist das hinzufügen von Elementen langsamer aber das Lesen ist genauso schnell, wie bei einem Array. Minimale Performanceverluste entstehen höchstens nur durch einen Overhead des Objektes.

Eine LinkedList ist eine verkettete Liste. Das hinzufügen geht hier schneller als bei einer ArrayList aber dafür ist der indexierte Zugriff langsamer, da immer von vorne angefangen werden muss zu zählen. Das Lesen über einen Iterator dürfte auch so schnell sein, wie bei einer ArrayList bzw. einem Array.

[jabu]

Kann gerne Messergebnisse anbringen, damit sich jeder sein eigenes Bild verschaffen möge:

 Ermittle Zugriffszeiten, bitte warten...
|---------------------------------------------|------------|--------------|
|  Datenstruktur (wird immer int gelesen)     |  Zugriffe  |     Zeit     |
|---------------------------------------------|------------|--------------|
| JIT-Aufwärmphase                            |  400000000 | 20553,026 ms |
| LinkedList<Point> per get(n).x und get(n).y | 1000000000 | 49457,365 ms |
| Vector<Point>     per get(n).x und get(n).y | 1000000000 |  7958,660 ms |
| ArrayList<Point>  per get(n).x und get(n).y | 1000000000 |  1569,531 ms |
| Point[100]        per x und y               | 1000000000 |  1127,172 ms |
| int[2][100]           per [0][n] und [1][n] | 1000000000 |   768,248 ms |
| int[100][2]           per [n][0] und [n][1] | 1000000000 |  1645,530 ms |
| int[200] alternierend per [n] und [n+1]     | 1000000000 |   846,452 ms |
| int[100] und int[100] abwechselnd           | 1000000000 |   783,917 ms |
| int[200] linear       per [n]               | 1000000000 |   812,161 ms |
| Integer[200] linear   per [n]               | 1000000000 |  1181,139 ms |
| ArrayList<Integer>    per get(n)            | 1000000000 |  2152,454 ms |
| ArrayList<Integer>    per Iterator          | 1000000000 |  2981,695 ms |
| LinkedList<Integer>   per Iterator          | 1000000000 |  4319,251 ms |
|---------------------------------------------|------------|--------------|
 Bei abwechselndem Lesen wurde immer in die zugehörige Koordinate kopiert (2 Ziele).
 Bei einzelnem Lesen wurde immer in dieselbe Koordinate kopiert (1 Ziel).
 Compiler anti cheat accumulator: 19838588785
 Fertig. Zum Beenden bitte die Eingabetaste betätigen.

Vector ist jetzt auch rechtzeitig optimiert, was vorher nicht der Fall gewesen ist (Vector kam am Anfang zu schnell dran).
Etwaige ineffiziente, effiziente sowie ähnliche und täuschend ähnliche Fälle sind nach wie vor absichtlich dabei, da es um den Lerneffekt geht (was ist ineffizient und warum?). Die Sache war daraus hervorgegangen, dass ursprünglich ziemlich oft zwei Koordinaten aus ArrayList<Koordinaten> (entspricht etwa ArrayList<Point>) gelesen wurden, weswegen hier x und y separat ausgelesen und separat gespeichert werden wie auch in den schnelleren Entsprechungen auf der Basis von int[]. Wo keine ersetzende Entsprechung von Point erfolgt (die fünf unteren Fälle), wird jeweils nur einmal gelesen und immer derselben Variable der Wert aufaddiert. Dort sieht man die Unterschiede noch deutlicher, weil der gemeinsame Overhead für die Dereferenzierung von x und y aus Point entfällt.

Ob ich für die Nullstellen ein Array nehme oder eine Liste ist eigentlich nicht so relevant. Dazu ist der Aufruf viel zu selten. Hab das jetzt mal getestet. Es brachte 0,01 Millisekunden.

Habe deinem Code mal hinzugefügt, was du hier weggelassen hast, sodass er bei mir funktioniert. Anscheinend stimmt das. Es fällt kaum ins Gewicht, was auch am Caching des Wertes liegen dürfte. Früher ist das ja mal anders gewesen. Allerdings bekomme ich es mit zwei statischen Arrays oder besser gleich mit einem statischen int[2][81] doch noch einen lohnenden Tick schneller hin, wogegen ein statisches ArrayList nichts brächte. Sobald der Kram schnell wird, fallen solche Kleinigkeiten doch auf.

Denke, dass ist bei anderen Aufgaben vermutlich wichtiger.

Ja, wenn es darum geht, viele Werte aus einem ArrayList möglichst schnell nacheinander zu verrechnen, dann kann das wohl zum Problem werden.

Von der alten Version weiß ich, dass es besser ist, die Spalten zu nehmen, am besten noch sortiert.

Bei dir sind Zeilen und Spalten andersherum benannt, als es bei mir wäre. Das will ich nicht problematisieren. Aber man sollte schon aufpassen, dass man beim ersten Test das Feld der natürlichen Reihenfolge der Arrayelemente nach durchgeht, denn es geht nur bei entweder Zeilen oder Spalten, nicht bei beiden. Und der frühe Vogel fängt hier den Wurm.

Und lach, ich hab das gerade mal probiert. Brauchte bei der Initialisierung der Nullstellen ja nur y mit x tauschen.

Je nachdem, wie du vorgegangen bist, müsstest du aufpassen, dass du das Sudoku nicht veränderst, denn die Initialisierung wirkt sich kaum aufs Tempo aus, weswegen mir das verdächtig erscheint. Es könnte auch mit anderen Werten gelöst sein.

Es könnte aber was gebracht haben, falls du zuvor die natürliche Reihenfolge verletzt hattest, also zwischen den einzelnen Arrays unnötigerweise hin- und hergesprungen bist. Der rechte Index sollte sich immer auf dasselbe Array beziehen, wenn ich das richtig in Erinnerung habe, weswegen es besser ist, wenn der sich aufeinanderfolgend ändert.

Eine andere Möglichkeit wäre, dass du vielleicht das ganze Brett auf einer um 90 ° gedrehten Basis gelöst und wieder zurückgederht haben könntest. Dann käme es natürlich auf das Brett an.

Unglaublich, was dabei rauskommt -> Ein Durchgang 0,154 Millisekunden. 151600 Aufrufe. Bei x y sind es 4.015.800 Aufrufe. (Also jeweils bei 1000 Durchgängen)
D,h. es dürfte sich lohnen, zu ermitteln, wo die Nullstellen am besten stehen. Das ist dann zwar langsamer, als wenn ich das ganze per Augenschein mache. Es dürfte aber schneller sein, als wenn ich tatsächlich grundsätzlich von links nach rechts gehe und das ganze Zeilenweise bearbeite.

Bei deinem Ansatz sollte sich das für viele richtig schwierige Sudokus lohnen. Deine Umsetzung ähnelt inzwischen meiner, wie ich sie am Anfang mal hatte, ziemlich stark. Doch meine musste von Anfang an keine Koordinaten holen. Aber auch das hat seinen Preis, denn von irgendwoher müssen sie ermitttelt werden, und das kostet auch Takte, sogar ziemlich viele... Deswegen könntest du meine Lösung mit dem Sortieren vielleicht noch unterbieten. Zumindest wenn viele Nullen am Anfang stehen und ich zu faul bin, das Brett automatisiert zu drehen, solltest du das ziemlich leicht schaffen.

Allerdings braucht dieses Sudoku, welches ich in deinem Code gefunden habe...

{
{0,0,2,0,7,0,9,4,0},
{9,0,1,0,0,0,0,0,0},
{0,7,3,9,8,0,0,0,6},
{0,0,4,5,0,7,0,0,8},
{6,3,0,0,9,0,0,0,0},
{0,0,0,1,0,0,3,0,0},
{0,9,0,4,5,6,0,7,3},
{0,0,0,0,0,0,0,8,1},
{0,0,0,0,1,3,0,0,0}
};

...bei meiner Lösung nur 64,5 µs (nicht Millisekunden), während Firefox und Visual Studio nebenherlaufen.

Inzwischen habe ich auch deine Java-Lösung bei mir ans Laufen gebracht (es fehlte etwas Code), bin bei 0,222 ms auf der Basis von 1000 Durchgängen, also dir viel zu dicht auf den Fersen, gemessen an meiner Hardware. Wie sieht denn dein Ermitteln von start_kx und start_ky aus?

Der Wert 3770 us bei mir bezog sich auf das von mir ganz unten gezeigte "Teuflisch (extrem)" (so schwierige hat zeit.de nicht), bei dem auch noch die Nullen ungünstig am Anfang stehen. Wenn ich das Brett äquivalent umstelle, drehe oder spiegele, ist es nur noch ein Bruchteil dessen.
Die Java-Lösung braucht dafür noch 10,7 ms (und mit längerem Warmup 10,0 ms), was mit knapp der dreifachen Zeit bereits ein sehr guter Wert ist. Ja, solche Sachen gehen mit Java schon ziemlich gut. Aber wehe, es geht um komplexe Anwendungen...

[Stiller Leser]

Habe deinem Code mal hinzugefügt, was du hier weggelassen hast, sodass er bei mir funktioniert. Anscheinend stimmt das. Es fällt kaum ins Gewicht, was auch am Caching des Wertes liegen dürfte. Früher ist das ja mal anders gewesen. Allerdings bekomme ich es mit zwei statischen Arrays oder besser gleich mit einem statischen int[2][81] doch noch einen lohnenden Tick schneller hin, wogegen ein statisches ArrayList nichts brächte. Sobald der Kram schnell wird, fallen solche Kleinigkeiten doch auf.

Aso, Tools und Zeitmesser habe ich nicht gepostet. Hab das irgendwann mal programmiert. Und man kann es immer wieder brauchen.

Bei dir sind Zeilen und Spalten andersherum benannt, als es bei mir wäre. Das will ich nicht problematisieren. Aber man sollte schon aufpassen, dass man beim ersten Test das Feld der natürlichen Reihenfolge der Arrayelemente nach durchgeht, denn es geht nur bei entweder Zeilen oder Spalten, nicht bei beiden. Und der frühe Vogel fängt hier den Wurm.

Je nachdem, wie du vorgegangen bist, müsstest du aufpassen, dass du das Sudoku nicht veränderst, denn die Initialisierung wirkt sich kaum aufs Tempo aus, weswegen mir das verdächtig erscheint. Es könnte auch mit anderen Werten gelöst sein.

Ja, eigentlich ist es falsch herum. Aber ich habe mir bei Arrays bei Java angewöhnt, das es umgekehrt laufen muss, weil die Arrays ja auch umgekehrt initialisiert werden.
Beim Sudoku brauchte ich gar nicht aufpassen. Ist wie gesagt bei der Initialisierung ein einfacher Tausch von x und y. Die Matrix an sich bleibt so wie sie ist. Die wird gar nicht verändert. Nur die Nullstellen sind in anderer Reihenfolge gespeichert.
Dafür braucht es lediglich zusätzlich eine zusätzliche For schleife, wo eben nach den Spalte für Spalte abgelaufen wird. Eigentlich könnte ich mir die auch sparen, weil es egal ist, ob ich die Matrix Zeile für Zeile einlese oder Spalte für Spalte. Jedenfalls wird dann lediglich statt
if(this.matrix[i][j]==0)nullstellen.add(new Koordinaten(i,j));
if(this.matrix[j][i]==0)nullstellen.add(new Koordinaten(j,i));

Das ist ja das gute mit den Nullstellen. Es ist völlig egal, wie ich die Nullstellen ablaufe. Ich könnte oben links anfangen, dann einen aus der Mitte nehmen und rechts unten weiter machen. Und hier kann man eben schauen, welche Reihenfolge gespeichert wird, weil man sie für günstig hält.

Es könnte aber was gebracht haben, falls du zuvor die natürliche Reihenfolge verletzt hattest, also zwischen den einzelnen Arrays unnötigerweise hin- und hergesprungen bist. Der rechte Index sollte sich immer auf dasselbe Array beziehen, wenn ich das richtig in Erinnerung habe, weswegen es besser ist, wenn der sich aufeinanderfolgend ändert.

Eine andere Möglichkeit wäre, dass du vielleicht das ganze Brett auf einer um 90 ° gedrehten Basis gelöst und wieder zurückgederht haben könntest. Dann käme es natürlich auf das Brett an.

Wie gesagt, die eigentliche Matrix bleibt unverändert. Da muss gar nichts gedreht werden, gespiegelt oder sonstwas. Es geht nur darum, in welcher Reihenfolge die Nullstellen bearbeitet werden und auch nur die müssen halt entsprechend der gewünschten Reihenfolge eingelesen werden.

Allerdings braucht dieses Sudoku, welches ich in deinem Code gefunden habe...

{
 {0,0,2,0,7,0,9,4,0},
 {9,0,1,0,0,0,0,0,0},
 {0,7,3,9,8,0,0,0,6},
 {0,0,4,5,0,7,0,0,8},
 {6,3,0,0,9,0,0,0,0},
 {0,0,0,1,0,0,3,0,0},
 {0,9,0,4,5,6,0,7,3},
 {0,0,0,0,0,0,0,8,1},
 {0,0,0,0,1,3,0,0,0}
 };

...bei meiner Lösung nur 64,5 µs (nicht Millisekunden), während Firefox und Visual Studio nebenherlaufen.

Glaube, damit fing es an. Irgendwann war mir das zu blöd und hab halt eben eine Eingabemaske erstellt, wo man in wenigen Sekunden jedes beliebige Sudoku einlesen kann. Muss oben weiter stehen. Das wird dann sogar noch als txt.datei gespeichert, so dass man beim nächsten mal noch aussuchen kann, ob man neu eingeben will oder laden.

Inzwischen habe ich auch deine Java-Lösung bei mir ans Laufen gebracht (es fehlte etwas Code), bin bei 0,222 ms auf der Basis von 1000 Durchgängen, also dir viel zu dicht auf den Fersen, gemessen an meiner Hardware. Wie sieht denn dein Ermitteln von start_kx und start_ky aus?

Da ist viel Rechnerei. Man muss ja einmal die Nummer der Matrix ermitteln und dann noch die Startwerte für die kleine Matrix. Es könnte tatsächlich schneller sein, hier statt die Matrix zu nutzen, wieder kleine Matrizen zur Verfügung zu stellen. Die Nummer muss ich trotzdem noch ermitteln, habe aber sofort Zugriff auf den Startwert.

[jabu]

Ich habe die Zitate nach dem Zusammenhang der Antworten sortiert:

Aso, Tools und Zeitmesser habe ich nicht gepostet. Hab das irgendwann mal programmiert. Und man kann es immer wieder brauchen.

Es ging mir um dieses, weil es für die Zeiten relevant ist:
Tools.get_zeile_aus_Matrix(...)
Tools.get_spalte_aus_Matrix(...)

Da ist viel Rechnerei. Man muss ja einmal die Nummer der Matrix ermitteln und dann noch die Startwerte für die kleine Matrix. Es könnte tatsächlich schneller sein, hier statt die Matrix zu nutzen, wieder kleine Matrizen zur Verfügung zu stellen. Die Nummer muss ich trotzdem noch ermitteln, habe aber sofort Zugriff auf den Startwert.

Viel Rechnerei? Dazu sind wird doch zu faul. Gurte anlegen und festhalten :

final int start_kx = x / 3 * 3;
final int start_ky = y / 3 * 3;

Na, was bringt's? Ich habe da gar kein externes Caching drin (Zugriff wäre voraussichtlich zu langsam), nur über die lokalen Variablen, wobei nicht mal das nötig wäre.

Beim Sudoku brauchte ich gar nicht aufpassen. Ist wie gesagt bei der Initialisierung ein einfacher Tausch von x und y. Die Matrix an sich bleibt so wie sie ist. Die wird gar nicht verändert. Nur die Nullstellen sind in anderer Reihenfolge gespeichert.
[...]
Jedenfalls wird dann lediglich statt
if(this.matrix[i][j]==0)nullstellen.add(new Koordinaten(i,j));
if(this.matrix[j][i]==0)nullstellen.add(new Koordinaten(j,i));
[...]
Das ist ja das gute mit den Nullstellen. Es ist völlig egal, wie ich die Nullstellen ablaufe. Ich könnte oben links anfangen, dann einen aus der Mitte nehmen und rechts unten weiter machen. Und hier kann man eben schauen, welche Reihenfolge gespeichert wird, weil man sie für günstig hält.

Ich hatte vorsichtshalber gefragt, weil man sich leicht vertun könnte. Einige Zweifel hast du ausgeräumt, klingt gut. Aber falls du nur den hier gezeigten Teil geändert hast, dann hast du ein (verdammt leicht zu übersehendes) Problem:

for(int i=0;i<zeilen;i++)
    for(int j=0;j<spalten;j++){
        this.matrix[i][j]=matrix[i][j];
        if(this.matrix[j][i]==0)
            nullstellen.add(new Koordinaten(j,i));
    }

Schau dir mal an, welche Matrix abgefragt wird. Ist die wirklich schon für alle [j][i] befüllt?
Hier ist das nicht garantiert. Demnach bekämest du viele falsche Nullstellen, mit der Folge, dass früher oder später vordefinierte Positionen überschrieben werden. Gut, vielleicht hast du weiter oben etwas angepasst, kann ich nicht wissen.

Ja, eigentlich ist es falsch herum. Aber ich habe mir bei Arrays bei Java angewöhnt, das es umgekehrt laufen muss, weil die Arrays ja auch umgekehrt initialisiert werden.

Hauptsache, du weißt, wie sie effizient abgearbeitet werden (worum es mir ging, nicht um deinen Code an sich, den kannst du selber daraufhin abklopfen):

Bei Java gibt es (anders als bei C oder C++) keine zweidimensionalen Arrays, sondern Konstrukte, die so ähnlich aussehen, nämlich eindimensionale Arrays, welche Referenzen an weitere eindimensionale Arrays halten, die ohne aneinander anknüpfen zum müssen, im Speicher liegen. Die referenzierten Arrays müssen nicht mal gleich groß sein, da es einzelne Arrays sind (anstatt ein mehrdimensionales, was zusammenhängender Speicher wäre). Hier wird das veranschaulicht.

In der Regel ist es schneller, die Arrays einzeln nacheinander komplett durchzugehen, anstatt zwischen mehreren zu springen. Aber ich konnte zeigen, dass es bei zwei Arrays (bzw. einem "zweidimensionalen" Array mit nur zwei Arrays) nicht immer so ist. Denn moderne Compiler und CPUs können solche unabhängigen Zugriffe, bei denen die Reihenfolge egal ist, manchmal optimieren. Aber ab drei Arrays sollte es schon nichts mehr bringen, vermute ich mal vorsichtig (hier sind es bis zu neun). Bei dir war ja die lineare Abarbeitung sowieso immer schneller, was daran liegen könnte, dass bei dir eine Optimierung nicht greift. Ich verwende derzeit (noch) das jdk1.8.0_161 in der 64-Bit-Ausführung und als JRE die darin enthaltene.

Was von alldem längst bekannt ist, darf gerne ignoriert werden (möchte nicht nerven).

Glaube, damit fing es an. Irgendwann war mir das zu blöd und hab halt eben eine Eingabemaske erstellt, wo man in wenigen Sekunden jedes beliebige Sudoku einlesen kann. Muss oben weiter stehen. Das wird dann sogar noch als txt.datei gespeichert, so dass man beim nächsten mal noch aussuchen kann, ob man neu eingeben will oder laden.

Ja, warum nicht.

Whiz-zarD hat Recht damit, dass ArrayList ein Array kapseln soll. Meistens ist das schnell genug, aber ich merke den Vorteil von einem statischen int[2][81] doch schon. Bei einer Sprache ohne ausreichende Wertsemantik ist das nicht verwunderlich. Da sind einfach zu viele Verweise und zu viel zusammenhangloser Speicher beteiligt, so gut der JIT-Compiler auch vorgehen mag.

[Stiller Leser]

Ich habe die Zitate nach dem Zusammenhang der Antworten sortiert:
Es ging mir um dieses, weil es für die Zeiten relevant ist:
Tools.get_zeile_aus_Matrix(...)
Tools.get_spalte_aus_Matrix(...)
Viel Rechnerei? Dazu sind wird doch zu faul. Gurte anlegen und festhalten :

final int start_kx = x / 3 * 3;
 final int start_ky = y / 3 * 3;

Die Tücke liegt im Detail. Ich kann da sicher noch ein wenig Zeit rausholen. Aber ich lass das so. Du hast ja gesehen, was ich alles übergebe. Das Problem ist, dass diese Methoden das x und das y einer beliebigen kleinen Matrix in einer beliebigen großen Matrix benennt. Die einzige Bedingung ist, dass die kleinen Matrizen so reinpassen müssen, dass es aufgeht. Beispielsweise ich habe eine 8x8 Matrix. Da könnte ich vier 4x4 Matrizen reinpacken oder auch vier 8x2 Matrizen, usw.. Ich weiß gar nicht mehr, für was ich das damals geschrieben habe. Aber es funktioniert halt und prüft auch gleich, ob die Matrizen zulässig sind und hat noch diverse andere Sicherheitsprüfungen.

Ich hatte vorsichtshalber gefragt, weil man sich leicht vertun könnte. Einige Zweifel hast du ausgeräumt, klingt gut. Aber falls du nur den hier gezeigten Teil geändert hast, dann hast du ein (verdammt leicht zu übersehendes) Problem:

for(int i=0;i<zeilen;i++)
     for(int j=0;j<spalten;j++){
         this.matrix[i][j]=matrix[i][j];
         if(this.matrix[j][i]==0)
             nullstellen.add(new Koordinaten(j,i));
     }

Schau dir mal an, welche Matrix abgefragt wird. Ist die wirklich schon für alle [j][i] befüllt?
Hier ist das nicht garantiert. Demnach bekämest du viele falsche Nullstellen, mit der Folge, dass früher oder später vordefinierte Positionen überschrieben werden. Gut, vielleicht hast du weiter oben etwas angepasst, kann ich nicht wissen.

Nein, nur diese beiden Werte. Und es ist tatsächlich für alles weitere egal. Ich glaube, Du hast das noch nicht richtig verstanden.

Du hast die Matrix 9x9, die mit Werten gefüllt ist.
Na dieser wird gearbeitet. Dort wird geändert.

01234
10234
12345
12340
12034

gespeichert wird der Punkt als x und y wert. x geht in dem fall bei mir von oben nach unten, eben Zeilen. und y von links nach rechts, eben Spalten.

der erste wert mit einer 0 ist in diesem Beispiel [0][0], der zweite [1][1], der vierte wert wäre [4][2]. Dran denken: IMMER ist der erste Wert x und der zweite Wert y.

this.matrix[i][j]=matrix[i][j];
if(this.matrix[j][i]==0) //ok, hier ist noch eine Änderung, tatsächlich steht da if(matrix[j][i]==0) . Das musste natürlich geändert werden, weil die Matrix der Klasse noch nicht besetzt ist. Aber wir haben ja die übergebene Matrix, wo das gleiche drinsteht in der gleichen Reichenfolge. Macht also keinen Unterschied.
nullstellen.add(new Koordinaten(j,i));

Wenn ich das ganze zeilenweise bearbeite, habe ich 0-0, 1-1, 4-4, 4-2.
Mache ich das ganze über spalten, habe ich 0-0, 1-1, 4-2, 4-4. Mache ich wilde Sau, habe ich 4-2, 1-1, 4-4, 0-0
Immer steht die erste Zahl für x und die zweite Zahl für y.
Und die wird Koordinate für Koordinate in der Reihenfolge bearbeitet, wie sie abgespeichert ist.

Aber ok, falls Du den Hinweis meinst, dass this.matrix u.U. bei dem Wert noch gar nicht besetzt ist, hast Du natürlich recht. Diese Änderung hab ich vergessen zu erwähnen. Vermutlich deshalb, weil ich einfach nur die übergebene Matrix nehmen musste, es also im Prinzip keinerlei Unterschied macht.

Hauptsache, du weißt, wie sie effizient abgearbeitet werden (worum es mir ging, nicht um deinen Code an sich, den kannst du selber daraufhin abklopfen):

Bei Java gibt es (anders als bei C oder C++) keine zweidimensionalen Arrays, sondern Konstrukte, die so ähnlich aussehen, nämlich eindimensionale Arrays, welche Referenzen an weitere eindimensionale Arrays halten, die ohne aneinander anknüpfen zum müssen, im Speicher liegen. Die referenzierten Arrays müssen nicht mal gleich groß sein, da es einzelne Arrays sind (anstatt ein mehrdimensionales, was zusammenhängender Speicher wäre). Hier wird das veranschaulicht.

In der Regel ist es schneller, die Arrays einzeln nacheinander komplett durchzugehen, anstatt zwischen mehreren zu springen. Aber ich konnte zeigen, dass es bei zwei Arrays (bzw. einem "zweidimensionalen" Array mit nur zwei Arrays) nicht immer so ist. Denn moderne Compiler und CPUs können solche unabhängigen Zugriffe, bei denen die Reihenfolge egal ist, manchmal optimieren. Aber ab drei Arrays sollte es schon nichts mehr bringen, vermute ich mal vorsichtig (hier sind es bis zu neun). Bei dir war ja die lineare Abarbeitung sowieso immer schneller, was daran liegen könnte, dass bei dir eine Optimierung nicht greift. Ich verwende derzeit (noch) das jdk1.8.0_161 in der 64-Bit-Ausführung und als JRE die darin enthaltene.

Ich weiß gerade nicht genau, welche Version ich nutze. Ok, 64 Bit, das ist klar. Die Achter habe ich auch, aber dahinter müsste ich heute Abend mal schauen. Und mit dem Optimieren des Compilers, da habe ich bisher ehrlich gesagt so gut wie nichts gemacht. Es war mehr oder weniger nicht nötig. Auch hier ist es eigentlich irrelevant, weil das Lösen doch sehr schnell geht. Selbst bei meiner ursprünglichen Lösung war es eigentlich noch hinreichend schnell. Aber es macht natürlich Spaß, zu sehen, wie man sowas verbessern kann. Wobei ich ein wenig enttäuscht bin, dass plumpes Probieren deutlich schneller funktioniert, als eine Lösung, die versucht tatsächlich das Problem zu lösen, also mit Logik rangeht.
EDIT: Hatte die die Version 1.7 genutzt. Habe jetzt mal die aktuelle Version runtergeladen. Also ab jetzt die 10.0.1

Was von alldem längst bekannt ist, darf gerne ignoriert werden (möchte nicht nerven).

Das sag ich dann schon.

Whiz-zarD hat Recht damit, dass ArrayList ein Array kapseln soll. Meistens ist das schnell genug, aber ich merke den Vorteil von einem statischen int[2][81] doch schon. Bei einer Sprache ohne ausreichende Wertsemantik ist das nicht verwunderlich. Da sind einfach zu viele Verweise und zu viel zusammenhangloser Speicher beteiligt, so gut der JIT-Compiler auch vorgehen mag.

ArrayList ist halt sehr bequem. Ich denke, hier kann man ja sehr schön sehen, dass man es ruhig nutzen kann, weil die Geschwindigkeitsvorteile nicht wirklich Vorteile sind bei diesem Problem. Ok, bei einem Wettrennen wäre es wichtig. Aber ich denke, wir sind uns einig, dass das Problem an sich rasend schnell gelöst wird und darum geht es ja eigentlich. Wenn man nun wirklich zeitintensive Dinge hat, lohnt es sich bestimmt, drüber nachzudenken, nach Alternativen zu schauen.

[jabu]

Nein, nur diese beiden Werte. Und es ist tatsächlich für alles weitere egal. Ich glaube, Du hast das noch nicht richtig verstanden.

Danke für deine Mühen, die Indizes zu erklären, aber das ist schon klar. Sonst wäre mir der kleine Bug (ist keine Kritik) wohl nicht aufgefallen.

Dass die Reihenfolge der Abarbeitung sich nicht auf das Ergebnis auswirkt, ist eine von dir klar kommunizierte Voraussetzung und deinem Code auch leicht anzusehen. Das müssen wir nicht extra mühsam abhandeln, da sind wir uns einig.

Ich stehe zwar manchmal (gerade bei der Hitze [Bild: igitt.gif]) ordentlich auf dem Schlauch, aber irgendwann hat sich das glücklicherweise immer wieder gelegt, sodass normalerweise (man weiß ja nie...) ein mehr oder minder zarter Wink genügen sollte, wenn du mal den Eindruck hast, dass es bei mir nötig ist (damit du weniger Arbeit hast).

Natürlich ist es rein von der äußeren Logik her gleichwertig, ob du die große Matrix um 90 ° drehst und zurückdrehst (was ein Austauschen von Indizes implizit bewirken kann, ohne dass man davon überhaupt was sieht) oder ob man mit der Reihenfolge der Nullstellen so verfährt, dass diese wie bei einem um 90 ° gedrehten Brett umsortiert sind. Dass du Letzteres gemacht hast, wusste ich vor deinem vorletzten Beitrag nicht. Viele Wege führen nach Rom, und da frage ich gerne mal nach, damit ich die Voraussetzungen weiß, unter denen du gemessen hast, denn darum ging es mir.

Und so ganz sicher, ob das bugfrei geschehen ist, war ich mir auch nicht, denn Murphy hat auch hier zugeschlagen, wie du nun beim Problem des noch teils unbefüllten Arrays sehen musstest und was man, ganz nach guter Sitte Murphys, erst mitbekommt, nachdem man schon auf dem Mond gelandet ist – äh, x Sudokus, wo es sich nicht auswirkt, den Schneid abgekauft hat...

Es ging also um Kenntnis der Voraussetzungen (die unter Murphy nicht stimmen müssen). Sonst wüsste dich deine Zeitangabe nicht einzuordnen. Und es ging darum, dass du dich wegen Murphy nicht später ärgern musst, denn der zeigt sich bekanntlich im unpassendsten Moment.

Ich weiß gerade nicht genau, welche Version ich nutze. Ok, 64 Bit, das ist klar. Die Achter habe ich auch, aber dahinter müsste ich heute Abend mal schauen.

Wenn du weißt, dass du die Achter mit 64-Bit verwendest, dann sollte es wohl an der CPU liegen.

Und mit dem Optimieren des Compilers, da habe ich bisher ehrlich gesagt so gut wie nichts gemacht. Es war mehr oder weniger nicht nötig. Auch hier ist es eigentlich irrelevant, weil das Lösen doch sehr schnell geht. Selbst bei meiner ursprünglichen Lösung war es eigentlich noch hinreichend schnell. Aber es macht natürlich Spaß, zu sehen, wie man sowas verbessern kann.

Hier habe auch ich nichts mit den Parametern gemacht, aber früher manchmal interessehalber und schon notgedrungen wegen der durchweg schlechten Leistung der meisten komplexen Java-Programme. Wenn ich Standardwerte verändere, dann sage ich das natürlich.

Wobei ich ein wenig enttäuscht bin, dass plumpes Probieren deutlich schneller funktioniert, als eine Lösung, die versucht tatsächlich das Problem zu lösen, also mit Logik rangeht.

Die Sudokus, die wir bisher hatten, sind schlicht alle viel zu einfach (von Eseln wie mir mit etwas Mühe lösbar). Und damit zusätzliche Logik etwas bringt, muss sie schnell genug implementiert sein.

Ich habe inzwischen Sudokus gefunden, wie es auch zu erwarten war, die viel länger brauchen (bisher bis zu 5,1 s), aber die nicht mehr von Menschen erstellt oder gelöst werden können. Das schwierigste von einem Menschen erstellte, das mir bisher untergekommen ist, braucht immerhin 296 ms. So viel, dass man das auf richtig gute Werte bekommt, sollte man wohl an einem Brute Force-Algorithmus gar nicht mehr verbessern können. Dennoch gibt es auch bei meinen noch einige Verbesserungsmöglichkeiten.

Du musst also nicht enttäuscht sein! Die Enttäuschung bezieht sich nur auf Sudokus, die Esel wie ich vielleicht noch an einem Feierabend schaffen können. Aber bei geringerer Vorbelegung wendet sich das Blatt sehr schnell. Im Netz lassen sich schwierigere finden:

0,0,0,  0,8,1,  0,0,0,
4,0,0,  0,0,0,  2,0,0,
0,0,0,  0,0,0,  0,0,0,
                    
0,8,3,  0,0,0,  0,0,7,
0,0,0,  2,0,0,  4,0,0,
0,0,0,  0,0,0,  0,0,0,
                    
2,4,0,  5,0,0,  0,6,0,
0,0,0,  0,7,0,  0,3,8,
9,0,0,  0,0,0,  0,0,0

Recursions: 80616105

Einem Menschen ist das wohl nicht mehr zuzumuten. Bei mir dauert es 5,1 Sekunden (und mit Vertauschen des oberen und unteren Zeilenblocks knapp 2 Sekunden), was bei mir das bisherige Maximum ist. Es dürfte wohl maßgeblich an der geringen Anzahl an Vorgaben liegen.

Hier sollte es sich lohnen, wenigstens eine Vorsortierung vorzunehmen. Vermutlich sind hier längst Mengenoperationen in Verbindung mit Wahrscheinlichkeitsbetrachtungen hilfreich. Das war eigentlich mein Ansatz, aber als ich sah, wie schnell für Menschen nur noch sehr schwer lösbare Rätsel durch Probieren lösbar sind, erschien mir das als zu aufwendig, zumindest für den Anfang und mal eben nebenher.

Die Tücke liegt im Detail. Ich kann da sicher noch ein wenig Zeit rausholen. Aber ich lass das so.

Ich wollte dir auch gar nichts aufdrängen, sondern nur zeigen, wie verblüffend einfach es manchmal sein kann:

Du hast ja gesehen, was ich alles übergebe. Das Problem ist, dass diese Methoden das x und das y einer beliebigen kleinen Matrix in einer beliebigen großen Matrix benennt. Die einzige Bedingung ist, dass die kleinen Matrizen so reinpassen müssen, dass es aufgeht. Beispielsweise ich habe eine 8x8 Matrix. Da könnte ich vier 4x4 Matrizen reinpacken oder auch vier 8x2 Matrizen, usw..

Das leisten diese beiden Zeilen ebenfalls (sonst hätte ich mein breites Grinsen unterlassen), unter der Bedingung, dass die x- und y-Werte schön bei Null anfangen. Vielleicht möchtest du sie dir doch noch einmal angucken. Die richtigen Zahlen per Variablen einzusetzen, sollte doch kein Problem sein. Du brauchst nur die jeweilige Dimension einzusetzen, bei einer 8x2-Matrix also (oder umgekehrt, je nachdem was x und was y ist):

final int start_kx = x / 8 * 8;
final int start_ky = y / 2 * 2;

Das unbegrenzte Kacheln (hier innerhalb von int) ergibt sich ganz von selbst. Und einen Überlauf kann es gar nicht geben, solange du nichts Ungültiges eingibst. Bei dir wird ja auch immer was zurückgegeben, weshalb auch bei dir vorausgesetzt wird, dass die Eingaben stimmen (damit kein Unsinn im Algorithmus landet). Wie groß die äußere Matrix ist, ist egal. Nur negative Werte darfst du nicht eingeben, weil die folgerichtig Spiegelung anstatt Fortsetzung hervorrufen würden (es sei denn, der Rest würde sich ebenfalls an den Nullachsen spiegeln).

Ich weiß gar nicht mehr, für was ich das damals geschrieben habe. Aber es funktioniert halt und prüft auch gleich, ob die Matrizen zulässig sind und hat noch diverse andere Sicherheitsprüfungen.

Gut, Zulässigkeit in einem wie auch immer gearteten äußeren Kontext prüft dieses nicht, aber es ist immerhin für sich genommen korrekt, weshalb sich ein Prüfen wenigstens dieses Ausdrucks erübrigt.

[Stiller Leser]

Die Sudokus, die wir bisher hatten, sind schlicht alle viel zu einfach (von Eseln wie mir mit etwas Mühe lösbar). Und damit zusätzliche Logik etwas bringt, muss sie schnell genug implementiert sein.

Ich habe inzwischen Sudokus gefunden, wie es auch zu erwarten war, die viel länger brauchen (bisher bis zu 5,1 s), aber die nicht mehr von Menschen erstellt oder gelöst werden können. Das schwierigste von einem Menschen erstellte, das mir bisher untergekommen ist, braucht immerhin 296 ms. So viel, dass man das auf richtig gute Werte bekommt, sollte man wohl an einem Brute Force-Algorithmus gar nicht mehr verbessern können. Dennoch gibt es auch bei meinen noch einige Verbesserungsmöglichkeiten.

Du musst also nicht enttäuscht sein! Die Enttäuschung bezieht sich nur auf Sudokus, die Esel wie ich vielleicht noch an einem Feierabend schaffen können. Aber bei geringerer Vorbelegung wendet sich das Blatt sehr schnell. Im Netz lassen sich schwierigere finden:

0,0,0,  0,8,1,  0,0,0,
4,0,0,  0,0,0,  2,0,0,
0,0,0,  0,0,0,  0,0,0,
                    
0,8,3,  0,0,0,  0,0,7,
0,0,0,  2,0,0,  4,0,0,
0,0,0,  0,0,0,  0,0,0,
                    
2,4,0,  5,0,0,  0,6,0,
0,0,0,  0,7,0,  0,3,8,
9,0,0,  0,0,0,  0,0,0

Recursions: 80616105

Einem Menschen ist das wohl nicht mehr zuzumuten. Bei mir dauert es 5,1 Sekunden (und mit Vertauschen des oberen und unteren Zeilenblocks knapp 2 Sekunden), was bei mir das bisherige Maximum ist. Es dürfte wohl maßgeblich an der geringen Anzahl an Vorgaben liegen.

Hier sollte es sich lohnen, wenigstens eine Vorsortierung vorzunehmen. Vermutlich sind hier längst Mengenoperationen in Verbindung mit Wahrscheinlichkeitsbetrachtungen hilfreich. Das war eigentlich mein Ansatz, aber als ich sah, wie schnell für Menschen nur noch sehr schwer lösbare Rätsel durch Probieren lösbar sind, erschien mir das als zu aufwendig, zumindest für den Anfang und mal eben nebenher.

Hm, das verwundert mich jetzt doch. Ein Durchgang 116,3 ms. Die Zeit habe ich über die 0 Nullstellen nach Spalten. Mache ich das ganze nach Zeilen, dauert es deutlich länger. Hier habe ich jetzt nur 10 Durchgänge genommen, weil es mir zu lange dauerte. Ein Durchgang wäre dann bei 3,85 Sekunden. Ich werde morgen mal schauen, ob ich das mit den nullstellen zeitgünstig optimieren kann.

Das leisten diese beiden Zeilen ebenfalls (sonst hätte ich mein breites Grinsen unterlassen), unter der Bedingung, dass die x- und y-Werte schön bei Null anfangen. Vielleicht möchtest du sie dir doch noch einmal angucken. Die richtigen Zahlen per Variablen einzusetzen, sollte doch kein Problem sein. Du brauchst nur die jeweilige Dimension einzusetzen, bei einer 8x2-Matrix also (oder umgekehrt, je nachdem was x und was y ist):

final int start_kx = x / 8 * 8;
final int start_ky = y / 2 * 2;

Das unbegrenzte Kacheln (hier innerhalb von int) ergibt sich ganz von selbst. Und einen Überlauf kann es gar nicht geben, solange du nichts Ungültiges eingibst. Bei dir wird ja auch immer was zurückgegeben, weshalb auch bei dir vorausgesetzt wird, dass die Eingaben stimmen (damit kein Unsinn im Algorithmus landet). Wie groß die äußere Matrix ist, ist egal. Nur negative Werte darfst du nicht eingeben, weil die folgerichtig Spiegelung anstatt Fortsetzung hervorrufen würden (es sei denn, der Rest würde sich ebenfalls an den Nullachsen spiegeln).


Gut, Zulässigkeit in einem wie auch immer gearteten äußeren Kontext prüft dieses nicht, aber es ist immerhin für sich genommen korrekt, weshalb sich ein Prüfen wenigstens dieses Ausdrucks erübrigt.

Die Rückgabe müsste ich eigentlich prüfen. Statt einer exception schmeißt er -1 bei fehlerhafte Eingabe zurück. Er prüft, ob die kleine Matrix funktioniert und es wird geprüft, ob x und y innerhalb der Indizes liegt. Die Rechnung selbst ist auch sehr kurz. Ich mache das mit modulo.

[jabu]

Hm, das verwundert mich jetzt doch. Ein Durchgang 116,3 ms. Die Zeit habe ich über die 0 Nullstellen nach Spalten. Mache ich das ganze nach Zeilen, dauert es deutlich länger. Hier habe ich jetzt nur 10 Durchgänge genommen, weil es mir zu lange dauerte. Ein Durchgang wäre dann bei 3,85 Sekunden.

Das hatte ich noch nicht probiert. Es ist bei mir derselbe Effekt, dauert nur, ungefähr dem System entsprechend, bei deiner (und von mir geringfügig angepassten) Java-Lösung jeweils ca. dreimal so lange wie bei dir (wobei auffällt, dass bei mehr Rekursionen der Abstand steigt, was an den mickrigen CPU-Caches bei mir liegen könnte).

Das nennt man dummes Glück oder Pech, je nachdem, wie man es betrachtet.

Ich werde morgen mal schauen, ob ich das mit den nullstellen zeitgünstig optimieren kann.

Bringt garantiert was. Ich hatte nämlich heute einen Copy-&-Paste-Fehler gemacht, als ich versuchsweise den unteren Dreierzeilenblock mit dem oberen austauschen wollte. Da hatte ich den einen verschoben und den anderen nicht. 2 s ist zu schlecht. Das Ergebnis bei meiner Lösung und dem lezten Sudoku: Von nun 4,9 s runter auf 2,1 ms, was noch krasser als beim Drehen (indirekt über die Nullstellen) ist. Die Idee war zwar trivial, aber nicht verkehrt, weil unten acht Werte vorgegeben sind. Also ist das Sudoku, zumindest für die Maschine, doch keine besondere Herausforderung (weil das Umstellen mit zu geringem Aufwand automatisch abschätz- und durchführbar wäre). Von 4,9 s auf 2,1 ms durch eine fast dümmstmögliche Operation zu kommen, könnte schon wieder demotivieren, wenn man idealistisch herangeht.

Gut, eines habe ich jetzt noch, soll angeblich das schwierigste bisher bekannte Sudoku sein, wobei ich vermute, dass es nicht das schwierigste ist, sondern lediglich das schwierigste, welches ohne maschinelle Hilfsmittel erstellt wurde. Aber das ist nur eine reine Vermutung. Hier ist es (erstellt von David Filmer) und von hier stammt es (hier gefunden):

6, 0, 0,   0, 0, 8,   9, 4, 0,
9, 0, 0,   0, 0, 6,   1, 0, 0,
0, 7, 0,   0, 4, 0,   0, 0, 0,

2, 0, 0,   6, 1, 0,   0, 0, 0,
0, 0, 0,   0, 0, 0,   2, 0, 0,
0, 8, 9,   0, 0, 2,   0, 0, 0,

0, 0, 0,   0, 6, 0,   0, 0, 5,
0, 0, 0,   0, 0, 0,   0, 3, 0,
8, 0, 0,   0, 0, 1,   6, 0, 0

Da sieht die Reihenfolge bereits allgemein günstig aus. Trotzdem dauert es bei meiner Lösung zeilenweise stolze 296 ms. Ich weiß nicht, ob du ohne Vorerfahrung etwas erkennen kannst, was helfen könnte. Ich sehe da erst mal wenig. Also könnte das vielleicht ein motivierender Kandidat sein.

Die Rückgabe müsste ich eigentlich prüfen. Statt einer exception schmeißt er -1 bei fehlerhafte Eingabe zurück. Er prüft, ob die kleine Matrix funktioniert und es wird geprüft, ob x und y innerhalb der Indizes liegt. Die Rechnung selbst ist auch sehr kurz. Ich mache das mit modulo.

Modulo habe ich bei meiner Lösung auch dabei, sogar zu oft. Davon etwas ohne Nachteil eliminieren zu können, wäre hilfreich.

[Stiller Leser]

Man muss aufpassen, dass das Raussuchen der Nullstellen selbst nicht zu lange dauert. Bei meiner alten Version habe ich Gewinne gehabt, indem ich Zeilen und Spalten zusammengetan habe und dort jeweils die besten Stellen genommen habe. Habe ich die Matrizen noch hinzugenommen, hat es sich verschlechtert, weil die eben zusätzlichen Aufwand benötigen.

Man stellt die Fehlstellen pro Zeile und Spalte fest und nimmt dann in der Nullstellenliste jeweils nacheiner von den besten zu den schlechten Nullstellen auf.
Möglich wäre auch eine Komplettbetrachtung. Also bei jeder Zelle mit 0 wird die Anzahl der Fehlstellen geprüft und dann eben nach der Reihenfolge bearbeitet. Auch das habe ich schon im anderen Code dabei. Mal sehen.

---
Naja, mit Modulo ist es halt x%Anzahl Matrizen in Zeilen und y%Anzahl Matrizen in Spalte.

EDIT:
So könnte ich mir das vorstellen:

Koordinaten [] nullstellen;


Konstruktor:
int [] besetzt_zeilen=new int[9];
int [] besetzt_spalten=new int[9];
int [] besetzt_nullstellen;

for(int i=0;i<9;i++)
 for(int j=0;j<9;j++){
 if(matrix[i][j]!=0)besetzt_zeilen[i]++;
 if(matrix[j][i]!=0)besetzt_spalten[i]++;
 }
for(int i=0;i<nullstellen.length;i++)besetzt_nullstellen[i]=besetzt_zeilen[nullstellen[i].getx()]+besetzt_spalten[nullstellen[i].gety()];
int hilf;
Koordinaten hilf2;
        for (int i = 0; i < besetzt_nullstellen.length; i++) { 
            for (int j = besetzt_nullstellen.length-1; j > 0; j--) { 
                if (besetzt_nullstellen[j-1] > besetzt_nullstellen[j]) { 
                    hilf = besetzt_nullstellen[j]; 
                    nullstellen_besetzt[j] = nullstellen_besetzt[j - 1]; 
                    nullstellen_besetzt[j - 1] = hilf; 
      hilf2=nullstellen[j];
                    nullstellen[j] = nullstellen[j - 1]; 
                    nullstellen[j - 1] = hilf2; 
                } 
            }

Mal auf die Schnelle reingehackt. Das ab Konstruktor müsste noch in den Konstruktur. Natürlich müssen die Arrays noch von der Größe her klar gemacht werden und ggf. initialisiert werden. Jedenfalls hätten wir nach diesem Zirkus die Nullstellen nach den vorhandenen Elementen in Zeilen und Spalten sortiert.

[Stiller Leser]

Also es funktioniert. Aber das Sortieren dauert. Es ist schneller, als meine Zeilenlösung, aber deutlich langsamer als meine Spaltenlösung. => 954 ms

[jabu]

Diese Antwort wurde schon vor deinem letzten Beitrag angefangen (schön, dass es funktioniert, wegen Tempo, siehe unten):

Naja, mit Modulo ist es halt x%Anzahl Matrizen in Zeilen und y%Anzahl Matrizen in Spalte.

Wenn ich Anzahl=8 3x3-Matrizen nebeneinander habe und x=15 einwerfe, dann kommt 15%8=7 heraus. Vielleicht meinst du etwas anderes. Falls du x%Weite_je_Matrix meinst, dann liegt der Nutzen auf der Hand, weil das die Position innerhalb der Matrix in x-Richtung ist.

Das ist bei linearem Speicher nützlich, um die Startposition der (imaginären) Spalte zu bestimmen, was dem x-Offset innerhalb einer (ebenfalls imaginären) Zeile entspricht. Denn ich erspare mir das Einteilen in Zeilen und Spalten, weswegen die eben imaginär sind. Das bringt enorme Vorteile bei der Effizienz (ein Nutzen: die Schleifen konnte ich deswegen abschaffen), aber hat auch Nachteile, weil immerhin dieses (zumindest noch) nötig ist:

const tint rowStart = static_cast<tint>(pos / 9 * 9);
const tint colStart = static_cast<tint>(pos % 9);
const tint divStart = static_cast<tint>((pos / 27 * 27) + (pos % 9) - (pos % 3));

tint ist nur ein anderer Name für den Ganzzahlentyp, damit ich ihn bequem austauschen kann. Der Cast ist nur für den Fall gedacht, dass sizeof(tint) < sizeof(pos) ist. Das sind die drei Startwerte im linearen Speicher (angelehnt an "row", "column", "division"). Die ersten beiden sind trivial, das letzte nicht unbedingt: Zuerst wird der Startwert eines Dreizeilenblockes ermittelt. Auf den addieren wir nun auf: Es ist egal, in welcher der (9 Positionen langen) Zeilen sich pos befindet, es interessiert nur der Offset innerhalb der Zeile, der dem Divisionsrest entspricht. Die Summe entspricht also (Dreizeilenblockstartposition + Offset_innerhalb_einer_Zeile), was nichts anderes als das Ergebnis eines Verschiebens aus einer der drei Zeilen in die Erste ist. Aber es fehlt noch das horizontale Einrücken in die Startposition der passenden kleinen Matrix ("division"). Das Zwischenergebnis befindet sich aber bereits darin. Es ist um pos%3 nach rechts verschoben, weswegen das abgezogen werden muss.

EDIT:
So könnte ich mir das vorstellen:

[...]

Mal auf die Schnelle reingehackt. Das ab Konstruktor müsste noch in den Konstruktur. Natürlich müssen die Arrays noch von der Größe her klar gemacht werden und ggf. initialisiert werden. Jedenfalls hätten wir nach diesem Zirkus die Nullstellen nach den vorhandenen Elementen in Zeilen und Spalten sortiert.

Dem Konzept nach sollte das wohl klappen.

Wenn du so weit bist, dann würde ich mir mal die Sortierschleife angucken. Die hat nämlich einen quadratischen Suchaufwand, was zu viel ist. Nachdem einmal bis oben oder unten (je nachdem, wie herum) durchgetauscht wurde, steht der extreme Wert bereits am Rand, sodass diese Position nicht mehr verglichen werden muss. Somit ist es zulässig, dass sich das Abbruchkriterium der inneren Schleife immer um eins auf die günstigere Richtung zubewegt, was sich über den Index der äußeren Schleife steuern lässt.

Diese Maßnahme ist nicht unbedingt sinnvoll, falls Loop-Unrolling (durch den Compiler) möglich und erwünscht ist. Hier sieht es eher nicht danach aus, dass der Compiler das machen würde, denn besetzt_nullstellen.length ist keine Konstante und erst spät bekannt. Also sollte das mitlaufende Abbruchkriterium etwas bringen. Ob man den Effekt herausmessen kann (sollte man eigentlich), ist eine andere Frage. Aber zigmal Kleinvieh macht auch einigen Mist.

Edit:

Also es funktioniert. Aber das Sortieren dauert. Es ist schneller, als meine Zeilenlösung, aber deutlich langsamer als meine Spaltenlösung. => 954 ms

Du meinst hoffentlich nicht das Sortieren, sondern die gesamte Zeit. Das Sortieren sollte man vielleicht extra messen. Es ist erwartbar, dass die "bestmögliche" (nach dem noch sehr simplen Kriterium) Sortierung nicht so gute Ergebnisse wie ein glücklicher Zufallsfund bringt (es gibt innerhalb der Menge der möglichen Sudokus immer beide Sudokus, wie für Zeilen- und Spaltenlösung günstig oder ungünstig hingedreht), was völlig normal wäre. Aber wenn sie die Zeiten durchschnittlich verbessert (wobei es darauf ankäme, wie dieser Durchschnitt gebildet wird), dann hast du schon was gewonnen. Zufall ist keine Leistung, geht aber mit in den Durchschnitt ein. Wenn du von 3,85 s auf 954 ms runter bist, dann ist das ein Indiz für einen besseren Durchschnitt, der vorher bei ca. ((3,85 + 0,116) / 2) s = 1,98 s lag (Indiz, weil man nur den Durchschnitt von zwei Fällen hat und die anderen Auswirkungen nicht kennt). Wenn das repräsentativ wäre, könntest du sagen, dass du die Zeiten halbiert hast.

[Stiller Leser]

Wenn ich Anzahl=8 3x3-Matrizen nebeneinander habe und x=15 einwerfe, dann kommt 15%8=7 heraus. Vielleicht meinst du etwas anderes. Falls du x%Weite_je_Matrix meinst, dann liegt der Nutzen auf der Hand, weil das die Position innerhalb der Matrix in x-Richtung ist.

Nein, so meine ich das nicht. Anzahl Matrizen pro Zeile heißt, dass es drei Matrizen in den Zeilen gibt. 15%3=0 => kx=0. Wobei x ein fehlerhafter Wert in einer 9x9 Matrix ist. x kann maximal 8 sein. Also von 0 bis 8 oder halt 1 bis 9. Nehmen wir die 8=> 8%3=2 => kx=2.
Bei y das selbe Spielchen, eben nur mit der Anzahl Matrizen in der Spalte. In dem Fall halt auch 3. Auf jeden Fall kommt als Modulowert 0, 1 oder 2 raus bei einer kleinen 3x3 Matrix.

Wenn du so weit bist, dann würde ich mir mal die Sortierschleife angucken. Die hat nämlich einen quadratischen Suchaufwand, was zu viel ist. Nachdem einmal bis oben oder unten (je nachdem, wie herum) durchgetauscht wurde, steht der extreme Wert bereits am Rand, sodass diese Position nicht mehr verglichen werden muss. Somit ist es zulässig, dass sich das Abbruchkriterium der inneren Schleife immer um eins auf die günstigere Richtung zubewegt, was sich über den Index der äußeren Schleife steuern lässt.

Diese Maßnahme ist nicht unbedingt sinnvoll, falls Loop-Unrolling (durch den Compiler) möglich und erwünscht ist. Hier sieht es eher nicht danach aus, dass der Compiler das machen würde, denn besetzt_nullstellen.length ist keine Konstante und erst spät bekannt. Also sollte das mitlaufende Abbruchkriterium etwas bringen. Ob man den Effekt herausmessen kann (sollte man eigentlich), ist eine andere Frage. Aber zigmal Kleinvieh macht auch einigen Mist.

Im Ungünstigsten Falle befindet sich der höchste Wert am Ende.

Du meinst hoffentlich nicht das Sortieren, sondern die gesamte Zeit. Das Sortieren sollte man vielleicht extra messen. Es ist erwartbar, dass die "bestmögliche" (nach dem noch sehr simplen Kriterium) Sortierung nicht so gute Ergebnisse wie ein glücklicher Zufallsfund bringt (es gibt innerhalb der Menge der möglichen Sudokus immer beide Sudokus, wie für Zeilen- und Spaltenlösung günstig oder ungünstig hingedreht), was völlig normal wäre. Aber wenn sie die Zeiten durchschnittlich verbessert (wobei es darauf ankäme, wie dieser Durchschnitt gebildet wird), dann hast du schon was gewonnen. Zufall ist keine Leistung, geht aber mit in den Durchschnitt ein. Wenn du von 3,85 s auf 954 ms runter bist, dann ist das ein Indiz für einen besseren Durchschnitt, der vorher bei ca. ((3,85 + 0,116) / 2) s = 1,98 s lag (Indiz, weil man nur den Durchschnitt von zwei Fällen hat und die anderen Auswirkungen nicht kennt). Wenn das repräsentativ wäre, könntest du sagen, dass du die Zeiten halbiert hast.

Ja, die Lösung braucht 954 ms.

    Sudoku(int [][]matrix){        this.matrix=new int[9][9];
        zeilen=9;spalten=9;
        int [] besetzt_zeilen=new int[9];
        int [] besetzt_spalten=new int[9];
        int [] besetzt_nullstellen;
        
        for(int i=0;i<9;i++) {
            besetzt_zeilen[i]=0;
            besetzt_spalten[i]=0;
        }
        
        int zaehler=0;
        for(int i=0;i<zeilen;i++)
            for(int j=0;j<spalten;j++){
                this.matrix[i][j]=matrix[i][j];
                if(this.matrix[i][j]==0)zaehler++;
                if(matrix[i][j]!=0)besetzt_zeilen[i]++; //Hier werden jeweils für Zeile und Spalte die Elemente gezählt, die ungleich 0 sind, also schon richtig besetzt sind.
                if(matrix[j][i]!=0)besetzt_spalten[i]++; //
            }
        nullstellen2=new Koordinaten[zaehler];
        besetzt_nullstellen=new int[zaehler];
        
        zaehler=0;
        for(int i=0;i<zeilen;i++)
            for(int j=0;j<spalten;j++){
                if(this.matrix[i][j]==0)nullstellen2[zaehler++]=new Koordinaten(i,j); //hier ist einfache Zuweisung der Nullstellen nach Zeilen.
            }
        for(int i=0;i<nullstellen2.length;i++)besetzt_nullstellen[i]=besetzt_zeilen[nullstellen2[i].get_x()]+besetzt_spalten[nullstellen2[i].get_y()]; //besetzt_zeilen bekommt in der gleichen Reihenfolge der vorhandenen Nullstellen die Anzahl der besetzt_zeilen und besetzt_spalten       


    int hilf;
    Koordinaten hilf2;
    
     for (int i = besetzt_nullstellen.length-1; i > 0; i--) { //einfacher Sortieralgorithmus
         for (int j = 1; j < besetzt_nullstellen.length-1; j++) { 
             if (besetzt_nullstellen[j-1] < besetzt_nullstellen[j]) { 
                 hilf = besetzt_nullstellen[j]; 
                 besetzt_nullstellen[j]=besetzt_nullstellen[j - 1]; 
                 besetzt_nullstellen[j - 1] = hilf; 
                 hilf2=nullstellen2[j];
                 nullstellen2[j] = nullstellen2[j - 1]; 
                 nullstellen2[j - 1] = hilf2; 
             } 
         }
     }
        
    }

Ich habe es übrigens umgedreht gemacht, damit Nullstellen, wo die meisten Besetzungen in Zeilen und Spalten sind, vorne sind. Also sortiert von vielen Besetzungen zu keiner Besetzung.

[jabu]

Nein, so meine ich das nicht. Anzahl Matrizen pro Zeile heißt, dass es drei Matrizen in den Zeilen gibt. 15%3=0 => kx=0. Wobei x ein fehlerhafter Wert in einer 9x9 Matrix ist. x kann maximal 8 sein. Also von 0 bis 8 oder halt 1 bis 9. Nehmen wir die 8=> 8%3=2 => kx=2.
Bei y das selbe Spielchen, eben nur mit der Anzahl Matrizen in der Spalte. In dem Fall halt auch 3. Auf jeden Fall kommt als Modulowert 0, 1 oder 2 raus bei einer kleinen 3x3 Matrix.

Alles klar. Vielleicht brauchtest du das mal wegen einer nicht rein rechteckigen äußeren Form.

Im Ungünstigsten Falle befindet sich der höchste Wert am Ende.

Das hatte ich doch berücksichtigt. Ich zitiere mich mal selbst:

Wenn du so weit bist, dann würde ich mir mal die Sortierschleife angucken. Die hat nämlich einen quadratischen Suchaufwand, was zu viel ist. Nachdem einmal bis oben oder unten (je nachdem, wie herum) durchgetauscht wurde, steht der extreme Wert bereits am Rand, sodass diese Position nicht mehr verglichen werden muss. Somit ist es zulässig, dass sich das Abbruchkriterium der inneren Schleife immer um eins auf die günstigere Richtung zubewegt, was sich über den Index der äußeren Schleife steuern lässt.

Das^ sollte eigentlich keines Beweises bedürfen, aber ich habe mir die Mühe trotzdem mal gemacht (gern geschehen):

package sortieren;

class Sortieren {
    static final int[] reihenfolge_01 = { -20, 1, 2, 3, 4, 4, -4, 5, 20, 10, -11, 12, 13, 0, 14, 15, 16, -17, 90, 90 };
    static final int[] reihenfolge_02 = { -19, -19, -11, 9, -17, -5, -9, -12, 10, -3, 7, 4, 5, -5, 4, 4, 3, 2, 1, 13 };

    static void Sort(int[] a) {
        for (int end = a.length - 1; end > 0; end--) {
            for (int i = 0; i < end; i++) {
                if (a[i] < a[i + 1]) {
                    int tmp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = tmp;
                }
            }
        }
    }

    static void Out(int[] a) {
        for (int i : a)
            System.out.format("%4d", i);
        System.out.println();
    }

    public static void main(String[] args) {
        int[] sammlung = null;

        sammlung = reihenfolge_01;
        Sort(sammlung);
        Out(sammlung);

        sammlung = reihenfolge_02;
        Sort(sammlung);
        Out(sammlung);
    }

}

Ergebnis:

  90  90  20  16  15  14  13  12  10   5   4   4   3   2   1   0  -4 -11 -17 -20
  13  10   9   7   5   4   4   4   3   2   1  -3  -5  -5  -9 -11 -12 -17 -19 -19

Ein kleines Quiz mit Praxisrelevanz:

for (int i = 0; i != end; ++i) {
    //do it;
}

for (int i = end; i != 0;) {
    --i;
    //do it;
}

Welche Schleife ist grundsätzlich schneller und warum?