Leetcode gültiges Sudoku

Question

Link hier

Ich werde eine Lösung in Python und C ++ aufnehmen, und Sie können eine überprüfen. Ich bin hauptsächlich daran interessiert, den C ++ - Code zu überprüfen, was ich kürzlich gelernt habe. Wer C ++ nicht kennt, kann den Python-Code überprüfen. Beide Lösungen haben eine ähnliche Logik, sodass die Überprüfung für alle gilt.

---

Problemstellung

Stellen Sie fest, ob ein 9 x 9 Sudoku-Board gültig ist. Nur die gefüllten Zellen müssen nach folgenden Regeln validiert werden:

• Jede Zeile muss die Ziffern 1-9 ohne Wiederholung enthalten. Jede Spalte
• muss die Ziffern 1-9 ohne Wiederholung enthalten. Jeder der neun 3 x
• 3 Unterfelder des Rasters müssen die Ziffern 1-9 ohne Wiederholung enthalten.

Hinweis:

Ein Sudoku-Brett (teilweise gefüllt) könnte gültig sein, ist aber nicht unbedingt lösbar. Nur die gefüllten Zellen müssen gemäß den genannten Regeln validiert werden.

Beispiel 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Beispiel 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

valid_sudoku.py

def is_valid(board, empty_value='.', b_size=3):
    seen = set()
    size = b_size * b_size
    for row in range(size):
        for col in range(size):
            if (value := board[row][col]) == empty_value:
                continue
            r = f'0{row}{value}'
            c = f'1{col}{value}'
            b = f'2{row // b_size}{col // b_size}{value}'
            if r in seen or c in seen or b in seen:
                return False
            seen.update({r, c, b})
    return True


if __name__ == '__main__':
    g = [
        ["5", "3", ".", ".", "7", "5", ".", ".", "."],
        ["6", ".", ".", "1", "9", "5", ".", ".", "."],
        [".", "9", "8", ".", ".", ".", ".", "6", "."],
        ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
        ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
        ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
        [".", "6", ".", ".", ".", ".", "2", "8", "."],
        [".", ".", ".", "4", "1", "9", ".", ".", "5"],
        [".", ".", ".", ".", "8", ".", ".", "7", "9"],
    ]
    print(is_valid(g))

Statistiken:

Runtime: 92 ms, faster than 81.70% of Python3 online submissions for Valid Sudoku.
Memory Usage: 14.1 MB, less than 73.95% of Python3 online submissions for Valid Sudoku.

Hier ist eine alternative Lösung mit Numpy: Sie ist kürzer und lesbarer, aber langsamer:

import numpy as np


def is_valid(board, size=3, empty_value='.'):
    board = np.array(board)
    blocks = board.reshape(4 * [size]).transpose(0, 2, 1, 3).reshape(2 * [size * size])
    for grid in [board, board.T, blocks]:
        for line in grid:
            non_empty = line[line != empty_value]
            if not len(non_empty) == len(set(non_empty)):
                return False
    return True

Statistiken:

Runtime: 172 ms, faster than 5.19% of Python3 online submissions for Valid Sudoku.
Memory Usage: 30.2 MB, less than 11.10% of Python3 online submissions for Valid Sudoku.

valid_sudoku.h

#ifndef LEETCODE_VALID_SUDOKU_H
#define LEETCODE_VALID_SUDOKU_H

#include <string_view>
#include <unordered_set>

bool sudoku_check_update(const size_t &row, const size_t &col, const char &value,
                         const int &block_size,
                         std::unordered_set<std::string_view> &seen);

bool sudoku_check(const std::vector<std::vector<char>> &board,
                  const char &empty_value = '.');

void test1();

#endif //LEETCODE_VALID_SUDOKU_H

valid_sudoku.cpp

#include <iostream>
#include <vector>
#include <string_view>
#include <cmath>
#include <unordered_set>


bool sudoku_check_update(const size_t &row, const size_t &col, const char &value,
                         const int &block_size,
                         std::unordered_set<std::string_view> &seen) {
    std::string_view r, c, b;
    r = "0-" + std::to_string(row) + value;
    c = "1-" + std::to_string(col) + value;
    b = "2-" + std::to_string(row / block_size) + std::to_string(col / block_size) +
        value;
    for (const auto &seen_id: {r, c, b}) {
        if (seen.find(seen_id) != seen.end())
            return false;
        seen.insert(seen_id);
    }
    return true;
}


bool sudoku_check(const std::vector<std::vector<char>> &board,
                  const char &empty_value = '.') {
    std::unordered_set<std::string_view> seen;
    const auto row_size = board.size();
    const int block_size = std::sqrt(row_size);
    for (size_t row = 0; row < row_size; ++row) {
        for (size_t col = 0; col < row_size; ++col) {
            auto value = board[row][col];
            if (value == empty_value)
                continue;
            if (!sudoku_check_update(row, col, value, block_size, seen))
                return false;
        }
    }
    return true;
}


void test1() {
    std::vector<std::vector<char>> v = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };
    std::cout << sudoku_check(v);
}

Statistiken:

Runtime: 48 ms, faster than 17.98% of C++ online submissions for Valid Sudoku.
Memory Usage: 20.4 MB, less than 22.55% of C++ online submissions for Valid Sudoku.

Answer 1

Hier sind einige Vorschläge, wie Sie Ihren Code verbessern können.

C ++ - Version

Verwenden Sie alle erforderlichen #includes

Der Typ std::vector<std::vector<char>>wird in der Definition von sudoku_check()in der Header-Datei verwendet, #include <vector>fehlt jedoch in der Liste der dort enthaltenen Includes.

Minimieren Sie die Schnittstelle

Die .hDatei ist eine Deklaration der Schnittstelle zu Ihrer Software. Das .cppist die Implementierung dieser Schnittstelle. Es ist eine gute Entwurfspraxis, die Schnittstelle auf das zu minimieren, was von externen Programmen benötigt wird. Aus diesem Grunde würde ich die entfernen sudoku_check_update()und test1()Funktionen und diese nur verwenden:

#ifndef LEETCODE_VALID_SUDOKU_H
#define LEETCODE_VALID_SUDOKU_H

#include <vector>

bool sudoku_check(const std::vector<std::vector<char>> &board,
                  const char &empty_value = '.');

#endif //LEETCODE_VALID_SUDOKU_H

Die Implementierung sollte den Schnittstellenheader enthalten

Wie der Titel dieses Abschnitts besagt, sollte die Implementierung den Schnittstellenheader enthalten. Dies stellt sicher, dass die Schnittstelle und die Implementierung übereinstimmen, und beseitigt Fehler. Wenn wir das in diesem Fall tun, sehen wir, dass der Standardwert für empty_valuezweimal deklariert wird. Es sollte nur einmal in der Header-Datei deklariert werden.

Machen Sie lokale Funktionen static

Mit der oben empfohlenen kleineren Schnittstelle wird die sudoku_check_updateFunktion zu einem Implementierungsdetail, das nur in der .cppDatei verwendet wird. Aus diesem Grund sollte es so gemacht werden, staticdass der Compiler weiß, dass es sicher ist, die Funktion zu integrieren.

Das Schlüsselwort staticbei Verwendung mit einer Funktionsdeklaration gibt an, dass die Verknüpfung intern ist. Mit anderen Worten bedeutet dies, dass nichts außerhalb dieser Datei auf die Funktion zugreifen kann. Dies ist für den Compiler hilfreich, da staticder Compiler beispielsweise die Option hat, den Code inline zu setzen , wenn eine Funktion nur einmal verwendet wird und / oder klein ist. Das heißt, anstelle der üblichen Assemblersprache call... retAnweisungen zum Springen zu einer Unterroutine und zum Zurückkehren von dieser kann der Compiler den Code für die Funktion einfach direkt an dieser Stelle ablegen, wodurch die Rechenkosten dieser Anweisungen gespart und der Cache sichergestellt werden Vorhersagen sind korrekt (da der Cache normalerweise die Referenzlokalität ausnutzt .)

Lesen Sie auch über Speicherklassenspezifizierer, um besser zu verstehen, was staticin anderen Kontexten funktioniert, und allgemeinere Deklarationsspezifizierer, um Erklärungen zu constexprund mehr zu erhalten.

Beheben Sie den Fehler!

Der Code wird derzeit nicht string_viewordnungsgemäß verwendet. A std::string_viewist im Wesentlichen ein Zeiger auf eine vorhandene Zeichenfolge. Ihre Zeichenfolgen werden jedoch dynamisch zusammengesetzt und gelöscht, sodass dies eine ungültige Verwendung von ist std::string_view. Wenn Sie alle Instanzen von string_viewdurch ersetzen string, funktioniert das Programm.

Speicherprobleme wie dieses und Parallelitätsfehler gehören zu den schwierigsten Problemen, die Programmierer erkennen und beheben können. Wenn Sie mehr Erfahrung sammeln, werden Sie feststellen, dass Ihre Fähigkeit, diese Probleme zu erkennen und zu vermeiden, reflexiver wird. Es gibt viele Ansätze, um solche Fehler zu finden. Siehe einfache Klasse zur Lecksuche für einige von ihnen.

Schreiben Sie bessere Testfunktionen

Der oben erwähnte Fehler wurde leicht entdeckt, indem die Funktion mehrmals mit unterschiedlichen Eingaben aufgerufen wurde. Vielleicht hatten Sie bereits ein umfangreicheres Spektrum an Testfunktionen, aber wenn nicht, empfehle ich dringend, diese zu erstellen und anzuwenden.

Verwenden Sie effiziente Datenstrukturen

Wenn das Ziel dieses Codes darin besteht, sowohl hinsichtlich der Laufzeit als auch des Speichers effizient zu sein, können viele Verbesserungen vorgenommen werden. Erstens ist die Datenstruktur std::unordered_set<std::string_view>nicht optimal. Wann immer wir an einer Leistungsoptimierung arbeiten, ist es nützlich zu messen. Also habe ich ein sehr einfaches Testprogramm geschrieben, das auf meiner Stoppuhr-Vorlage basiert . Es ist hier:

#include "valid_sudoku.h"
#include "stopwatch.h"
#include <iostream>
#include <vector>
#include <string>

int main(int argc, char* argv[]) {
    std::vector<std::vector<char>> v = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };
    if (argc != 2) {
        std::cout << "Usage: " << argv[0] << " num_trials\n";
        return 1;
    }
    auto iterations = std::stoul(argv[1]);

    Stopwatch<> timer{};

    bool valid{true};
    for (auto i{iterations}; i; --i) {
        valid &= sudoku_check(v);
    }

    auto elapsed{timer.stop()};
    if (!valid) {
        std::cout << "The program failed!\n";
        return 2;
    }
    std::cout << iterations << " trials took " << elapsed << " microseconds\n"
        " for an average of " << elapsed/iterations << " microseconds/trial\n";
}

Wenn ich dies auf meinem Computer mit 1.000.000 Versuchen ausführe (wobei der oben angegebene Fehler wie beschrieben behoben wurde), erhalte ich Folgendes Ergebnis:

1000000 Versuche dauerten 1,44351e + 07 Mikrosekunden für durchschnittlich 14,4351 Mikrosekunden / Versuch

Stellen wir uns nun eine effizientere Datenstruktur vor. Anstelle von a unordered_setkönnen wir auch eine Reihe fester Arrays verwenden. Es gibt neun Zeilen, neun Spalten und neun Teilquadrate. Jeder von ihnen enthält entweder eine Nummer oder nicht. Für mich bedeutet das, dass wir ein Objekt wie dieses verwenden könnten:

using SeenType = std::array<std::array<std::array<bool, 9>, 9>, 3>;

Diese enthält die 3 Typen (Zeilen, Spalten, Teilquadrate) und jeweils 9 Sammlungen mit 9 Bits; ein Bit für jede Nummer. Schreiben wir die Funktion neu, um dies zu verwenden:

static bool sudoku_check_update(std::size_t row, std::size_t col, 
        char value, SeenType &seen) {
    static constexpr std::size_t block_size{3};
    static_assert(block_size * block_size == row_size, "block_size must be the square root of row_size");
    const std::size_t block = col / block_size + block_size * (row / block_size);
    std::size_t dim{0};
    value -= '1';   // adjust from digits '1'-'9' to indices 0-8.
    for (const auto &seen_id: {row, col, block}) {
        if (seen[dim][seen_id][value])
            return false;
        seen[dim][seen_id][value] = true;
        ++dim;
    }
    return true;
}

Führen Sie das Programm jetzt wie zuvor mit einer Million Testversionen erneut aus:

1000000 Versuche dauerten 562153 Mikrosekunden für durchschnittlich 0,562153 Mikrosekunden / Versuch

Diese eine Änderung machte die Dinge 25x schneller . Wir könnten auch die Tatsache nutzen, dass die Dimensionen bekanntermaßen a std::array<std::array<char, 9>, 9>anstelle der Vektoren verwenden und constexprfür diese Dimensionen verwenden. Wenn wir diese Änderung auch vornehmen, erhalten wir Folgendes:

1000000 Versuche dauerten 160808 Mikrosekunden für durchschnittlich 0,160808 Mikrosekunden / Versuch

Jetzt ist es also 90x schneller .

Bevorzugen Sie {}Stilinitialisierungen

Möglicherweise stellen Sie fest, dass der von mir geschriebene Code tendenziell den {}Initialisierungsstil verwendet. Dafür gibt es mehrere Gründe, einschließlich der Tatsache, dass es sich bei der Anzeige immer um eine Initialisierung handelt und nicht mit einem Funktionsaufruf verwechselt werden kann. Siehe ES.23 für weitere Details.

Übergeben Sie Werte anstelle von Referenzen für kurze Datentypen

Anstatt zu bestehen const size_t &coloder const char& value, ist es im Allgemeinen besser, diese nach Wert zu übergeben. Dies ist häufig vorteilhaft, da der Zeiger wahrscheinlich länger ist als das, auf das er zeigt, und weil dadurch eine Indirektion und eine Speichersuche vermieden werden können.

Verschieben Sie Berechnungen von der Laufzeit in die Kompilierungszeit, wo dies sinnvoll ist

Es nimmt wahrscheinlich nicht viel Zeit in Anspruch, aber diese Linie ist nicht so schnell wie sie sein könnte:

const int block_size = std::sqrt(row_size);

Dies konvertiert row_sizein a double, ruft die Gleitkommafunktion auf sqrtund konvertiert den doubleBack in a int. Im Gegensatz dazu könnten wir einfach Folgendes schreiben:

constexpr std::size_t block_size{3};

Jetzt dauert es zur Laufzeit überhaupt keine Zeit, da der Wert zur Kompilierungszeit bekannt ist. Außerdem muss der Wert nicht mehr übergeben werden, und wie oben kann seine Definition an der einzigen Stelle platziert werden, die tatsächlich benötigt wird, und zwar innerhalb der sudoku_check_updateFunktion.

Im Allgemeinen ziehen wir es aus drei Gründen vor, Dinge von der Laufzeit zur Kompilierungszeit zu verschieben:

1. Programme werden in der Regel öfter ausgeführt als kompiliert, daher optimieren wir sie für das häufigere Auftreten
2. Je früher wir Fehler erkennen, desto billiger und einfacher können sie behoben werden
3. Dadurch wird die Software tendenziell kleiner und intern einfacher, was die Ladegeschwindigkeit, die Cache-Leistung und die Qualität der Software verbessert

Python-Version

Vermeiden Sie continuedurch Umstrukturierung der Schleife

Es ist an sich nichts Falsches an Ihrer Verwendung des Walross-Operators, aber es scheint wenig Grund zu geben, den Sinn des Vergleichs nicht umzukehren und das Update einfach zu verarbeiten, anstatt es zu verwenden continue. Dies wirkt sich nicht auf die Leistung aus, hilft jedoch dem menschlichen Leser des Codes beim Verständnis des Programmflusses. Ich neige dazu, frühzeitig "Bailout" -Klauseln in eine Funktion einzufügen, um ungültige Bedingungen schnell abzulehnen, aber continuein Schleifen zu vermeiden ; Letztendlich ist es eine Frage der Lesbarkeit und des Stils in C ++ oder Python.

Verwenden Sie effizientere Datenstrukturen

Was in C ++ wahr war, funktioniert auch in Python. Wir können dieselben Ideen verwenden und den Code um den Faktor 6 beschleunigen:

def is_valid(board, empty_value='.', b_size=3):
    size = b_size * b_size
    seen = [[(size * [False]) for _ in range(size)] for _ in range(3)]
    for row in range(size):
        for col in range(size):
            if (value := board[row][col]) != empty_value:
                block = col // b_size + b_size * (row // b_size)
                dim = 0
                value = int(value) - 1
                for seen_id in [row, col, block]:
                    if seen[dim][seen_id][value]:
                        return False
                    seen[dim][seen_id][value] = True
                    dim += 1
    return True

Answer 2

Minor (und Python), aber ich persönlich finde das etwas verwirrend:

if (value := board[row][col]) == empty_value:
    continue
r = f'0{row}{value}'
c = f'1{col}{value}'
b = f'2{row // b_size}{col // b_size}{value}'

Sie verwenden einen Zuweisungsausdruck, um einen Wert zuzuweisen, verwenden ihn dann aber nur im falschen Fall. Ich denke, das wäre viel sauberer, wenn man eine einfache alte Zuweisungsanweisung verwendet:

value = board[row][col]
if value == empty_value:
    continue
r = f'0{row}{value}'
c = f'1{col}{value}'
b = f'2{row // b_size}{col // b_size}{value}'

Ich denke nicht, dass die gespeicherte Zeile es wert ist, die Erstellung einer Variablen zu begraben.

Answer 3

C ++

Es ist einfacher und möglicherweise schneller, kleine einfache Datentypen wie size_tund charnach Wert zu übergeben, nicht nach Referenz. Also sollten wir haben:

bool sudoku_check_update(size_t row, size_t col, char value, int block_size,
                         std::unordered_set<std::string_view> &seen)

bool sudoku_check(const std::vector<std::vector<char>> &board,
                  char empty_value = '.')

---

Noch wichtiger: std::string_view Kann nicht zum Speichern von Zeichenfolgen verwendet werden. Es besitzt nicht die Zeichenfolge, es ist nur ein Zeiger und eine Größe.

Wenn Sie so etwas tun:

std::string_view r = "0-" + std::to_string(row) + value;

... wir konstruieren ein temporäres std::stringund weisen es dann einem zu string_view. Die temporäre Zeichenfolge wird jedoch am Ende dieser Zeile nicht mehr angezeigt!

Es ist weitergegangen. Diese Zeichenfolge ist nicht mehr. Es hat aufgehört zu sein. Es ist abgelaufen und gegangen, um seinen Schöpfer zu treffen. Dies ist eine späte Saite. Es ist steif. Ohne Leben ruht es in Frieden. Wenn wir es nicht festgenagelt std::string_viewhätten, würde es die Gänseblümchen hochschieben. Es ist den Vorhang heruntergekommen und hat sich unsichtbar dem Chor angeschlossen. Dies ist ein Ex-String.

Mit anderen Worten, es ist undefiniertes Verhalten, dies zu versuchen und zu verwenden string_view. Also r, cund bmüssen std::stringselbst sein. Und seensollte ein sein std::unordered_set<std::string>.

---

Re. std::string_view::

std::string_viewzeigt auf eine Reihe von Zeichen im Speicher. Diese Zeichen können in a std::string, in a std::array, a std::vectoroder in einem String-Literal gespeichert werden .

Durch die Verwendung erhalten std::string_viewwir dieselbe Schnittstelle (Suchen, Vergleichen, Erstellen von Teilzeichenfolgen), unabhängig davon, um welchen Speicher es sich handelt. Daher ist es als gemeinsame Sprache zwischen diesen Typen nützlich.

Da std::string_viewdie Zeichen nicht gehören, erfolgt keine Speicherzuweisung oder das Kopieren selbst. Dies macht es nützlich für Dinge wie das Parsen langer Textdateien - wir können in Teilzeichenfolgen suchen und vergleichen, ohne das Kopieren durchzuführen, das std::stringdies tun würde.

Der Nachteil ist, dass wir sicherstellen müssen, dass die Lebensdauer der tatsächlichen Zeichenfolge im Speicher länger ist als die der string_view.