입문

이 글은 회사 내 Advent Calendar 2013의 12/11점짜리 글입니다.
회사 기밀을 특별히 다루는 정보가 없어서 공개하려고 합니다.
말랑말랑한 내용이라 편하게 읽었으면 좋겠어요.

한편, 이미지는 12/9 초롱군의 보도문외한분들이 Surface Pro로 그림을 그려보세요.를 읽고 문외한이 마우스로 그림을 그릴 때의 질과 개인적으로 비교했을 때의 것이다.
자꾸 내 그림이 사악한 분위기를 풍기는 것 같아.역시 서피스 프로 대단해!(.마음에 들어.)☆

갈라질 수 없는 굳세고 변함없는 그리움

며칠 전 고등학교 시절 친구와 술을 마시러 갔을 때 한 말이다.
그 친구 얼마 전에 결혼했어요.
축의금에는 30011엔의 신비한 금액이 있다고 한다.
일반적으로 지폐의 장수를 두 부분으로 나누지 않기 위해
나는 3만 엔과 5만 엔이 비교적 많다고 생각한다.
그럼 직감이 좋은 사람이 눈치채겠지.
예.“소수”.
30000은 2로 찢어지잖아!
절대로 다른 수로 나누면 안 되는 수,'소수'로 두 사람을 축하합시다!
이렇게 부드러운 숫자.
소수.너무 좋아요.
음...?30011 진짜 소수야?
여기 한번 알아볼게요.
이곳에서 시작된 이 기획은
SQL(Sosuu reQuest Language)

어차피 하려면...

30011이 소수인지 아닌지 조사하는 게 너무 아쉬워요.
소수 일람표를 만들어서 어떤 숫자도 알아낼 수 있도록 하세요!
그래서 나는 소수의 일람표를 만들기로 했다.
이번의 경우 대략 어릴 때부터 10000개의 소수 일람을 하면 충분하지 않을까.
부족하면 늘었으면 좋겠어요.

아무튼 한번 해봤어요.

어떤 숫자가 소수인지 아닌지
"그 숫자가 자신보다 작은 소수로 갈라진 것이 있는지 조사해 보세요.
만약 깨진 것이 하나도 없다면, 이 숫자는 소수이다. "
사용자 정의 모양새를 정의합니다.
그래서

결과 테이블에서 소수는 INSERT

작은 순서로 숫자를 계수하면서 검증

앞에서 나온 결과표를 사용하여 검증

나는 이렇게 하면 할 수 있을까 봐 두렵다.
…
이 앞의 결과표를 사용하여 검증...?
...최초의 첫 번째는 어떡하지?
그럼...최초의 하나는'2'이니 결과용 책상 위에 미리 놓으세요!
그러니까 아무 생각 없이 쓰기 시작해.

--素数一覧結果用テーブル
CREATE TABLE #PrimeNumbers
(
    SEQ             int   
,   PrimeNumber     bigint
)

--最初の素数である2は入れておく
INSERT INTO #PrimeNumbers VALUES(1, 2)

DECLARE 
    @RequiredPrimeNumberCount   int     = 10000
,   @PrimeNumberCount           int     = 1
,   @Number                     bigint  = 3
,   @TestNumber                 bigint
,   @HasFound                   bit    

--取得できた素数のカウントが要求された件数に達するまでループする
WHILE @PrimeNumberCount < @RequiredPrimeNumberCount
BEGIN

    --FLG初期化
    SET @HasFound = 0

    --これまでに見つけた素数で割れるかを順に検証する為にカーソルを回す
    DECLARE Cur CURSOR FOR
        SELECT
            PrimeNumber
        FROM #PrimeNumbers
        ORDER BY 
            SEQ

    OPEN Cur

    FETCH NEXT FROM Cur INTO @TestNumber

    -- ココから検証
    --割り切れる数が見つかるか、素数カーソルを最後まで回しきったら検証終了
    WHILE @HasFound = 0 AND @@FETCH_STATUS = 0 
    BEGIN
        IF @Number % @TestNumber = 0
        BEGIN
            --割り切れちゃったらFLGを立てる
            SET @HasFound = 1
        END

        FETCH NEXT FROM Cur INTO @TestNumber
    END

    CLOSE Cur
    DEALLOCATE Cur

    --検証した結果、割り切れる数が見つからなかった場合は素数の件数をカウントアップして、結果用テーブルにINSERT
    IF @HasFound = 0
    BEGIN
        SET @PrimeNumberCount += 1
        INSERT INTO #PrimeNumbers VALUES(@PrimeNumberCount, @Number)
    END
    --そして、また次の数字の検証へ…
    SET @Number += 1

END

--全件取得
SELECT
    *
FROM #PrimeNumbers
ORDER BY
    SEQ

--30011の確認
SELECT
    *
FROM #PrimeNumbers
WHERE
    PrimeNumber = 30011

DROP TABLE #PrimeNumbers

완성!
확실히 30011은 소수!!
너무 좋아!!!

아니, 대단한 건 아니지..

나는 결과를 얻게 되어 매우 기쁘다

처리 시간: 00:21:03(hhss)
...기다릴 때 배꼽으로 차를 끓이는 수준이다.
제대로 참을 수 있는 연기를 어떻게...
관건은 어떻게 검증을 가속화하는가이다.
원래 순환 중에 커서가 느려지는 것은 당연하다.
수량이 갈수록 많아지다.
커서 사용하지 않기...
만약 네가 그 숫자를 제거할 수 있는 소수를 찾을 수 있다면, 그것은 소수가 아니다.
...어?WHERE로 하면 되잖아...?
그래서
여기 아주 무거운 조회가 있죠?

    --これまでに見つけた素数で割れるかを順に検証する為にカーソルを回す
    DECLARE Cur CURSOR FOR
        SELECT
            PrimeNumber
        FROM #PrimeNumbers
        ORDER BY 
            SEQ

    OPEN Cur

    FETCH NEXT FROM Cur INTO @TestNumber

    -- ココから検証
    --割り切れる数が見つかるか、素数カーソルを最後まで回しきったら検証終了
    WHILE @HasFound = 0 AND @@FETCH_STATUS = 0 
    BEGIN
        IF @Number % @TestNumber = 0
        BEGIN
            --割り切れちゃったらFLGを立てる
            SET @HasFound = 1
        END

        FETCH NEXT FROM Cur INTO @TestNumber
    END

    CLOSE Cur
    DEALLOCATE Cur

이 부분은...

    SELECT
        @HasFound = 1
    FROM #PrimeNumbers MAIN
    WHERE
        @Number % MAIN.PrimeNumber = 0

그렇구나!
비주얼도 상당히 상큼하네요.
처음 그거 뭐였지?
결과는...

처리 시간: 00:00:58(hhss)
좋아요.
이렇게 되면 라면을 만드는 것보다 결과가 더 빨리 돌아올 것이다!

하면, 만약, 만약...

검증 예
"그 숫자가 자신보다 작은 소수로 갈라진 것이 있는지 조사해 보세요.
만약 깨진 것이 하나도 없다면, 이 숫자는 소수이다. "
갔습니다.
...깨진 것이 하나도 없다면...?
…EXISTS!!!
왜 처음에 커서를 썼을까요?
나는 정말 바보다.
WHERE 때 결과를 시계로 전부 스캔했어요.
EXISTS를 사용하면 하나를 얻을 때 처리에서 벗어날 수 있기 때문에 성능 향상을 기대할 수 있습니다.
그래서...

    SELECT
        @HasFound = 1
    FROM #PrimeNumbers MAIN
    WHERE
        @Number % MAIN.PrimeNumber = 0

이 부분은...

    SELECT
        @HasFound = 1
    WHERE EXISTS
    (
        SELECT
            *
        FROM #PrimeNumbers MAIN
        WHERE
            @Number % MAIN.PrimeNumber = 0
    )

그렇구나!!!
결과는...

처리 시간: 00:00:07(hhss)
뜻밖에!
아까 조회한 8배속 정도였나요!!
여기까지 왔다!!!
왜 처음부터 그런 방법을 썼을까...
할 줄 모르고 해봤어요.
프롬 자구SELECT ○○ WHERE EXISTS～를 사용하지 않으면 됩니다.
이번에 이런 발견이 있을 줄은 생각지도 못했다.
이 기사를 쓸 수 있어서 정말 다행이다.

결국 이런 조회를 마쳤습니다.

GetPrimeNumbers.sql

CREATE TABLE #PrimeNumbers
(
    SEQ             int   
,   PrimeNumber     bigint
)

INSERT INTO #PrimeNumbers VALUES(1, 2)

DECLARE 
    @RequiredPrimeNumberCount   int     = 10000
,   @PrimeNumberCount           int     = 1
,   @Number                     bigint  = 3
,   @HasFound                   bit    

WHILE @PrimeNumberCount < @RequiredPrimeNumberCount
BEGIN

    SET @HasFound = 0

    SELECT
        @HasFound = 1
    WHERE EXISTS
    (
        SELECT
            *
        FROM #PrimeNumbers MAIN
        WHERE
            @Number % MAIN.PrimeNumber = 0
    )

    IF @HasFound = 0
    BEGIN
        SET @PrimeNumberCount += 1
        INSERT INTO #PrimeNumbers VALUES(@PrimeNumberCount, @Number)
    END

    SET @Number += 1

END

SELECT
    *
FROM #PrimeNumbers
ORDER BY
    SEQ

DROP TABLE #PrimeNumbers

이렇게 하면 소수의 일람표를 얻을 수 있다!
아주 긴 길.
아이고, 원래 축하 선물의 30011엔이 수수한 금액인지 알아보고 있었어요.
결국...
30011은 3246번째 소수!

총결산

이번에 나는 이 느낌을 했다

의외로 조회도 수학이구나

질의에서 커서를 사용할 때 성능에 유의해야 함

FROM 자구가 없어도 WHERE EXISTS를 사용할 수 있을지 모르겠다~

WHERE 자구를 조금만 바꾸면 성능이 크게 향상됩니다

생각만 해도 다양한 방안이 있다

정답을 찾은 전방에서 얻은 것

이런 느낌인가요?
마지막이 더 멋있네.
조회가 생각보다 많아요.
이런 어리석은 사용법도 있군요.자리라고 생각하시면 좋을 것 같습니다.
이번에는 아무것도 찾지 않고 생각난 이 알고리즘으로 소수 판정을 했는데 찾아보니 더 똑똑한 방법이 많은 것 같다.
위키백과-질수판정
일련번호표탄성 강도 체를 만들어 조회하는 것도 재미있다.
며칠 후에 도전해 보세요.
또 "이렇게 재미있고 어리석은 조회를 썼어요!"하면, 만약, 만약...
반드시 정보를 공유하세요!
여기까지 읽어줘서 고마워!

추가

참고로 실제로는 조회Project Euler입니다.이런 신비한 도전에서 시작된다.
관심이 있다면 SQL과 C#에 도전해 보세요.
또 7번째 문제인'10001개의 소수를 구하기'문제에서 정확하기 때문에
이번 조회에서 얻은 결과집은 틀림없이 정확할 것이다!

게다가

어렵기 때문에, 겸사겸사 분해소 인수에 대한 조회를 써 보았다
그것을 쓰는 공백이 너무 좁다.