Java, 메모리 참조를 통한 효율적인 트리 구성
쓰레기 코드에서 더 나은 코드로 진화하는 방법
Oct 31, 2024
인 게임에서 유저의 인벤토리를 트리 구조로 만들어야 하는 요구사항이 있었습니다. 모든 값은 자식을 가지고, 자식은 부모의 ID를 참조하여 구성 됩니다. 이를 테면 이런식입니다.
rawInventories[] data = { item1("A", "0"), // 트리의 꼭대기의 루트 노드 item2("B", "A"), item3("C", "A"), item4("D", "B"), item5("E", "C") };
여기서
item1을 루트 노드로 두었을 때, 자식 노드들이 트리 형태로 연결되어야 합니다. 위와 같은 구조를 JSON 형식으로 변환해보면, 실제로는 다음과 같은 계층 구조가 되어야 합니다.{ "id": "A", "children": [ { "id": "B", "children": [ { "id": "D", "children": [] } ] }, { "id": "C", "children": [ { "id": "E", "children": [] } ] } ] }
만약 배열의 깊이가 일정하다면 단순히 루프를 통해 트리 구조를 쉽게 구성할 수 있습니다. 그러나 배열의 깊이가 동적이고, 데이터가 정렬되지 않은 채로 무작위로 들어온다면 더 복잡한 처리가 필요합니다. 고민해봐야 할 주제를 생각하면 다음과 같은 주제들이 있습니다.
- 트리 깊이가 고정되지 않고 동적으로 변할 수 있다.
- 입력 데이터가 정렬되어 있지 않기 때문에 불완전환 데이터 처리가 될 수 있습니다.
- 순환 참조 문제가 발생할 수 있다.
첫 번째로 생각했 던 것은, 배열의 깊이 별로 리스트를 만들어서 재귀 호출을 통해 DFS와 유사하게 개발해 보자였습니다. 완전 탐색으로 불완전한 데이터를 처리할 수 있고, 처리된 데이터는 삭제하여 순환 참조 문제 등을 예방할 수 있다고 생각했습니다.
public static List<RelationInventory> buildInventoryTree(Item[] items) { InventoryMapping itemMapping = mapItemsToRelations(items); Map<String, Integer> itemOrderMap = itemMapping.getItemOrderMap(); List<RelationInventory> rootRelations = new ArrayList<>(); List<RelationInventory> parents = itemMapping.getRootRelations(); // 아이템 정렬 List<Item> sortedItems = new ArrayList<>(Arrays.asList(items)); sortedItems.forEach(item -> item.setSort(itemOrderMap.get(item.getItemId()))); sortedItems.sort(Comparator.comparing(Item::getSort)); int recursiveLimit = 500; for (RelationInventory parentNode : parents) { RelationInventory currentNode = parentNode; for (Item item : sortedItems) { // 재귀 깊이 제한 if (recursiveLimit-- <= 0) { break; } List<Object> result = buildRelationTree(currentNode, item); currentNode = (boolean) result.get(1) ? (Relation) result.get(0) : currentNode; } rootRelations.add(parentNode); } return rootRelations; } public static List<Object> buildRelationTree(RelationInventory currentNode, Item item) { if (currentNode.getId().equals(item.getRefId())) { currentNode.getChildren().add(createRelation(item)); return List.of(currentNode, true); } else { for (RelationInventory child : currentNode.getChildren()) { List<Object> result = buildRelationTree(child, item); if ((boolean) result.get(1)) { return result; } } } return List.of(currentNode, false); } public static InventoryMapping buildInventoryTree(Item[] items) { List<Item> itemList = new ArrayList<>(Arrays.asList(items)); List<RelationInventory> rootRelations = new ArrayList<>(); Map<String, Integer> orderMap = new HashMap<>(); Map<String, Relation> relationMap = new HashMap<>(); int currentLevel = 0; // 루트 노드 생성 for (Item item : itemList) { if (item.getId().equals("0")) { RelationInventory newRelation = createRelation(item); relationMap.put(newRelation.getId(), newRelation); orderMap.put(item.getId(), currentLevel); rootRelations.add(newRelation); } } // 남은 아이템에서 자식 노드 찾기 itemList.removeIf(item -> relationMap.containsKey(item.getItemId())); while (!itemList.isEmpty()) { List<RelationInventory> childRelations = new ArrayList<>(); Iterator<Item> iterator = itemList.iterator(); while (iterator.hasNext()) { Item item = iterator.next(); for (Relation parentRelation : rootRelations) { if (item.getRefId().equals(parentRelation.getId())) { RelationInventory newRelation = createRelation(item); childRelations.add(newRelation); relationMap.put(item.getId(), newRelation); orderMap.put(item.getId(), currentLevel + 1); iterator.remove(); break; } } } rootRelations.addAll(childRelations); currentLevel++; } return new InventoryMapping(orderMap, rootRelations); }
이와 같은 방식으로 작성했을 때는 정상적으로 동작하지만, 몇 가지 문제가 있었습니다:
- 스택 오버플로우 위험: 자식 노드가 깊은 트리에서는 스택 오버플로우가 발생할 위험이 있습니다.
- 성능 저하:
buildTrees메서드가 매번 순회하여 성능이 좋지 않았습니다.
- 불필요한 반환값:
List<Object>를 반환하는 것이 필요 없는 작업이었습니다.
- 유지보수의 어려움: 정렬과 트리 구조가 결합되어 있어 코드의 유지보수가 어렵습니다.
결론적으로, 성능은 좋지 않지만 돌아는 간다는 느낌의 코드였습니다. 이러한 문제들을 해결하기 위해 몇 가지 피드백을 받은 후 수정하게 되었습니다.
두 번째로 생각했던 것은, 배열의 깊이에 따라 리스트에 순서대로 입력하여 트리 형태로 구성하자는 아이디어였습니다. 이렇게 하면 트리의 깊이가 고정되지 않고 동적으로 변하는 문제를 해결할 수 있으며, 입력 데이터 정렬 문제도 동시에 해결할 수 있습니다.
public static List<RelationInventory> build(RawInventoryOriginData[] vo) { Map<String, Object> headMap = new HashMap<>(); List<RelationInventory> stacks = new ArrayList<>(); List<RawInventoryOriginData> restArrayList = new ArrayList<>(); Integer dimension = 1; /* 첫번 째 부모 저장, 및 잔여 리스트 저장 */ for (RawInventoryOriginData v : vo) { if (v.getContainerItemUid().equals("0")) { headMap.put(v.getId(), dimension); stacks.add(getMappingRelation(v, dimension)); } else { restArrayList.add(v); } } Map<String, Object> parentMap = headMap; int roop = 1; while (vo.length > stacks.size()) { roop ++; if(roop > 500) { break; } Map<String, Object> childMap = new HashMap<>(); /* 위에서 1차원을 저장했기 때문에 2차원부터 시작 */ dimension++; for (RawInventoryOriginData v : restArrayList) { if(parentMap.containsKey(String.valueOf(v.getRefId()))) { childMap.put(v.getId(), dimension); stacks.add(getMappingRelation(v, dimension)); } } parentMap = childMap; } return stacks; } public static List<RelationInventory> getInventoryBuilder(List<RelationInventory> stacks) { List<RelationInventory> childList = new ArrayList<>(); List<RelationInventory> inventoryList = new ArrayList<>(stacks); int dimension = inventoryList.get(inventoryList.size() - 1).getDimension(); for (int i = 0; i < inventoryList.size(); i++) { RelationInventory v = inventoryList.get(inventoryList.size() - i - 1); if(!childList.isEmpty()) { for (RelationInventory child : childList) { if(Objects.equals(v.getDimension(), child.getDimension())) { continue; } if (v.getId().equals(child.getRefId())) { v.getChild().add(child); } } } if(v.getDimension() == dimension) { childList.add(v); } else { dimension --; childList.add(v); } } return stacks.stream().filter(v -> Objects.equals(v.getRefId(), "0")).toList(); }
하지만 위 코드도 시간 복잡도가 O(n^2)로서 그다지 효율적이진 않았습니다. 물론 이전보다는 확실히 가독성도 좋아지고 유지보수도 수월해진 건 사실입니다만, 만족스럽지 않았죠
그렇게 사용하다가 익명의 개발자 A가 저에게,
“변수 선언하면 메모리에 올라가는데 값 참조해서 적용하면 되는거 아닌가요?”
라고 말씀해주셔서, 간단하게 자바 변수의 메모리 관리와 참조에 대해서 찾아보고 새롭게 반영해봤습니다.
Java의 선언된 변수 메모리 관리
자바에서 선언된 변수는 메모리에 올라가게 됩니다. 이때, 변수가 기본형(Primitive Type)이라면 실제 값 자체가 변수 선언과 동시에 메모리의 스택(stack)에 저장됩니다. 기본형 데이터 타입은 다음과 같습니다.
- boolean
- char
- byte, short, int, long
- float, double
위의 8가지 자료형을 제외한 참조형(Reference Type)의 경우, 실제 값이 저장되지 않고 해당 값이 저장된 메모리 공간의 주소만 저장됩니다. 즉, 실제 값은 힙(heap) 영역에서 관리되며, 참조 값(메모리 주소)은 스택에 저장되어 관리됩니다. 참조형은 다음과 같습니다.
- Custom Class
- Array, List
- 열거형(Enum)
- 기타 기본형이 아닌 모든 타입
힙 영역에 할당된 변수의 실제 값은 가비지 컬렉터(gc)에 의해 관리됩니다. 가비지 컬렉터는 참조되지 않은 경우로 판단되면 해당 메모리 공간을 해제합니다.
메서드 내에서 선언된 스택 영역의 변수는 메서드 호출 시 메모리에 할당되고, 메서드가 종료되면 메모리에서 해제됩니다.
메모리에 올라간 변수
선언된 변수의 실제 값은 힙(Heap) 영역에 위치하게 되며, 이 힙 영역에 존재하는 객체는 일반적으로 내부 리스트인 child를 비어 있는 상태로 초기화합니다. 만약 힙 영역에 할당된 값을 참조하여 child 내부에 값을 추가(add)하게 된다면, 이 값은 힙 영역에서 관리됩니다. 예를 들어,
Map<String, RelationInventory> nodeMap = new HashMap<>(); List<RelationInventory> rootNodes = new ArrayList<>(); for (RawInventoryOriginData item : vo) { RelationInventory node = getMappingRelation(item); nodeMap.put(item.id(), node); if ("0".equals(item.refId())) { rootNodes.add(node); } } private static RelationInventory getMappingRelation(RawInventoryOriginData v) { RelationInventory newItem = new RelationInventory(); newItem.setId(v.getId()); newItem.setRefId(v.getRefId()); newItem.setChild(new ArrayList<>()); return newItem; }
위 코드처럼 처리하게 되면, 모든 RawInventory 데이터는 RelationInventory 객체로 변환되어 각각 메모리에 할당됩니다. 각 객체는 부모와 자식 관계를 아래와 같이 형성하게 됩니다.
for (RawInventoryOriginData item : vo) { if (!"0".equals(item.getRefId())) { RelationInventory parent = nodeMap.get(item.getRefId()); RelationInventory child = nodeMap.get(item.getId()); if (parent != null && child != null) { parent.getChild().add(child); } } }
이 과정에서 자식의 refId가 특정 노드의 Id와 같다면, 해당 노드는 부모의 자식 노드로 리스트에 추가됩니다. 모든 루프가 종료되면 부모-자식 관계가 설정된 모든 노드가 연결되어 있게 됩니다.
부모의 child 안에 담겨 있는 자식의 메모리 주소는 자식 객체의 값을 기억하고 있으며, 자식 객체도 만약 child가 있다면 그 메모리 주소를 참조하게 됩니다.
이렇게 모든 노드가 이어지면서 트리 구조가 형성됩니다. 초기 설계보다 훨씬 가독성이 좋고, 유지보수하기 수월하며 성능 또한 효율적인 방법으로 변했습니다.
결론
자바의 메모리 관리에 대한 이해는 객체 간의 관계를 효과적으로 설정하고 트리 노드를 구축하는 데 큰 도움을 줄 수 있습니다. 힙 영역에 할당된 객체는 가비지 컬렉터에 의해 관리되며, 이를 통해 참조와 메모리 주소를 기반으로 부모-자식 관계를 맺은 메모리 주소를 트리 노드로 만들게 됩니다.
이러한 지식을 토대로 보다 효과적이고, 시간복잡도와 공간복잡도가 높은 코드를 구성할 수 있게 됩니다.
Share article