Leetcode 유효한 스도쿠
여기에 링크
저는 Python과 C ++로 된 솔루션을 포함 할 것이며 하나를 검토 할 수 있습니다. 저는 최근에 배우기 시작한 C ++ 코드를 검토하는 데 주로 관심이 있습니다. C ++를 모르는 사람들은 Python 코드를 검토 할 수 있습니다. 두 솔루션 모두 유사한 논리를 공유하므로 검토가 모두 적용됩니다.
문제 설명
9 x 9 스도쿠 보드가 유효한지 확인합니다. 다음 규칙에 따라 채워진 셀만 확인하면됩니다.
- 각 행은 반복없이 숫자 1-9를 포함해야합니다. 각 열
- 반복없이 숫자 1-9를 포함해야합니다. 아홉 3 x
- 그리드의 3 개의 하위 상자는 반복없이 1-9의 숫자를 포함해야합니다.
노트 :
스도쿠 보드 (부분적으로 채워진)는 유효 할 수 있지만 반드시 해결할 수있는 것은 아닙니다. 언급 된 규칙에 따라 채워진 셀만 확인하면됩니다.
예 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
예 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))
통계 :
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.
다음은 numpy를 사용하는 대체 솔루션입니다. 더 짧고 읽기 쉽지만 더 느립니다.
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
통계 :
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);
}
통계 :
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.
답변
다음은 코드를 개선 할 수있는 방법에 대한 몇 가지 제안입니다.
C ++ 버전
필요한 모든 #includes 사용
유형 std::vector<std::vector<char>>은 sudoku_check()헤더 파일 의 정의에 사용 되지만 #include <vector>포함 목록에서 누락되었습니다.
인터페이스 최소화
이 .h파일은 소프트웨어 에 대한 인터페이스 선언입니다 . 이 인터페이스 .cpp의 구현 입니다. 인터페이스를 외부 프로그램에 필요한 것으로 최소화하는 것이 좋은 디자인 관행입니다. 따라서 sudoku_check_update()및 test1()함수를 제거 하고 다음을 사용합니다.
#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
구현에는 인터페이스 헤더가 포함되어야합니다.
이 섹션의 제목에서 알 수 있듯이 구현에는 인터페이스 헤더가 포함되어야합니다. 이렇게하면 인터페이스와 구현이 일치하고 오류가 제거됩니다. 이 경우에 그렇게하면의 기본값 empty_value이 두 번 선언 되는 것을 볼 수 있습니다. 헤더 파일에서 한 번만 선언해야합니다.
지역 기능 만들기 static
위에서 언급 한 것처럼 더 작은 인터페이스를 사용하면 sudoku_check_update함수가 .cpp파일 내에서만 사용되는 구현 세부 정보가 됩니다. static따라서 컴파일러가 함수를 인라인하는 것이 안전하다는 것을 알 수 있도록 만들어야합니다 .
static함수 선언과 함께 사용되는 키워드 는 연결 이 내부 임을 지정합니다 . 즉, 해당 파일 외부의 어떤 것도 함수에 액세스 할 수 없음을 의미합니다. 예를 들어 static함수가 한 번만 사용되거나 작은 경우 컴파일러가 코드를 인라인으로 넣을 수 있기 때문에 컴파일러가 알면 유용합니다 . 즉, 일반적인 어셈블리 언어 call... ret서브 루틴으로 이동하여 반환하는 명령 대신 컴파일러는 해당 위치에 함수에 대한 코드를 직접 배치하여 해당 명령의 계산 비용을 절약하고 캐시를 보장 할 수 있습니다. 예측이 정확합니다 (일반적으로 캐시는 참조 의 지역성을 활용하기 때문 입니다.)
또한 다른 컨텍스트에서 수행되는 작업 을 더 잘 이해하기 위해 스토리지 클래스 지정자 에 대해 읽어보고 static, 기타에 대한 설명은 일반적으로 선언 지정자 를 constexpr참조하십시오.
버그 수정!
코드는 현재 string_view부적절하게 사용 됩니다. A std::string_view는 본질적으로 존재하는 문자열에 대한 포인터입니다. 그러나 문자열은 동적으로 구성되고 삭제되므로 std::string_view. 의 모든 인스턴스를 string_view로 string바꾸면 프로그램이 작동합니다.
이와 같은 메모리 문제와 동시성 오류는 프로그래머가 감지하고 수정하기 가장 어려운 문제 중 하나입니다. 더 많은 경험을 쌓을수록 이러한 문제를 발견하고 피할 수있는 능력이 더 반사적으로 온다는 것을 알게 될 것입니다. 이러한 오류를 찾는 방법에는 여러 가지가 있습니다. 그들 중 일부는 누출 감지 단순 클래스 를 참조하십시오 .
더 나은 테스트 함수 작성
위에서 언급 한 버그는 다양한 입력으로 함수를 여러 번 호출하여 쉽게 발견되었습니다. 이미 더 광범위한 테스트 함수 배열이있을 수 있지만 그렇지 않은 경우이를 만들고 적용하는 것이 좋습니다.
효율적인 데이터 구조 사용
이 코드의 목표가 런타임과 메모리 모두에서 효율적이라면 많은 개선이 이루어질 수 있습니다. 첫째, 데이터 구조 std::unordered_set<std::string_view>가 최적이 아닙니다. 성능 최적화 작업을 할 때마다 측정하는 것이 유용합니다. 그래서 저는 스톱워치 템플릿을 기반으로 매우 간단한 테스트 프로그램을 작성했습니다 . 여기 있습니다 :
#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";
}
내 컴퓨터에서 1,000,000 번의 평가판을 실행하면 (위에서 설명한대로 버그가 수정 된 상태에서) 다음과 같은 결과가 나옵니다.
1000000 번의 시도는 평균 14.4351 마이크로 초 / 시행 동안 1.44351e + 07 마이크로 초가 걸렸습니다.
이제 더 효율적인 데이터 구조를 생각해 봅시다. 대신 unordered_set고정 배열 세트를 사용할 수 있습니다. 9 개의 행, 9 개의 열 및 9 개의 하위 사각형이 있습니다. 각각은 숫자를 포함하거나 포함하지 않습니다. 나에게는 다음과 같은 객체를 사용할 수 있음을 시사합니다.
using SeenType = std::array<std::array<std::array<bool, 9>, 9>, 3>;
여기에는 3 가지 유형 (행, 열, 하위 정사각형)과 각각 9 비트의 9 개 모음이 포함됩니다. 각 숫자에 대해 1 비트. 이것을 사용하도록 함수를 다시 작성해 보겠습니다.
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;
}
이제 이전과 같이 백만 번의 시도로 프로그램을 다시 실행하십시오.
1000000 회 시도는 평균 0.562153 마이크로 초 / 시행 동안 562153 마이크로 초가 소요되었습니다.
그래서 한 번의 변화로 인해 25 배 더 빨라졌습니다 . 또한 차원이 std::array<std::array<char, 9>, 9>벡터 대신 a 를 사용 constexpr하고 해당 차원 에 사용하는 것으로 알려져 있다는 사실을 사용할 수도 있습니다 . 이 변경을 수행하면 다음과 같은 결과를 얻을 수 있습니다.
1000000 회 시도는 평균 0.160808 마이크로 초 / 시행 동안 160808 마이크로 초가 소요되었습니다.
이제 90 배 더 빨라졌습니다 .
{}스타일 초기화 선호
내가 작성한 코드 {}는 초기화 스타일 을 사용하는 경향이 있음을 알 수 있습니다 . 여기에는 몇 가지 이유가 있습니다. 그 이유는 볼 때 항상 초기화이며 함수 호출로 착각 할 수 없다는 사실을 포함합니다. 자세한 내용은 ES.23 을 참조하십시오.
짧은 데이터 유형에 대한 참조 대신 값 전달
오히려 전달보다 const size_t &col나 const char& value,이 값을 기준으로 사람들을 전달하는 데 일반적으로 좋습니다. 이는 포인터가 가리키는 것보다 길 수 있고 간접 및 메모리 조회를 제거 할 수 있기 때문에 종종 유리합니다.
실용적인 경우 런타임에서 컴파일 시간으로 계산 이동
시간이 많이 걸리지는 않지만이 라인은 다음과 같이 빠르지 않습니다.
const int block_size = std::sqrt(row_size);
이것이하는 일은 변환하는 것입니다 row_sizeA를 double, 부동 소수점 호출 sqrt기능과 변환 double가기 int. 대조적으로 다음과 같이 작성할 수 있습니다.
constexpr std::size_t block_size{3};
이제 컴파일 시간에 값이 알려지기 때문에 런타임에 시간이 전혀 걸리지 않습니다. 또한 값을 전달할 필요가 없으며 위와 같이 정의가 실제로 필요한 유일한 위치, 즉 sudoku_check_update함수 내에서 배치 될 수 있습니다 .
일반적으로 다음과 같은 세 가지 이유로 런타임에서 컴파일 시간으로 이동하는 것을 선호합니다.
- 프로그램은 일반적으로 컴파일 된 시간보다 더 많이 실행되므로 더 일반적인 경우에 최적화합니다.
- 버그를 빨리 발견할수록 더 저렴하고 쉽게 수정할 수 있습니다.
- 소프트웨어를 더 작게 만드는 경향이 있으며 내부적으로는 더 간단하게 로딩 속도, 캐시 성능을 향상시키고 더 간단한 소프트웨어는 품질을 향상시키는 경향이 있습니다.
Python 버전
continue루프를 재구성하여 방지
해마 연산자를 사용하는 데 본질적으로 잘못된 것은 없지만 비교의 의미를 뒤집지 않고 단순히 업데이트를 처리하는 것보다 continue. 성능에는 영향을주지 않지만 코드를 읽는 사람이 프로그램 흐름을 이해하는 데 도움이됩니다. 잘못된 조건을 신속하게 거부하기 위해 함수의 초기에 "bailout"절을 초기에 배치하는 경향이 있지만 continue루프 에서는 피합니다 . 궁극적으로 C ++ 또는 Python의 가독성과 스타일의 문제입니다.
보다 효율적인 데이터 구조 사용
C ++에서 사실이었던 것은 Python에서도 작동합니다. 동일한 아이디어를 사용하여 6 배로 코드 속도를 높일 수 있습니다.
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
사소한 (및 Python), 개인적으로 이것이 약간 혼란 스럽습니다.
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}'
값을 할당하기 위해 할당 식을 사용하고 있지만 false 경우에만 사용합니다. 평범한 할당 문을 사용하면 훨씬 더 깨끗할 것이라고 생각합니다.
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}'
저장된 선이 변수 생성을 묻을 가치가 있다고 생각하지 않습니다.
C ++
이 같은 작은 일반 데이터 형식을 전달하는 빠른 가능성이 간단하고 size_t및 char참조가 아닌 값으로. 그래서 우리는 :
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 = '.')
더 중요한 것은 문자열을 저장하는 데 사용할 std::string_view 수 없다는 것입니다. 그것은 문자열을 소유하지 않으며 단지 포인터와 크기 일뿐입니다.
다음과 같이 할 때 :
std::string_view r = "0-" + std::to_string(row) + value;
... 임시를 생성 한 std::string다음 string_view. 그러나 임시 문자열은이 줄 끝에서 범위를 벗어납니다!
그것은지나 갔다. 이 문자열은 더 이상 없습니다. 그것은 중단되었습니다. 만료되어 제작자를 만나러갔습니다. 이것은 늦은 문자열입니다. 뻣뻣합니다. 생명을 잃은 것은 평화롭게 쉬고 있습니다. 우리가 그것을 못 박지 않았다면 그것은
std::string_view데이지를 밀어 올리는 것입니다. 그것은 막을 내리고 보이지 않는 합창단에 합류했습니다. 이것은 전 문자열입니다.
즉, 그것을 시도하고 사용하는 것은 정의되지 않은 동작입니다 string_view. 그래서 r, c그리고 b필요가 되실 std::string들에게 자신을. 그리고 seen반드시 a std::unordered_set<std::string>.
레. std::string_view:
std::string_view메모리의 문자 범위를 가리 킵니다. 이러한 문자는 std::string, a std::array, a std::vector또는 문자열 리터럴에 저장 될 수 있습니다 .
사용함으로써 std::string_view우리는 기본 스토리지가 무엇인지에 관계없이 동일한 인터페이스 (찾기, 비교, 하위 문자열 생성)를 얻습니다. 따라서 이러한 유형 간의 공통 언어로 유용합니다.
std::string_view캐릭터를 소유하지 않기 때문에 메모리 할당이나 자체 복사를하지 않습니다. 이것은 긴 텍스트 파일을 구문 분석하는 것과 같은 작업에 유용합니다 std::string. 복사를 수행하지 않고도 하위 문자열에서 검색하고 비교할 수 있습니다 .
단점은 메모리에있는 실제 문자열의 수명이 string_view.