4
실제로 선형 시간 알고리즘을 병렬 처리해야하는 경우가 있습니까? 선생님은 가치가 없다고 주장하지만 저는 그렇게 믿지 않습니다.이미 선형 시간 알고리즘 병렬화
A
답변
0
입력이 충분하면 은입니다. 항상.
예제 : 정렬되지 않은 'List'에서 가장 큰 숫자를 찾는 순진한 알고리즘은 목록을 순회합니다. 레코드를 찾으려면 O(n) 주문 시간이 필요합니다.
100 개 또는 1000 개의 레코드가 있으면 괜찮습니다.
10 억 개의 레코드가 있다면 어떨까요? 목록을 여러 CPU로 분할하고 각 CPU가 최대 값을 찾으면 작업 할 새로운 작은 목록이 생깁니다. 이것을 다시 나눌 수 있습니다 => 병렬, 그리고 더 빠릅니다. 효율적으로 나누고 줄이면 O(log(n))이라고 생각합니다. 및은 n 개의 CPU가입니다.
요점 : 입력 내용이 충분히 큰 경우 O(n)은 더 이상 충분하지 않습니다. O (n)을 수행해야 할 필요에 따라 원하는 시간에 비해 너무 많은 초, 분, 시간이 걸릴 수 있습니다.
참고 : 위에서 O(n) 또는 O(log(n))이라고 말하면 검색을 완료하는 데 걸리는 시간을 나타냅니다. 즉 이 아닌 모든 CPU에서 수행되는 '총 작업'. 일반적으로 알고리즘을 병렬 처리하면 CPU가 수행하는 총 작업이 다소 증가합니다.
+0
문제가 모든 요소를 검사해야하는 경우 O (n)보다 개선 될 수 없습니다. 그러나 병렬 처리는 검사를 동시에 수행함으로써 더 빨리 수행 할 수 있습니다. –
+0
O (n)은 입력 크기로 계산 시간 스케일링을 위해 대부분의 사람들에 의해 암묵적으로 사용되며, 귀하의 대답은 대용량 병렬 컴퓨터 (예 : FPGA)에서 * 프로세서 * 또는 시간 스케일링의 수로 시간 스케일링을 참조하는 것 같습니다. . 'O (log n)'을 한정하십시오. 그렇지 않으면 매우 혼란 스럽습니다. – thiton
+0
예, 끝에 메모를 편집했습니다. – ArjunShankar
4
나는 선생님도 동의하지 않습니다. 필자의 주장은 MapReduce에서 실행되는 많은 알고리즘이 선형 시간 알고리즘이라는 것입니다.
예를 들어 색인 생성, 많은 html 페이지 (예 : 위키 피 디아의 모든 페이지)를 탐색하고 특정 단어를 찾는 것은 입력에서 선형 인 알고리즘입니다. 그러나 병렬 처리 없이는 실행할 수 없습니다.
12
선생님이 오인 된 것입니다. 단일 CPU 알고리즘의 런타임 복잡성 (O (n), O (log n) 등)은 병렬화의 이점 여부에 영향을 미치지 않습니다.
코드를 1 CPU에서 K CPU로 변경하면 실행 시간을 K로 나눌 수 있습니다. 허공에서 CPU를 임의로 만들 수 없으므로 K는 사실 상수입니다. 따라서 런타임 복잡성은 병렬 처리의 영향을받지 않습니다. 당신이 할 수있는 일은 지속적인 요소 개선을하는 것입니다.
가치가 없다고 말하는 것은 아닙니다. 어떤 경우에는 2 배의 개선이 큰 도움이됩니다. 또한 수천 개의 CPU로 구성된 대규모 병렬 시스템에서 상수는 상당히 커집니다.
+0
+1하지만 K는 하나의 시스템을 언급 할 때만 상수입니다. 다양한 시스템의 범위에 걸친 알고리즘의 성능에 대해 말하면, K는 변수가됩니다. –
+0
@Shane MacLaughlin - K는 런타임 복잡성과 관련하여 여전히 일정합니다. 이는 n (입력 길이)의 함수가 아니기 때문입니다. – mbeckish
+0
+1 ""허공에서 CPU를 임의로 만들 수 없기 때문에 : P – ArjunShankar
0
단일 코어, 단일 CPU, 단일 컴퓨터 환경 및 CPU 바운드 작업이 주어지면 교사가 올바른 것입니다. (비록이 경우 다중 스레드를 실행하고있을지라도 병렬로 작동한다는 환상을 감안할 때 실제로는 병렬로 실행되지 않는다고 주장 할 수는 있지만)
요즘은 단일 코어 시스템이 거의 없습니다. , 심지어 많은 스마트 폰이 멀티 코어로 이동하고 있기 때문에 실제로는 병렬화의 이점을 누릴 수 있습니다. 태스크가 작 으면 스레드 생성 비용이 이점보다 높아지고 마찬가지로 프로세서 사이클에 비용이 소요되는 컨텍스트 전환이 발생하기 때문에 가능성이 높습니다.현명하게 수행되지 않으면 항상 병렬 처리를 수행하면 실제로 처리 속도가 느려질 수 있습니다.
4
명확한 예. 그래픽 카드는 병렬 처리를 제공하며 GPU에서 CPU에서 병렬 계산으로 전환하면 많은 시간을 절약 할 수 있습니다. 선형 시간 알고리즘은 병렬로 실행될 때 기념비적 인 속도 향상을 가질 수 있습니다. GPGPU 및 "응용 프로그램"섹션을 참조하거나 "그래픽 카드 계산"에 대해서는 google을 참조하십시오.
당신이 물어 보지 않았지만, 이론에서 답 은 (프로세서의 다항식 번호가 부여 대수 시간에 해결 될 수있다) 예, 복잡성 클래스 NC는 "효과적으로 병렬 처리"할 수있는 문제가 아니라 명확한이다, 과 다항 시간에 풀릴 수 있지만 NC에 있지 않은 것으로 의심되는 "P-complete"문제가있다. (P 문제와 NP 완전 문제가있는 것처럼 NP 완료도 P에 있지 않은 것으로 의심된다)
관련 문제
- 1. 조합 알고리즘 병렬화
- 2. 최대 공약수를 찾기위한 선형 시간 알고리즘
- 3. 그래프를 강하게 연결하기위한 선형 시간 알고리즘
- 4. 파이썬 : Levenberg Marquardt 알고리즘 병렬화
- 5. 선형 패턴 일치를위한 알고리즘?
- 6. 트리에서 가장 긴 경로에 대한 선형 시간 알고리즘
- 7. 병렬화
- 8. 선형 적으로 증가하는 암흑 알고리즘
- 9. Python에서 SQLITE3 액세스 시간 줄이기 (병렬화?)
- 10. 선형 시간 일반 구문 분석기
- 11. 설계 및 선형 시간 알고리즘을
- 12. 선형 레이아웃을 허용하는 빠른 알고리즘/데이터 구조?
- 13. 선형 적합을 위해 데이터를 결합하는 알고리즘?
- 14. 알고리즘 - 하나의 변수에서 선형 방정식을 푸십시오.
- 15. Big-Theta (n) 선형 정렬 알고리즘?
- 16. 재귀 호출을 사용한 선형 검색 알고리즘?
- 17. 선형 방정식을 풀기위한 병렬 반복 알고리즘
- 18. 시간 복잡도 알고리즘 분석
- 19. 다항식 시간 알고리즘
- 20. 시간 접근 알고리즘?
- 21. 동작 병렬화
- 22. 의존성이있는 중첩 루프 병렬화
- 23. 벤치마킹 : 알고리즘 사용자 시간 받기
- 24. 시간 복잡도에 대한 알고리즘 검토
- 25. 은행가 알고리즘 계산 시간 복잡도
- 26. 시간 복잡도에 대한 알고리즘 분석
- 27. 데이터베이스에 이미 존재하는 시간 찾기
- 28. 해시 콜리 전 선형 검사 실행 시간
- 29. 문자열에 대한 선형 시간 정렬 알고리즘은 무엇입니까?
- 30. 선형 검색 알고리즘의 평균 사례 실행 시간
이 알고리즘은 일반적으로 해당 알고리즘에 의해 처리 될 요소의 수에 의존하며, 이들 요소는 서로간에, 물론 병렬 처리기가 있어도 속도를 향상시킬 수 있는지 여부를 묻는 메시지가 표시됩니다. – codeling
나는 이것이 완전히 잘못된 생각이라고 말하고 싶습니다. 속도가 너무 느리고 (빠르지 만) 병렬화 될 수 있다면 가치가 있습니다. 시간과 관계없이 복잡성과 기타 등등. 현실 세계에서는 실시간이 중요합니다. 너무 느리지 않으면 문제가되지 않습니다. 실제로는 지수 함수 알고리즘 일 수도 있습니다. – harold