트라이 자료구조(Trie Data Structure)

https://leetcode.com/problems/implement-trie-prefix-tree/

Implement Trie (Prefix Tree) - LeetCode

리트코드를 풀다 만난 트라이 자료구조의 구현 문제다. Abstract Data Type을 직접 구현해보는 좋은 문제다. 몇 시간만에 겨우 문제를 풀었는데, Accepted는 떴지만, 퍼포먼스가 저조해서 이걸 좀 개선해보고자 한다. 

LeetCode Platform serves your position of the Runtime that you submitted. 

100%에 근접할수록 좋은 퍼포먼스(낮은 시간복잡도를 갖는)를 내는 코드인데, 이를 100%에 가깝게 개선하고자 한다. 먼저 아래는 기존의 퍼포먼스가 저조한 코드다. 

#define ALPHABET 26
using namespace std;

class Node {
public:
    Node* next_words[ALPHABET] = {NULL};
    bool isEnd;
    Node(): isEnd(0){}
};

class Trie {
public:
    /** Initialize your data structure here. */
    
    Node *root;
    
    Trie() {
        root = (Node*)malloc(sizeof(Node));
        memset(root->next_words, NULL, sizeof(root->next_words));
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        //prefix 가 이미 있는 경우,
        Node* tmp = root;
        for(int i = 0; i < word.length(); i++){
            if(tmp->next_words[word[i]-'a'] != NULL){
                tmp = tmp->next_words[word[i]-'a'];
            }
            else{
                tmp->next_words[word[i]-'a'] = new Node;
                tmp = tmp->next_words[word[i]-'a'];
            }
        }
        tmp->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* tmp = root;
        int word_len = int(word.length());
        for(int i = 0; i < word_len; i++){
            if(tmp->next_words[word[i]-'a'] == NULL){
                return false;
            }
            tmp = tmp->next_words[word[i]-'a'];
        }
        if(tmp->isEnd) return true;
        else return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* tmp = root;
        int prefix_len = int(prefix.length());
        for(int i = 0; i < prefix_len; i++){
            if(tmp->next_words[prefix[i]-'a'] == NULL){
                return false;
            }
            tmp = tmp->next_words[prefix[i]-'a'];
        }
        return true;
    }
};

이를 개선 시키기 위해 Node Class 를 instantiate 할 때, 힙이 아닌, 스택에 할당하고, Trie 클래스 생성자의 memset함수를 줄이고, Node class에서 초기화하도록 Redundancy를 줄여서 속도를 개선해보았다. 

Perfomance got much better and up to 81.27%

우선 아래는 1차 개선 코드다. 

#define ALPHABET 26
using namespace std;

class Node {
public:
    Node* next_words[ALPHABET];
    bool isEnd;
    Node(): isEnd(0){
        for(int i = 0; i < ALPHABET; i++) next_words[i] = NULL;
    } //초기화를 하겠다는 선언임,이렇게 초기화된 변수는 object로 로드 되면서, 멤버변수로 메모리에 할당됩니다.
};

class Trie {
public:
    /** Initialize your data structure here. */
    Node root;
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        //prefix 가 이미 있는 경우,
        Node* tmp = &root;
        for(int i = 0; i < word.length(); i++){
            if(tmp->next_words[word[i]-'a'] != NULL){
                tmp = tmp->next_words[word[i]-'a'];
            }
            else{
                tmp->next_words[word[i]-'a'] = new Node;
                tmp = tmp->next_words[word[i]-'a'];
            }
        }
        tmp->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* tmp = &root;
        int word_len = int(word.length());
        for(int i = 0; i < word_len; i++){
            if(tmp->next_words[word[i]-'a'] == NULL){
                return false;
            }
            tmp = tmp->next_words[word[i]-'a'];
        }
        if(tmp->isEnd) return true;
        else return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* tmp = &root;
        int prefix_len = int(prefix.length());
        for(int i = 0; i < prefix_len; i++){
            if(tmp->next_words[prefix[i]-'a'] == NULL){
                return false;
            }
            tmp = tmp->next_words[prefix[i]-'a'];
        }
        return true;
    }
};