shopkeeper/kowiki-cleaned-020126 huggingface dataset:
DTIME

계산 복잡도 이론에서 DTIME 또는 TIME은 결정론적 튜링 기계의 연산 시간 연산 자원이다. 이는 "일반적인" 물리 컴퓨터가 특정 알고리즘을 사용하여 특정 계산 문제를 해결하는 데 걸리는 시간(또는 계산 단계 수)을 나타낸다. 이는 중요한 실제 자원(컴퓨터가 문제를 해결하는 데 걸리는 시간)과 매우 밀접하게 관련되어 있기 때문에 가장 잘 연구된 복잡성 자원 중 하나이다.

DTIME 자원은 특정 양의 연산 시간을 사용하여 해결할 수 있는 모든 결정 문제의 집합인 복잡도 종류를 정의하는 데 사용된다. 입력 크기 n의 문제가 으로 해결될 수 있다면, 복잡도 종류 (또는 )를 가진다. 사용되는 메모리 공간의 양에는 제한이 없지만, 다른 복잡성 자원(예: 교대)에는 제한이 있을 수 있다.

 DTIME의 복잡도 종류 
많은 중요한 복잡도 종류는 DTIME으로 정의되며, 특정 양의 결정론적 시간으로 해결할 수 있는 모든 문제를 포함한다. 모든 적절한 복잡도 함수를 사용하여 복잡도 종류를 정의할 수 있지만, 특정 종류만 연구하는 데 유용하다. 일반적으로, 우리는 복잡도 종류가 계산 모델의 변화에 대해 견고하고, 서브루틴의 구성에 대해 닫혀 있기를 원한다.

DTIME은 시간 계층 정리를 만족하며, 이는 점근적으로 더 많은 양의 시간이 항상 엄격하게 더 큰 문제 집합을 생성한다는 것을 의미한다.

잘 알려진 복잡도 종류 P는 다항식 시간 DTIME으로 해결할 수 있는 모든 문제를 포함한다. 이는 공식적으로 다음과 같이 정의할 수 있다.

P는 선형 시간 문제 를 포함하는 가장 작은 견고한 종류이다 (AMS 2004, Lecture 2.2, pg. 20). P는 "계산적으로 실현 가능한" 것으로 간주되는 가장 큰 복잡도 종류 중 하나이다.

결정론적 시간을 사용하는 훨씬 더 큰 종류는 EXPTIME이며, 이는 지수 시간에 결정론적 기계로 해결할 수 있는 모든 문제를 포함한다. 공식적으로, 우리는 다음을 얻는다.

더 큰 복잡도 종류도 비슷하게 정의할 수 있다. 시간 계층 정리 때문에, 이들 종류는 엄격한 계층 구조를 형성한다; 우리는 임을 알고 있으며, 그 이상도 마찬가지다.

 기계 모델 

P와 같은 견고한 종류의 경우, DTIME을 정의하는 데 사용되는 정확한 기계 모델은 자원의 성능에 영향을 주지 않으면서 변경될 수 있다. 계산 복잡성 문헌은 특히 매우 작은 시간 종류를 논의할 때 다중 테이프 튜링 기계를 기반으로 DTIME을 정의하는 경우가 많다. 다중 테이프 결정론적 튜링 기계는 단일 테이프 기계보다 2차 시간 가속을 제공할 수 없다.

튜링 기계의 선형 속도 향상 정리 때문에, 시간 경계의 곱셈 상수는 DTIME 종류의 범위에 영향을 주지 않는다; 유한 상태 제어의 상태 수를 늘리고 테이프 알파벳의 크기를 늘림으로써 항상 상수 곱셈 속도 향상을 얻을 수 있다. 파파디미트리우의 진술에서, 언어 에 대해,

Let . Then, for any , , where .

 일반화 

결정론적 튜링 기계 이외의 모델을 사용하면 DTIME의 다양한 일반화 및 제한이 있다. 예를 들어, 비결정론적 튜링 기계를 사용하면 NTIME 자원을 얻는다. DTIME과 다른 계산 자원의 표현력 간의 관계는 거의 이해되지 않고 있다. 몇 안 되는 알려진 결과 중 하나는 다음과 같다.

다중 테이프 기계의 경우. 이것은 Santhanam에 의해 다음으로 확장되었다. 여기서 은 반복 로그이다.

교대 튜링 기계를 사용하면 ATIME 자원을 얻는다.

 각주 

분류:복잡도 종류
분류:계산 자원
DSPACE

계산 복잡도 이론에서 DSPACE 또는 SPACE는 결정론적 튜링 기계의 메모리 공간 자원을 설명하는 연산 자원이다. 이는 주어진 알고리즘으로 주어진 계산 문제를 해결하는 데 "일반적인" 물리적 컴퓨터가 필요로 하는 총 메모리 공간의 양을 나타낸다.

복잡도 종류

DSPACE 측정은 특정 양의 메모리 공간을 사용하여 해결할 수 있는 모든 결정 문제의 집합인 복잡도 종류를 정의하는 데 사용된다. 각 함수 f(n)에 대해 SPACE(f(n))라는 복잡도 종류가 있으며, 이는 O(f(n)) 공간을 사용하는 결정론적 튜링 기계에 의해 해결될 수 있는 결정 문제의 집합이다. 사용될 수 있는 계산 시간의 양에는 제한이 없지만, 다른 복잡도 측정(예: 교대)에는 제한이 있을 수 있다.

몇 가지 중요한 복잡도 종류는 DSPACE로 정의된다. 여기에는 다음이 포함된다.

 REG = DSPACE(O(1)), 여기서 REG는 정규 언어의 종류이다. 사실, REG = DSPACE(o(log log n))이다 (즉, 비정규 언어를 인식하는 데는 공간이 필요하다).

증명:
만약 s(n) = o(log log n)에 대해 비정규 언어 L ∈ DSPACE(s(n))가 존재한다고 가정하자. M을 공간 s(n)에서 L을 결정하는 튜링 기계라고 하자. 가정에 의해 L ∉ DSPACE(O(1))이므로, 임의의 에 대해 M의 입력 중 k보다 더 많은 공간을 요구하는 것이 존재한다.

k보다 더 많은 공간을 요구하는 가장 작은 크기(n으로 표시)의 입력 x를 잡고, 를 입력 x에 대한 M의 모든 구성의 집합이라고 하자. M ∈ DSPACE(s(n))이므로, 이며, 여기서 c는 M에 의존하는 상수이다.

S를 x에 대한 M의 모든 가능한 교차열의 집합이라고 하자. x에 대한 M의 교차열 길이는 최대 임을 주목하자: 만약 이보다 길다면, 일부 구성이 반복되어 M은 무한 루프에 빠질 것이다. 교차열의 모든 요소에 대해 가능한 경우도 최대 이므로, x에 대한 M의 서로 다른 교차열의 수는 다음과 같다.

비둘기집 원리에 따르면, 인 i < j인 인덱스가 존재하며, 여기서 와 는 각각 경계 i와 j에서의 교차열이다.

를 i + 1부터 j까지의 모든 셀을 제거하여 에서 얻은 문자열이라고 하자. 기계 은 입력 에서도 입력 에서와 똑같이 동작하므로, 를 계산하는 데 를 계산하는 데와 같은 공간이 필요하다. 그러나 , 이는 의 정의와 모순된다. 따라서 가정한 언어 은 존재하지 않는다. □

위 정리는 공간 위계 정리에서 공간 구성 가능 함수 가정의 필요성을 시사한다.

 L = DSPACE(O(log n))
 PSPACE = 
 EXPSPACE = 

기계 모델

DSPACE는 전통적으로 결정론적 튜링 기계에서 측정된다. 몇 가지 중요한 공간 복잡도 종류는 준선형이다. 즉, 입력 크기보다 작다. 따라서 입력 크기 또는 출력 크기에 대해 알고리즘에 "비용을 부과"하는 것은 사용된 메모리 공간을 진정으로 포착하지 못할 것이다. 이는 입력 및 출력 테이프가 있는 다중 테이프 튜링 기계를 정의함으로써 해결되는데, 이는 표준 다중 테이프 튜링 기계와 동일하지만 입력 테이프에는 절대 쓰지 않고 출력 테이프에서는 절대 읽지 않는다는 점이 다르다. 이를 통해 L (로그 공간)과 같은 더 작은 공간 종류를 모든 작업 테이프(특수 입력 및 출력 테이프 제외)가 사용한 공간의 양으로 정의할 수 있다.

알파벳의 적절한 거듭제곱을 취하여 많은 기호를 하나로 묶을 수 있으므로, 모든 c ≥ 1 및 f(n) ≥ 1인 f에 대해 c f(n) 공간에서 인식 가능한 언어의 종류는 f(n) 공간에서 인식 가능한 언어의 종류와 동일하다. 이는 정의에서 점근 표기법의 사용을 정당화한다.

위계 정리

공간 위계 정리는 모든 공간 구성 가능 함수 에 대해 공간 에서 결정 가능하지만 공간 에서는 결정 불가능한 어떤 언어 L이 존재함을 보여준다.

다른 복잡도 종류와의 관계
DSPACE는 비결정론적 튜링 기계의 메모리 공간 종류인 NSPACE의 결정론적 대응물이다. 사비치 정리에 따르면, 다음과 같다.

NTIME은 다음과 같은 방식으로 DSPACE와 관련이 있다. 모든 시간 구성 가능 함수 t(n)에 대해,

.

결정론적 시간에 대한 훨씬 더 나은 시뮬레이션이 알려져 있다: 만약 이라면,

이는 윌리엄스의 결과로, 홉크로프트, 폴, 밸리언트의 이전 한계를 개선한 것이다.

반면에, 인 모든 함수에 대해,

.

 각주 

 
 

 외부 링크 
.

분류:복잡도 종류
분류:계산 자원
ALL (복잡도)

계산 가능성과 복잡도 이론에서 ALL은 모든 결정 문제의 집합이다.

 다른 종류와의 관계 
ALL은 RE와 Co-RE를 포함하는 모든 결정 문제의 복잡도 종류를 포함하며, RE도 Co-RE도 아닌 셀 수 없이 많은 언어를 포함한다. 이것은 모든 다른 복잡도 종류를 포함하는 가장 큰 복잡도 종류이다.

 외부 링크 
 

분류:복잡도 종류
유니버설 씬 디스크립션

유니버설 씬 디스크립션(Universal Scene Description, USD)은 3차원 컴퓨터 그래픽스 데이터 교환을 위한 프레임워크이다. 이 프레임워크는 협업, 비파괴 편집, 그리고 그래픽스 데이터에 대한 다양한 관점과 의견을 가능하게 하는 데 중점을 둔다. USD는 시각 효과, 건축, 디자인, 로봇공학, CAD, 렌더링을 포함한 많은 산업에서 사용된다.

 역사 
이것은 픽사에 의해 개발되었으며 2016년 수정된 아파치 라이선스에 따라 오픈 소스 소프트웨어로 처음 공개되었다. 픽사, 어도비, 애플, 오토데스크, 엔비디아는 리눅스 재단의 JDF(Joint Development Foundation)와 함께 2023년 8월 1일 AOUSD(Alliance for OpenUSD)를 발표하며 "픽사의 유니버설 씬 디스크립션 기술의 표준화, 개발, 진화 및 성장을 촉진"할 것이라고 밝혔다.

 파일 형식 

사양에 사용되는 파일 형식은 다음과 같다.

 : ASCII 또는 바이너리 인코딩 가능
 : ASCII 인코딩
 : 바이너리 인코딩
 : 무압축, 암호화되지 않은 zip 아카이브인 패키지 파일로, usd, usda, usdc, PNG, jpeg, m4a, MP3, WAV 파일을 포함할 수 있다.

 지원 
 3ds Max 버전 2022 (최신 업데이트가 공개 베타로 제공), 버전 2023. USD에서 가져오기 및 USD로 내보내기 포함.
 오토데스크 퓨전 360은 2022년 4월부터 USD 내보내기를 지원한다.
 블렌더는 버전 4.0부터 USD 가져오기 및 내보내기를 지원한다.
 시네마 4D는 USD 가져오기 및 내보내기를 지원한다.
 후디니는 형식 교환 및 장면 편집 목적으로 USD를 구현한다.
 오토데스크 인벤터 – 버전 2023부터 USD를 지원한다.
 마야 – 버전 2022부터 USD를 지원한다.
 mesh2mesh (macOS)는 USD를 다른 형식으로 변환하거나 다른 형식에서 USD로 변환한다.
 엔비디아는 옴니버스에서 USD 지원을 발표했다.
 다빈치 리졸브는 USD 가져오기를 지원한다.
 퓨전은 USD 가져오기를 지원한다.
 애플의 SceneKit은 3D 모델 교환을 위해 파일을 지원한다.
 애플의 Reality Composer Pro는 Reality Kit 및 VisionOS 생태계를 위해 파일을 지원한다.
 벡터웍스 2023 서비스 팩 3부터 USD 내보내기 및 가져오기가 포함된다.
 라이노세로스 3D는 현재 v8 WIP (작업 중)로 지원이 제한되어 있으며 현재 안정 버전에서는 아직 지원되지 않는다.
 Adobe Substance 3D
 언리얼 엔진은 (.usd, .usda, .usdc, .usdz)를 지원하지만, 가져오기 기능은 현재 베타 버전이다.
 키샷 – USD (.usd, .usda, .usdc, .usdz)를 지원한다.
 오토데스크 VRED Professional 2025 (.usd, .usda, .usdc, .udsz)

 같이 보기 
 알렘빅 (상호 교환 가능한 컴퓨터 그래픽스 파일 형식)
 glTF (그래픽스 언어 전송 형식)

 각주 

 외부 링크 
 픽사의 유니버설 씬 디스크립션 소개

분류:파일 포맷
분류:3차원 그래픽 소프트웨어
분류:가상 현실
분류:픽사
분류:증강 현실
분류:3차원 그래픽스 파일 포맷
Zstd

Zstandard는 페이스북의 Yann Collet이 개발한 비손실 데이터 압축 알고리즘이다. Zstd는 해당 C로 된 참조 구현이며, 2016년 8월 31일 오픈 소스 소프트웨어로 공개되었다.

이 알고리즘은 2018년에 로 발행되었으며, 관련 미디어 타입 "application/zstd", 파일 확장자 "zst", 그리고 HTTP 콘텐츠 인코딩 "zstd"를 정의한다.

특징
Zstandard는 DEFLATE 알고리즘(1991년에 개발되어 원본 ZIP 및 gzip 프로그램에 사용됨)과 유사한 압축비를 제공하지만, 특히 압축 해제 속도가 더 빠르도록 설계되었다. 압축 수준은 음수 7(가장 빠름)부터 22(압축 속도는 가장 느리지만 최상의 압축비)까지 조절 가능하다.

버전 1.3.2(2017년 10월)부터 zstd는 rzip 또는 lrzip과 유사하게 매우 긴 범위의 검색 및 중복 제거(, 128 MiB 창)를 선택적으로 구현한다.

압축 속도는 가장 빠른 수준과 가장 느린 수준 간에 20배 이상 차이가 날 수 있지만, 압축 해제는 균일하게 빠르며 가장 빠른 수준과 가장 느린 수준 간에 20% 미만의 차이를 보인다. Zstandard 명령줄에는 I/O 조건, 주로 출력 기록 속도에 따라 압축 수준을 변경하는 "적응형"() 모드가 있다.

Zstd는 최대 압축 수준에서 LZMA, LZHAM, PPMX와 유사한 압축비를 제공하며, Zstandard는 현재 파레토 최전선에 도달했으며, 유사하거나 더 나은 압축비를 가진 다른 어떤 현재 사용 가능한 알고리즘보다 빠르게 압축을 해제한다.

사전은 작은 파일의 압축비에 큰 영향을 미칠 수 있으므로 Zstandard는 사용자가 제공한 압축 사전을 사용할 수 있다. 또한 샘플 집합에서 사전을 생성할 수 있는 훈련 모드를 제공한다. 특히, 하나의 사전을 로드하여 파일 내에는 중복이 없더라도 파일 간에 중복이 있는 대규모 파일 집합(예: 로그 파일)을 처리할 수 있다.

설계

Zstandard는 사전 일치 단계(LZ77)와 큰 검색 창, 그리고 빠른 엔트로피 부호화 단계를 결합한다. 이는 허프먼 부호화(리터럴 섹션의 항목에 사용됨)와 유한 상태 엔트로피(FSE) ANS의 빠른 테이블 버전인 tANS를 시퀀스 섹션의 항목에 사용한다. FSE가 기호 간에 상태를 전달하는 방식 때문에 압축 해제는 각 블록의 시퀀스 섹션 내 기호를 역순(마지막부터 처음까지)으로 처리하는 것을 포함한다.

사용

리눅스 커널은 2017년 11월(버전 4.14)부터 btrfs 및 squashfs 파일 시스템의 압축 방법으로 Zstandard를 포함했다.

2017년 Allan Jude는 Zstandard를 FreeBSD 커널에 통합했으며, 이후 코어 덤프(사용자 프로그램 및 커널 패닉 모두)의 압축 옵션으로 통합되었다. 또한 개념 증명 OpenZFS 압축 방법을 만드는 데 사용되었으며 2020년에 통합되었다.

AWS 레드쉬프트 및 RocksDB 데이터베이스는 Zstandard를 사용한 필드 압축을 지원한다.

2018년 3월, 캐노니컬은 우분투 리눅스 배포판의 deb 패키지 압축 방법으로 zstd를 기본값으로 사용하는 것을 테스트했다. deb 패키지의 xz 압축과 비교할 때, zstd 레벨 19는 패키지 파일이 6% 더 커지는 대신 압축 해제 속도가 상당히 빠르다. 2018년 4월(버전 1.6~rc1)에 데비안(및 이후 우분투)에 지원이 추가되었다.

페도라는 2018년 5월(페도라 릴리스 28)에 RPM에 ZStandard 지원을 추가했으며, 2019년 10월(페도라 31) 릴리스 패키징에 사용했다. 페도라 33에서는 파일 시스템이 기본적으로 zstd로 압축된다.

아치 리눅스는 2019년 10월 pacman 5.2 패키지 관리자 출시와 함께 zstd를 패키지 압축 방법으로 지원했으며, 2020년 1월에는 공식 저장소의 패키지에 xz 대신 zstd로 전환했다. 아치는 zstd -c -T0 --ultra -20 -를 사용하며, 모든 압축된 패키지의 총 크기는 0.8% 증가했지만(xz 대비), 압축 해제 속도는 14배 빨라졌고, 여러 스레드를 사용할 때 압축 해제 메모리는 50 MiB 증가했으며, 압축 메모리는 증가했지만 사용된 스레드 수에 비례한다. 아치 리눅스는 나중에 mkinitcpio 초기 램디스크 생성기의 기본 압축 알고리즘으로도 zstd로 전환했다.

압축 수준을 선택할 수 있는 알고리즘의 전체 구현은 닌텐도 스위치 하이브리드 게임 콘솔용 홈브루 커뮤니티에서 개발한 .NSZ/.XCZ 파일 형식에 사용된다. 또한 .RVZ Wii 및 닌텐도 게임큐브 디스크 이미지 파일 형식에서 지원되는 여러 압축 알고리즘 중 하나이다.

2020년 6월 15일, Zstandard는 zip 파일 형식의 버전 6.3.8에 코덱 번호 93으로 구현되었으며, 6월 1일에 출시된 버전 6.3.7에 구현된 이전 코덱 번호 20은 더 이상 사용되지 않게 되었다.

2024년 3월, 구글 크롬 버전 123(및 크로미엄 기반 브라우저인 브레이브 또는 마이크로소프트 엣지 등)은 HTTP 헤더 Content-Encoding에 zstd 지원을 추가했다. 2024년 5월, 모질라 파이어폭스 릴리스 126.0은 HTTP 헤더 Content-Encoding에 zstd 지원을 추가했다.

라이선스
참조 구현은 BSD 허가서에 따라 깃허브에 게시되었다. 2016년 8월 31일 출시된 버전 1.0부터 추가적인 특허 권한 부여가 있었다.

2017년 8월 20일 출시된 버전 1.3.1부터 이 특허 부여는 철회되었고 라이선스는 BSD + GPLv2 이중 라이선스로 변경되었다.

 같이 보기 
 LZ4 (압축 알고리즘) – LZ77 계열의 빠른 멤버
 LZFSE – iOS 9 및 OS X 10.11부터 애플이 사용하고 2016년 6월 1일에 오픈 소스로 공개된 유사한 알고리즘
 Zlib
 브로틀리 – 브라우저에 통합됨

 각주 

 외부 링크 
 
 
 
 "Zstandard를 이용한 더 작고 빠른 데이터 압축", Yann Collet 및 Chip Turner, 2016년 8월 31일, 페이스북 공지
 더 가디언은 zlib 대신 ZStandard를 사용하고 있다

분류:C 라이브러리
분류:데이터 압축
분류:무손실 압축 알고리즘
분류:자유 압축 소프트웨어
분류:BSD 라이선스 소프트웨어
분류:2016년 소프트웨어
렘펠-지브-오버휴머

렘펠-지브-오버휴머(Lempel–Ziv–Oberhumer, LZO)는 압축 해제 속도에 중점을 둔 비손실 데이터 압축 알고리즘이다.

 설계 
1996년에 출시된 오리지널 "lzop" 구현은 마르쿠스 프란츠 크사버 요하네스 오버후머가 아브라함 렘펠과 야코브 지브의 이전 알고리즘을 기반으로 개발했다. LZO 라이브러리는 다음 특성을 가진 여러 알고리즘을 구현한다.
 DEFLATE 압축에 비해 더 높은 압축 속도
 매우 빠른 압축 해제
 압축 중 추가 버퍼 필요 (압축 수준에 따라 8kB 또는 64kB 크기)
 원본 및 대상 버퍼 외에 압축 해제를 위한 추가 메모리가 필요하지 않음
 압축 해제 속도에 영향을 주지 않고 압축률과 압축 속도 사이의 균형을 조절할 수 있음

LZO는 중첩 압축 및 제자리 압축 해제를 지원한다. 블록 압축 알고리즘으로서 데이터 블록을 압축 및 압축 해제한다. 압축 및 압축 해제에 사용되는 블록 크기는 동일해야 한다. LZO는 데이터 블록을 일치(슬라이딩 딕셔너리) 및 일치하지 않는 리터럴 실행으로 압축하여 중복성이 높은 데이터에서 좋은 결과를 생성하고 압축 불가능한 데이터를 수용 가능하게 처리하며, 최소 1KB의 블록 크기로 측정할 때 원본 크기의 최대 1/64까지만 압축 불가능한 데이터를 확장한다.

 구현 
참조 구현은 ANSI C로 작성되었으며 GNU 일반 공중 사용 허가서에 따라 자유 소프트웨어로 제공되었다. 코드의 저작권은 마르쿠스 F. X. J. 오버후머가 소유한다. 이 코드는 1996년에 처음 출판되었다. 오버후머는 또한 lzop이라는 명령줄 프런트엔드를 작성했다.

LZO 버전은 펄, 파이썬, 자바 언어에서 사용할 수 있다. 다양한 LZO 구현은 AIX, 아타리 TOS (아타리 ST), ConvexOS, IRIX, 리눅스, Mac OS, 닌텐도 64, 팜 OS, 플레이스테이션, 솔라리스, SunOS, VxWorks, Wii, Win32에서 작동하는 것으로 보고되었다.

FFmpeg의 libavutil 라이브러리는 비손실 비디오 압축을 위한 가능한 방법으로 자체 LZO 구현을 포함한다. FFmpeg의 압축 해제기 구현은 OpenConnect에서도 주니퍼 네트웍스 및 펄스 시큐어 VPN 서버에서 전송하는 LZO 압축 ESP 패킷을 지원하기 위해 사용된다.

리눅스 커널은 일부 기능에 LZO 구현을 사용한다:

 Btrfs는 파일 시스템 압축을 위한 가능한 압축 방식으로 LZO를 사용한다.
 initrd 및 initramfs는 초기 램 드라이브 압축을 위한 가능한 압축 방식으로 LZO를 사용한다.
 SquashFS는 파일 시스템 압축을 위한 가능한 압축 방식으로 LZO를 사용한다.
 zram은 램 드라이브 압축을 위한 기본 압축 방식으로 LZO-RLE라는 런 렝스 부호화를 사용하는 LZO를 사용한다.
 zswap은 가상 메모리 압축을 위한 기본 압축 방식으로 LZO를 사용한다.

 각주 

 외부 링크 
 
 - liblzo2 LZO 압축 알고리즘의 순수 자바 구현

분류:C 라이브러리
분류:데이터 압축
분류:무손실 압축 알고리즘
분류:자유 압축 소프트웨어
LZX

LZX는 LZ77 계열의 압축 알고리즘으로, DEFLATE의 약간 개선된 버전이다. 같은 이름의 파일 압축기의 이름이기도 하다. 둘 다 1990년대에 조너선 포브스와 토미 포우타넨이 발명했다.

 LZX 알고리즘의 사용 사례 
 아미가 LZX 
LZX는 저자들이 캐나다의 워털루 대학교에서 공부하던 중 1995년에 아미가 파일 압축기로 공개되었다. 이 소프트웨어는 당시 압축 소프트웨어에서 흔히 볼 수 있었던 셰어웨어였다. 등록된 버전에는 평가판에서 사용할 수 없었던 수정 사항과 개선 사항이 포함되어 있었다. 1997년, 저자들은 압축기에 대한 작업을 중단하고 등록을 받지 않게 되자, 누구나 등록된 버전을 사용할 수 있도록 무료 키 파일을 제공했다.

 마이크로소프트 캐비닛 파일 
1996년 포브스는 마이크로소프트에 입사했고, 마이크로소프트의 캐비닛 압축기는 LZX 압축 방식을 포함하도록 향상되었다. 개선 사항에는 가변 검색 창 크기가 포함되었는데, 아미가 LZX는 64 KB로 고정되었고, 마이크로소프트 LZX는 32에서 2048 킬로바이트 (32,768에서 2,097,152바이트) 사이의 2의 거듭제곱으로 범위가 지정될 수 있었다. 인텔 80x86 "CALL" 명령을 감지하여 피연산자를 상대 주소 지정에서 절대 주소 지정으로 변환하는 특별한 전처리기가 추가되어, 동일한 위치에 대한 호출이 압축기가 일치시킬 수 있는 반복된 문자열을 생성하여 80x86 이진 코드의 압축률을 향상시켰다. (이 기술은 나중에 Branch-Call-Jump [BCJ] 필터링으로 일반화되었다.)

 마이크로소프트 압축 HTML 도움말 (CHM) 파일 
마이크로소프트가 클래식 도움말 파일 형식을 대체하는 마이크로소프트 압축 HTML 도움말을 도입했을 때, 모든 HTML 데이터를 LZX 알고리즘으로 압축하도록 선택했다. 그러나 무작위 접근 속도를 향상시키기 위해, 압축기는 64킬로바이트(65,536바이트) 간격마다 재설정되고 32킬로바이트 간격마다 16비트 경계에 재정렬되도록 변경되었다. 따라서 HTMLHelp 소프트웨어는 항상 압축된 데이터 스트림의 시작부터 디코딩하는 대신 가장 가까운 64킬로바이트 간격을 즉시 탐색하고 거기서부터 디코딩을 시작할 수 있었다.

 마이크로소프트 리더 (LIT) 파일 
마이크로소프트 리더용 마이크로소프트 LIT 파일은 단순히 CHM 파일 형식의 확장이며, 따라서 LZX 압축도 사용한다.

 윈도우 이미징 포맷 (WIM) 파일 
윈도우 비스타와 윈도우 7의 설치/드라이브 이미지 파일 형식인 윈도우 이미징 포맷은 LZX를 압축 방식 중 하나로 사용한다.

 CompactOS NTFS 파일 압축 
윈도우 10에서는 윈도우 이미징 포맷의 LZX 압축이 새로운 CompactOS NTFS 파일 압축에 사용된다.

 엑스박스 라이브 아바타 
마이크로소프트는 디스크 및 대역폭 요구 사항을 줄이기 위해 엑스박스 라이브 아바타에 LZX 압축을 사용한다.

 LZX 파일 압축 해제 
unlzx 프로그램과 XAD는 아미가 LZX 아카이브를 압축 해제할 수 있다. cabextract 프로그램은 LZX 방식을 사용하여 마이크로소프트 캐비닛 파일을 압축 해제할 수 있다. CHM 문서에 명시된 바와 같이, CHM 파일을 역컴파일하거나 보는 데 사용할 수 있는 다양한 크로스 플랫폼 도구들이 있다. LIT 파일은 Convert LIT 소프트웨어를 사용하여 압축 해제할 수 있다.

 같이 보기 

 압축 파일 포맷 목록
 압축 소프트웨어의 비교

 각주 

 외부 링크 
 The LZX page, including many versions of the Amiga LZX archiver
 unlzx source code
 cabextract (includes source code)
 wimlib (included source code)
 Convert LIT (includes source code)
 Microsoft's LZX DELTA specification

분류:데이터 압축
분류:무손실 압축 알고리즘
분류:아미가
알렘빅

섬네일|upright=1.2|중세 필사본에 묘사된 알렘빅 그림
섬네일|알렘빅
알렘빅(alembic, , 에서 유래한 '컵, 비커'라는 뜻)은 액체를 증류하는 데 사용되는, 튜브로 연결된 두 개의 용기로 구성된 연금술 증류기이다.

 설명 
완전한 증류 장치는 세 부분으로 구성된다.

 증류할 액체가 들어 있는 증류 솥인 "쿠커빗"(아랍어: ; 그리스어: , )으로, 불꽃으로 가열된다.
 증기를 받기 위해 쿠커빗의 입구에 맞는 "헤드" 또는 "캡"(, ; 그리스어 , )으로, 아래쪽으로 기울어진 "튜브"(, )가 부착되어 있다.
 "수신기"(, ; , 또는 , ) 용기

또 다른 증류 용기인 레토르트의 경우 "캡"과 "쿠커빗"이 결합하여 하나의 용기를 형성한다. 안빅은 쿠커빗의 라스(아랍어 라스 raʾs는 "머리"를 의미한다)라고도 불린다. 쿠커빗의 액체는 가열되거나 끓여지며, 증기는 안빅으로 올라가 벽과 접촉하여 냉각되고 응축되어 주둥이를 통해 수신기로 흘러 들어간다. 알렘빅의 현대적 후손은 증류주를 생산하는 데 사용되는 포트 스틸이다.

 역사 
섬네일|upright|1606년 연금술 책에 실린 알렘빅들

디오스코리데스의 약물에 대하여(기원후 약 50년)에 묘사된 그의 암빅스(ambix)는 응축된 수은을 모으는 헬멧 모양의 뚜껑이다. 아테나이오스(기원후 약 225년)에게는 병이나 플라스크였다. 후대 화학자들에게는 조악한 증류 장치의 다양한 부분을 의미했다.

알렘빅 그림은 연금술사 클레오파트라(3세기), 파노폴리스의 조시모스(기원후 약 300년), 시네시우스(기원후 약 373년 ~ 약 414년)의 작품에 등장한다. 두 개의(디비코스) 또는 세 개의(트리비코스) 수신기를 가진 알렘빅이 있었다. 파노폴리스의 조시모스에 따르면, 알렘빅은 유대인 마리아가 발명했다.

안빅은 이븐 알-아왐의 (농업서)에 묘사되어 있는데, 그는 장미수가 어떻게 증류되는지 설명한다. 그 외에도 콰리즈미의 (과학의 열쇠)과 알-라지의 (비밀의 책)에 언급되어 있다. 게버의 저작으로 알려진 라틴어 번역본에는 몇 가지 삽화가 실려 있다.

 유니코드 
유니코드 문자 집합은 알렘빅에 대한 세 가지 기호를 지정한다. 그림문자 ⚗ (), 그 이모지 변형 ⚗️ (), 그리고 고대 연금술 기호 🝪 ()이다.

 같이 보기 
 알루델

 각주 

분류:아랍의 발명품
알렘빅 (컴퓨터 그래픽스)

알렘빅(Alembic)은 소니 픽처스 이미지워크스와 인더스트리얼 라이트 & 매직이 개발한 컴퓨터 그래픽스 파일 형식이다. 이 형식은 2011년 SIGGRAPH에서 발표되었고, 시각 효과 및 애니메이션 전문가들 사이에서 업계 전반에 걸쳐 널리 채택되었다.

주요 초점은 동일한 샷이나 동일한 자산에서 작업하는 여러 그룹 간에 애니메이션된 지오메트리(모델)를 효율적으로 교환하는 것이다. 이들은 서로 다른 애플리케이션을 사용할 수도 있다. 종종 같은 회사나 다른 스튜디오의 다른 부서가 동일한 프로젝트를 작업한다. Alembic은 폴리곤 메시, 서브디비전 서피스, 매개변수 곡선, NURBS 패치 및 입자를 포함하여 업계에서 사용되는 일반적인 지오메트리 표현을 지원한다. Alembic은 또한 변환 계층 및 카메라를 지원한다. 최신 버전에는 재료 및 조명에 대한 초기 지원도 포함된다. Alembic은 특히 절차적 도구의 복잡한 종속성 그래프를 저장하는 데 초점을 맞추지 않고, 애니메이션 장면의 타임라인을 따라 여러 지점에서 모델 데이터를 샘플링하여 "구운" 결과를 저장한다.

알렘빅을 지원하는 도구

내장 지원 도구

플러그인

 각주 

 외부 링크 
 
 

분류:루카스필름
분류:3차원 그래픽스 파일 포맷
양방향 탐색

양방향 탐색(Bidirectional search)은 유향 그래프에서 초기 꼭짓점에서 목표 꼭짓점까지의 최단 경로를 찾는 그래프 탐색 알고리즘이다. 이는 두 가지 동시 탐색을 실행하는데, 하나는 초기 상태에서 앞으로 진행하고 다른 하나는 목표에서 뒤로 진행하여 두 탐색이 만날 때 중지한다. 이 접근 방식의 이유는 많은 경우 더 빠르기 때문이다. 예를 들어, 두 탐색이 모두 분기 인자 b를 가진 트리를 확장하고 시작점에서 목표까지의 거리가 d인 탐색 문제 복잡성의 단순화된 모델에서, 두 탐색 각각은 O(bd/2)의 복잡도(큰 O 표기법 참조)를 가지며, 이 두 탐색 시간의 합은 시작점에서 목표까지의 단일 탐색에서 발생하는 O(bd) 복잡도보다 훨씬 적다.

앤드루 골드버그 외 다수는 데이크스트라 알고리즘의 양방향 버전에서 올바른 종료 조건을 설명했다.

A* 탐색과 마찬가지로 양방향 탐색은 목표까지의 남은 거리(정방향 트리) 또는 시작점부터의 거리(역방향 트리)에 대한 휴리스틱 추정치에 의해 안내될 수 있다.

이라 폴은 양방향 휴리스틱 탐색 알고리즘을 설계하고 구현한 최초의 인물이었다. 시작 노드와 목표 노드에서 발생하는 탐색 트리가 해법 공간의 중간에서 만나지 못했다. 드 샹포의 BHFFA 알고리즘이 이 결함을 해결했다.

허용 가능한 휴리스틱을 사용하는 단방향 A* 알고리즘에 의해 발견된 해법은 최단 경로 길이를 가지며, 드 샹포가 설명한 BHFFA2 양방향 휴리스틱 버전도 동일한 속성을 가진다. BHFFA2는 BHFFA보다 더 신중한 종료 조건을 가진다.

 설명 

양방향 휴리스틱 탐색은 특정 상태 에서 다른 상태 로의 상태 공간 탐색이며, 에서 로, 그리고 에서 로 동시에 탐색한다. 이는 에 적용하면 를 얻을 수 있는 유효한 연산자 목록을 반환한다.

역방향 탐색을 위해 연산자가 가역적이어야 하는 것처럼 보일 수 있지만, 주어진 노드 에 대해, 각 부모 노드에서 으로 가는 유효한 연산자가 존재하는 의 부모 노드 집합을 찾을 수 있는 것만 필요하다. 이는 종종 경로 찾기 영역에서 일방통행 도로에 비유된다. 즉, 양방향으로 이동할 수 있을 필요는 없지만, 도로의 끝에 서 있을 때 도로의 시작을 가능한 경로로 결정하는 것이 필요하다.

마찬가지로, 역방향 아크(즉, 양방향으로 가는 아크)가 있는 엣지의 경우 각 방향의 비용이 같을 필요는 없다. 역방향 탐색은 항상 역비용(즉, 정방향 아크의 비용)을 사용한다. 더 공식적으로, 이 부모 를 가진 노드라면, 는 에서 까지의 비용으로 정의된다.

 용어 및 표기법 

 탐색 트리의 분기 인자
 노드 에서 노드 으로 이동하는 데 관련된 비용
 루트에서 노드 까지의 비용
 노드 과 목표 사이의 거리에 대한 휴리스틱 추정치
 시작 상태
 목표 상태 (때때로 로 표시되지만 함수와 혼동하지 말 것)
 현재 탐색 방향. 관례상 는 정방향의 경우 1, 역방향의 경우 2이다
 반대 탐색 방향 (즉, )
 방향 d의 탐색 트리. 이면 루트는 이고, 이면 루트는 이다.
 의 리프 (때때로 라고도 함). 이 집합에서 확장을 위한 노드가 선택된다. 양방향 탐색에서는 이를 탐색 '프론티어' 또는 '파면'이라고 부르기도 하는데, 탐색이 그래픽으로 표현될 때 나타나는 방식 때문이다. 이 비유에서, 확장 단계 중 한 파면의 노드가 반대 파면에서 후계자를 가지는 것으로 발견될 때 '충돌'이 발생한다.
 의 비리프 노드. 이 집합에는 탐색에 의해 이미 방문된 노드가 포함된다.

 양방향 휴리스틱 탐색 접근 방식 

양방향 알고리즘은 크게 세 가지 범주로 나눌 수 있다: 프론트 투 프론트, 프론트 투 백(또는 프론트 투 엔드), 그리고 경계 탐색. 이들은 휴리스틱을 계산하는 데 사용되는 함수가 다르다.

 프론트 투 백 

프론트 투 백 알고리즘은 노드 의 값을 과 반대 탐색 트리의 루트인 또는 사이의 휴리스틱 추정치를 사용하여 계산한다.

프론트 투 백은 세 가지 범주 중 가장 활발하게 연구되는 분야이다. 2004년 현재, 현재 가장 좋은 알고리즘(최소한 15-퍼즐 영역에서)은 BiMAX-BS*F 알고리즘이다.

 프론트 투 프론트 

프론트 투 프론트 알고리즘은 노드 의 값을 과 의 일부 부분 집합 사이의 휴리스틱 추정치를 사용하여 계산한다. 전형적인 예는 BHFFA(양방향 휴리스틱 프론트 투 프론트 알고리즘)이다. 여기서 함수는 현재 노드와 반대쪽 프론트의 노드들 사이의 모든 휴리스틱 추정치 중 최소값으로 정의된다. 또는 공식적으로:

여기서 는 노드 과 사이의 거리에 대한 허용 가능한(즉, 과대평가하지 않는) 휴리스틱 추정치를 반환한다.

프론트 투 프론트는 지나치게 많은 계산을 요구한다는 단점이 있다. 노드 이 열린 목록에 들어갈 때마다 해당 값을 계산해야 한다. 이는 위에서 설명한 대로 에서 반대쪽 집합의 모든 노드까지의 휴리스틱 추정치를 계산하는 것을 포함한다. 인 모든 영역에서 집합의 크기는 기하급수적으로 증가한다.

 각주 

 더 읽어보기 
.

분류:그래프 알고리즘
분류:검색 알고리즘
양자 상태 비소거 정리

물리학에서 양자 상태 비소거 정리(No-deleting theorem)는 양자 정보 이론의 불가능 정리로, 일반적으로 임의의 양자 상태의 두 복사본이 주어졌을 때 그 복사본 중 하나를 삭제하는 것은 불가능하다는 것을 명시한다. 이것은 임의의 상태를 복사할 수 없다는 것을 명시하는 복제 불가능성 정리의 시간 역전된 쌍대이다. 이것은 아룬 K. 파티와 새뮤얼 L. 브라운스타인에 의해 증명되었다. 직관적으로, 이는 정보가 유니터리 진화 하에 보존되기 때문이다.

이 정리는 놀랍게 보이는데, 여러 면에서 양자 상태는 깨지기 쉽기 때문이다; 이 정리는 특정 경우에 양자 상태가 또한 견고하다는 것을 주장한다.

양자 상태 비소거 정리는 복제 불가능성 정리와 함께 범주론의 관점에서 양자 역학의 해석을 뒷받침하며, 특히 대거 대칭 단일 범주로 해석한다. 범주형 양자 역학으로 알려진 이 공식화는 결국 양자 역학에서 선형 논리로의 연결을 양자 정보 이론의 논리로서 가능하게 한다 (고전 논리가 데카르트 닫힌 범주에 기초를 둔 것과 정확히 유사하게).

 개요 
알 수 없는 양자 상태의 두 복사본이 있다고 가정하자. 이 맥락에서 중요한 질문은 두 개의 동일한 복사본이 주어졌을 때 양자 역학적 연산을 사용하여 그 중 하나를 삭제하는 것이 가능한가 하는 것이다. 불가능한 것으로 밝혀졌다. 양자 상태 비소거 정리는 양자역학의 선형성의 결과이다. 복제 불가능성 정리와 마찬가지로 이것은 양자 컴퓨팅, 양자 정보 이론 및 일반적인 양자역학에 중요한 의미를 가진다.

양자 삭제 과정은 입력 포트에서 임의의 알 수 없는 양자 상태의 두 복사본을 받아들이고 원본과 함께 빈 상태를 출력한다. 수학적으로 이것은 다음과 같이 설명될 수 있다.

여기서 는 유니터리 연산자, 는 알 수 없는 양자 상태, 는 빈 상태, 는 삭제 기계의 초기 상태이고 는 기계의 최종 상태이다.

고전적인 비트는 복사하고 삭제할 수 있으며, 직교 상태의 큐비트도 마찬가지이다. 예를 들어, 두 개의 동일한 큐비트 와 가 있다면, 우리는 이를 와 로 변환할 수 있다. 이 경우 두 번째 복사본을 삭제했다. 그러나 양자 이론의 선형성으로부터 임의의 상태 에 대해 삭제 연산을 수행할 수 있는 는 존재하지 않는다는 것이 따른다.

 정식 진술 

시스템 에 대한 세 개의 힐베르트 공간이 주어지고, 시스템 에 대한 힐베르트 공간은 동일하다.

만약 가 유니터리 변환이고, 가 보조 상태이며, 다음을 만족한다면 여기서 보조 상태 의 최종 상태는 에 의존할 수 있으며, 이 경우 는 스와핑 연산인데, 이는 매핑이 등거리 임베딩이라는 의미이다.

 증명 

이 정리는 임의의 차원의 힐베르트 공간에 있는 양자 상태에 대해 성립한다. 간단히 하기 위해, 두 개의 동일한 큐비트에 대한 삭제 변환을 고려해 보자. 만약 두 큐비트가 직교 상태에 있다면, 삭제는 다음을 요구한다.
,
.

를 알 수 없는 큐비트의 상태라고 하자. 만약 알 수 없는 큐비트의 두 복사본을 가지고 있다면, 삭제 변환의 선형성에 의해 다음을 얻는다.

위 표현에서 다음 변환이 사용되었다.

그러나 만약 복사본을 삭제할 수 있다면, 삭제 기계의 출력 포트에서 결합된 상태는 다음과 같아야 한다.
.

일반적으로 이 상태들은 동일하지 않으므로 기계가 복사본을 삭제하는 데 실패했다고 말할 수 있다. 최종 출력 상태가 동일하도록 요구한다면, 단 하나의 선택만이 있음을 알 수 있다.

그리고

보조 상태 의 최종 상태는 의 모든 값에 대해 정규화되므로, 와 는 직교해야 한다. 이는 양자 정보가 단순히 보조 상태의 최종 상태에 있다는 것을 의미한다. 보조 힐베르트 공간에 대한 국소 연산을 사용하여 보조 상태의 최종 상태로부터 알 수 없는 상태를 항상 얻을 수 있다. 따라서 양자 이론의 선형성은 알 수 없는 양자 상태가 완벽하게 삭제되는 것을 허용하지 않는다.

 결과 
 만약 알 수 없는 양자 상태를 삭제하는 것이 가능하다면, EPR 상태 두 쌍을 사용하여 빛보다 빠르게 신호를 보낼 수 있을 것이다. 따라서 양자 상태 비소거 정리의 위반은 신호 비발송 조건과 일치하지 않는다.
 복제 불가능성 정리와 양자 상태 비소거 정리는 양자 정보의 보존을 나타낸다.
 복제 불가능성 정리와 양자 상태 비소거 정리의 강력한 버전은 양자 정보에 영속성을 부여한다. 복사본을 생성하려면 우주의 일부에서 정보를 가져와야 하고, 상태를 삭제하려면 계속 존재할 우주의 다른 부분으로 정보를 내보내야 한다.

 같이 보기 
 비방송 정리
 복제 불가능성 정리
 통신 불가능성 정리
 숨김 불가능성 정리
 양자 복제
 양자 얽힘
 양자 정보
 양자 순간 이동
 불확정성 원리
 란다우어의 원리

 각주 

분류:양자정보과학
분류:양자역학 정리
구마노군

frame|교토부 구마노군의 위치
구마노군()은 일본 교토부(단고국)에 있던 군이다.

 군역 
1879년 행정 구역으로 발족 당시의 군역은 교탄고시의 일부에 해당한다.

 역사 
 1879년 4월 10일 - 군구정촌 편제법이 교토부에서 시행됨에 따라, 행정 구역으로서의 구마노군(熊野郡)이 발족.
right|frame|1.구미하마촌 2.구미타니촌 3.가와카미촌 4.가이베촌 5.가미사노촌 6.시모사노촌 7.다촌 8.간노촌 9.미나토촌 (주황: 교탄고시 11~22는 나카군 31~47은 다케노군)
 1889년 4월 1일 - 정촌제 시행으로, 아래의 촌이 발족. 전역이 현 교탄고시.(9촌)
 구미하마촌(久美浜村)
 구미타니촌(久美谷村)
 가와카미촌(川上村)
 가이베촌(海部村)
 가미사노촌(上佐濃村)
 시모사노촌(下佐濃村)
 다촌(田村)
 간노촌(神野村)
 미나토촌(湊村)
 1894년 11월 24일 - 구미하마촌이 정제 시행으로 구미하마정(久美浜町)이 됨.(1정 8촌)
 1899년 7월 1일 - 군제 시행.
 1951년
 1월 1일 - 가미사노촌·시모사노촌이 합병하여, 사노촌(佐濃村)이 발족.(1정 7촌)
 4월 1일 - 구미타니촌이 구미하마정에 편입.(1정 6촌)
 1955년 1월 1일 - 구미하마정·가와카미촌·가이베촌·다촌·간노촌·미나토촌이 합병하여, 새로이 구미하마정이 발족.(1정 1촌)
 1958년 5월 3일 - 사노촌이 구미하마정에 편입.(1정)
 2004년)4월 1일 - 구미하마정이 나카군 미네야마정·오미야정·다케노군 아미노정·단고정·야사카정와 합병하여 교탄고시(京丹後市)가 발족. 당일 구마노군은 폐지됨.

 
분류:교토부의 폐지된 군
분류:단고국의 군
분류:교탄고시의 역사
컨테이너 (추상 자료형)

컴퓨터 과학에서 컨테이너(container)는 다른 객체들의 클래스 또는 자료 구조의 인스턴스이다. 즉, 특정 접근 규칙을 따르는 조직화된 방식으로 객체를 저장한다.

컨테이너의 크기는 컨테이너가 포함하는 객체(요소)의 수에 따라 달라진다. 다양한 컨테이너 유형의 하위(상속된) 구현은 크기, 복잡성 및 언어 유형에 따라 달라질 수 있지만, 많은 경우 주어진 시나리오에 맞는 올바른 구현을 선택할 수 있는 유연성을 제공한다.

컨테이너 자료 구조는 많은 종류의 프로그래밍 언어에서 흔히 사용된다.

 기능 및 속성 
컨테이너는 다음 세 가지 속성으로 특징지을 수 있다.
 접근: 컨테이너의 객체에 접근하는 방식. 배열의 경우, 배열 인덱스로 접근한다. 스택의 경우, LIFO (후입선출) 순서에 따라 접근하고 큐의 경우, FIFO (선입선출) 순서에 따라 접근한다.
 저장: 컨테이너의 객체를 저장하는 방식.
 순회: 컨테이너의 객체를 순회하는 방식.

컨테이너 클래스는 다음을 수행하기 위한 CRUD와 유사한 메서드를 구현할 것으로 예상된다.
 빈 컨테이너 생성(생성자)
 컨테이너에 객체 삽입
 컨테이너에서 객체 삭제
 컨테이너의 모든 객체 삭제(지우기)
 컨테이너의 객체 접근
 컨테이너의 객체 수 접근(개수)

컨테이너는 때때로 반복자와 함께 구현된다.

 종류 
컨테이너는 단일 값 컨테이너 또는 연관 컨테이너로 분류될 수 있다.

단일 값 컨테이너는 각 객체를 독립적으로 저장한다. 객체는 직접, 언어 루프 구조(예: For 루프) 또는 반복자로 접근할 수 있다.

연관 컨테이너는 키-값 쌍으로 구성된 연관 배열, 맵 또는 딕셔너리를 사용하며, 각 키는 컨테이너에 최대 한 번 나타난다. 키는 컨테이너에 저장되어 있는 경우 값인 객체를 찾는 데 사용된다. 연관 컨테이너는 프로그래밍 언어에서 클래스 템플릿으로 사용된다.

컨테이너 추상 자료형은 다음을 포함한다.

 FIFO 큐
 LIFO 스택
 우선순위 큐
 순람표 (LUT)
 키-연관 자료 구조
 집합: 값 또는 특정 속성으로 객체를 포함하고 인덱싱한다.
 맵: 각 키에 조회를 위한 "값"을 연관시킨다.

이러한 추상 유형을 구현하는 데 사용되는 일반적인 자료 구조는 다음을 포함한다.
 배열 및 그 파생형
 연결 리스트
 이진 탐색 트리 (BST), 특히 자가 균형 BST
 해시 테이블

 그래픽 컨테이너 
위젯 툴킷은 또한 창, 패널과 같은 다른 위젯을 그룹화하는 특수 위젯인 컨테이너를 사용한다. 그래픽 속성 외에도 컨테이너 클래스와 동일한 유형의 동작을 가지는데, 이는 자식 위젯 목록을 유지하고 자식 중에서 위젯을 추가, 제거 또는 검색할 수 있도록 하기 때문이다.

 정적 타입 언어에서 

컨테이너 추상화는 타입 시스템에 관계없이 거의 모든 프로그래밍 언어로 작성할 수 있다. 그러나 강한 타입 객체 지향 프로그래밍 언어에서는 개발자가 재사용 가능한 동종 컨테이너를 작성하는 것이 다소 복잡할 수 있다.

요소 유형의 차이로 인해 각 요소 유형에 대한 컨테이너 컬렉션을 작성하고 유지하는 지루한 과정이 발생한다.

많은 요소 유형(예: 정수 또는 부동 소수점 숫자)은 차지하는 메모리 크기와 의미론적 의미로 인해 본질적으로 서로 호환되지 않으므로 다른 컨테이너가 필요하다(물론 상호 호환되거나 변환 가능한 경우는 제외). 최신 프로그래밍 언어는 이 문제를 해결하는 데 도움이 되는 다양한 접근 방식을 제공한다.

 범용 기본 타입
 다른 어떤 타입으로든 범용적으로 할당 가능한 타입(예: 루트 객체 클래스).
다운캐스팅;
클래스 대체
 위의 세 가지 접근 방식은 약한 타입 언어에 사용되며, 일반적으로 타입 간에 공유되는 상속과 다형성을 의미한다.
공용체 (C/C++ 언어)
 다른 데이터 크기의 타입을 저장할 수 있다. 그러나 검색 시 공용체에 어떤 타입이 저장되어 있는지 확인하기 어렵고 신중하게 따라야 한다.
형 변환
 템플릿 또는 제네릭
 재사용성과 타입 안전성을 보장한다. 역상속으로 생각할 수 있다. 그러나 이 접근 방식은 템플릿 특수화를 구현해야 할 수 있는데, 타입이 메서드에서 다르다는 점을 고려할 때 시간이 많이 소요되는 과정으로 알려져 있다.

 같이 보기 
 자료 구조 목록
 표준 템플릿 라이브러리#컨테이너
 컬렉션 (추상 자료형)
 자바 동시성 맵

 각주 

 외부 링크 
 컨테이너 자료 구조 선언 및 초기화

분류:객체 지향 프로그래밍
분류:추상 자료형
헬퍼 클래스

객체 지향 프로그래밍에서 헬퍼 클래스(Helper class)는 사용되는 애플리케이션이나 클래스의 주요 목표가 아닌 일부 기능을 제공하는 데 도움을 주기 위해 사용된다. 헬퍼 클래스의 인스턴스는 헬퍼 객체라고 불린다 (예를 들어, 위임 패턴에서).

헬퍼 클래스는 종종 초보 프로그래머가 한두 개의 클래스를 만드는 것을 넘어선 후에 초급 프로그래밍 수업에서 생성된다.

유틸리티 클래스는 모든 메서드가 정적이라는 점에서 헬퍼 클래스의 특별한 경우이다. 일반적으로 헬퍼 클래스는 모든 정적 메서드를 가질 필요는 없지만 인스턴스 변수를 가질 수 있다. 헬퍼 클래스의 여러 인스턴스가 존재할 수도 있다.

 예시 
이것은 유틸리티 클래스의 예시이기도 하다. 아래는 문자열 객체에 대한 확장 메서드이다.
public static class PrependHelper
{
 // static functions
 public static string MeowPrepend(this string text)
 {
 return $"Meow meow {text}!";
 }

 public static string WoofPrepend(this string text)
 {
 return $"Woof woof {text}!";
 }

 public static string WoohPrepend(this string text)
 {
 return $"Wooh {text}!";
 }
}

 헬퍼 클래스의 대안 
헬퍼 클래스가 될 함수들은 사용되는 곳 가까이에 배치될 수 있다.
다른 대안은 헬퍼 클래스 매개변수를 필드로 클래스에 래핑하는 것이다. 그 클래스는 가지고 있는 필드와 연결된 비즈니스 도메인에서 이름을 가질 수 있다. 아래 예시는 헬퍼 메서드를 도메인 타입의 메서드로 변환하는 방법을 보여준다:

public class Text
{
 string text;

 public string MeowPrepend()
 {
 return $"Meow meow {text}!";
 }

 public string WoofPrepend()
 {
 return $"Woof woof {text}!";
 }

 public string WoohPrepend()
 {
 return $"Wooh {text}!";
 }
}

 각주 

 같이 보기 
 계층 구조
 클래스 다이어그램 (UML)
 클래스 기반 프로그래밍

분류:클래스