[HADOOP] brute force 알고리즘은 확장 할 수 있습니까?
HADOOPbrute force 알고리즘은 확장 할 수 있습니까?
나는 시행 착오로 해결할 수있는 수학 문제가있다. (나는 이것이 무차별 대항력이라고 생각한다.) 몇 가지 옵션이있을 때 프로그램이 잘 작동하지만 더 많은 변수 / 데이터를 추가하면 실행 시간이 길어지고 길어진다.
내 문제는 프로토 타입이 작동하지만 수천 개의 변수와 대용량 데이터 세트에서 유용하다는 것입니다. 그래서 무차별 대입 알고리즘을 확장하는 것이 가능한지 궁금합니다. 어떻게 스케일링에 접근 할 수 있습니까?
나는 Hadoop (그리고 HBase)으로 배우고 놀기 시작했다. 그것이 유망 해 보이지만, 나는하려고하는 것이 불가능하지 않다는 것을 증명하기를 원했다.
도움이된다면, 필자는 Java로 프로그램을 작성했지만 가능하면 그것을 사용할 수있었습니다.하지만 Python으로 이식하는 것은 끝났습니다.
업데이트 : 통찰력을 높이기 위해 단순화 된 버전의 코드를 추가하여 아이디어를 얻습니다. 기본적으로 합계가 100임을 알면 변수와 같을 수있는 모든 조합을 찾으려고합니다. 이것은 간단합니다. 제 버전에서는 큰 숫자와 많은 변수를 사용할 수 있습니다. 그것은 디오 판틴 (Diophantine)이며, 무식한 힘없이 해결할 수있는 알고리즘이 없다고 생각합니다.
int sum = 100;
int a1 = 20;
int a2 = 5;
int a3 = 10;
for (int i = 0; i * a1 <= sum; i++) {
for (int j = 0; i * a1 + j * a2 <= sum; j++) {
for (int k = 0; i * a1 + j * a2 + k * a3 <= sum; k++) {
if (i * a1 + j * a2 + k * a3 == sum) {
System.out.println(i + "," + j + "," + k);
}
}
}
}
프로그래밍에 익숙하지 않아이 질문에 올바르게 답하지 못해서 미안합니다. 이것은 더 일반적인 질문입니다.
해결법
-
==============================
1.일반적으로 성장률을 분석하기 위해 big-O 표기법을 사용하여 알고리즘의 확장 정도를 계량 할 수 있습니다. 알고리즘이 "무력 (brute force)"으로 작동한다고 말하면 어느 정도 확장되는지는 분명하지 않습니다. "brute force"솔루션이 가능한 모든 하위 집합 또는 데이터 집합의 조합을 나열하여 작동하면 거의 확실하게 확장되지 않습니다 (각각 점근 적 복잡성 O (2n) 또는 O (n!)을 갖습니다). 귀하의 무차별 대항력 솔루션이 모든 요소 쌍을 찾고 각각을 검사함으로써 작동한다면, 합리적으로 잘 확장 될 것입니다 (O (n2)). 그러나 알고리즘이 어떻게 작동하는지에 대한 정보가 없어도 말하기는 어렵습니다.
일반적으로 성장률을 분석하기 위해 big-O 표기법을 사용하여 알고리즘의 확장 정도를 계량 할 수 있습니다. 알고리즘이 "무력 (brute force)"으로 작동한다고 말하면 어느 정도 확장되는지는 분명하지 않습니다. "brute force"솔루션이 가능한 모든 하위 집합 또는 데이터 집합의 조합을 나열하여 작동하면 거의 확실하게 확장되지 않습니다 (각각 점근 적 복잡성 O (2n) 또는 O (n!)을 갖습니다). 귀하의 무차별 대항력 솔루션이 모든 요소 쌍을 찾고 각각을 검사함으로써 작동한다면, 합리적으로 잘 확장 될 것입니다 (O (n2)). 그러나 알고리즘이 어떻게 작동하는지에 대한 정보가 없어도 말하기는 어렵습니다.
프로그램의 장기간의 확장 가능성에 대한 판단의 출발점으로 big-O에 대한 훌륭한 게시물을보고 싶을 수도 있습니다. 일반적으로 성장률 O (n log n), O (n), O (log n) 또는 O (1) 규모의 성장 속도가 O O (n2) 또는 O 성장 속도가 O (2n) 이상인 항목은 전혀 확장되지 않습니다.
또 다른 옵션은 얼마나 잘 연구되었는지보기 위해 해결하려는 문제를 찾아 보는 것입니다. 어떤 문제는 훌륭한 해결책을 가지고있는 것으로 알려져 있습니다. 만약 당신이 그들 중 하나라면, 다른 사람들이 생각해내는 것을 볼 가치가있을 것입니다. 아마도 정말로 잘 스케일 된 매우 깨끗하고 비 짐진 솔루션이있을 것입니다! 일부 다른 문제는 확장 가능한 알고리즘이 전혀 없다고 추측됩니다 (소위 NP 하드 문제). 그렇다면 확장 가능한 접근법을 얻을 수있는 방법이 없다는 것을 확실히 알고 있어야합니다.
마지막으로 스택 오버플로 (Stack Overflow)에서 새로운 질문을 던지면 입력하려는 내용에 대해 설명 할 수 있습니다. 어쩌면 커뮤니티가 처음 예상했던 것보다 효율적으로 문제를 해결할 수 있습니다!
편집 : 당신이 해결하려고하는 문제에 대한 설명을 감안할 때, 지금 당장 0에서 목표로하려는 번호까지 변수 당 루프를 수행하고 있습니다. 이 알고리즘의 복잡성은 O (Uk)입니다. 여기서 k는 변수의 수이고 U는 합계입니다. 이 접근 방식은 전혀 잘 확장되지 않습니다. 위의 경우에 각각의 새로운 변수를 도입하면 algori2thm이 100 배 더 느리게 실행됩니다. 100 개의 변수를 원한다면 확실히 확장되지 않습니다!
그러나, 나는 그 문제를 해결하기 위해 O (Uk) 메모리를 사용하는 런타임이 O (U2k) 인 상당히 훌륭한 알고리즘이 있다고 생각한다. 직감은 다음과 같습니다. 1, 2, 4를 합하여 10을 얻고 싶다고 가정 해보십시오. 이렇게하는 방법은 여러 가지가 있습니다.
2 * 4 + 1 * 2 + 0 * 1 2 * 4 + 0 * 2 + 2 * 1 1 * 4 + 3 * 2 + 0 * 1 1 * 4 + 2 * 2 + 2 * 1 1 * 4 + 1 * 2 + 4 * 1 1 * 4 + 0 * 2 + 6 * 1 0 * 4 + 5 * 2 + 0 * 1 0 * 4 + 4 * 2 + 2 * 1 0 * 4 + 3 * 2 + 4 * 1 0 * 4 + 2 * 2 + 6 * 1 0 * 4 + 1 * 2 + 8 * 1 0 * 4 + 0 * 2 + 10 * 1핵심 관측은 우리 모두를 합계로 쓸 수 있지만 더 중요한 것은 합계의 각 항이 이전 항보다 크지 않은 합계입니다.
2 * 4 + 1 * 2 + 0 * 1 = 4 + 4 + 2 2 * 4 + 0 * 2 + 2 * 1 = 4 + 4 + 1 + 1 1 * 4 + 3 * 2 + 0 * 1 = 4 + 2 + 2 + 2 1 * 4 + 2 * 2 + 2 * 1 = 4 + 2 + 2 + 1 + 1 1 * 4 + 1 * 2 + 4 * 1 = 4 + 2 + 1 + 1 + 1 + 1 1 * 4 + 0 * 2 + 6 * 1 = 4 + 1 + 1 + 1 + 1 + 1 + 1 0 * 4 + 5 * 2 + 0 * 1 = 2 + 2 + 2 + 2 + 2 0 * 4 + 4 * 2 + 2 * 1 = 2 + 2 + 2 + 2 + 1 + 1 0 * 4 + 3 * 2 + 4 * 1 = 2 + 2 + 2 + 1 + 1 + 1 + 1 0 * 4 + 2 * 2 + 6 * 1 = 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 0 * 4 + 1 * 2 + 8 * 1 = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 0 * 4 + 0 * 2 + 10 * 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1그래서 이것은 목표까지 요약 할 수있는 모든 가능한 방법을 생성하는 방법에 대한 흥미로운 아이디어를 제공합니다. 아이디어는 첫 번째 계수를 수정 한 다음 나머지 합계를 만드는 모든 가능한 방법을 생성하는 것입니다. 즉, 우리는 재귀 적으로 문제를 생각할 수 있습니다. 변수를 x1, x2, ..., xn으로 순서대로 나열하면 x1에 대한 특정 계수를 수정 한 다음 x2, ..., xn을 사용하여 합계 - c_1 x_1을 합산하는 문제를 해결할 수 있습니다.
지금까지이 모든 것이 그다지 환상적이지는 않습니다. 실제로, 당신이 위에서 뭘하고 있는지 정확히 알 수 있습니다. 그러나 우리가 사용할 수있는 트릭이 있습니다. 우리가이 문제를 재귀 적으로 생각하는 한, 반대의 방식으로 문제를 생각해 봅시다. 합계로 시작해서 그것을 분해하려고하는 대신, 0으로 시작하여 우리가 할 수있는 모든 것을 구축하려고 시도한다면 어떨까요?
여기에 아이디어가 있습니다. 우리가 이미 x1의 합계를 사용하여 만들 수있는 모든 수를 이미 알고 있다고 가정합니다. 그러면 0과 합계 사이의 모든 수 k에 대해 x2와 x1 중 k를 x1의 조합으로 만들 수있는 임의의 조합 중에서 k-c2 x2를 만들 수 있습니다. 그러나 우리는 이것을 미리 계산했기 때문에 c2의 가능한 모든 합법적 인 값을 반복하고, k - c2 x2를 계산하고, 어떻게 만들어야하는지 알 수 있습니다. 테이블 엔트리 [x, y]가 "정확하게 U까지 합계하는 방식으로 첫 번째 y 값을 합산 할 수 있습니까?"와 같은 부울 값의 거대한 U x (k + 1) 테이블을 저장한다고 가정하면, 테이블을 효율적으로 채울 수 있습니다. 이것은 동적 프로그래밍이라고하며 강력한 알고리즘 도구입니다.
보다 구체적으로, 이것이 작동하는 방법은 다음과 같습니다. k 개의 변수가 주어지면, U x (k + 1) 개의 T 값 표를 만듭니다. 그런 다음, 모든 x> 0에 대해 T [0] [0] = true 및 T [x] [0] = false를 설정합니다. 여기서 T [0] [0]은 " 첫 번째 0 변수의 선형 조합? " 대답은 분명히 예 (공백의 합이 0입니다!)입니다. 그러나 변수의 선형 조합이 아닌 다른 합계에 대해서는 확실히 만들 수 없습니다.
자, i = 1 .. k에 대해서 우리는 T [x] [i]의 값을 채우려고 시도 할 것입니다. T [x] [i]는 "x를 첫 번째 변수의 선형 조합으로 만들 수 있습니까?"라는 의미입니다. 자, 우리는 k - c xi가 x 1, x 2, ..., x i - 1의 선형 조합을 사용하여 만들 수있는 계수 c가 있다면 이것을 할 수 있음을 압니다. 그러나 어떤 C에 대해서도 그것은 T [x-cxi] [i-1]은 참이다. 따라서 우리는 말할 수있다.
for i = 1 to k for z = 0 to sum: for c = 1 to z / x_i: if T[z - c * x_i][i - 1] is true: set T[z][i] to true루프를 살펴보면 바깥 쪽 루프는 k 번 실행되고 내부 루프는 반복 당 총 횟수가 실행되며 가장 안쪽 루프는 최대 반복 횟수만큼 실행됩니다. 그들의 제품은 (위에서 설명한 우리의 표기법을 사용하여) O (U2 k)입니다. 원래 O (Uk) 알고리즘보다 뛰어납니다.
그러나이 정보를 사용하여 목표까지 요약 할 수있는 가능한 모든 방법을 나열하려면 어떻게합니까? 여기의 트릭은 테이블을 사용하여 많은 사람들이 일하지 않을 때 모든 가능한 조합을 검색하는 데 막대한 노력을 낭비하지 않도록한다는 것입니다.
예를 보도록하겠습니다. 이 테이블을 완전히 계산하고 모든 솔루션을 나열하려고한다고 가정합니다. 하나의 아이디어는 마지막 변수의 계수가 0이고 마지막 변수가 1 일 때 모든 솔루션을 나열하는 것에 대해 생각하는 것입니다. 이전에 사용한 방법의 문제점은 일부 계수의 경우 전혀 솔루션이 없을 수도 있다는 것입니다 . 그러나 우리가 위에 만든 테이블로, 우리는 그 가지들을 제거 할 수 있습니다. 예를 들어 계수가 0 인 xk로 시작하는 솔루션이 있는지 알아보기를 원한다고 가정합니다. 즉, 첫 번째 k - 1 변수의 선형 조합을 요약하는 방법이 있는지 묻습니다. 그 값들의 합은 합계입니다. 이는 T [k-1]이 참인 경우에만 가능하다. 그것이 참이라면 합계로 합산하는 방식으로 나머지 값에 계수를 재귀 적으로 할당 해 볼 수 있습니다. 그렇지 않다면이 계수를 건너 뛰고 다음으로 넘어갑니다.
재귀 적으로 다음과 같이 보입니다.
function RecursivelyListAllThatWork(k, sum) // Using last k variables, make sum /* Base case: If we've assigned all the variables correctly, list this * solution. */ if k == 0: print what we have so far return /* Recursive step: Try all coefficients, but only if they work. */ for c = 0 to sum / x_k: if T[sum - c * x_k][k - 1] is true: mark the coefficient of x_k to be c call RecursivelyListAllThatWork(k - 1, sum - c * x_k) unmark the coefficient of x_k재귀 적으로 방대한 양의 낭비되는 작업을 건너 뛰기 위해 방금 생성 한 표의 값을 사용하여 작동하는 모든 솔루션이 나열됩니다. 이 테이블을 작성한 후에는 여러 컴퓨터로 작업을 나누어서 전체 솔루션의 하위 집합을 나열하고 모두 병렬로 처리하여이 작업을 나눌 수 있습니다.
희망이 도움이!
-
==============================
2.정의에 의해, brute force 알고리즘은 어리 석다. 좀 더 똑똑한 알고리즘을 사용하면 훨씬 나아질 것입니다. 더 나은 알고리즘은 수행해야 할 작업을 줄여 주며 여러 컴퓨터에 "수평 확장"할 필요없이 수행 할 수 있습니다.
정의에 의해, brute force 알고리즘은 어리 석다. 좀 더 똑똑한 알고리즘을 사용하면 훨씬 나아질 것입니다. 더 나은 알고리즘은 수행해야 할 작업을 줄여 주며 여러 컴퓨터에 "수평 확장"할 필요없이 수행 할 수 있습니다.
알고리즘에 관계없이 필요한 데이터 또는 계산 능력이 너무 커서 Hadoop과 같은 것을 사용해야하는 시점이 있습니다. 그러나 대개, 우리는 여기서 빅 데이터를 실제로 말하고 있습니다. 요즘에는 하나의 PC로 이미 많은 것을 할 수 있습니다.
-
==============================
3.이 문제를 해결하는 알고리즘은 수작업으로 수학을 배울 때 배울 수있는 프로세스 또는 십진수 또는 16 진수와 같은 다른 기본 단위로 변환하는 과정에서 닫힙니다. 단 두 가지 예는 하나의 표준 솔루션 만 찾습니다.
이 문제를 해결하는 알고리즘은 수작업으로 수학을 배울 때 배울 수있는 프로세스 또는 십진수 또는 16 진수와 같은 다른 기본 단위로 변환하는 과정에서 닫힙니다. 단 두 가지 예는 하나의 표준 솔루션 만 찾습니다.
재귀가 끝나기 위해서는 데이터 배열을 정렬하는 것이 중요합니다. 효율적이고 재귀 횟수를 제한하려면 더 높은 데이터 값으로 시작하는 것이 중요합니다.
구체적으로, 이론상 예상대로 각 재귀에 대한 결과 벡터 coeff의 사본을 사용하여이 문제에 대한 자바 재귀 구현을 설명합니다.
import java.util.Arrays; public class Solver { public static void main(String[] args) { int target_sum = 100; // pre-requisite: sorted values !! int[] data = new int[] { 5, 10, 20, 25, 40, 50 }; // result vector, init to 0 int[] coeff = new int[data.length]; Arrays.fill(coeff, 0); partialSum(data.length - 1, target_sum, coeff, data); } private static void printResult(int[] coeff, int[] data) { for (int i = coeff.length - 1; i >= 0; i--) { if (coeff[i] > 0) { System.out.print(data[i] + " * " + coeff[i] + " "); } } System.out.println(); } private static void partialSum(int k, int sum, int[] coeff, int[] data) { int x_k = data[k]; for (int c = sum / x_k; c >= 0; c--) { coeff[k] = c; if (c * x_k == sum) { printResult(coeff, data); continue; } else if (k > 0) { // contextual result in parameters, local to method scope int[] newcoeff = Arrays.copyOf(coeff, coeff.length); partialSum(k - 1, sum - c * x_k, newcoeff, data); // for loop on "c" goes on with previous coeff content } } } }하지만 이제 코드가 특별한 경우입니다. 각 coeff에 대한 마지막 값 테스트가 0이므로 복사가 필요하지 않습니다.
복잡도 추정으로 최대 재귀 호출 깊이를 data.length * min ({data})로 사용할 수 있습니다. 확실히 잘 확장되지 않으며 스택 추적 메모리 (-Xss JVM 옵션)가 제한적입니다. 큰 데이터 세트의 경우 스택 오버플로 오류로 인해 코드가 실패 할 수 있습니다.
이러한 단점을 피하기 위해 "탈퇴"프로세스가 유용합니다. 이것은 나중에 호출 할 실행 컨텍스트를 저장하기 위해 프로그램 스택에 의해 메소드 호출 스택을 대체하는 것으로 구성됩니다. 그 코드는 다음과 같습니다.
import java.util.Arrays; import java.util.ArrayDeque; import java.util.Queue; public class NonRecursive { // pre-requisite: sorted values !! private static final int[] data = new int[] { 5, 10, 20, 25, 40, 50 }; // Context to store intermediate computation or a solution static class Context { int k; int sum; int[] coeff; Context(int k, int sum, int[] coeff) { this.k = k; this.sum = sum; this.coeff = coeff; } } private static void printResult(int[] coeff) { for (int i = coeff.length - 1; i >= 0; i--) { if (coeff[i] > 0) { System.out.print(data[i] + " * " + coeff[i] + " "); } } System.out.println(); } public static void main(String[] args) { int target_sum = 100; // result vector, init to 0 int[] coeff = new int[data.length]; Arrays.fill(coeff, 0); // queue with contexts to process Queue<Context> contexts = new ArrayDeque<Context>(); // initial context contexts.add(new Context(data.length - 1, target_sum, coeff)); while(!contexts.isEmpty()) { Context current = contexts.poll(); int x_k = data[current.k]; for (int c = current.sum / x_k; c >= 0; c--) { current.coeff[current.k] = c; int[] newcoeff = Arrays.copyOf(current.coeff, current.coeff.length); if (c * x_k == current.sum) { printResult(newcoeff); continue; } else if (current.k > 0) { contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff)); } } } } }필자의 견지에서 볼 때 단일 스레드 실행에서 더 효율적이지는 않습니다. 스택 메커니즘에는 이제 coeff 배열 복사본이 필요합니다.
from https://stackoverflow.com/questions/7265576/can-brute-force-algorithms-scale by cc-by-sa and MIT license
'HADOOP' 카테고리의 다른 글
| [HADOOP] hadoop 작업에 외부 항아리를 추가하는 방법? (0) | 2019.05.31 |
|---|---|
| [HADOOP] 높은 카디널리티 필드에 대한 하이브 쿼리 성능 (0) | 2019.05.31 |
| [HADOOP] Hadoop WordCount 예제가지도에서 멈춤 100 % 감소 0 % (0) | 2019.05.31 |
| [HADOOP] spark에서 textinputformat.record.delimiter 설정하기 (0) | 2019.05.31 |
| [HADOOP] jdbc와 kerberos keytab을 사용하여 하이브 메타 스토어에 액세스하기 (0) | 2019.05.31 |