알고리즘 효율

컴퓨터 과학에서 알고리즘 효율은 알고리즘에 의해 사용되는 계산 자원의 양과 관련된 알고리즘의 특성입니다.알고리즘을 분석하여 자원 사용량을 결정해야 하며, 알고리즘의 효율은 다른 자원의 사용에 기초하여 측정할 수 있습니다.알고리즘 효율은 반복 프로세스 또는 연속 프로세스의 엔지니어링 생산성과 유사하다고 생각할 수 있습니다.

효율성을 최대화하려면 리소스 사용을 최소화하는 것이 좋습니다.그러나 시간과 공간의 복잡성과 같은 다른 자원은 직접 비교할 수 없기 때문에 두 알고리즘 중 어느 것이 더 효율적인 것으로 간주되는지는 종종 효율의 측정이 가장 중요하다고 간주되는가에 달려 있다.

예를 들어 버블 정렬과 팀 정렬은 모두 항목 목록을 가장 작은 항목에서 가장 큰 항목 순으로 정렬하는 알고리즘입니다.버블 정렬은 요소의 제곱($$ $({n\mathrm{}}^{}$2)$${$textstyle$ O$(n^{2$ '빅O 표기법 참조)에 비례하여 목록을 정렬하지만 목록 길이에 따라 일정한 추가 메모리($$( $1$)$${$textstyle$O(1$)})$만 필요로 합니다.Timsort sorts the list in time linearithmic (proportional to a quantity times its logarithm) in the list's length (${\textstyle O(n\log n)}$), but has a space requirement linear in the length of the list (${\textstyle O(n)}$).특정 응용 프로그램에 대해 대용량 목록을 고속으로 정렬해야 하는 경우에는 팀 정렬을 선택하는 것이 좋습니다. 그러나 정렬의 메모리 공간을 최소화하는 것이 더 중요한 경우에는 버블 정렬을 선택하는 것이 좋습니다.

배경

시간 대비 효율의 중요성은 1843년 Ada Lovelace에 의해 찰스 배비지의 기계 분석 엔진에 적용된 바와 같이 강조되었습니다.

"거의 모든 계산에서 프로세스의 승계를 위한 다양한 준비가 가능하며, 계산 엔진을 위해 다양한 고려사항이 이들 프로세스 선택에 영향을 미칠 수 있습니다.중요한 목적 중 하나는 계산 ^[1]완료에 필요한 시간을 최소한으로 줄이는 방법을 선택하는 것이다.

초기의 전자 컴퓨터는 제한된 속도와 제한된 랜덤 액세스 메모리를 가지고 있었다.따라서 시공간의 트레이드오프가 발생하였습니다.태스크는 많은 메모리를 사용하는 고속 알고리즘을 사용할 수도 있고 적은 메모리를 사용하는 저속 알고리즘을 사용할 수도 있습니다.엔지니어링의 트레이드오프는 사용 가능한 메모리에 들어갈 수 있는 가장 빠른 알고리즘을 사용하는 것이었습니다.

최신 컴퓨터는 초기 컴퓨터보다 훨씬 더 빠르고 사용 가능한 메모리(킬로바이트가 아닌 기가바이트)가 훨씬 더 많습니다.그럼에도 불구하고 Donald Knuth는 효율성이 여전히 중요한 고려사항이라고 강조했습니다.

확립된 엔지니어링 분야에서는 쉽게 얻을 수 있는 12%의 향상은 결코 한계로 간주되지 않습니다.소프트웨어 ^[2]엔지니어링에서도 같은 견해가 우세해야 한다고 생각합니다.

개요

알고리즘은 계산 비용이라고도 하는 자원 소비량이 허용 가능한 수준 이하인 경우 효율적인 것으로 간주됩니다.대략적으로 말하면, 「허용 가능」이란, 사용 가능한 컴퓨터상에서 적절한 시간 또는 공간내에서 동작하는 것을 의미합니다.일반적으로 입력 크기의 함수로서 동작합니다.1950년대 이후 컴퓨터는 사용 가능한 계산 능력과 메모리 용량이 모두 극적으로 증가했기 때문에 10년 전만 해도 현재의 허용 수준은 허용되지 않았습니다.실제로 컴퓨터 처리 능력이 2년마다 약 2배씩 증가했기 때문에 최신 스마트폰 및 임베디드 시스템에서 허용되는 효율이 높은 태스크는 10년 전에는 산업용 서버에서는 허용할 수 없을 정도로 비효율적이었을 수 있습니다.

컴퓨터 제조업체들은 종종 더 높은 성능을 가진 새로운 모델을 출시합니다.소프트웨어 비용은 매우 높을 수 있습니다.따라서 기존 컴퓨터와 호환성이 있는 경우 고성능을 얻기 위한 가장 간단하고 저렴한 방법은 더 빠른 컴퓨터를 구입하는 것일 수 있습니다.

알고리즘에 의해 사용되는 자원을 측정할 수 있는 방법은 여러 가지가 있습니다.가장 일반적인 것은 속도와 메모리 사용률입니다.다른 측정에는 전송 속도, 일시적인 디스크 사용률, 장기간의 디스크 사용률, 소비전력, 총소유비용, 외부 자극에 대한 응답시간 등이 있습니다.이러한 측정의 대부분은 알고리즘에 대한 입력의 크기, 즉 처리할 데이터의 양에 따라 달라집니다.또한 데이터가 정렬된 방식에 따라 달라질 수 있습니다. 예를 들어 일부 정렬 알고리즘은 이미 정렬된 데이터나 역순으로 정렬된 데이터에 대해 성능이 저하됩니다.

실제로는 알고리즘의 효율성에 영향을 줄 수 있는 다른 요인(예: 정확도 및/또는 신뢰성 요건)이 있습니다.아래에 상술한 바와 같이 알고리즘의 실장 방식도 실제 효율성에 큰 영향을 미칠 수 있습니다.다만, 이 문제의 많은 측면은 최적화 문제와 관련되어 있습니다.

이론적 분석

알고리즘의 이론적 분석에서 일반적인 방법은 점근적 의미에서 알고리즘의 복잡성을 추정하는 것입니다.자원 소비량 또는 "복잡도"를 기술하기 위해 가장 일반적으로 사용되는 표기법은 $입력$n(\$textstyle$ n$)$ 크기의 함수로 알고리즘의 복잡성을 나타내는 Donald Knuth의 Big O 표기법이다. Big O 표기법은 함수 복잡도의 점근적 척도이다. $여기$서$$f ($n$ ) $=O$ ($g$ ) {$textstyle$f($n)$$O{\bigl (}g$ $(n)$ {\$bigr}}:$ 알고리즘의 시간 요건은 대략${\displaystyle }$g ($n)$ {$style$g($n$에 비례하며$,$ n {$textstyle$ n$}$이 임의로 커짐에 $따라$ g${\displaystyle }$($)$ {$display g(n}$보다 작은 하위 항은 생략됩니다.이 추정치는 n$(\textstyle$n)이$$ 작을 $경우$ 오해를 일으킬 수 있지만, 일반적으로 n$(\textstyle$ n$)$이 클 $경우$ 점근 표기이므로 충분히 정확하다.예를 들어, 버블 정렬은 소수의 항목만 정렬해야 하는 경우 병합 정렬보다 더 빠를 수 있지만, 어느 구현이든 작은 목록의 성능 요구 사항을 충족할 수 있습니다.일반적으로 프로그래머는 큰 입력 크기로 효율적으로 확장되는 알고리즘에 관심이 있으며, 대부분의 데이터 집약적인 프로그램에서 발생하는 길이의 목록에는 버블 정렬보다 병합 정렬이 선호됩니다.

알고리즘의 점근 시간 복잡도에 적용되는 빅 O 표기법의 예는 다음과 같습니다.

표기법	이름.	예
${\displaystyle O(1)}$	일정한	정렬된 측정값 목록에서 중위수 찾기, 고정 크기 조회 테이블 사용, 항목 검색에 적합한 해시 함수 사용.
${\displaystyle O(\log n)}$	로그의	이진 검색 또는 균형 잡힌 검색 트리와 이항 힙의 모든 작업을 사용하여 정렬된 배열에서 항목 찾기
${\displaystyle O(n)}$	선형의	정렬되지 않은 목록 또는 잘못된 형식의 트리(최악의 경우) 또는 정렬되지 않은 배열에서 항목 찾기, 리플 캐리 방식으로 두 개의 n비트 정수 추가.
${\displaystyle O(n\log n)}$	선형, 로그 선형 또는 준선형	Fast Fourier 변환 수행: 힙소트, 퀵소트(최적의 경우 및 평균의 경우) 또는 병합 정렬
${\displaystyle O(n^{2})}$	이차적인	간단한 알고리즘에 의한 2개의 n자리 숫자 곱하기: 버블 정렬(최악의 경우 또는 단순 구현), 셸 정렬, 퀵 정렬(최악의 경우), 선택 정렬 또는 삽입 정렬
${\displaystyle O(c^{n}),\;c>1$	지수적	동적 프로그래밍을 사용하여 출장 중인 세일즈맨 문제에 대한 최적의 솔루션(대략적이지 않은)을 찾고, 브루트포스 검색을 사용하여 두 개의 논리문이 동일한지 확인

벤치마크: 퍼포먼스 측정

새로운 버전의 소프트웨어를 사용하거나 경쟁 시스템과 비교하기 위해 알고리즘의 상대적인 성능을 측정하는 데 도움이 되는 벤치마크를 사용하는 경우가 있습니다.예를 들어 새로운 정렬 알고리즘이 생성되면 기능 개선을 고려하여 적어도 기존 데이터와 마찬가지로 효율적이라는 것을 보증하기 위해 이전 알고리즘과 비교할 수 있습니다.벤치마크란 대체 공급업체의 다양한 제품을 비교할 때 기능 및 성능 측면에서 고객의 특정 요건에 가장 적합한 제품을 추정하기 위해 사용할 수 있습니다.예를 들어 메인프레임 세계에서는 Syncsort와 같은 독립 소프트웨어 회사의 특정 독점 정렬 제품이 IBM과 같은 주요 공급업체의 제품과 속도를 놓고 경쟁합니다.

예를 들어^[3][4], 일부 벤치마크에서는 다양한 컴파일 및 해석된 언어의 상대적인 속도를 비교한 분석을 작성할 수 있습니다.컴퓨터 언어 벤치마크 게임은 여러 프로그래밍 언어로 일반적인 프로그래밍 문제의 구현 성능을 비교합니다.

"직접 실행" 벤치마크를 작성해도 다양한 사용자 지정 기준을 사용하여 다양한 프로그래밍 언어의 상대적 성능을 보여줄 수 있습니다.이것은 크리스토퍼 W. 코웰샤의 "나인 언어 퍼포먼스 요약"이 예를 ^[5]들어 보여주듯이 매우 간단합니다.

구현에 관한 우려 사항

구현 문제는 또한 프로그래밍 언어의 선택, 알고리즘의 실제 ^[6]코드화 방법, 특정 언어에 대한 컴파일러의 선택, 사용되는 컴파일 옵션 또는 사용 중인 운영 체제와 같은 효율성에 영향을 미칠 수 있습니다.많은 경우 인터프리터에 의해 구현된 언어는 ^[3]컴파일러에 의해 구현된 언어보다 훨씬 느릴 수 있습니다.적시 컴파일 및 통역 언어에 대한 기사를 참조하십시오.

시간 또는 공간 문제에 영향을 미칠 수 있지만 프로그래머가 통제할 수 없는 다른 요인도 있습니다. 데이터 정렬, 데이터 입도, 캐시 로컬리티, 캐시 일관성, 가비지 컬렉션, 명령 수준 병렬 처리, 멀티 스레드(하드웨어 또는 소프트웨어 수준), 동시 멀티태스킹, 서브루틴 계산 등이 있습니다.ls.^[7]

일부 프로세서는 벡터 처리 기능을 가지고 있어 하나의 명령으로 여러 오퍼랜드에서 동작할 수 있습니다.프로그래머나 컴파일러가 이러한 기능을 사용하는 것은 쉽거나 쉽지는 않을 수 있습니다.순차 처리를 위해 설계된 알고리즘은 병렬 처리를 이용하기 위해 완전히 재설계되거나 쉽게 재구성될 수 있습니다.2010년대 후반 병렬 및 분산 컴퓨팅의 중요성이 커짐에 따라 CUDA, TensorFlow, Hadoop, OpenMP 및 MPI와 같은 병렬 및 분산 컴퓨팅 시스템을 위한 효율적인 고급 API에 대한 투자가 증가하고 있습니다.

프로그래밍에서 발생할 수 있는 또 다른 문제는 동일한 명령 집합(x86-64 또는 ARM 등)과 호환되는 프로세서가 다른 방식으로 명령을 구현하기 때문에 일부 모델에서 상대적으로 빠른 명령이 다른 모델에서 상대적으로 느릴 수 있다는 것입니다.이는 컴파일러의 최적화에 많은 과제가 됩니다.컴파일러는 컴파일러의 퍼포먼스를 최적화하기 위해 컴파일 타깃에서 사용할 수 있는 특정 CPU 및 기타 하드웨어에 대한 지식이 풍부해야 합니다.극단적인 경우 컴파일러는 컴파일 대상 플랫폼에서 지원되지 않는 명령어를 에뮬레이트하도록 강제되어 코드를 생성하거나 외부 라이브러리 호출을 링크하여 다른 플랫폼 상의 하드웨어에서 네이티브하게 지원되고 더 효율적인 결과를 얻을 수 있습니다.이는 부동소수점 산술에 관한 임베디드 시스템에서 흔히 볼 수 있습니다.소형 및 저전력 마이크로컨트롤러는 부동소수점 산술에 대한 하드웨어 지원이 부족하기 때문에 부동소수점 계산을 생성하기 위해 계산 비용이 많이 드는 소프트웨어 루틴이 필요합니다.

자원 사용률 측정

측정은 보통 $입력{\displaystyle }$ n$\$의 크기에 따라 표시됩니다.

가장 일반적인 두 가지 척도는 다음과 같습니다.

• 시간: 알고리즘이 완료되는 데 얼마나 걸립니까?
• 공간: 알고리즘에 필요한 작업 메모리(일반적으로 RAM)의 양여기에는 코드에 필요한 메모리 용량(보조 공간 사용)과 코드가 동작하는 데이터에 필요한 메모리 양(내 공간 사용)의 2가지 측면이 있습니다.

배터리(예: 노트북 및 스마트폰) 또는 매우 길고 큰 계산(예: 슈퍼컴퓨터)을 위해 전원이 공급되는 컴퓨터의 경우, 다른 관심 척도는 다음과 같습니다.

• 직접 소비전력: 컴퓨터를 작동시키기 위해 직접 필요한 전력.
• 간접소비전력: 냉각, 조명 등에 필요한 전력

2018년 현재^[update] 전력 소비량은 임베디드 기기, 시스템 온 칩 기기, 서버 팜에 이르기까지 모든 유형의 컴퓨팅 작업에 중요한 지표로 성장하고 있습니다.이러한 경향은 흔히 그린 컴퓨팅이라고 불립니다.

계산 효율성에 대한 덜 일반적인 척도는 다음과 같은 경우에 적절할 수 있다.

• 전송 크기: 대역폭이 제한 요인이 될 수 있습니다.데이터 압축은 전송되는 데이터 양을 줄이기 위해 사용할 수 있습니다.그림 또는 이미지(예: Google 로고)를 표시하면 "Google" 텍스트의 경우 6바이트를 전송하는 것과 비교하여 수만 바이트(이 경우 48K)의 전송이 발생할 수 있습니다.이는 I/O에 얽매이는 컴퓨팅 태스크에서 중요합니다.
• 외부 공간: 디스크 또는 기타 외부 메모리 장치에 필요한 공간입니다.알고리즘이 실행되는 동안 임시 저장용이거나 나중에 참조하기 위해 장기간 저장해야 할 수 있습니다.
• 응답시간(레이텐시): 이는 컴퓨터 시스템이 외부 이벤트에 신속하게 응답해야 하는 실시간 애플리케이션에서 특히 유용합니다.
• 총소유비용: 특히 컴퓨터가 특정 알고리즘 전용일 경우.

시간을

이론.

알고리즘을 분석합니다.일반적으로 시간 복잡도 분석을 사용하여 입력 데이터 크기의 함수로 실행 시간을 추정합니다.결과는 보통 Big O 표기법을 사용하여 표현됩니다.이는 특히 대량의 데이터를 처리해야 하는 경우 알고리즘을 비교할 때 유용합니다.데이터 양이 적을 때 알고리즘 성능을 비교하려면 더 자세한 추정치가 필요하지만, 이는 그다지 중요하지 않을 수 있습니다.병렬 처리를 포함하는 알고리즘은 분석하기가 더 어려울 수 있습니다.

연습

벤치마크를 사용하여 알고리즘의 사용 시간을 측정합니다.많은 프로그래밍 언어에는 CPU 시간 사용률을 제공하는 기능이 있습니다.장기 실행 알고리즘의 경우 경과 시간도 관심사가 될 수 있습니다.결과는 일반적으로 여러 테스트에 걸쳐 평균화되어야 합니다.

실행 기반 프로파일링은 하드웨어 구성과 멀티프로세서 및 멀티프로그래밍 환경에서 다른 프로그램이나 태스크가 동시에 실행될 가능성에 매우 민감할 수 있습니다.

이러한 종류의 테스트는 또한 특정 프로그래밍 언어, 컴파일러 및 컴파일러 옵션의 선택에 크게 의존하므로 비교되는 알고리즘은 모두 동일한 조건에서 구현되어야 합니다.

공간

이 섹션에서는 알고리즘 실행 중 메모리 리소스(레지스터, 캐시, RAM, 가상 메모리, 세컨더리 메모리)의 사용에 대해 설명합니다.상기의 시간 해석에 대해서는, 통상, 공간 복잡도 해석을 이용해, 입력 데이터의 사이즈로서 함수로서 필요한 런타임 메모리의 추정치를 구한다.결과는 보통 Big O 표기법을 사용하여 표현됩니다.

메모리 사용량에는 최대 4가지 측면을 고려해야 합니다.

• 알고리즘의 코드를 유지하는 데 필요한 메모리의 양.
• 입력 데이터에 필요한 메모리 양입니다.
• 출력 데이터에 필요한 메모리 양입니다.
  • 정렬과 같은 일부 알고리즘은 종종 입력 데이터를 재배치하므로 출력 데이터를 위한 추가 공간이 필요하지 않습니다.이 속성을 "in-place" 작업이라고 합니다.
• 계산 중에 작업 공간으로 필요한 메모리 양입니다.
  • 여기에는 로컬 변수와 계산 중에 호출되는 루틴에 필요한 스택스페이스가 포함됩니다.이 스택스페이스는 재귀적인 기술을 사용하는 알고리즘에 있어서 중요합니다.

초기 전자 컴퓨터와 초기 가정용 컴퓨터는 상대적으로 적은 양의 작업 메모리를 가지고 있었다.예를 들어, 1949년형 EDSAC(Electronic Delay Storage Automatic Calculator)는 최대 1024개의 17비트 워드의 작업 메모리를 가지고 있었지만, 1980년형 Sinclair ZX80은 처음에는 1024개의 8비트 바이트의 작업 메모리를 가지고 있었습니다.2010년대 후반 PC의 RAM은 보통 4 ~32 GB로 메모리 용량이 3억 배 이상 증가했습니다.

캐시 및 메모리 계층

현재의 컴퓨터에는 비교적 많은 메모리(기가바이트)가 탑재되어 있을 가능성이 있기 때문에 한정된 메모리 용량에 알고리즘을 짜넣는 것은 이전보다 훨씬 문제가 되지 않습니다.다만, 다음의 4개의 다른 카테고리의 메모리가 존재하는 것은 중요합니다.

• 프로세서 레지스터는 컴퓨터 메모리 기술 중 가장 고속으로 저장 공간이 가장 적은 기술입니다.최신 컴퓨터의 대부분의 직접 계산은 캐시, 메인 메모리 및 가상 메모리로 업데이트되기 전에 레지스터에 소스 피연산자와 타깃 피연산자를 사용하여 수행됩니다.프로세서 코어에서는 일반적으로 수백 바이트 이하의 레지스터 가용성이 존재하지만 레지스터 파일은 명령 집합 아키텍처에서 정의된 아키텍처 레지스터보다 더 많은 물리 레지스터를 포함할 수 있습니다.
• 캐시 메모리는 메모리 계층에서 두 번째로 빠르고 두 번째로 작은 메모리입니다.캐시는 CPU, GPU, 하드 디스크 드라이브 및 외장 주변기기에 있으며 일반적으로 정적 RAM에 구현됩니다.메모리 캐시는 멀티레벨로 되어 있습니다.저레벨은 더 크고 느리며 일반적으로 멀티코어 프로세서의 프로세서 코어 간에 공유됩니다.캐시 메모리내의 오퍼랜드를 처리하기 위해서, 처리 유닛은 캐시로부터 데이터를 취득해, 레지스터내의 조작을 실행해, 데이터를 캐시에 다시 쓸 필요가 있다.이것은 CPU 또는 GPU의 연산 로직 유닛 또는 부동소수점 유닛(L1 ^[8]캐시에 있는 경우)과 동등한 속도(약 2-10배 느림)로 동작합니다.L1 캐시 누락이 있어 L2 캐시에서 취득하여 L2 캐시에서 기입해야 하는 경우에는 약 10배 느립니다.L2 캐시 누락이 있는 경우에는 L3 캐시에서 취득해야 합니다(존재하는 경우 L2 캐시 미스가 있는 경우에는 L3 캐시에서 취득해야 합니다.
• 메인 물리 메모리는 대부분의 경우 Dynamic RAM(DRAM)에 구현됩니다.메인 메모리는 L3 CPU 캐시보다 훨씬 크고(일반적으로 8메가바이트 이상), 읽기 및 쓰기 지연은 보통 10~100배 ^[8]느립니다.2018년 현재^[update] RAM은 CPU 또는 GPU 메모리로 점점 더 온칩 프로세서를 구현하고 있습니다.
• 가상 메모리는 하드 디스크와 같은 세컨더리 스토리지와 관련하여 구현되는 경우가 가장 많으며, 메모리 계층에 대한 확장으로 스토리지 공간은 훨씬 크지만 대기 시간은 훨씬 길어 일반적으로 RAM ^[8]값의 캐시 누락보다 약 1000배 느립니다.원래 가상 메모리는 실제 사용 가능한 메모리보다 더 많은 양의 메모리를 사용할 수 있다는 인상을 주기 위한 목적으로 제공되었지만, 가상 메모리는 시간 공간의 균형을 유지하고 가상 ^[8]머신을 사용할 수 있도록 하기 위해 현대 사용에서 더 중요합니다.메인 메모리로부터의 캐시 누락은 페이지 장애라고 불리며, 프로그램의 퍼포먼스에 큰 악영향을 미칩니다.

메모리 요구가 캐시 메모리에 적합한 알고리즘은 메인 메모리에 적합한 알고리즘보다 훨씬 빠릅니다.이 알고리즘은 가상 메모리에 의존해야 하는 알고리즘보다 훨씬 빠릅니다.따라서 캐시 교체 정책은 캐시 인식 프로그래밍 및 데이터 정렬과 마찬가지로 고성능 컴퓨팅에 매우 중요합니다.이 문제를 더욱 복잡하게 하기 위해 일부 시스템에는 다양한 유효 속도로 최대 3레벨의 캐시 메모리가 있습니다.시스템마다 이러한 다양한 유형의 메모리가 다르기 때문에 알고리즘 메모리의 필요성은 시스템마다 크게 다를 수 있습니다.

전자 컴퓨팅 초기에는 알고리즘과 데이터가 메인 메모리에 맞지 않으면 알고리즘을 사용할 수 없었습니다.오늘날 가상 메모리의 사용은 많은 메모리를 제공하는 것처럼 보이지만 성능의 희생을 감수해야 합니다.알고리즘과 그 데이터가 캐시 메모리에 들어갈 경우 매우 빠른 속도를 얻을 수 있습니다.이 경우 공간을 최소화하는 것도 시간을 최소화하는 데 도움이 됩니다.이것을 국소성의 원리라고 하며, 기준의 국소성, 공간적 국소성, 시간적 국소성으로 나눌 수 있다.캐시 메모리에 완전히 들어가지는 않지만 참조의 인접성을 나타내는 알고리즘은 상당히 잘 수행될 수 있습니다.

프로그래밍 현황에 대한 비판

• 영국의 컴퓨터 과학자이자 현재 브리스톨 대학의 컴퓨터 과학 교수이자 XMOS Semiconductor의 설립자이자 CTO인 David May FRS는 문제점 중 하나는 비효율적인 문제를 해결하기 위해 무어의 법칙에 의존한다는 것이라고 믿고 있습니다.그는 다음과 ^[9]같이 명시된 무어의 법칙(May's law)에 대한 '대안'을 제시했습니다.

소프트웨어 효율이 18개월마다 반감하여 무어의 법칙을 보완

May는 다음 상태로 넘어갑니다.

유비쿼터스 시스템에서는 실행 명령을 절반으로 줄이면 배터리 수명이 두 배로 늘어나고 빅데이터 세트가 더 나은 소프트웨어와 알고리즘의 기회를 제공합니다. N × N에서 N × log(N)로 작업 수를 줄이면 N이 클 때 극적인 효과가 있습니다.N = 300억의 경우, 이러한 변화는 50년간의 기술 개선과 같습니다.

• 소프트웨어 작가 Adam N. Rosenburg는 블로그 "디지털 컴퓨터의 실패"에서 프로그래밍의 현재 상태를 "소프트웨어 이벤트 지평선"에 가까워지고 있다고 설명했습니다(더글러스 애덤스가 갤럭시 가이드에서^[10] 설명한 가공의 "신발 이벤트 지평선"을 암시).그는 1980년대 이후 생산성의 70dB 요소 손실 또는 "물품 납품 능력의 99.9999%"가 있었다고 추정했습니다."Arthur C 때. 클라크는 저서 2001: 스페이스 오디세이에서 2001년의 컴퓨팅 현실을 컴퓨터 HAL 9000과 비교하면서 컴퓨터가 얼마나 작고 강력한지 지적했지만 컴퓨터 프로그래밍이 얼마나 실망스러웠는지 지적했습니다.

최고의 알고리즘을 위한 경쟁

다음 경기는 심판이 결정한 임의 기준에 따라 최고의 알고리즘에 대한 참가 신청을 받는다.

• 와이어드 매거진^[11]

「 」를 참조해 주세요.

• 알고리즘 분석 - 알고리즘에 필요한 자원을 결정하는 방법
• 산술 부호화: 효율적인 데이터 압축을 위한 가변 길이 엔트로피 부호화의 한 형태
• 연관 어레이 - Patricia tree 또는 Judy 어레이를 사용하여 보다 효율적으로 만들 수 있는 데이터 구조
• 벤치마크 - 정의된 경우 비교 실행 시간을 측정하는 방법
• 베스트 케이스, 워스트 케이스 및 평균 케이스—3가지 시나리오에서 실행 시간을 추정하기 위한 고려 사항
• 바이너리 검색 알고리즘 - 정렬된 어레이를 검색하기 위한 간단하고 효율적인 기술
• 브랜치 테이블—명령 경로 길이, 머신 코드 크기(메모리도 포함)를 줄이는 기술
• 프로그래밍 패러다임 비교—패러다임 고유의 성능 고려 사항
• 컴파일러 최적화: 컴파일러에서 파생된 최적화
• 수학적 연산의 계산 복잡성
• 계산 복잡도 이론
• 컴퓨터 퍼포먼스 - 컴퓨터 하드웨어 메트릭스
• 데이터 압축 - 전송 대역폭 및 디스크 스토리지 절감
• 데이터베이스 인덱스: 데이터베이스 테이블 상의 데이터 취득 처리 속도를 향상시키는 데이터 구조
• 엔트로피 부호화: 문자열 발생 빈도를 치환 기준으로 사용하여 데이터를 효율적으로 부호화합니다.
• 가비지 컬렉션: 사용 후 메모리 자동 해방
• 친환경 컴퓨팅—자원 소모를 줄이고 '친환경' 기술을 구현하기 위한 움직임
• Huffman 알고리즘: 효율적인 데이터 인코딩을 위한 알고리즘
• 관리 코드 퍼포먼스 향상: Microsoft MSDN 라이브러리
• 참조 인접성: 로컬 이외의 메모리액세스로 인한 캐시 지연을 회피합니다.
• 루프 최적화
• 메모리 관리
• 최적화(컴퓨터 과학)
• 퍼포먼스 분석: 런타임에 알고리즘의 실제 퍼포먼스를 측정하는 방법
• 실시간 컴퓨팅—시간 크리티컬 애플리케이션의 다른 예
• 런타임 분석 - 예상 런타임 및 알고리즘의 확장성 추정
• 동시 멀티스레딩
• 정렬 알고리즘 compar 알고리즘 비교
• 투기적 실행 또는 신속한 실행
• 분기 예측
• 슈퍼스레딩
  • 하이퍼스레딩
• 스레드 코드: 가상 메서드테이블 또는 브랜치테이블과 유사합니다.
• Virtual Method 테이블: 디스패치를 위한 포인터가 동적으로 할당된 브랜치테이블

레퍼런스