애플리케이션에 적합한 데이터 구조를 선택하는 방법

당신과 같은 독자는 MUO를 지원하는 데 도움이 됩니다. 귀하가 당사 사이트의 링크를 사용하여 구매하면 당사는 제휴 수수료를 받을 수 있습니다. 자세히 알아보기

사용 가능한 여러 옵션으로 목표에 가장 적합한 데이터 구조를 선택하는 것이 어려울 수 있습니다. 데이터 구조를 선택할 때 처리할 데이터, 데이터에서 수행할 작업 및 응용 프로그램이 실행되는 환경을 고려하십시오.

오늘의 메이크업 비디오 콘텐츠를 계속하려면 스크롤하세요.

데이터 이해

데이터 구조를 선택하기 전에 처리할 데이터를 이해하는 것이 중요합니다. 공통 데이터 구조 배열, 연결 목록, 트리, 그래프 및 해시 테이블을 포함한 다양한 데이터 유형과 함께 작동합니다.

예를 들어 데이터에서 요소에 임의로 액세스해야 하는 경우 배열이 최선의 선택일 수 있습니다. 목록에서 요소를 지속적으로 추가하거나 삭제해야 하고 목록 크기도 변경될 수 있는 경우 연결 목록이 특히 유용할 수 있습니다.

내 노트북이 충전되지 않는 이유

레코드 구조와 같은 여러 수준의 데이터를 효과적으로 저장하고 검색 및 정렬과 같은 작업을 수행해야 하는 경우 트리가 유용합니다.

소셜 네트워크와 같은 엔터티 간의 상호 작용을 설명하고 최단 경로 및 연결과 같은 작업을 수행해야 하는 경우 그래프가 선호됩니다. 해시 테이블은 빠른 키 조회에 유용합니다.

데이터에 대해 수행할 작업 고려

데이터 구조를 선택하는 동안 데이터에서 수행할 작업도 고려해야 합니다. 서로 다른 데이터 구조는 정렬, 검색, 삽입 및 삭제와 같은 수많은 작업을 최적화합니다.

예를 들어 연결된 목록은 삽입 및 삭제와 같은 작업에 더 적합하지만 이진 트리는 검색 및 정렬에 가장 적합합니다. 애플리케이션에 동시 삽입 및 검색이 필요한 경우 해시 테이블이 최선의 선택이 될 수 있습니다.

환경 평가

데이터 구조를 고려할 때 애플리케이션이 실행될 환경을 평가해야 합니다. 환경은 데이터 구조에 얼마나 신속하게 액세스할 수 있는지에 영향을 미칩니다.

현재 상태를 평가할 때 다음 요소를 고려하십시오.

처리 능력 : 플랫폼에서 실행되는 동안 처리 능력이 거의 없는 PC에서 잘 작동하는 응용 프로그램의 데이터 구조를 선택하십시오. 예를 들어 배열과 같은 단순한 데이터 구조가 트리나 그래프보다 더 적절할 수 있습니다.
동시성 : 데이터 손상 없이 동시 액세스를 처리할 수 있는 스레드로부터 안전한 데이터 구조를 선택해야 합니다. 응용 프로그램이 여러 스레드 또는 프로세스가 데이터 구조에 동시에 액세스하는 동시 환경에서 실행되는 경우. 이 경우 다음과 같은 잠금 없는 데이터 구조 ConcurrentLinkedQueue 그리고 ConcurrentHashMap ArrayList와 같은 전통적인 것보다 더 적절할 수 있습니다. 그리고 해시맵.
네트워크 대기 시간 : 애플리케이션에 네트워크를 통한 데이터 전송이 필요한 경우 최상의 데이터 구조를 결정할 때 네트워크 대기 시간을 고려해야 합니다. 이러한 상황에서 네트워크 호출을 제한하거나 데이터 전송량을 줄이는 데이터 구조를 사용하면 실행을 개선하는 데 도움이 될 수 있습니다.

일반적인 데이터 구조 및 사용 사례

다음은 널리 사용되는 여러 데이터 구조와 그 용도에 대한 요약입니다.

Xbox 앱에서 오프라인으로 표시하는 방법

어레이 : 이것은 동일한 데이터 유형의 고정 크기 계열 요소를 보유할 수 있는 간단하고 효율적인 데이터 구조입니다. 제대로 작동하려면 인덱스를 통해 특정 개체에 대한 빠르고 직접적인 액세스가 필요합니다.
연결된 목록 : 연결 리스트는 요소와 다음 노드 및/또는 이전 노드에 대한 참조를 포함하는 노드로 구성됩니다. 효율적인 작업으로 인해 연결된 목록은 요소를 자주 삽입하거나 삭제해야 하는 상황에 가장 적합합니다. 그러나 연결된 목록의 인덱스로 개별 요소에 액세스하는 것은 배열에 비해 느립니다.
대기열 및 스택 : 스택은 LIFO(후입선출) 규칙을 준수하며 마지막으로 삽입된 항목이 제거된 첫 번째 항목입니다. 대기열은 FIFO(First-In-First-Out) 원칙에 따라 관리됩니다. 추가된 첫 번째 요소는 삭제된 첫 번째 요소이기도 합니다.
해시 테이블 : 해시 테이블은 키-값 쌍을 보유하는 데이터 구조의 한 형태입니다. 가장 좋은 솔루션은 구성 요소의 수를 예측할 수 없고 키로 값에 빠르게 액세스해야 하는 경우 해시 테이블을 사용하는 것입니다.
나무 : 트리는 계층 구조의 요소 그룹을 저장할 수 있는 계층적 데이터 구조입니다. 최고의 용도 이진 검색 트리 데이터 항목 간의 관계가 트리와 같은 구조를 나타낼 수 있는 계층적 데이터 구조입니다.

올바른 데이터 구조 선택

데이터 구조를 선택하기 전에 애플리케이션의 데이터, 의무 및 환경을 고려하십시오. 선택하는 동안 다음 요소에 대해 생각하십시오.

시간 복잡도 : 애플리케이션의 성능은 데이터 구조의 시간 복잡도에 의해 크게 영향을 받을 수 있습니다. 애플리케이션에 빈번한 검색 또는 가져오기 작업이 필요한 경우 해시 테이블과 같이 시간 복잡성이 감소된 데이터 구조를 사용하십시오.
공간 복잡성 : 데이터 구조의 공간 복잡도는 또 다른 중요한 고려 사항입니다. 응용 프로그램이 메모리 집약적인 경우 배열과 같이 공간 복잡성이 적은 데이터 구조를 선택하십시오. 공간이 중요하지 않은 경우 트리와 같이 공간이 더 복잡한 데이터 구조를 사용할 수 있습니다.
읽기 대 쓰기 작업 : 응용 프로그램에서 쓰기 작업을 많이 사용하는 경우 해시 테이블과 같이 삽입 성능이 더 빠른 데이터 구조를 선택하십시오. 애플리케이션에서 많은 읽기 작업을 요구하는 경우 이진 검색 트리와 같이 검색 속도가 더 빠른 데이터 구조를 선택합니다.
데이터 유형 : 처리 중인 데이터가 선택한 데이터 구조에 영향을 줄 수도 있습니다. 예를 들어, 데이터가 계층적이라면 트리 기반 데이터 구조를 사용할 수 있습니다. 임의로 액세스해야 하는 간단한 데이터가 있는 경우 배열 기반 데이터 구조를 선택하는 것이 가장 좋습니다.
사용 가능한 라이브러리 : 고려 중인 데이터 구조에 쉽게 액세스할 수 있는 라이브러리를 고려하십시오. 프로그래밍 언어에 특정 데이터 구조에 사용할 수 있는 내장 라이브러리가 있는 경우 실행 및 유지 관리가 더 쉬울 수 있습니다.

다음 Python 예제는 특정 사용 사례에 가장 적합한 데이터 구조를 선택하는 방법을 보여줍니다.

계층 구조에서 파일을 저장하고 검색해야 하는 파일 시스템 애플리케이션을 개발하는 경우를 고려하십시오. 이러한 계층 구조를 효율적으로 표현할 수 있는 데이터 구조를 선택하고 검색, 삽입 및 삭제와 같은 작업을 신속하게 수행해야 합니다.

Windows 10에 오래된 게임 설치

이진 검색이나 B-트리와 같은 트리 기반 데이터 구조를 사용하는 것이 좋습니다. 각 디렉토리의 항목 수가 상대적으로 적고 트리가 매우 깊은 이진 검색 트리가 아닌 경우 잘 작동합니다. B-트리는 더 많은 수의 파일과 더 깊은 디렉터리 구조에 더 적합합니다.

다음은 Python의 이진 검색 트리의 예입니다.

 class Node: 
   def __init__(self, value): 
 
       self.value = value 
       self.left_child = None 
       self.right_child = None 
 
class BinarySearchTree: 
 
   def __init__(self): 
       self.root = None 
   def insert(self, value): 
 
       if self.root is None: 
           self.root = Node(value) 
 
       else: 
           self._insert(value, self.root)  
   def _insert(self, value, current_node): 
 
       if value < current_node.value: 
           if current_node.left_child is None: 
               current_node.left_child = Node(value) 
 
           else: 
               self._insert(value, current_node.left_child) 
       elif value > current_node.value: 
           if current_node.right_child is None: 
               current_node.right_child = Node(value) 
           else: 
               self._insert(value, current_node.right_child) 
 
       else: 
           print("Value already exists in tree.") 
   def search(self, value): 
       if self.root is not None: 
           return self._search(value, self.root) 
 
       else: 
           return False 
   def _search(self, value, current_node): 
 
       if value == current_node.value: 
           return True 
 
       elif value < current_node.value and current_node.left_child is not None: 
           return self._search(value, current_node.left_child) 
 
       elif value > current_node.value and current_node.right_child is not None: 
           return self._search(value, current_node.right_child) 
 
       else: 
           return False

이 구현에서는 두 개의 클래스를 구성합니다. 이진검색트리 삽입 및 검색 작업을 관리하는 클래스와 마디 이진 검색 트리의 노드를 상징하는 클래스.

insert 방식은 값에 따라 트리의 적절한 위치에 새로운 노드를 삽입하는 반면, search 방식은 지정된 값을 가진 노드를 찾는다. 균형 트리에서 두 작업의 시간 복잡도는 다음과 같습니다. O(로그 n) .

최적의 데이터 구조 선택

선택한 데이터 구조에 따라 애플리케이션의 속도와 적응성이 크게 향상될 수 있습니다. 데이터, 작업 및 환경을 고려하면 최상의 데이터 구조를 선택하는 데 도움이 될 수 있습니다.

시간 복잡성, 공간 복잡성, 읽기 대 쓰기 작업, 동시성, 데이터 유형 및 라이브러리 액세스 가능성과 같은 고려 사항이 중요합니다.

각 구성 요소의 가중치를 평가하여 애플리케이션의 요구 사항을 충족하는 데이터 구조를 선택해야 합니다.