수면 분류: 이론과 맑은 현실의 교차점

약 6년 전, 한 익명 사용자가 4Chan에 게시:

그는 놀랍게도 발견되지 않은 이 유형을 케이스에 썼다. 역시, 일이었다.Check out my repo to download the code and try it yourself!

나는 처음에 매우 곤혹스러웠다는 것을 인정한다.나는 출력 값을 줄이는 데 필요한 시간을 줄이든 그에 상응하는 데이터 집합을 확장하든 이 알고리즘을 어떻게 개선하고 실현할 것인가를 구상할 수 있다.그런데 만약에 이런 방식(내 머릿속에서 O(n)가 실행될 때)이 정말 효과가 있다면 왜 IBM/Sun/Oracle의 천재는 아직 실현되지 않았을까?나는 처음으로 이 점을 어떻게 실현하는지 알고 싶은 사람이 아니다.왜 내 앞에 있는 사람은 안 해요?왜 우리는 현실 생활에서 그것을 사용하지 않습니까?
결국 컴퓨터는 여전히 기계이기 때문이다.말하자면, 이론은 이론이고, 현실은 영원히 현실이다.

수면 분류는 어떻습니까?

수면 정렬 코드는 다음과 같습니다.

#!/usr/bin/env bash

sort() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    sort "$1" &
    shift
done
wait

우리 이 문제를 부분적으로 분석합시다.(알고 싶으시면 #!/usr/bin/env bash 라고 하십시오.)

사방 함수

sort() {
    sleep "$1"
    echo "$1"
}

코드는 이 함수를 반복해서 호출합니다.그것은 첫 번째 파라미터 "$1" 를 받아들여 그렇게 오랫동안 잤다. 는 현재 프로세스(또는 더 중요한 것은 스레드)를 정해진 초로 정지시키는 명령입니다.예를 들어, sleep 100 프로세스가 휴면하거나 100초 동안 중단됨을 의미합니다.
그리고 Sleep 첫 번째 인자를 호출하여 인자를 출력합니다.따라서 코드sort 3는 휴면3초 후에 인쇄3됩니다.

메아리치다 while 순환

while [ -n "$1" ]
do
    sort "$1" &
    shift
done
wait

보시다시피 while 순환의 조건은 [ -n "$1" ] 입니다. 첫 번째 매개 변수에서 -n 로고를 사용합니다.매개 변수가 0이 아니라면, 이 로고는true를 되돌려줍니다.따라서 이 순환은 $1 곳의 매개 변수가null일 때까지 교체될 것이다.
그리고 우리는 첫 번째 매개 변수 sort "$1" 에서sort를 사용합니다. 그러나 가장 중요한 부분은 기호와 (&)입니다. 마지막으로, 이 기호와 하는 일은 이 줄에서 설명하는 과정, 즉sort 함수 호출을 시작하는 것입니다.
다음 줄에서 우리는 내장 함수shift라고 부른다.이 함수는 매개 변수가 없기 때문에shift의 기본값은 1입니다.전환의 작용은 우리의 논점을 바꾸는 것이다.$2의 매개 변수 이동$1, $3의 매개 변수 이동$2은 이와 같다.최초의 첫 번째 논점은 뒤이어 잃어버렸다.

자세한 내용은 여기를 참조하십시오. 실행 코드

위의 코드에서 보듯이, 우리는 첫 번째 파라미터를 가져오고, 이 파라미터의 길이에서 휴면하는 단독 라인을 실례화합니다.일단 그것이 깨어나면, 그것은 그것의 가치를 인쇄할 것이다.1초 자고, 2초 자고, 5초 자고, 등등. 낮은 값으로 잠을 이루지 못하면, 미리 값을 출력하기 때문에 목록을 정렬합니다.이거 신기하지 않아요?

왜 수면 정렬이 실패했는가

이런 데이터에는 기본적인 결함이 존재하고 대형 데이터 집합에 대해서는 붕괴될 수 있다는 것을 직감적으로 알려준다.수면 분류의 성공은 세 가지 기본 가설에 의존한다. 우리가 한 조의 5나 10개의 숫자를 초과할 때 이런 가설은 종종 성립되지 않는다.

1. 프로세서는 어느 하위 프로세스가 "최소" 인지 즉시 확인할 수 있다

일반적으로 프로세서 자체는 하위 프로세스를 저장하는 데이터 구조를 가지고 있다.프로세서가 요소를 효과적으로 훑어보고'최소'값을 가진 요소를 찾을 수 있도록 하는 , 하나Tree 또는 다른 데이터 구조일 수 있다.최소값을 찾아서 다음 프로세스를 찾자는 뜻입니다.
밀리초 단위로 수면 정렬은 여기서 분해할 수 있다.만약 주어진 값이 3과 3.00001이라면, 프로세서가 잘못된 프로세스를'최소'값으로 확정할 수 있습니다. 이것은 단지 프로세서의 시간이 아무리 적더라도 정확한 프로세스를 찾아야 하기 때문입니다.

쌓다 2. 컴퓨터는 몇 개의 스레드가 있습니까?

수면 정렬은 각 값을 다른 값 으로 분리할 수 있는지에 달려 있기 때문에 n개의 원소에 대해 n개의 사용 가능한 라인이 있다고 가정한다.네가 더 높은 수량급의 원소집에 들어갔을 때, 이 가설은 근본적으로 성립되지 않았다.당신의 컴퓨터에는 유한한 수량의 라인이 있는데, 만약 이 수량을 초과하면 수면 정렬에 실패할 것이다.

라인 3. 프로세서는 프로세스 사이를 빠르게 전환할 수 있다

당신의 프로세서를 작은 주식 코드로 상상해 보세요.여러 개의 작업을 병행할 때, 실제로 우리의 은유 표시기는 우리의 작업 사이를 빠르게 전환한다.이것은 작업 A를 1밀리초, 그리고 작업 B를 1밀리초, 그리고 작업 A로 되돌아옵니다. 이렇게 작은 규모로 전환되어 사람들이 보기에 이 두 가지는 병행 운행하는 것 같습니다.
대량의 작업이 있을 때, 이 코드기는 붕괴되기 시작한다.문제#1에서 지적한 바와 같이 다음 단계에서 어떤 임무를 처리해야 할지 결정하기 어렵고 현재 임무에 시달릴 수 있습니다.작업 사이를 왔다 갔다 하는 효율을 잃으면, 작업 순서대로 완벽하게 수행할 수 없기 때문에 수면 정렬이 붕괴되기 시작한다.

수면 분류는 우리에게 무엇을 가르쳐 줍니까

확장성은 모든 소프트웨어 엔지니어가 시스템을 구축할 때 반드시 명심해야 할 문제이다.
Often, the best products are the ones who consider scalability from the very start.
수면이 나에게 무엇을 주었는지, 나는 그것이 당신들에게 무엇을 주었는지 명확한 일깨움이 되기를 바란다. 우리는 이론 세계에서 효과적인 것이 물리 세계에서 작용하지 않을 것이라고 믿는다.이 말은 매우 뚜렷한 것 같지만, 많은 사람들이 만든 제품은 모두 이상적인 상황을 가설하였으며, 어떤 가설이 성립되지 않는 상황을 고려하지 않았다.
우리는 한 걸음 물러서서 우리의 시스템이 어떻게 작동하는지 깊이 이해해야 한다.그 밖에 우리가 더 크거나 다른 데이터 집합을 위해 해결 방안을 확장할 때, 우리는 이렇게 할 때 기능이 어떻게 영향을 받는지 알아야 한다.이런 통찰력을 얻는 유일한 방법은 환경의 한계성과 기계의 한계성을 인정하는 것이다.
하루가 끝났을 때, 당신의 기계는 여전히 이동하는 기계 부품으로 구성되어 있습니다.그에 상응하여 시스템을 설계하다.
나는 이 문장이 수면 분류를 이해하는 데 도움이 되기를 바란다. ! 가장 중요한 것은, 만약 당신이 내가 어떤 사실상의 잘못을 저질렀다고 생각하거나, 만약 내가 이 게시물을 개선하기 위해 해명/확장/수정할 수 있는 것이 있다면, 논평을 발표하거나 저에게 연락하세요!