Ruby 개발자를 위한 데이터 구조 개요

데이터 구조란 무엇입니까?

데이터 구조는 데이터를 구성하고 액세스하는 특정 방법입니다. .

예는 다음과 같습니다.

배열
이진 트리
해시

서로 다른 데이터 구조는 서로 다른 작업에서 탁월합니다.

예를 들어 해시는 사전(단어 및 정의) 또는 전화번호부(사람 이름 및 번호)처럼 보이는 데이터를 저장하려는 경우 유용합니다.

사용 가능한 데이터 구조 파악 및 각각의 특성 , 당신을 더 나은 Ruby 개발자로 만들어줄 것입니다.

이것이 이 기사에서 배울 내용입니다!

배열 이해

배열은 프로그래밍에 대해 읽기 시작할 때 배우는 첫 번째 데이터 구조입니다.

배열은 객체가 간격 없이 차례로 저장되는 연속적인 메모리 청크를 사용합니다.

C와 같은 저수준 프로그래밍 언어와 달리 Ruby는 메모리를 관리하고 요소를 삭제할 때 최대 배열 크기를 확장하고 압축하는 모든 힘든 작업을 수행합니다.

용도 :

고급 데이터 구조의 기반으로
루프 실행 결과 수집
아이템 수집

split와 같은 배열을 어디에서나 찾을 수 있습니다. &chars 문자열을 문자 배열로 분해하는 메소드.

예 :

out =[]10.times { |i| 아웃 < 
 다음 표는 배열 크기가 증가함에 따라 다양한 배열 작업이 어떻게 작동하는지 보여줍니다.
 
 시간 복잡도 표기법에 익숙하지 않다면 이 기사를 읽으십시오.
 
 배열의 시간 복잡성 :
 작업  복잡성  
 
 푸시  O(1)  
 팝  O(1)  
 접근  O(1)  
 찾기  O(n)  
 삭제  O(n)  
 
 
 
 이것이 도움이 되는 이유는 무엇입니까? 
 
 어레이의 성능 특성을 알려 주기 때문입니다.
 
 find를 많이 하는 경우 느릴 예정인 거대한 어레이에서의 작업...
 
 그러나 사용할 인덱스를 알고 있다면 O(1) 때문에 배열이 빠를 것입니다. 시간 복잡도.
 
 이 기준으로 데이터 구조 선택 :
  성능 특성 => 데이터로 무엇을 하고 있습니까? 데이터세트의 크기는 얼마입니까?
 데이터의 형태 및 형식 => 어떤 종류의 데이터로 작업하고 있습니까? 더 나은 데이터 구조에 맞도록 데이터를 재구성할 수 있습니까?
 
 해시 데이터 구조
 
 국가 코드와 국가 이름 사이에 매핑이 있습니까?
 
 아니면 그냥 물건을 세고 싶을 수도 있습니다.
 
 이것이 바로 해시가 도움이 되는 이유입니다!
 
 해시는 모든 값에 키가 있고 이 키는 무엇이든 될 수 있는 데이터 구조입니다. , 문자열, 정수, 기호 등
 
 어떻게 작동합니까? 
 
 해시는 키를 숫자로 변환합니다(hash Ruby의 메소드) &그 숫자를 인덱스로 사용합니다. 하지만 Ruby 프로그램에서 해시를 사용하려면 이를 이해할 필요가 없습니다.
 
 용도 :
  문자열의 문자 세기
 단어를 정의에, 이름에 전화번호 등을 매핑합니다.
 배열 내에서 중복 찾기
 
 
 예 :
 "aaabcd" .each_char .with_object(Hash.new(0)) { |ch, 해시| 해시[ch] +=1 }# {"a"=>3, "b"=>1, "c"=>1, "d"=>1}
 
 시간 복잡도 :
 작업  복잡성  
 
 저장  O(1)  
 접근  O(1)  
 삭제  O(1)  
 (값) 찾기  O(n)  
 
 
 
 해시는 상수 O(1) 때문에 성능과 관련하여 가장 유용한 데이터 구조 중 하나입니다. 저장, 삭제 및 액세스 시간.
 
 해시 컨텍스트에서 찾기는 특정 값을 찾고 있음을 의미합니다.
 스택
 
 스택은 접시 더미와 같습니다. 한 접시를 다른 접시 위에 올려 놓고 맨 위에 있는 접시만 제거할 수 있습니다.
 
 이것은 처음에 들리는 것보다 더 유용합니다!
 
 용도 :
  재귀 메서드를 일반 루프로 대체
 남은 작업을 추적하고 가장 최근 작업이 맨 위에 표시되도록 합니다.
 배열 반전
 
 
 예 :
 스택 =[1,2,3,4,5](1..stack.size).map { 스택.팝 }# [5, 4, 3, 2, 1]
 
 예, reverse을 사용할 수 있습니다. 대신.
 
 이것은 스택의 이러한 특정 특성을 보여주는 예시일 뿐입니다.
 
 시간 복잡도 :
 작업  복잡성  
 
 푸시  O(1)  
 팝  O(1)  
 찾기  ---  
 접근  ---  
 
 
 
 스택(및 대기열)에는 insert라는 두 가지 작업만 있습니다. &delete , 또는 push &pop .
 
 스택 내부를 검색하는 것은 가능하지만 매우 드뭅니다.
 이진 트리를 사용하는 방법
 
 대부분의 Ruby 개발자는 바이너리 트리에 대해 들어는 보았지만 한 번도 사용해 본 적이 없습니다.
 
 왜 그래? 
 
 첫째, 내장된 바이너리 트리 구현이 없습니다.
 
 둘째, 바이너리 트리는 항상 사용하는 배열 및 해시와 달리 일상적인 프로그래밍 문제에 그다지 도움이 되지 않습니다.
 
 그러나 이진 트리는 매우 흥미로운 데이터 구조입니다. .
 
 
 
 실제로 Trie(다음 섹션에서 다룸), B-Tree(데이터베이스에서 사용) 및 힙과 같은 다중 방식 트리와 같은 많은 변형이 있습니다.
 
 용도 :
  데이터 압축
 라우팅 테이블
 추상 구문 트리(AST)
 
 
 예 :
 # https://github.com/jamesconant/bstreerequire 'bstree'root =Bstree::Node.new(5)root.insert(2)root.insert(7)root.search(3)# nil 
 시간 복잡도 :
 작업  복잡성  
 
 삽입  O(로그 n)  
 삭제  O(로그 n)  
 찾기  O(로그 n)  
 접근  ---  
 
 
 
 균형 이진 트리는 모든 노드에 두 개의 자식이 있고 모든 잎이 동일한 수준을 갖는 경우입니다.
 
 트리가 불균형해지면 성능이 O(n)로 저하됩니다. .
 
 자체 균형 이진 트리에서 (Red-Black Tree 또는 AVL 트리와 같이) 모든 작업은 트리의 높이(또는 레벨)에 비례하여 시간이 걸립니다.
 
 노드에 액세스하려면 먼저 노드를 찾아야 하기 때문에 액세스 시간이 없다는 점에 유의하세요...
 
 이 경우 O(log n)가 됩니다. 액세스를 위해.
 
 그러나 특정 노드에 대한 참조(변수로)를 유지하는 경우 O(1) 액세스 시간.
 트라이 데이터 구조
 
 트리는 트리와 같은 특수 데이터 구조입니다.
 
 단어로 작업한 다음 접두사로 시작하는 단어를 빠르게 검색하거나 전체 단어를 검색하는 데 유용합니다.
 
 용도 :
  단어 게임
 맞춤법 검사기
 자동 완성 제안
 
 
 예 :
 # https://github.com/gonzedge/rambling-trierequire 'rambling-trie'trie =Rambling::Trie.create('words.txt')trie.include?('초콜릿')# truetrie.include ?('연어')# 사실
 
 시간 복잡도 :
 작업  복잡성  
 
 추가  O(k)  
 포함하시겠습니까?  O(k)  
 단어  O(k)  
 
 
 
 이 표에서는 k를 사용합니다. 입력 문자열의 크기를 나타내기 위해 n 데이터 구조 자체의 크기를 나타내는 데 사용됩니다.
 
 따라서 apple이라는 단어의 경우 , k 5가 됩니다.
 요약
 
 일반적인 데이터 구조, 주요 용도 및 특성, Ruby에서 사용하는 방법에 대해 배웠습니다.
 
 
 
 이 새로운 지식을 적용하면 문제를 더 빨리 해결할 수 있습니다!
 
 도움이 되셨다면 이 게시물을 공유해 주시겠습니까?
 
 감사합니다 🙂

작업	복잡성
삽입	O(로그 n)
삭제	O(로그 n)
찾기	O(로그 n)
접근	---