CS지식/자료구조5 퀵정렬 (feat 메모리 참조지역화) [ 의미 ] 분할 정복기법으로 적어도 한개 이상은 정렬된다. 최악의 경우 n제곱번 비교한다. 왜냐면 한번의 재귀호출당 무조건 정렬이 하나이상되기 때문이다. 메모리 참조 지역화로 빠르다(시간지역성, 공간지역성, 순차지역성) [ 참조지역화 ] 내가 짠 코드는 순차지역성에 특징에 부합할거다 재귀 짜면서 임시변수를 만들어놔서 호출될때마다 스택에 가까운주소로 쌓이면서 core 캐쉬에 적재가 될꺼다. 그래서 굳이 해당 데이터를 메모리에서 가지고 올 필요가 없어서 빨라질것이다. 공간지역성까지 고려한 코드를 짜면 좀 더 빠를것이다 하나의 데이터만 두고 스왑하는거다 [ 테스트 과정 ] 원소 사이즈는 10000개 정도 Collections.sort로 정렬된 결과와 내가 작성한 quickSort 결과 비교해서 assert로.. 2022. 7. 17. 여러 스레드에서 ConcurrentHashMap 빠르게 수정/삭제 하기 상황 ConcurrentHashMap 사용 32개 스레드에서 정해진 범위에 key로 삭제 -> 추가 연산을 지정한 요청 수 만큼하고 걸린 시간초를 출력한다. 테스트 코드 MainClass import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; public class MainClass { public static Map setCoordinate(Map coordinate, int MAX_PEOPLE) { for (int count = 0; count < MAX_PEOPLE; count++) { coordinate.put(count, count); .. 2022. 2. 12. 선택/삽입정렬 구현및 비교 선택/삽입정렬 시간복잡도 O(n의 제곱)이다. 선택정렬 class Sort{ void print(int[] items){ for (int item : items) { System.out.print(item+", "); } } int[] selectSort(int[] items){ int standardVal; int standardIndex; boolean bFind = false; for(int keyIndex = 0; keyIndex < items.length - 1; keyIndex++) { standardVal = items[keyIndex]; standardIndex = keyIndex; print(items); System.out.println("standardVal: " + standardV.. 2021. 12. 11. 이진트리 정의 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리임 장점 노드가 균형을 잡고있다면 효율적인 검색이 가능하다. 단점 노드가 불균형하다면 한쪽으로 치우쳐져있으면 연결리스트 성능이 나온다..(레드블랙트리가 있다) 용어 정리 루트노드: 최상위 노드 부모노드: 자식노드를 가지고있는 노드 자식노드: 부모노드가 가지고 있는 노드 잎노드: 자식 노드가 없는 노드 차수: 자식노드 갯수 레벨 깊이: 루트에서 어떤 노드에 도달하기 위해 거치는 간선의 수 이진트리 종류 루트 이진 트리: 하나의 루트 노드를 가지고 있고 모든 노드가 최대 두개의 자식노드를 가지고 있는 트리. 정 이진 트리: 모든 노드가 0개 또는 2개의 자식 노드만 가짐 포화 이진 트리: 모든 내부 노드가 두개의 자식 노드를 가진다.그리고 모든 잎 노.. 2021. 6. 16. ArrayList, LinkedList 비교, 성능테스트 일단 기본적인 차이점은 생략한다. ArrayList 정의 ArrayList는 내부에 배열을 가지고 있음. ArrayList 단점 배열 사이즈만큼 삽입 삭제는 성능이 좋지만 사이즈가 넘어가면 다시 배열 복사하고 생성해야한다. ArrayList 배열복사시 사용하는 System.arraycopy 함수 이때 자바에서는 System.arraycopy native 메소드를 사용한다. 우선 객체를 복사하는 유형은 깊은복사/얕은복사가 있다. 깊은복사는 객체를 new 생성하는거고 얕은복사는 해당 객체의 주소만 참조하는것이다. 얕은복사의 문제는 주소참조로인해 참조하는 다른곳도 바뀔수 있다는거다. arraycopy해보면 알겠지만 객체타입의 배열은 복사시 얕은복사가 진행된다. 즉 overlap에 취약하다는 애기다. 하지만 속.. 2021. 6. 12. 이전 1 다음
