RestHighLevelClient를 사용하여 search after 기능 구현하기

web/Spring|2019. 11. 14. 17:55

https://wedul.site/541에서 search after 기능을 사용해서 검색을 하는 이유를 알아봤었다.

그럼 spring boot에서 RestHighLevelClient를 이용해서 search after를 구현을 해보자.

 

1. Mapping

우선 index가 필요한데 간단하게 상품명과 지역 가격정보들을 가지고 있는 wedul_product 인덱스를 만들어 사용한다.

{
    "settings": {
        "index": {
            "analysis": {
                "tokenizer": {
                    "nori_user_dict": {
                        "type": "nori_tokenizer",
                        "decompound_mode": "mixed",
                        "user_dictionary": "analysis/userdict_ko.txt"
                    }
                },
                "analyzer": {
                    "wedul_analyzer": {
                        "tokenizer": "nori_user_dict",
                        "filter": [
                            "synonym"
                        ]
                    }
                },
                "filter": {
                    "synonym": {
                        "type": "synonym",
                        "synonyms_path": "analysis/synonyms.txt"
                    }
                }
            }
        }
    },
    "mappings": {
        "dynamic": "false",
        "properties": {
            "productId": {
                "type": "keyword"
            },
            "place": {
                "type": "text",
                "fields": {
                    "keyword": {
                        "type": "keyword"
                    }
                }
            },
            "message": {
                "type": "text"
            },
            "query": {
                "type": "percolator"
            },
            "name": {
                "type": "text",
                "analyzer": "wedul_analyzer",
                "fields": {
                    "keyword": {
                        "type": "keyword"
                    }
                }
            },
            "price": {
                "type": "integer"
            },
            "updateAt": {
                "type": "date",
                "format": "epoch_second"
            },
            "createAt": {
                "type": "date",
                "format": "epoch_second"
            }
        }
    }
}

값은 적당하게 3개정도 삽입하였다.

저장되어 있는 초기값.

 

2. 라이브러리 

사용에 필요한 라이브러리들을 gradle을 사용해서 추가한다. 

plugins {
    id 'org.springframework.boot' version '2.2.0.RELEASE'
    id 'io.spring.dependency-management' version '1.0.8.RELEASE'
    id 'java'
}

ext {
    set('elasticsearch.version', '7.4.2')
}

group = 'com.wedul'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = '1.8'

repositories {
    mavenCentral()
    maven { url "https://plugins.gradle.org/m2/" }
}

dependencies {
    implementation 'org.springframework.boot:spring-boot-starter-web'
    compileOnly 'org.projectlombok:lombok'
    compile group: 'org.apache.commons', name: 'commons-lang3', version: '3.9'
    compile group: 'com.fasterxml.jackson.core', name: 'jackson-databind', version: '2.10.0'
    annotationProcessor 'org.projectlombok:lombok'
    testCompile group: 'org.mockito', name: 'mockito-all', version:'1.9.5'
    testImplementation 'org.springframework.boot:spring-boot-starter-test'

    // gson
    compile group: 'com.google.code.gson', name: 'gson', version: '2.8.6'

    // elasticsearch
    compile 'org.elasticsearch.client:elasticsearch-rest-high-level-client:7.4.2'
    compile group: 'org.elasticsearch', name: 'elasticsearch', version: '7.4.2'
}

 

 

3.RestHighLevelClient configuration

restHighLevelClient 사용을 위한 Configuration 파일을 만들어주는데 id와 pw는 AppConfig라는 별도 properties를 관리하는 bean에서 받아서 사용하는데 base64로 인코딩되어있어서 이를 decoding후 사용한다. (부족한 코드는 글 맨 아래있는 github 링크 참조)

package com.wedul.study.common.config;

import com.wedul.study.common.util.EncodingUtil;
import lombok.extern.slf4j.Slf4j;
import org.apache.http.HttpHost;
import org.apache.http.auth.AuthScope;
import org.apache.http.auth.UsernamePasswordCredentials;
import org.apache.http.client.CredentialsProvider;
import org.apache.http.impl.client.BasicCredentialsProvider;
import org.elasticsearch.client.RestClient;
import org.elasticsearch.client.RestClientBuilder;
import org.elasticsearch.client.RestHighLevelClient;
import org.springframework.beans.factory.DisposableBean;
import org.springframework.beans.factory.FactoryBean;
import org.springframework.beans.factory.InitializingBean;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.context.annotation.Configuration;

/**
 * study
 *
 * @author wedul
 * @since 2019-11-07
 **/
@Configuration
@Slf4j
public class ElasticsearchClientConfig implements FactoryBean<RestHighLevelClient>, InitializingBean, DisposableBean {

    @Autowired
    AppConfig appConfig;

    private RestHighLevelClient restHighLevelClient;

    @Override
    public RestHighLevelClient getObject() {
        return restHighLevelClient;
    }

    @Override
    public Class<?> getObjectType() {
        return RestHighLevelClient.class;
    }

    @Override
    public void destroy() {
        try {
            if (null != restHighLevelClient) {
                restHighLevelClient.close();
            }
        } catch (Exception e) {
            log.error("Error closing ElasticSearch client: ", e);
        }
    }

    @Override
    public boolean isSingleton() {
        return false;
    }

    @Override
    public void afterPropertiesSet() {
        restHighLevelClient = buildClient();
    }

    private RestHighLevelClient buildClient() {
        try {
            String id = EncodingUtil.decodingBase64(appConfig.getElasticsearchConfig().getId());
            String pw = EncodingUtil.decodingBase64(appConfig.getElasticsearchConfig().getPw());

            // 계정 설정
            final CredentialsProvider credentialsProvider = new BasicCredentialsProvider();
            credentialsProvider.setCredentials(AuthScope.ANY,
                new UsernamePasswordCredentials(id, pw));

            // client 설정
            RestClientBuilder builder = RestClient.builder(
                new HttpHost(appConfig.getElasticsearchConfig().getIp(),
                    appConfig.getElasticsearchConfig().getPort(), "http"))
                .setHttpClientConfigCallback(httpClientBuilder -> httpClientBuilder.setDefaultCredentialsProvider(credentialsProvider));

            restHighLevelClient = new RestHighLevelClient(builder);
        } catch (Exception e) {
            log.error(e.getMessage());
        }
        return restHighLevelClient;
    }

}

 

 

4. Handler 추가

자주 사용되는 Elasticsearch 문법을 처리하기 위해서 만들어 놓은 ElasticsearchHandler에 search after에 사용 될 메소드를 추가한다. search after는 sort 필드가 없으면 사용이 불가능 하기 때문에 sort 필드가 없는 경우 에러를 전달한다.

public static SearchSourceBuilder searchAfter(Map<String, SortOrder> sortFields, QueryBuilder query, Object[] searchAfter, int size) {
    return searchAfterBuilder(sortFields, query, searchAfter,  size);
}

public static SearchSourceBuilder searchAfter(Map<String, SortOrder> sortFields, QueryBuilder query, Object[] searchAfter) {
    return searchAfterBuilder(sortFields, query, searchAfter, 20);
}

private static SearchSourceBuilder searchAfterBuilder(Map<String, SortOrder> sortFields, QueryBuilder query, Object[] searchAfter, int size) {
    SearchSourceBuilder builder = new SearchSourceBuilder();

    if (CollectionUtils.isEmpty(sortFields)) {
        throw new InternalServerException("잘못된 필드 요청입니다.");
    }

    sortFields.forEach((field, sort) -> {
        builder.sort(field, sort);
    });
    builder.size(size);
    builder.query(query);

    if (ArrayUtils.isNotEmpty(searchAfter)) {
        builder.searchAfter(searchAfter);
    }

    return builder;
}

 

 

5. 기능 구현

위의 기능들을 이용해서 실제로 구현해보자. productService와 productRepository 클래스를 통해서 구현하였다. 자세한 설명없이 간단하기 때문에 소스를 보면 알 수 있다. 

 

우선 최종 결과물로 사용될 클래스는 ElasticResult인데 다음과 같이 현재 요청이 마지막인지 표시하는 isLast와 다음 요청을 위해 보내줘야 하는 cursor값과 결과값 전체 total과 결과 리스트 list 필드가 존재한다.

@Builder
@Data
public class ElasticResult<T extends ElasticsearchDto> {

    private boolean isLast;
    private long total;
    private List<T> list;
    private Object[] cursor;

}

 

그 다음 service로직을 통해 결과를 얻어서 위 ElasticResult에 결과를 담아보자. products 메서드는 요청을 받아서 elasticsearch에 실제 조작요청을 하는 productRepository에 동작을 요청하고 값을 받아서 처리하는 메서드이다. 그리고 extractProductList는 결과값에서 ProductDto 값을 뽑아내는 메서드이다.

public ElasticResult<ProductDto> products(String index, Object[] searchAfter, int size) throws IOException {
    SearchResponse searchResponse = productRepository.products(index, searchAfter, size);
    SearchHits searchHits = searchResponse.getHits();
    int hitCnt = searchHits.getHits().length;
    boolean isLast = 0 == hitCnt || size > hitCnt;

    return ElasticResult.<ProductDto>builder()
        .cursor(isLast ? null : searchHits.getHits()[hitCnt - 1].getSortValues())
        .isLast(isLast)
        .list(extractProductList(searchHits))
        .total(searchHits.getTotalHits().value)
        .build();
}

private List<ProductDto> extractProductList(SearchHits searchHits) {
    List<ProductDto> productList = new ArrayList<>();

    searchHits.forEach(hit -> {
        Map<String, Object> result = hit.getSourceAsMap();

        productList.add(ProductDto.builder()
            .name(String.valueOf(result.get("name")))
            .productId(String.valueOf(result.get("productId")))
            .place(String.valueOf(result.get("place")))
            .price(Integer.valueOf(result.get("price").toString()))
            .updateAt(Long.valueOf(result.get("updateAt").toString()))
            .createAt(Long.valueOf(result.get("createAt").toString())).build());
    });

    return productList;
}

 

그리고 마지막으로 es에 직접적으로 콜을 하는 productRepository 이다. 여기서 정렬 키워드는 name과 place를 사용한다.

public SearchResponse products(String index, Object[] searchAfter, int size) throws IOException {
    SearchRequest searchRequest = new SearchRequest(index);
    Map<String, SortOrder> sorts = new HashMap<String, SortOrder>() {
        {
            put("name.keyword", SortOrder.DESC);
            put("place.keyword", SortOrder.DESC);
        }
    };

    SearchSourceBuilder searchSourceBuilder = ElasticsearchHandler.searchAfter(sorts, QueryBuilders.matchAllQuery(), searchAfter, size);
    searchRequest.source(searchSourceBuilder);
    return restHighLevelClient.search(searchRequest, RequestOptions.DEFAULT);
}

 

 

6. 테스트

그럼 위에 내용이 잘 구현되었는지 테스트를 해보자. 총 3개의 데이터가 있는데 이 데이터를 1개씩 search after를 통해서 값을 받아서 저장하고 한번에 출력하도록 해보자.

@Test
@DisplayName("search after")
public void searchAfter() throws IOException {
    ElasticResult<ProductDto> result = productService.products(PRODUCT_INDEX, new Object[]{}, 1);
    List<ProductDto> productDtos = new ArrayList<>();

    while(result != null && !result.isLast()) {
        productDtos.addAll(result.getList());
        result = productService.products(PRODUCT_INDEX, result.getCursor(), 1);
    }
    productDtos.addAll(result.getList());

    productDtos.forEach(productDto -> {
        System.out.println("이름 : " + productDto.getName());
        System.out.println("장소 : " + productDto.getPlace());
    });
}

결과는 정상적으로 3가지 모두 잘 출력되는 걸 알 수있다.

 

우선 기능 구현을 해보기 위해서 진행하였는데 더 다듬어야 할 것같다.

자세한 소스는 github참조

댓글()

SELECT-LIST 컬럼 가공시 정렬연산 수행 확인 및 개선방법

인덱스가 Id,  ch_date, ch_order 순으로 생성되어 있을 경우 MIN 값을 구해도 별도의 정렬연산을 수행하지 않는다. 수직적 탐색을 통해서 가장 왼쪽지점에서 보는 최소 값이 바로 구하고자 하는 값이기 때문이다.


1
SELECT MIN(ch_date) FROM scott.SORT_TEST WHERE ID = ‘C’;
cs

MAX의 경우도 마찬가지이다. MIN과 다른 점은 왼쪽에서 찾는게 아니라 가장 오른쪽에 있는 데이터를 찾는다는 점이다.

1
SELECT MAX(ch_date) FROM scott.SORT_TEST WHERE ID = ‘C’;
cs

그래서 두 개의 실행계획을 살펴보면 인덱스 리프 블록의 왼쪽(MIN) 또는 오른쪽 (MAX)에서 레코드 하나(FIRST ROW)만 읽고 멈춘다.

1
SELECT MAX(TO_DATE(ch_date)) FROM scott.SORT_TEST WHERE ID = 'C';
cs

이 경우에는 MAX일지라도 ch_date가 내부적으로 변경을 한 뒤에 최대값을 찾기 때문에 정렬을 한뒤에 진행이 가능하다.


하지만 이걸 반대로 바꿔서 진행하면 최대 값을 찾고 그 값을 TO_DATE()로 변경하기 때문에 큰 문제 없이 FIRST 항목만 찾게된다.

출처 : 친절한 SQL 튜닝

댓글()
  1. 2019.03.30 14:54 댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다

인덱스를 이용한 sort 연산 생략

인덱스 Range Scan이 가능하려면 가공하려는 컬럼의 데이터가 정렬되어 있어야 가능하다. 인덱스는 그렇기 때문에 정렬이 되어있다. 그래서 인덱스를 사용하는 이유가 있다. 

테이블 생성

1
2
3
4
create table sort_test (
id char,
ch_date date,
ch_order varchar(10));
cs


제약조건 추가

1
ALTER TABLE SCOTT.SORT_TEST ADD CONSTRAINT ODER_PRIMARY PRIMARY KEY (ID,CH_DATE,CH_ORDER);
cs


데이터


실행계획

PK를 기준으로 알아서 정렬이 되어있다. ( ID -> CH_DATE -> CH_ORDER 순서대로)


만약 별도로 order by를 sql에 지정한다고 해도 옵티마이저는 sort order by를 진행하지 않는다. 왜냐면 이미 pk 인덱스 생성시에 결과 집합에 대한 order by가 된 상태로 진행되기 때문이다.


만약 이렇게 정렬 연산을 생략가능하게 구성되어 있지 않다면 SORT ORDER BY가 추가 될 것이다.

인덱스에서 값을 찾을 때 인덱스 리프 블록에서 각 블록들은 더블 링크드 리스트로 연결되어있다. ASC 정렬인 경우에는 왼쪽에서 오른쪽 DESC인 경우에는 오른쪽에서 왼쪽으로 진행된다. 

각 DESC (내림차순)으로 사용하도록 쿼리를 작성하고 실행계획을 확인해도 별도의 SORT 작업은 진행하지 않는것을 알 수있다.

ORDER BY를 이용한 정렬 컬럼 가공
인덱스에서 사용되는 컬럼을 가공하면 INDEX가 타지 않는다고 알고있다. 근데 앞에서 살펴본 부분은 where조건에서 컬럼을 가공한 경우였다.

이번에는 인덱스에서 선언한 구조와 반대되는 쿼리를 짜보자. 위의 쿼리에서 PK 인덱스는 ID,CH_DATE,CH_ORDER 순서로 인덱스를 만들었다. 그렇기 때문에 ID -> CH_DATE -> CH_ORDER 순서로 정렬을 하면서 데이터를 찾는다.

하지만 다음과 같은 쿼리는 어떨까?

생성된 인덱스와 다른 기준으로 CH_DATE -> CH_ORDER 으로 정렬을 진행하였기 때문에 다시 정렬연산이 필요로 하게된다.


정리하면 인덱스 생성시에 sort가 되기 때문에 order by를 하여도 별도의 sort 연산을 하지 않는다.


댓글()

Deque를 통해 버킷정렬(Bucket Sort)을 해보자.

IT 지식/자료구조|2018. 6. 2. 23:55

저번시간에 만들었던 Deque를 사용하여 버킷정렬을 연습해보기로 했다.



우선 버킷정렬이 무엇인지 알아보자.



버킷정렬(Bucket Sort) 이란??


n개의 데이터를 정렬할 때 같은 크기의 간격을 갖는 n개의 버켓에 데이터를 분배한다. 입력 데이터가 균일하게 분포되었다면 각 버켓에는 1개의 데이터가 있게 되지만, 균일하게 분포되지 않으면 다수의 데이터가 버켓에 들어 갈 수 있으며 각 버켓의 데이터는 정렬하여 저장한다. n개의 모든 데이터를 버켓에 분배하였다면 버켓 번호 순으로 스캔하여 출력하면 정렬된 데이터를 얻게 된다.


[예제] 최대 2자리를 갖는 정수 (0부터 99까지의 정수) 10개를 버켓 정렬한다고 하자. 각 버켓은 같은 크기의 간격 (0-9, 10-19, 20-29,, 90-99)을 갖는 10개의 버켓을 만들어 데이터를 해당 버켓에 분배한다. 각 버켓에 분배된 데이터는 정렬한다. 다음 버켓 번호 순으로 데이터를 모으면 정렬된 데이터가 된다. 다음은 배열에 10개의 정수 [22, 43, 27, 31, 83, 7, 92, 69, 36, 25]를 버켓 정렬한 것을 도식으로 표현하였다. 





그럼 이 버킷정렬을 deque를 통해 어떤 방식으로 이루어질지 알아보자.


우선 정렬이 되지 않은 데이터를 담고 있는 Deque를 만든다. 그리고 그 데이터의 개수만큼의 Deque 배열을 만든다. 그리고 정렬되지 않은 데이터를 담고 있는 Deque에서 하나씩 데이터를 꺼낸다. 그리고 그 데이터에서 배열 인덱스를 구하고 그 인덱스 위치에 있는 Deque에 데이터를 삽입한다.


이때 데이터를 삽입할 때 Deque에 정렬해서 데이터를 삽입해야 나중에 데이터를 정렬되어서 가져올 수 있다. 인덱스에 위치한 Deque가 데이터가 없는경우 addFirstItem메서드를 통해서 데이터를 집어넣는다. 만약 데이터가 있다면 기존에 데이터의 front에 있는 데이터와 비교하여 순서에 맞게 삽입한다. 이때 순서를 찾기위해서 임시 Deque를 사용하는데 이부분은 단순하여 코드를 보면 쉽게 이해할 수 있다.


이렇게 정렬되지 않은 Deque의 데이터를 버킷에 다 집어 넣고 나서 버킷을 순회하면서 정렬된 데이터를 기존 Deque에 삽입한다.


그럼 정렬이 끝난다.


완성된 코드와 실행화면은 아래와 같다.


Deque에서 사용할 인터페이스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package practice3;
 
public interface Deque<T> {
    public void addFirst(T item);
 
    public void addLast(T item);
 
    public T removeFirst();
 
    public T removeLast();
 
    public T peekFirst();
 
    public T peekLast();
 
    public boolean isEmpty();
 
    public int size();
 
    public String toString();
 
}
 
cs


기존에 만든 Deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
package practice3;
 
import java.util.ArrayList;
import java.util.List;
 
public class LinkedDeque<T> implements Deque<T>{
    private static class Node<T> {
        private T item;
        private Node<T> next;
        private Node<T> prev;
 
        private Node() {
            next = null;
            prev = null;
        }
 
        private Node(T item) {
            this.item = item;
            next = null;
            prev = null;
        }
    }
 
    private Node<T> front;
    private Node<T> rear;
    private int size;
 
    public LinkedDeque() {
        front = null;
        rear = null;
        size = 0;
    }
 
    @Override
    public void addLast(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            rear.next = node;
            node.prev = rear;
            rear = node;
            size++;
        }
    }
 
    @Override
    public void addFirst(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            front.prev = node;
            node.next = front;
            front = node;
            size++;
        }
    }
    
    private void addFirstItem(Node<T> item) {
        front = item;
        rear = item;
        size = 1;
    }
 
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
 
    @Override
    public T removeFirst() {
        T item = null;
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = front.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = front.item;
            front = front.next;
            front.prev = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T removeLast() {
        T item = null;
 
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = rear.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = rear.item;
            rear = rear.prev;
            rear.next = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T peekFirst() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return front.item;
    }
 
    @Override
    public T peekLast() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return rear.item;
    }
 
    @Override
    public int size() { return size; }
 
    @Override
    public String toString() {
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = front;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.next;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
    public String reverse() { // 역순으로 출력
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = rear;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.prev;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
}
 
cs




Deque를 정렬하는 Bucket Sort 클래스 (이번 문제의 핵심 클래스)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package practice3;
 
public class BucketSort {
    
    public BucketSort() {}
 
    // 들어온 Deque에 데이터를 버킷정렬을 이용하여 정렬 
    public void bucketSort(LinkedDeque<Integer> data) {
        int bucketIdx;
        int value;
        int size = data.size();
        LinkedDeque<Integer>[] bucketArray = new LinkedDeque[data.size()];
        
        // 들어온 덱에 있는 데이터를 버켓으로 정렬 
        while (!data.isEmpty()) {
            value = data.removeFirst();
            
            bucketIdx = (int) (size * (value / Math.pow(10, getNumCnt(value))));
            if (bucketArray[bucketIdx] == null || bucketArray[bucketIdx].isEmpty()) {
                bucketArray[bucketIdx] = new LinkedDeque<Integer>();
                bucketArray[bucketIdx].addFirst(value);
            } else {
                LinkedDeque<Integer> temp = new LinkedDeque<>();
                while (bucketArray[bucketIdx] != null && !bucketArray[bucketIdx].isEmpty() && bucketArray[bucketIdx].peekFirst() < value) {
                    temp.addFirst(bucketArray[bucketIdx].removeFirst());
                }
                bucketArray[bucketIdx].addFirst(value);
                
                while(!temp.isEmpty()) {
                    bucketArray[bucketIdx].addFirst(temp.removeFirst());
                }
            }
        }
        
        // 버켓에 정렬된 데이터를 다시 덱으로 옮기는 작업 
        for (int i = 0; i < size; i++) {
            while (bucketArray[i] != null && !bucketArray[i].isEmpty()) {
                data.addLast(bucketArray[i].removeFirst());
            }
        }
    }
    
    /**
     * 자리수를 구하는 메소드 
     * 
     * @param value
     * @return
     */
    private int getNumCnt(int value) {
        return (int) Math.log10(value) + 1 ;
    }
}
 
cs




각 Deque의 기능을 호출하는 메인 클래스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package practice3;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        System.out.println("Enter a command: af(addFirst), al(addLast),\n"
                + "rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),\n" + "p(rint), r(verse), or q(uit)");
        System.out.print("> ");
 
        Scanner input = new Scanner(System.in);
        String command = input.next();
        LinkedDeque<Integer> deque = new LinkedDeque<Integer>();
        BucketSort bSort = new BucketSort();
        int item;
 
        while (!command.equals("q")) {
            if (command.equals("af")) {
                item = input.nextInt();
                deque.addFirst(item);
            } else if (command.equals("al")) {
                item = input.nextInt();
                deque.addLast(item);
            } else if (command.equals("rf"))
                deque.removeFirst();
            else if (command.equals("rl"))
                deque.removeLast();
            else if (command.equals("s"))
                System.out.println("size: " + deque.size());
            else if (command.equals("pf"))
                System.out.println("Front of the deque: " + deque.peekFirst());
            else if (command.equals("pl"))
                System.out.println("Rear of the deque: " + deque.peekLast());
            else if (command.equals("r"))
                System.out.println(deque.reverse());
            else if (command.equals("p"))
                System.out.println(deque);
            else if (command.equals("bsort"))
                bSort.bucketSort(deque);
            System.out.print("> ");
            command = input.next();
        }
        System.out.println("Commands Terminated.");
        input.close();
    }
}
 
cs





실행결과

Enter a command: af(addFirst), al(addLast),

rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),

p(rint), r(verse), or q(uit)

> af 45

af 18

af 35

af 43

af 47

af 39

af 64

af 11

af 15

af 90> > > > > > > > > 

> p

90,15,11,64,39,47,43,35,18,45

> bsort

> p

11,15,18,35,39,43,45,47,64,90

> 

댓글()
  1. Favicon of http://tvple.me/movie/ BlogIcon 영화다시보기 2020.06.16 11:56 댓글주소  수정/삭제  댓글쓰기

    잘 보고 갑니다~~

정렬알고리즘 - 버블정렬

JAVA/알고리즘|2018. 5. 28. 22:46
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i = money.length; i>0; i--){
 
    for(int j=0;j<i-1;j++){
 
     if(money[j]>money[j+1]){
 
      temp=money[j];
 
      money[j]=money[j+1];
 
      money[j+1]=temp;
 
     }
 
    }
 
   }
cs


댓글()

정렬알고리즘 - 삽입정렬

JAVA/알고리즘|2018. 5. 28. 22:45
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
for(int i=0;i<money.length;i++){
 
    for(int j=0;j<=i;j++)
 
    {
 
     if(money[i]<money[j]){
 
      temp=money[i];
 
      for(int k=i;k>j;k--)
 
      {
 
       money[k] = money[k-1]; 
 
      }
 
      money[j]=temp;
 
      break;
 
     }
 
    }
 
   }
cs


댓글()

정렬알고리즘 - 선택정렬

JAVA/알고리즘|2018. 5. 28. 22:44
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
for(int i = 0; i<money.length ;i++){
 
    min = i;
 
    for(int j=i;j<money.length;j++){
 
     if(money[j]<money[min])
 
      min=j;
 
    }
 
    temp=money[i];
 
    money[i] = money[min];
 
    money[min]=temp;
 
   }
 
 
 
 
 
 
 
여기서 money.length는 정렬하고자하는 배열의 키기임
 
money는 정렬하고자하는 배열의 이름을 칭함
cs


'JAVA > 알고리즘' 카테고리의 다른 글

정렬알고리즘 - 버블정렬  (0) 2018.05.28
정렬알고리즘 - 삽입정렬  (0) 2018.05.28
정렬알고리즘 - 선택정렬  (0) 2018.05.28
10진수 2진수 변환  (0) 2018.05.28
더블링크드 리스트 구현하기  (0) 2018.05.28
백준 1924 - 요일 맞추기  (0) 2018.05.28

댓글()