Developer with Cat
© 2021. All rights reserved.
#[🌎elasticsearch] Elasticsearch 타입에 대해서 알아보자!
Elasticsearch 가이드북 ✈
Elasticsearch 홈페이지 가기 ✈
ElasticSearch 의 다양한 기능들을 둘러보기 전 꼭 알아야 할 타입들에 대해서 알아보겠습니다.!! 진짜 진짜 진짜 중요하니 꼭 커피 스윽 마시고 읽어주세요!!
Mapping 어떻게 ElasticSearch 의 문서들이 저장되고 색인 되었는지에 대한 정의입니다. 이 Mapping 의 정의를 통해 불필요한 프로세스 들과 공간 낭비를 줄이고 필요한 기능을 사용할 수 있습니다. 예를 들면,
또한 이후 포스트에서 Dynamic Mapping 을 다룰 때에도 Mapping 과 타입에 대한 기본 개념이 필요합니다.
먼저 이번 포스트에서는 Metadata Fields 가 아닌 Properties 에 대한 Field Type 다룹니다.
Metadata Fields 는 “_index”, “_id”, “_source” 와 같이 metadata 와 관련된 녀석들입니다!
먼저 중요한 녀석들을 뽑자면,
그 외에
등이 있습니다.
더 자세한 내용은 👆엘라스틱 홈페이지 참고하기!!
요 두 녀석은 정말 중요합니다.
기본적으로 우리가 어떤 필드 타입을 지정해주지 않고 문자열 데이터를 넣게 되면 (지정 안해도 가능합니다.) ElasticSearch 는 이 필드가 어떤 용도로 사용될 지 알 방법이 없기 때문에 keyword 와 text 타입을 같이 지정해주어 색인과정을 진행하게 됩니다.
keyword 와 text 의 두 기능이 모두 필요하다면 keyword 와 text 타입을 같이 지정해주는 것이 정말 유용합니다.
하지만 예를 들어봅시다. 문서의 작성자를 검색을 하고 싶습니다. 작성자를 Email 이라고 합시다. 우리가 검색할 단어와 Email 이 비슷한지는 상관관계를 따질 필요가 없습니다. 오직 keyword 타입의 필드만 있으면 되겠죠.
그럼 Email 필드에 text 타입은 불필요한 타입이고, 이는 disk 공간을 낭비하게 됩니다. 만약 문서가 수백만 수천만개가 넘어간다면 이는 무시할 수 없는 공간일 것 입니다.
이는 반대도 마찬가지 입니다.
필드에 필요한 Type 만 지정하는 것은 결국 disk 비용을 줄이는 결과를 가져오겠죠?? 비용은 매우 중요하니까 꼭 필요한 만큼만 씁시다!!
숫자 또한 중요하지만 알아야 할 개념은 많지 않습니다. 만약 JSON 형식의 데이터가 날라와 저장하는데 정수 형식이다 그러면 Long 타입으로, 실수 형식이다 그러면 Double 타입으로 자동으로 매핑됩니다.
자 여기서 질문. 왜 Long 이고, Double 일까?
ElasticSearch 는 지정되지 않은 타입에 대해서 정보가 없습니다.
다시말해 정수가 저장되면 이 정수의 범위가 어떻게 될지에 대해서 알 수 없습니다. 그렇기 때문에 Interger 가 아니라 더 큰 수를 담을 수 있는 Long 타입에 매핑하는 것 입니다. Double 또한 마찬가지 입니다.
하지만 무조건 Long, Double 타입을 사용하는건 좋지 않습니다. 이전에 이미 말했지만 비용은 매우 중요합니다. Integer 의 범위면 충분한데 Long 을 사용하는 것은 disk 공간을 낭비하는 행동이겠죠?
만약 정확하게 특정 필드가 다룰 숫자의 범위를 안다면 그에 맞게 사용하시는 것이 좋습니다.
JSON 형식의 데이터에는 이 필드는 date 타입이다!! 라고 알려주는 지표가 없습니다. 우리가 JSON 형식으로 데이터를 주고 받을텐데.. ElasticSearch 는 이걸 어떻게 알까요?
ElasticSearch 는 매우 유용한 기능을 가지고 있습니다.
이 필드가 Date 타입인지 아닌지 유추하는 것이죠
문자열 필드이며, Date 정보를 포함하고 있다면 예들들어 다음과 같은 형식이라면
{ "date": "2015-01-01" } { "date": "2015-01-01T12:10:30Z" }
ElasticSearch 는 아!! 이 필드는 Date 타입이구나! 라고 추론하게 됩니다.
물론 이 형식은 아래와 같이 형식을 정할 수 있습니다.
"mappings": { "properties": { "date": { "type": "date", "format": "yyyy-MM-dd HH:mm:ss||yyyy-MM-dd||epoch_millis" } } }
아직 mapping 하는 법을 배우진 않았지만 format 형식을 보면서 아 이런 식으로 지정 가능하구나 라고 아시면 될 것 같습니다.
또한 미리 지정한다면 Interger, Long 타입을 Date 필드로 표현이 가능도 합니다.
JSON 의 데이터 형식은 Object 라고 보시면 됩니다. 계층적으로 내부 Object 를 다시 포함하게 되죠.
ElasticSearch 에서는 사실 Object 라는 타입이 애매모호합니다.
예를 들어
{ "region": "US", "manager": { "age": 30, "name": { "first": "John", "last": "Smith" } } }
이런 데이터가 있다면 ElasticSearch 는 내부적으로
{ "region": "US", "manager.age": 30, "manager.name.first": "John", "manager.name.last": "Smith" }
점을 통해 저장합니다. 따라서 내부적으로 본다면, “Object 라는 타입은 없다.” 라고도 할 수 있겠네요.
Nested 타입은 배열과 관련이 있습니다. 더 자세하게 말하면 Object 의 배열을 색인 하기 위한 특수 타입이라고 보시면 되겠네요.
이전에 말했던 것 처럼ElasticSearch 내부적으로는 Object 라는 타입이 없다. 라고 말씀드렸는데요.
{ "group" : "fans", "user" : [ { "first" : "John", "last" : "Smith" }, { "first" : "Alice", "last" : "White" } ] }
이와 같은 타입은 어떻게 저장되어야 할까요? user.first 는 여러개 있으니 배열로 저장해야 할 것입니다. 다음과 같이요.
{ "group" : "fans", "user.first" : [ "alice", "john" ], "user.last" : [ "smith", "white" ] }
이렇게 저장되면 alice white 라는 이름과 john smith 이름의 연관성은 사라지게 됩니다.
순수히 user.first 에 “alice”, “john” 이 저장되었고 마찬기자로 user.last 에 “smith”, “white” 이 저장되었기 때문이죠.
다시말해 smith 라고 검색한다면 alice 가 튀어나올 수도 있는 상황이라는 겁니다.
이를 해결하기 위해 Nested 라는 타입을 지정할 수 있습니다. Nested 를 사용하게 되면 ElasticSearch 는 배열을 내부적으로 숨겨진 문서에 해당 내용을 따로 저장하게 됩니다.
만약 user 가 11명이라면, 11개의 숨겨진 user 문서와 1개의 본 문서가 저장되겠네요.
문서가 늘어난다는 것은 검색 비용이 늘어난다는 말입니다. 유의해서 써라… 이 말이죠.
끝이라 적고 한가지만 더 말씀드리자면.. 이 Mapping 을 통해 데이터 타입을 정하고 인덱스를 만들었습니다. 그리고 엄청난 양의 데이터를 만들고 나니 데이터의 타입을 변경해야할 상황이 오게 되면…
인덱스를 삭제하고 다시 만드는 Reindex 과정이 필요합니다… 그러니 반드시.. 심사숙고해서.. 만드세요..
짞짞짞 고생 많으셨습니다.!! 잠시 눈 운동하고 쉬고 계세요!!
다음에는 또 어려운 내용으로 찾아뵐게요.. 흑흐구 ㅜㅜ 공부할 수록 알아야할 내용이 많습니다.
#[leetcode][32] Longest Valid Parentheses 문제풀기
”(“ 또는 “)” 로만 구성되어 있는 문자열을 줄거야!! 유효한 괄호들의 가장 긴 길이를 구해줘!
자세한 문제 설명과 릿코드 홈페이지 참고. 문제풀러가기
유효한 괄호의 조건은 “)” 가 나왔을 때 “(“ 의 개수와 대조해보면 된다!!
즉, 괄호가 유효한 조건을 확인하는 방법은,
”(“ 가 나왔을 때는 입의 방향 기준으로 rightCount를 1 더해주고 “)” 가 나왔을 때는 rightCount 가 0이 아니라면 rightCount 를 1 빼주고 또한 유효하다고 할 수 있다!!
이 문제는 문자열 전체가 유효한지 아닌지가 아니라 부분집합중 유효한 길이의 최대를 구하는 것이다!
이 문제의 해결법은 Dynamic Programming, Brute Force, Stack 등 여러 방법이 있다.
나는 Dynamic Programming 기법을 이용해 풀었다.
이전에 무엇이 나오던간에 “)” 가 나온 부분이 유효하다면 유효한 괄호의 길이는 2 이상이라는 것을 보장한다. 즉 유효한 “)” 가 연속으로 나온다면 길이가 2씩 늘어난다는 것을 보장한다!
만약 아래와 같은 상황이라면
) ( ( ) ) 1 2 3 4 5 : 인덱스 번호
인덱스 4번까지 검사한다면 길이가 2, 5번까지 검사한다면 4 라는 것을 보장할 수 있다. 아래와 같은 상황이면 어떻게 해야할까?
( ) ( ( ) ) 1 2 3 4 5 6
인덱스 2번, 5번, 6번에서는 각각 길이가 2, 2, 4 라는 것을 보장할 수 있다. 하지만 답은 6이지 않은가 !!
이를 해결하기 위해서 5번 검사할 때 유효한 길이 인 2만큼 전의 인덱스 즉 3번의 인덱스에서 보장한 값이 무엇인지 확인해야한다. 어랏 0이네? 그럼 5번에서는 2까지만 보장한다.
6번을 검사할 때는 유효한길이인 4만큼 전의 인덱스 즉 2번을 보면 2의 길이를 보장한다. !! 즉 2번에서 보장한 2의 길이와 원래 6에서 보장한 길이 4 더한 6의 길이만큼을 다시 6번에서 보장할 수 있다 뚜둔!!!
즉, 만약 유효한 괄호가 계속 유지가 된다면 원래 유효한 길이 바로 전에도 유효해야 한다는 것이다.
우리가 구하려는 인덱스를 i 라고 하자 (0 부터 시작하자)
dp[i] 는
이제 보니 별로 어렵진 않지 않은가?
var longestValidParentheses = function (s) { let answer = 0; let dp = new Array(s.length); dp.fill(0); // agari direction let rightCount = 0; if (s[0] === "(") { rightCount++; } for (let i = 1; i < s.length; i++) { if (s[i] === "(") { dp[i] = 0; rightCount++; } else { if (rightCount === 0) { dp[i] = 0; } else { dp[i] = dp[i - 1] + 2; if (i - dp[i] > 0) { dp[i] += dp[i - dp[i]]; } rightCount--; } } answer = Math.max(answer, dp[i]); } return answer; };
구현 능력 자체는 어렵지 않으나, 어떻게 풀지를 생각하는데 조금 오래 걸린 문제다.
stack 으로 푸는 방법도 있길래 봤는데 정말 나는 멀었다고 생각한다. 이 방법으로도 풀어봐야겠다.
#[leetcode][31] Next Permutation 문제풀기!
다음 순열 구해라.
솔직히 말해서 다음 순열이 뭔데? 뭔데? 하면서 한 5분은 찾아봤다.
다음 순열은 예를 들면 다음과 같다. 숫자 1,2,3,4 각각 하나씩 있다. 이를 통해 순열을 만들어보면
등 이 가능하다.
하지만 문제에서는 lexicographically 즉 사전순서대로 순열을 만들었을 때, 해당 순열 다음으로 오는 순열이 무엇이냐?? 를 물어본 것이다.
예를 들면 1,2,3,4 의 순열들은
- 1,2,3,4 - 1,2,4,3 - 1,3,2,4 - 1,3,4,2 ....
순서로 이어진다.
단순히 모든 경우의 수를 알아보는 방법도 있겠지만… 우리는 효율적인 코딩을 목표로 하기 때문에 다른 방법을 생각해보자.
!!!! 탐욕기법을 사용 한다면 가능하다!
이전 순열은 무조건 이번 순열보다 작기 때문에 규칙을 적용하면 될 것 같다 뜨악!! 갑자기 고기먹고싶다.
아니 문제로 돌아와서.
1,2,3,4,5 를 예로 들어보자.
1,4,3,2,5 라는 순열이 주어졌다. 이 순열의 다음 순열은 무엇일까?
여기서 규칙을 찾을 수 있다.
3, 2, 5 의 경우 2 가 5보다 작기 때문에 서로의 위치를 바꾸게 되면
3, 5, 2 로서 3, 2, 5 순열보다 큰 값이라는 것을 보장한다.
하지만 바로 다음 순열이라는 것은 보장하지 않는다.
1,2,5,4,3 가 있다고 생각하자.
2 보다 큰 숫자중 5와 바꾸어주면
1,5,2,4,3 이 된다 하지만 정답은 1,3,2,4,5 이다.
즉 단순히 큰 값이 아닌, 큰 값중 가장 작은 값을 찾아 바꿔야 한다는 것이다.
또 조건이 있다. 2 와 5 처럼 증가하는 모양을 보이는 가장 마지막 놈끼리 바꿔야 한다는 것이다.
또오오오 조건이 있다. 바꾼 후에 오른쪽에 있는 놈들은 해당 수열로 만들 수 있는 가장 큰 값이다. 가장 작은 값으로 형태를 바꾸어 주어야한다.
이건 단순히 바꾼놈 기준 오른쪽에 있는 놈들을 바깥에서 안쪽으로 전부 위치를 교환해주면 된다.
자자자 정리하자면
var nextPermutation = function (nums) { let standIndex = -1; let changeIndex = 0; for (let i = 0; i < nums.length - 1; i++) { if (nums[i] < nums[i + 1]) { standIndex = i; changeIndex = i + 1; } if (nums[changeIndex] >= nums[i + 1] && nums[standIndex] < nums[i + 1]) { changeIndex = i + 1; } } if (standIndex !== -1) { swap(nums, standIndex, changeIndex); } let i = standIndex + 1; let j = nums.length - 1; while (i < j) { swap(nums, i, j); i++; j--; } }; const swap = (nums, a, b) => { let temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; };
문제 이해하기가 어려웠다.
내 영어 능력을 의심했다.
나랑 비슷한 사람이 많을까?
#[leetcode][30] Substring with Concatenation of All Words 문제풀기!
문자열과 단어집을 줄테니 단어집의 모오오오든 단어를 포함하는 문자열의 부분 집합을 찾아줘!!
단순히 Brute force 기법을 쓴다면 시간제한에 걸리게 된다. 자료구조 Map을 통해 특정 문자를 logN 시간만에 접근하는 방법을 통해 풀자!
단어집의 모든 단어를 map 자료구조에 할당하고
단어집의 모든 단어를 합친 길이 만큼 문자열에서 떼와서 검사를 했다.
당연히 통과할 줄 알았는데, 단순히 map 자료형으로는 시간적 제한을 통과하지 못했다.
그래서 찾아본 결과 !!
뚜둔
Map 자료형은 레드블랙트리 기반으로 되어 있습니다. 모든 데이터는 정렬되어 저장이 됩니다. 레드블랙트리는 Binary Search Tree 에 Self-Balancing 기능이 추가된 자료구조 입니다. Search 에 Time complexity 가 O(logN) 을 보장하긴 하지만 키 삽입, 제거 할 때마다 트리를 보정하는 비용이 들어가기 때문에 성능이 저하될 수 있습니다. 물론 O(logN) 을 크게 벗어나진 않습니다.
HashMap 은 hash table 을 통해 자료에 접근하게 따라서 데이터를 정렬하지 않습니다. 충분한 크기의 hash table 이 주어진다면, 데이터의 삽입, 제거, 검색시에 성능저하가 거의 일어나지 않습니다.
저는 기본적인 Map 자료구조를 이용했을 때 문제의 시간제한을 통과하지 못했습니다. 다른거는 전부 그대로 두고 hash table 을 사용하니 바로 통과하더군요!!
만약 데이터의 양이 매우 많아진다면 Hash Table 을 사용하는 것도 좋은 선택인 것 같습니다.
#include<vector> #include<string> #include<algorithm> #include<unordered_map> using namespace std; vector<int> findSubstring(string s, vector<string>& words); bool testSubstringMatch(string& s, int start, int end, int wordLength, int wordsSize); unordered_map<string, int> mapWord; int main() { findSubstring(in2[0], inp); } vector<int> findSubstring(string s, vector<string>& words) { vector<int> ans; if (s.size() < words[0].size() * words.size()) return ans; for (int i = 0; i < words.size(); i++){ mapWord[words[i]]++; } for (int i = 0; i <= s.size() - words[0].size(); i++) { if (testSubstringMatch(s, i, i + words[0].size() * words.size(), words[0].size(), words.size())) { ans.push_back(i); } } return ans; } bool testSubstringMatch(string& s, int start, int end, int wordLength, int wordsSize) { unordered_map<string, int> mapTemp; int count = 0; for (int i = start; i < end; i += wordLength) { string compareStr = s.substr(i, wordLength); mapTemp[compareStr]++; if (mapTemp[compareStr] <= mapWord[compareStr]) count++; else return false; } if (count == wordsSize) return true; return false; }
자료구조에 대해 더 신경써야할 시간이 온 것 같다. !!!! Hard 문제는 확실히 일반 문제랑 조금 다르다.!!
#[📣top interview question] Best Time to Buy and Sell Stock II 문제풀기!
어떤 물건의 가격이 매일 달라..
매일 달라지는 가격을 줄테니…
나를 부자로 만들어줘!!
가격이 언제 꺾이는지 (하강하다 상승, 상승하다 하강) 에 포인트를 주면 될 것 같다.
하강하다가 상승한다면 그 지점에서 사야하고, 상승하다가 하강하면 팔아야한다.
더 쉽게 풀려면 그냥
prices[i] < prices[i + 1]
일 때 그 차이를 그냥 더해주면 되지 싶다.
var maxProfit = function (prices) { let buyDate = -1; let profit = 0; for (let i = 0; i < prices.length; i++) { if (prices[i] < prices[i + 1]) { if (buyDate === -1) { buyDate = i; } } else { //감소할때 팔면 이득. if (buyDate !== -1) { profit += prices[i] - prices[buyDate]; buyDate = -1; } } } return profit; };
에이 너무 쉽네 하고 Hard 문제 도전했다가 탈탈 털렸다… 틈틈히 시간 날 때마다 Hard 문제도 풀어야겠다.