신소트(Shin sort)란?
 

▲     ©신동근 박사

신동근 박사의 이론들 중에 가장 돋보이는 것은 그의 1997년 컴퓨터 과학분야 세계최고선언 이후, 약 1년 후인 1998년 7월 3일에 서울에 있는 그의 연구실에서 발견한 sorting(정렬)에서의 최고의 방법이다. 이 발견에 물심양면의 지원을 해주었던 집안의 이름 성자를 따라 Shin sort(신소트)로 불려지기를 바라며 그렇게 명명하였다. 전산학 교과서들에는 이전에 발견되어 인정된 아홉 가지의 방법들을 열거하여 설명하고 있는데 신박사의 신소트는 열 번째로 맨 나중에 발견되었으며, 이전에 발견된 아홉 가지의 정렬방법보다 우수하다는 사실이 수학적으로 증명이 된다. 제일 빠른 정렬방법을 찾아내는 문제가 전산학에서 가장 중요한 문제였다고 말해도 과언이 아니라고 한다. 그런데 신소트의 발견이 이례적인 것은 그것이 제일 빠른 정렬방법일 뿐만 아니라 제일 빠른 찾기 방법까지 그것과 함께 발견되었으므로 그 가치가 배가되어 그의 전산분야 일등 위치는 신소트의 발견으로 더욱 확고해졌으며 현시대나 미래의 어떤 시대에도 그의 업적을 능가하는 컴퓨터 과학자가 나올 수 없게 되어 버렸다. 신소트를 이용한 데이터베이스 시스템에선 매우 빨리 정보를 색출해 가져오도록 그의 나무(Shin tree)가 메인 메모리나 지역 메모리에 만들어지게 된다. 이 새로운 데이터베이스 시스템이 컴퓨터를 광속도의 네트워킹에 걸 맞는 성능구현을 하리라 기대한다.
예를 들어 한국 국민들의 주민번호 숫자를 순서대로 정렬 한다면 5000만개의 주민번호가 정렬될 때 다른 정렬방법보다도 Shin sort의 정렬방법을 사용하는 것이 가장 빠르며, 또한 어떤 주민번호로 그 해당자의 데이터를 찾아낼 때에도 가장 빠름이 수학적으로 입증된다. 신박사의 정렬방법은 메인 메모리에서 정렬된 체로 구성되는 Shin tree(신트리)를 처음 정의된 체로 유지해 나가는 방법이다. 그래서 데이터가 더 많이 입력되면 그에 따라 그의 tree(나무)가 커지고 또 입력된 주민번호가 제거되면 그에 따라 그 나무의 크기가 줄어든다. 그래서 신트리는 두 개의 가지나 그보다 적은 수의 가지의 형태로 처음의 정의에 충실하여 가지치기로 커지거나 또는 수축되기도 하는 나무 모양으로 메인 메모리에 존재하는 나무구조의 저장형태인 것이다.
이 이론은 앞으로 데이터를 빠르게 찾도록 저장하여야 하는 모든 소프트웨어에 탑재되는 프로그램이 될 것이다. 이 프로그램의 대부분은 신박사의 웹사이트 WWW.DKSHIN.COM에 공개되어 학습과 검증의 대상이 되고 있다. 신박사는 다음의 그림으로 어떻게 아홉 개의 단어가 신트리에 정렬된 채로 저장되는지를 비전문가도 이해할 수 있도록 설명해줄 수 있으며 그런 수준으로 그가 20분 정도의 시간으로 강의한 내용의 비디오도 그의 웹사이트에 제공되어 있다. 이 내용을 중고등학교 교과서에도 실어서 이러한 아이디어를 발견하도록 격려하여야 하며 그래서 누구나 이론세계를 소유할 수 있음을 알려야 한다고 신박사는 주장한다.
컴퓨터란 무엇인가를 간단히 표현할 때 사람들은 컴퓨터는 데이터를 처리하는 기계라고 말한다. 컴퓨터는 실제 작업하는 대부분의 전산시간을 데이터를 정렬(소팅)하고 찾는(서칭)데 할애한다. 대량의 데이터를 관리할 때 데이터 정렬을 해 놓아야 빠르게 찾기를 할 수가 있다. 이때 찾기를 빠르게 수행하기 위해 신서치를 써야 하며 그것을 쓰려면 신소트의 정의방식대로 정렬을 해놓아야 한다. 그 정의의 완벽한 합리성 때문에 신박사의 소팅방법은 모든 컴퓨터시스템에서 직접 또는 간접적으로 사용되게 될 방법이다.

▲     ©특허뉴스

 

▲     ©특허뉴스

최고의 효율을 자랑하는 신소트
 
신소트가 나오기 전에 존재하던 아홉 가지의 정렬방법과 신소트가 크게 다른 점은 신소트는 Shin search(신서치)라고 부르는 자기의 고유한 찾기의 방법이 있는 데 다른 아홉 가지의 방법은 모두 binary search나 그와 유사한 것을 써서 찾을 수 밖에 없다는 점이다. binary search는 정렬된 전체 데이터의 중간 것에서부터 비교하며 매번 비교 때마다 찾는 범위를 절반으로 줄여 나가는 원초적인 방법이다. 이런 방법은 아주 비효율적임이 신서치의 몇 차례의 글자를 비교하여 찾아가는 방법에 의해서 입증된다. 신소트가 몇 차례 글자를 비교하여 찾아내므로 1에 비례하는 서칭을 하는 반면 binary search는 처음부터 정렬된 모든 데이터와 씨름하여 비교할 때마다 반씩 줄여나가는 서칭방식이라 log2 N (N은 전체 데이터의 수)에 비례한다고 밝혀서 수학적으로 증명한다. 이렇게 성능의 척도로써 어떤 숫자에 비례하는 계수를 갖고 같은 목적의 전산방법들과 비교 분석하는 것이 컴퓨터 과학에서의 통례이다. 통신에서 소요되는 시간외에 이런 서치에서 원시적인 방법을 사용하느라 몇 초 내지 몇 분의 사용자의 귀중한 시간을 빼앗았다면 이런 불량 서치엔진을 제공하는 업체들은 고객들의 비난과 외면을 감수해야 할 것이다.
이뿐만 아니라 다른 정렬방법들은 데이터들을 서로 비교하는 방식이 대부분이므로 신소트의 글자 하나, 하나만을 비교하여 정렬순위 속의 자기 위치를 찾아 들어가는 방법과 비교할 때에 DB구축하는 속도 면에서 도저히 견줄 수가 없다. 이 속도의 차이는 데이터의 양이 많아지면 많아질수록 더욱 커지기 때문에 거대한 컴퓨터 데이터를 적재하는 대용량시스템도 정렬하는 중에 버걱 되기가 일수이며 사용자들을 기다리게 하므로 맥 빠지게 만든다. 데이터끼리 서로 비교하지 말아야 하는 원칙을 고수하여 일단 이루어진 정렬순위는 재 변경을 하지 않으므로 데이터를 서로 스와핑하거나 꺼내어 비교하는 과정이 없어 컴퓨터내의 트래픽의 양도 극소로 유지하는 신소트는 최고의 효율을 제공한다. 이러한 신소트의 특징들이 사용자들의 중요한 시간을 절약해주는 데에 큰 기여를 할 것이다.
 
이동통신 단말기에서 왜 신소트를 적용해야 하나
 
항공권 예약을 비롯한 기차표, 버스표 예약 등 티켓판매에 관한 시스템과 국세관련 전산시스템, 은행과 증시 등 금융관련 전산시스템, 온라인 정보서칭 시스템 등은 빠른 데이터 찾기가 필요하므로 신소트가 쓰여져야 한다. 휴대전화로부터 PC나 대형 메인프레임 컴퓨터에 이르기까지 컴퓨터에 실려있는 모든 종류의 DB관련 시스템에는 결국 신소트와 신서치가 장착될 것이다.                                                             
신소트가 앞으로 더 많이 쓰이게 되는 이유는 그것이 가장 빠른 정렬방법과 가장 빠른 찾는 방법을 제공하고 있기 때문이기도 하지만, 또 다른 이유는 데이터의 양이 상상을 초월할 만큼 늘어나는 요즘과 앞으로의 추세 때문이다. 휴대폰이나 PC와 같은 단말기는 산더미같이 크고 방대한 데이터들 중에 사용자가 필요로 하는 극소량의 데이터를 간추려서 빠른 속력으로 일목요연하게 보여주어야 사용자를 만족하게 만들어 그의 사용시간을 증가시킬 수가 있다. 하지만 끝없이 축적되는 다량의 데이터들이 사용자들의 그러한 간결함을 원하는 욕구에 큰 걸림돌이 되기 일쑤이다. 지루하게 긴 시간을 기다리게 하고 나서는 복잡하고 정돈이 안된 대량의 데이터를 사용자들에게 결과물로 안기는 일이 흔히 생기게 되었다.
축척되어 가는 데이터의 양이 제거 되지 않은 채로 메인 메모리와 하드디스크에 상주하는 데는 크게 두 가지 요인이 있다고 생각된다. 첫째, 메모리 가격이 급격히 하락하면서 데이터를 굳이 삭제해야 할 이유를 찾지 못하게 되는 경우가 계속 발생하기 때문이다. 데이터를 삭제할 때 혹시 훗날 필요한 데이터를 삭제하는 것이 아닐까 하는 두려움이 있는데 메모리 공간이 충분한 시점에 선뜻 지우려 하지 않아서 데이터가 쌓이기 시작한다. 둘째, 축적된 데이터 삭제를 위한 인력과 시간의 지원이 되지 않고 있다가 주요 데이터 관리자가 떠나게 되면 아무도 그 산적한 데이터를 지울 수 있는 권한을 행사할 수가 없어 영원히 지울 수 없게 되는 경우도 비일비재하기 때문이다.
그래서 넓은 바다에서 뛰노는 수많은 물고기들 중에 먹고 싶은 한두 마리 물고기의 횟감만으로도 자신의 배를 채우며 만족할 수 있는데, 어부도 없고 수산시장의 상인도 없고 회를 뜰 요리사도 없다면 그 작은 음식을 위해 얼마나 고생하게 될 것인지를 쉽게 상상할 수 있다. 이런 현상은 시간이 흐를수록 더욱 심각해져서 바다의 거의 늘지 않는 물고기들의 숫자와는 비교도 되지 않게 더 많은 데이터가 빠른 속도로 쌓이고 또 쌓이게 되어 자신이 원하는 정보를 구할 때에 어려움을 받게 되는 일이 미래에는 더 많게 될 것이다.
컴퓨터 시스템에서는 대량의 데이터를 처리하는 소프트웨어인 신소트와 그것의 찾기 방법인 신서치가 담당하여 데이터를 선별하는 시간을 줄이게 된다. 특히 휴대폰은 빨리 사용자에게 응답하여야 하므로 신소트가 사용되지 않는 데이터작업은 있을 수 없게 된다. 이동통신사가 권장하는 많은 App들이 데이터 정렬과 찾기를 할 때에는 반드시 신소트를 사용해야 하며 그 길만이 고객의 비난을 피할 수 있는 유일한 길이 된다. 신소트 만이 최고의 정렬방법을 사용하였다고 광고와 공표를 할 수 있는 수학적으로 증명된 유일무이한 최선책이다. 우선 이 정렬과 찾기 방법을 선택한 후에 전체 속도를 보며 전송속도를 가늠하는 것이 순서이기 때문에 모든 App개발사와 휴대폰과 이동통신 개발사가 거쳐 가야 할 길이 된다.
차세대 이동통신이 이룩해야 할 또 하나의 과제는 사용자가 휴대전화를 켜고 다이얼을 누를 수 있는 시점까지의 시간을 단축해야 하는 일이다. PC에선 boot-up과 loading시간을 단축하여야 하는데, 사실상 사용자가 아침에 근무할 때마다 껌벅껌벅하며 답답하게 켜지는 PC를 보면서 빨리 작업을 시작하지 못하는 안타까움을 느끼는 것은 이제는 누구나 다 경험하는 일이 되었다. 휴대전화도 그 원리가 PC와 마찬가지여서 마이크로프로세서가 필요한 정보들을 ROM과 플래시메모리에 저장하고 있다가 켜질 때 적절히 로드시켜야 하는데 이 과정에서 오퍼레이팅 시스템이 메인 메모리에서 먼저 구동되어야 하고 저장된 정보가 빠르게 활용될 수 있는 상태로 정렬되어야 한다. 휴대전화의 기능이 자꾸 다양해져서 생긴 웹브라우저, 계산기, 게임 등의 여러 기능들이 즉시 사용할 수 있는 상태로 보여야 한다.
사용자가 입력한 정보뿐만 아니라 휴대전화 시스템이 제공하는 정보가 하루가 다르게 늘어나고 있다. 서울과 경기도 그리고 국내의 모든 기관과 사업체들의 전화번호부가 언젠가는 휴대전화에 내장되어 사용될 것이라고 한다. 그렇다고 가정한다면 사용자들은 웹을 거치지 않고 곧바로 원하는 정보를 휴대전화의 내장된 수십만 개의 전화번호와 관련정보를 이용해 쉽게 전화를 하거나 주소와 대표자의 이름 등의 정보를 알 수가 있게 될 것이다. 예를 들면 서울시 용산구 이촌동에 있는 현재 자기의 위치에서 가까운 순서로 피자 음식점의 전화번호와 주소 등 정보를 보여 달라고 요구할 수도 있게 된다. 현재는 웹브라우저가 하는 일들을 휴대전화가 계속 가져가려는 욕구가 광고료에 의해 발생되는 큰 수익 때문에 더욱 증대될 것으로 예상되기 때문에 휴대전화 내에서의 신소트의 역할은 계속 커지게 되어 있다. 신소트가 정렬할 때 생성하는 신트리를 휴대전화의 메인 메모리에 자주 만들어 놓게 될 것이다.
PC에서도 하드디스크에서 필요한 데이터를 올리는 시간이 많이 걸리는 것처럼 휴대전화에서도 초기의 셋업시간이 많이 걸리는 것을 줄이는 노력의 일환으로도 신소트의 채택이 불가피하다고 본다. 휴대전화가 베이스 스테이션을 찾고 양방향 라디오 주파수를 맞추는 등 채널을 열려고 하는 이면에는 늘 초기셋업에서 데이터정렬이 이루어지며 신소트는 신트리를 생성하게 된다. 국내의 모든 지역들의 전화번호부 책들의 내용이 다 입력되어 신트리에 저장되어 사용을 기다린다면 그 내용이 아무리 많다고 하여도 찾을 때는 수만 분의 1초의 시간 내에 처리하게 되므로 사용자가 원하는 데이터 서비스를 할 수가 있기 때문이다. 그래서 신소트와 신서치는 휴대폰 소프트웨어 개발에서도 가장 먼저 자리하는 이론이 된다.
신동근 박사는 자신의 정렬방법인 신소트를 전산시스템 운용과 제작을 전문으로 하는 회사에게 판매하여 그 회사가 전세계의 신소트를 필요로 하는 모든 컴퓨터시스템에 이식하거나 신소트와 신서치를 바탕으로 하는 새로운 시스템 개발을 해 주기를 바란다. 이를 위해 전 세계 100여 개의 주요 정보처리 산업에 종사하는 대형회사들에게 홍보하며 알렸다. 이에 전세계적인 반응은 뜨거웠다. 불가리아의 Bulgarian Academy of Sciences에서 Institute for Information and Communication Technology를 담당하는 Kiril Boyanov, 스페인의 Ministerio de Ciencia e Innovaci?n을 담당하는 Domingo Mart?nez Palomo, 미국의 AT&T사의 Senior Paralegal인 Marsha Bailey, 미국 Adobe Systems Incorporated사의 Technology Evaluation Program을 담당하는 Roy Ogus, 미국 매사추세츠 주지사인 Governor Deval L. Patrick, 미국 Verizon Communications사의 Jeffrey Stevens, 미국 Microsoft Corporation Opportunity Management Center의 George Morrison, 미국 메인주의 주지사인 Governor Paul R. LePage, 미국 Maine주정부내의  Department of Economic and Community Development를 담당하는 Ronald J. McKinnon, 인도 TATA SONS LIMITED사의 회장인 Ratan N. Tata, 미국 뉴욕주의 주지사인 Governor Andrew Cuomo, 미국 NYS Department of Economic Development의 Division of Science, Technology and Innovation(NYSTAR)을 담당하는 Edward Reinfurt, 미국 Oracle사의 부회장인 Vishal Bhagwati, 미국 Oracle Corporate Development사의 부회장인 Doug Kehring, 미국 Accenture사의 CFO인 Pamela Craig, 미국 Accenture사의 한국지사장인 Nick Taylor, 호주 Telstra Corporation Limited사의 CEO인 David Thodey 등 수백통의 답신을 받으며 신소트 프로그램에 대해 전세계 IT관계자들은 찬사를 보냈다. 특히 데이터 처리속도에서 최고의 평가를 받으며 신소트의 위상이 드높아지고 있는 시점에서 왜 Computer Scientist 신동근 박사가 컴퓨터 과학분야 세계최고를 선언한 이유를 짐작해 볼 수 있다.
신박사는 학문적 연구와 집필에도 많은 시간이 필요하므로 수천 명의 종업원을 소유하는 회사가 신소트를 전 세계에 배포하는 일을 더 잘할 수 있으리라는 것이 신박사의 생각이자 바램이다.

이성용 기자
WWW.DKSHIN.COM

 

기사 내용과 관련이 없는 글, 욕설을 사용하는 등 타인의 명예를 훼손하는 글은 관리자에 의해 예고없이 임의 삭제될 수 있으므로 주의하시기 바랍니다. 댓글 작성 시 상대방에 대한 배려와 책임을 담아주세요.

• 닉네임
• 비밀번호
• 
• 도배방지 입력