메뉴

문서정보

Sets 과 Sorted sets

소프트웨어 프로그래밍에서 가장 먼저 다루는 데이터 스트럭처는 비트, 배열, 스트링, 리스트다. 단순해서 배우고 응용하기 쉽고, 다른 데이터 스트럭처를 이해하기 위한 기본이 되기 때문이다. 단점은 단순한 만큼 응용범위도 넓지 않다는데 있다.

Sets는 좀 더 복잡하고 그 만큼 더 다양한 응용을 할 수 있다.

Sets는 key에 하나 이상의 value를 가지는 데이터 스트럭쳐다. 값은 정렬되지는 않지만 데이터 중복을 허용하지 않는다. SADD 명령으로 key에 value를 추가 할 수 있다. 그리고 SMEMBERS명령으로 value들을 가져올 수 있다.
SADD key member [member ...]
SMEMBERS key
SADD와 SMEMBERS 사용 예제다.
> SADD myset "c++"
(integer) 1
> SADD myset "java"
(integer) 1
> SADD myset "ruby"
(integer) 1
> SADD myset "golang"
(integer) 1
> SADD myset "java"
(integer) 0
> SMEMBERS myset
1) "golang"
2) "ruby"
3) "java"
4) "c++"
java를 두번 add 요청을 했지만 두번째 add 요청은 무시된 걸(반환 갓이 0 이다) 알 수 있다. 여기에서 의문점 List와 뭐가 다른가. ? LPUSH로 값을 입력하고 LRANGE 로 값을 읽는 것과 어떤 차이가 있을까 ?
  1. 위 예제로 set은 중복을 허용하지 않는다는 걸 알았다. List는 중복을 허용 한다.
  2. List는 삽입 순서에 따라 정렬이 된다. 한편 set은 정렬되지 않는 value의 모음이다. 순서를 유지하지 않는다.

SET의 사용

Set도 List와 마찬가지로 string을 저장한다는 점에서 유사점이 있다. 하지만 List와는 달리 해시 테이블을 사용해서 모든 문자열을 고유하게 유지한다. Set은 List와 다르게 순서가 없기 때문에 아이템을 POP 하거나 Push 할 수 없다. 대신 SADD와 SREM을 이용해서 아이템을 추가하거나 삭제한다. 또한 SISMEMBER로 찾는 아이템이 있는지 확인 할 수 있고 SMEMBERS로 전체 아이템 목록을 가져올 수 있다.

시간 복잡도(time Complexity)관점에서 살펴보자. List는 내부적으로 링크드 리스트다. 따라서 List의 크기와 상관 없이 처음과 마지막에 아이템을 추가하는 것은 O(1)이 된다. 하지만 목록의 중간에 있는 아이템을 찾는데는 시간이 걸릴 수 있다. 이 작업은 기본적으로 O(n)이다. 반면 SET은 아이템 추가, 삭제, 확인에 O(1)복잡도를 가진다.

만약 자료구조에 임의의 아이템이 있는지를 확인하는 작업이 요구된다면 List가 아닌 Set을 사용하도록하자. 그밖에 Union, Diff, Intersection 같은 연산을 수행 할 수 있는 것도 장점이다. 가장 큰 장점은 정렬된 set을 만들 수 있다는 점이다. 이 내용은 따로 다루도록 하겠다.

아래는 SET 데이터 스트럭처를 위해서 사용 할수 있는 명령들이다.
명령 설명
SADD Set에 아이템을 추가한다.
SMEMBERS Set에 있는 아이템 목록을 가져온다.
SISMEMBER Set에 아이템이 있는지 확인한다.
SREM Set에서 아이템을 삭제한다.
SDIFF 첫 번째 set와 나머지 set의 차이를 반환한다.
SUNION 모든 set의 아이템을 반환한다.
SINTER 모든 set에서 공통된 아이템을 반환한다.

Set을 이용한 태그 검색

온라인 책을 서비스하려고 한다. 태그 기반의 검색&분류 기능을 추가하기로 했다. 책은 하나 이상의 태그를 가질 수 있으며, 사용자는 여러 개의 태그를 조합해서 가장 적합한 책 목록을 확인 할 수 있다. 책 정보는 SET 명령으로 입력하기로 했다.
> SET book:1 'Diving into python'
> SET book:2 'Running Python'
> SET book:3 'Running AWS'
> SET book:4 'Puppet Cookbook'

> SADD tag:python 1 2 4
> SADD tag:programming 1 2
> SADD tag:cloud 3 4

python과 programming 모두에 태깅된 책을 찾아보자.
> SINTER tag:python tag:programming
1) "1"
2) "2"
"Diving into python"과 "Running Python"이 검색됐다.

"python"과 "cloud"에 태깅된 책을 찾아보자.
> SINTER tag:python tag:cloud
1) "4"

Sorted Set

Redis는 Sorted Set을 지원한다. "정렬을 위한 필드를 제공하고 여기에 정렬 값을 설정하는 것으로 아이템을 정렬 할 수 있다"는 점을 제외하면 set과 동일하다. Sorted set에서의 아이템 추가, 삭제, 확인의 시간 복잡도는 O(1)이다. 하나의 set당 최대 2^32 - 1(약 40억)개의 아이템을 저장 할 수 있다.

ZADD 명령으로 아이템을 삽입할 수 있다.
ZADD key [NX|XX] [CH] [INCR] score member [score member ...]
ZRANGE명령으로 아이템을 가져올 수 있다. tag key에 저장된 아이템을 가져와보자.
> ZRANGE tag 0 -1 
1) "programming"
2) "ruby"
3) "python"
4) "aws"
아이템은 score를 기준으로 오름차순으로 정렬된다. withscore 옵션을 이용해서 각 아이템의 score도 출력할 수 있다.
> ZRANGE tag 0 -1 WITHSCORES
1) "programming"
2) "5"
3) "ruby"
4) "8"
5) "python"
6) "12"
7) "aws"
8) "13"
ZREVRANGE명령을 이용하면 내림차순으로 정렬된 아이템을 얻을 수 있다.
> ZREVRANGE tag 0 -1 WITHSCORES
1) "aws"
2) "13"
3) "python"
4) "12"
5) "ruby"
6) "8"
7) "programming"
8) "5"
Sorted Set을 이용해서, 카테고리별 인기 아이템을 서비스 할 수 있을 것이다. 개인화된 유저 추천 서비스를 만든다고 가정해 보자. 아래 그림을 보자.

 추천 서비스

유저 id를 key로 해서 방문한 카테고리이름과 방문횟수를 sorted set 형태로 저장을 한다. 간단하게 INCR을 하는 것으로 유저가 선호하는 카테고리 정보를 저장할 수 있을 것이다. 위 그림에서 3210 유저가 선호하는 카테고리는 "beauty"다. 그리고 각 카테고리 별로 인기있는 제품의 sorted set을 만든다. 위 그림에서 "beauty"카테고리의 인기 상품은 Fragrance와 Skincare다 그러므로 3120 유저에게는 Fragrance와 Skincare 제품을 추천하면 될 것이다. 물론 실제 서비스에서는 유저의 나이, 성별, 세부 제품별로 더 정교한 Set을 만들어야 할 것이다.

소셜 그래프

Set과 Sorted set을 이용해서 친구들간의 연결관계를 나타내는 소셜 그래프를 만들어보자. 아래와 같은 소셜 그래프가 있다고 가정해보자.

 소셜 그래프