long long nth_perfect_power(int n){
if(n == 1) return 1;
auto limit = 1e10;
set<long long> powers;
for(long long m = 2; m * m < limit; m++){
long long power = m * m;
while(power < limit){
powers.insert(power);
power *= m;
}
}
auto it = powers.begin();
std::advance(it, n-2);
return *it;
}
이 소스는 퍼포먼스에 문제가 있습니다.
set은 고성능으로 sorting된 형태로 저장하지만 위와 같은 소스에서는 set으로 인하여 탐색과 삽입을 수십만번 반복함으로써 성능상의 문제가 발생합니다.하여 저장시에는 저장만하고 마지막에 한번 sorting하는 방식으로 바꿔봅니다.
long long nth_perfect_power2(int n){
if(n == 1) return 1;
auto limit = 1e10;
vector<long long> powers;
for(long long m = 2; m * m < limit; m++){
long long power = m * m;
while(power < limit){
powers.push_back(power);
power *= m;
}
}
std::sort(powers.begin(), powers.end());
return powers[n-2];
}
n이 늘어 나면 늘어 날수록 memory와 cpu비용이 함께 증가하는 아주 안좋은 알고리즘 되겠다.
int to string역시 O(n)이므로 사실상의 시간 복잡도는 O(n^n)이다.
그러나
이걸 아키텍처 적으로 플어본다면 문자열 str은 상수와가 가능하고 상수화하고 n번째 문자를 찾는다면 결국은 O(1)의 완벽한 알고리즘이된다. 상황과 시스템에 따라서 이런 알고리즘도 상당한 퍼포먼스를 발휘할수도 있다. 만약 str을 생성하는 문제가 복잡하고 수식으로 계산하기 힘든경우에는 웜업시간에 str을 생성하고 매 요청때마다 결과를 도출하는것도 사실상 더 많이 쓰이는 방법되겠다.
그래도 알고리즘만 연구하시는 분들은 최적의 공간/시간 복잡도를 추구하므로 최적의 공간/시간 복잡도를 가지는 알고리즘을 연구해보자!!
2. 수치해석적 알고리즘
- 일단 문제를 해결하기 위해서 규칙을 찾아내야한다.
- 문자열을 만드는 숫자를 "k"라고 하고 요구하는 위치값을 "n"이라하자.
- k의 자릿수를 digit이라하자
- 각 digit별 자리수 count(digit) = 9 * 10 ^ (digit-1) 이다.
세계인의 타임킬링게임 "지뢰찾기"게임에서 특정 블럭을 눌렀을때 막혀있지 않은 최대 면접을 구하여 OPEN해줄때 사용할 수 있는 면적구하기 알고리즘 입니다. Graph, DFS에 관련해서는 미로찾기(graph traversal)을 먼저 읽고 오면 도움이 됩니다.
이전 포스트에서 언급한바와 같이 Graph - DFS ( Depth First Search ) 알고리즘은 완전 탐색 즉 모든 노드를 방문할 수 있는 알고리즘입니다. 이 알고리즘은 조금 응용해서 방문할 수 있는 모든 노드를 방문하면 결국은 방문수가 해당 node group의 넓이가 됩니다.
문제
아래와 같은 지도가 존재할때 빈칸으로 이루어진 영역중 최대 크기 영역의 크기를 구해봅시다.
3 | let a = String::from("string"); | - move occurs because `a` has type `String`, which does not implement the `Copy` trait 4 | let b = a; | - value moved here 5 | let c = a; | ^ value used here after move
C++은 b, c에 a가 copy되어 문제없이 들어가지만 Rust는 a의 소유권이 b로 넘어간후 a를 다시 사용하였기 때문에 에러가 발생합니다.
여기까지는 다른 블로그에서도 많이 하는 얘기고.. C++을 Rust와 같이 바꿔 보겠습니다.
C++
Rust
intmain(int argc, constchar * argv[]) { auto a = std::unique_ptr<std::string>(newstd::string("string")); auto b = std::move(a); auto c = a; return0; }
fnmain() { let a =10; let b = a; let c = a; }
Call to implicitly-deleted copy constructor of 'std::unique_ptr<std::string>'
3 | let a = String::from("string"); | - move occurs because `a` has type `String`, which does not implement the `Copy` trait 4 | let b = a; | - value moved here 5 | let c = a; | ^ value used here after move
아시는바와 같이 std::unique_ptr은 copy operator를 삭제하여 copy동작을 막은 템플릿입니다. 소유권이 하나의 인스턴스에만 유지하도록 하는 helper class입니다.
Rust은 기본이 unique value이므로 위와 같이 하면 rust와 똑같이 동작합니다.
C++만 Rust형으로 바꿔보는건 재미가 없으니 Rust를 C++로도 바꿔 보겠습니다. 일단 rust에서만 에러나는 케이스입니다
C++
Rust
structtestStruct{ int value; };
intmain(int argc, constchar * argv[]) { testStruct a = { 10 }; auto b = a; auto c = a; return0; }
struct TestStruct{ a:u16 }
fn main() { let a = TestStruct{ a: 10 }; let b = a; let c = a; }
[SUCESS]
7 | let a = testStruct{ a: 10 }; | - move occurs because `a` has type `TestStruct`, which does not implement the `Copy` trait 8 | let b = a; | - value moved here 9 | let c = a; | ^ value used here after move
fn main() { let a = TestStruct{ a: 10 }; let b = a; let c = a; }
[SUCESS]
[SUCESS]
Rust도 Copy함수를 구현했더니 C++처럼 동작합니다.
정리
간단히 rust의 의도를 파악해 보자면
object의 기본동작으로 move이므로 memory deallocation 시점을 정확히 잡을수있다.
의도하지 않는 copy가 일어나서 memory가 낭비되지 않도록한다 ( copy, clone이 필요할때는 의도적으로 coding 해라 )
사실 처음에 코드를 작성할때는 헷갈렸지만 자꾸 작성하다보면 변수의 scope이 심각하게 명확하고 function, thread등에서 공유되는 변수들의 범위와 scope가 정말 명확하게 보입니다( 그렇기 때문에 의도하지 않은 변수공유, 스코프가 벗어난 변수 참조등을 원천적으로 막아 안전한 프로그래밍이 가능합니다)
다음시간에는 C++ struct (class)와 Rust struct를 비교해 보겠습니다.
