코드 최적화와 데이터 압축의 관계

Question

인터넷에서이 질문을 검색 한 결과 일부 연구자가 허프만 코딩과 같은 컴파일러 최적화에 데이터 압축 알고리즘을 사용함을 발견했습니다.

내 질문은 더 일반적이다 : 우리는 압축의 손실 유형으로 코드 최적화가

고려할 수 있습니까?

Answer 1

구체적인 수준에서 사과와 오렌지입니다. 그러나 추상적 인 수준에서 그것은 흥미로운 질문입니다.

데이터 압축은 데이터와 정보의 차이 인 중복성을 처리합니다. 정보의 코딩을 수정함으로써 불필요한 중복성을 줄이려고합니다. 종종이 코딩은 공통 부분 문자열을 가져 와서 부분 문자열을 반복하는 대신 코드를 참조하는 코드를 작성하는 방식으로 작동합니다.

컴파일러 최적화 (속도 향상)는 불필요한 사이클을 줄이기 위해 노력합니다. 어떤 계산 결과가 두 번 이상 필요하다면 어떤 주소에 저장되어 있는지 확인하거나 등록 (memoizing)하여 더 적은 사이클로 재사용 할 수 있는지 확인하십시오.

또 다른 형태의 인코딩 번호는 소위 "단항 표기법"으로 한 자리 만 있고 숫자는 반복하여 나타냅니다. 예를 들어, 숫자 "3"과 "4"는 "111"과 "1111"이며 N 자릿수입니다. 이 코드는 로그 (N) 자릿수 (물론 기본 2)를 취하는 "011"및 "100"에서처럼 이진으로 전환하여 최적화됩니다.

이 프로그래밍은 선형 검색과 이진 검색의 차이점을 설명합니다. 선형 검색은 O (N) 비교를 필요로합니다. 각각의 비교 결과는 많은 정보를 얻을 수 있거나 매우 적습니다. 바이너리 검색은 O (log (N)) 비교를 취하고 각 비교 결과 하나의 비트를 생성합니다.

어떤 생각으로 다른 유사점을 찾아야합니다.