☰

GNU seq보다 숫자를 더 빠르게 열거하는 방법은 무엇입니까? [폐쇄]

tag-icon • tag-icon linux performance seq
GNU seq보다 숫자를 더 빠르게 열거하는 방법은 무엇입니까? [폐쇄]

숫자(1부터 10 136 까지)를 열거하고 싶지만 지금까지 시도한 대부분의 도구와 트릭은 10 9 주변의 숫자 이후에 어려움을 겪습니다 .

다음은 (소규모) 몇 가지 예입니다.

~을 위한seq 99999

real    0m0.056s
user    0m0.004s
sys     0m0.051s

~을 위한seq 9999999

real    1m5.550s
user    0m0.156s
sys     0m6.615s

등등... 문제는 9번째 숫자(이 경우 999999999) 이후에만 투쟁이 시작된다는 것입니다. 나는 그것들을 더 작은 범위로 나누고 병렬로 실행하는 것을 생각했습니다.

cat <(seq 000 999) <(seq 999 1999) <(seq 1999 2999) <(seq 2999 3999) <(seq 3999 4999) <(seq 4999 5999) <(seq 5999 6999) <(seq 6999 7999) <(seq 7999 8999) <(seq 8999 9999) <(seq 9999 10999) <(seq 10999 11999) <(seq 11999 12999) <(seq 12999 13999) <(seq 13999 14999)

real    0m0.258s
user    0m0.008s
sys     0m0.908s

이는 그보다 훨씬 느립니다(특히 더 넓은 범위에서). seq 000 14999

real    0m0.042s
user    0m0.000s
sys     0m0.041s

나는 SO에서 찾은 이 Perl 스크립트를 시도했습니다.

#!/usr/bin/perl
use strict;
if ( ($#ARGV+1)!=2 ) { print "usage $0  \n"; }
my @r = &bitfizz( $ARGV[0], $ARGV[1] );
for(@r){ print "$_\n"; }
sub bitfizz() {
    $_[0]=join( ",", split(//, $_[0] ) );
    for( my $i=1; $i<=$_[1]; $i+=1 ) { $_=$_."{$_[0]}"; }
    @r=glob( $_ );
}

seq보다 빠른 것 같지만 (10 10perl script.pl "0123456789" 10* 미만의 작업을 수행할 때 ) 여전히 어렵고 완료하는 데 시간이 오래 걸리는 것 같습니다...

열거형의 숫자를 파일에 쓸 필요는 없지만 처리할 수 있도록 표준 출력에 넣어야 합니다.

편집하다:

@Isaac은 자신의 답변(및 댓글)에서 무언가를 언급했습니다.할 수 있다작동하고, 언급된 다른 어떤 것보다 훨씬 빠르게 10 10 을 통과하지만 10 10 (및 더 나아가 10 136 )보다 큰 것에서는 여전히 어려움을 겪습니다 .

이 게시물의 중복일 가능성이 있으므로 언급할 가치가 있습니다(기술적으로는 그렇지 않습니다).

GNU seq보다 0에서 10 136까지 더 빠르게 열거하는 방법은 무엇입니까 ?

답변1

불가능한. 어떻게 잘라도 10 136 을 열거할 수 있는 방법은 없습니다.

대략 있습니다.관측 가능한 우주의 원자 10 80개, 총. 모든 원자의 힘을 활용하는 완전한 병렬화의 한계를 상상해 보십시오. 각 원자가 숫자를 내는 데 100피코초가 걸린다면(이는 현재 컴퓨터보다 훨씬 빠른 10GHz의 클럭 주파수를 의미함) 다음과 같은 결과를 얻습니다.초당 10 90개 숫자. 이 놀라운 속도에서도 시퀀스를 열거하는 데는 여전히 10 46 초 또는 약 10초가 걸립니다.10 38 세. 내 생각엔 당신이 그렇게 오래 기다릴 준비가 되어 있지 않은 것 같아요.

답변2

답은 이미 글에 써있습니다

문자와 숫자의 가능한 모든 조합

c 소스코드를 이용하여 문자셋을 only로 변경 0123456789하고 실행한다.

단지 필요하다

➤ time ./permute.out 5 >/dev/null
run    : 0m0.012s sec

➤ time ./permute.out 7 >/dev/null
run    : 0m0.764s sec

➤ time ./permute.out 9 >/dev/null
run    : 1m12.537s sec

오래되고 느린 기계에서.

하지만 경고합니다. 작은 C 코드라도 시간은 순열 길이에 비례합니다. 136 순열의 길이는 대략 10 136-9 = 10 127 곱하기 1분 또는 대략 19025875190258751902587519025875190258751902587519025875190258751902587519025 87519025입니다. 8751902 5875190258751902587519

년도. 또는 더 짧은 방식으로 작성하면(그러나 처리 시간은 더 짧아질 수 없음) 약 10,129 년 입니다 . 우주는 138억년(13.8*10 9 ) 전에 시작되었다고 추측됩니다 . 우리는 대략 10,121개의 우주 존재에 대해 이야기하고 있습니다. 행운을 빌어요!

모든 일에는 시간이 걸린다는 점을 이해하시기 바랍니다. 아주 짧은 시간이라도 각 숫자는 1펨토초(빛은 1펨토초에 약 0.3μm(마이크로미터)를 이동하는데, 이는 바이러스의 직경과 비슷한 거리)이며, 그 안에는 원자만큼 많은 컴퓨터가 있습니다. 우주)는 다음을 생성합니다.

10 15 × 10 80 = 10 95

완료하는 데 10 136-95 =10 41 초가 걸립니다 .

소스 코드

소스 코드 편집기:

#include <stdio.h>

//global variables and magic numbers are the basis of good programming
const char* charset = "0123456789";
char buffer[200];

void permute(int level) {
  const char* charset_ptr = charset;
  if (level == -1){
    puts(buffer);
  } else {
    while( (buffer[level] = *charset_ptr++) ) {
      permute(level - 1);
    }
  }
}

int main(int argc, char **argv)
{
  int length;
  sscanf(argv[1], "%d", &length); 

  //Must provide length (integer < sizeof(buffer)==200) as first arg;
  //It will crash and burn otherwise  

  buffer[length] = '\0';
  permute(length - 1);
  return 0;
}

답변3

조금 다른 접근 방식을 취해보자. 이것이 실제로 수행될 수 있다고 가정하십시오. 그럼 어떻게 인쇄하나요? 다음의 간단한 C 프로그램을 예로 들어보겠습니다.

#include <stdio.h>
void main(){
  int i;
  for(i=1;i<=100;i++){
    printf("%i\n",1);
  }
}

이것은 단순히 숫자를 1100번 출력합니다. 100번 실행하고 시간을 측정해 보니 실행당 평균 시간은 다음과 같습니다.

$ time ./printOne >/dev/null

real    0m0.004s
user    0m0.001s
sys     0m0.003s

그러니까 약 0.004초인데, 상대적으로 성능이 좋은 제 노트북에서는 1밀리초에 해당합니다. 그러나 1나노초(10 -9 초 또는 0.000000001초) 에 100라인을 인쇄할 수 있다고 가정하면 훨씬 더 빠른 기계를 상상해 보십시오. 즉 1,000,000배 더 빠릅니다.

이제 실제로 숫자를 계산하는 데 걸리는 시간도 무시하고 즉시 계산하는 마법의 솔루션을 상상해 봅시다. 이제 우리가 해야 할 일은 초고속 인쇄 프로그램을 사용하여 이 숫자를 인쇄하는 것뿐입니다. 1나노초에 100줄을 인쇄할 수 있다는 것을 알고 있으므로 이는 10,136 줄 을 인쇄하는 데 10,136 /100 = 10,134 나노초 가 걸린다는 것을 의미합니다 . 10136 나노초 는 3.1688739 x 10117 년과 같습니다.데이터를 인쇄만 하고 계산도 하지 마세요.! 그리고 이 숫자는 이해하기 쉽지 않기 때문에 수년 동안 이것이 의미하는 바는 다음과 같습니다.

316887390000000000000000000000000000000000000000000000000000000000000000000000

우주의 열사멸 예상 시간은 지금으로부터 약 10,106 년이다 . 이것은 의미한다데이터만 인쇄다른 어떤 것보다 훨씬 더 빠른 컴퓨터가 필요하기 때문에 우리는 우주 전체의 나머지 생명체보다 더 많은 시간을 가지고 있습니다. 실제로 우주의 수명보다 훨씬 더 많은 시간이 걸립니다.

따라서 확실히, 실제로 가능하다고 말할 수도 있지만 "가능"이라는 단어의 의미는 꽤 쓸모가 없습니다. 왜냐하면 어떻게 보든 우리나 우리가 타고 있는 우주는 종말에 기회가 없을 것이기 때문입니다. 그것은 존재하지 않을 것입니다. 인쇄.

답변4

숫자(1~10^136 범위)를 열거하고 싶습니다.

당신이 얻은 답변은 당신이 그렇게 하지 않을 이유를 알려줄 것입니다.

또는 예, 다음을 열거할 수 있습니다.

#!/usr/bin/perl
use bigint;
for (1..1e136) { print $_ . ", "}

하지만 시간이 많이 걸릴 거예요. 마치... 당신이 예상했던 것보다 훨씬 오래 살 것 같아요. seq로 재미있게 놀아볼까요?

j=9 TIMEFORMAT='%lR';  \
for i in `seq 1 9`; do 
    j=$(( $j * 10 + 9));
    echo -n "$i digits: ";
    time seq $j > /dev/null; 
done

알겠어요

1 digits: 0m0,002s
2 digits: 0m0,002s
3 digits: 0m0,001s
4 digits: 0m0,002s
5 digits: 0m0,014s
6 digits: 0m0,126s
7 digits: 0m1,261s
8 digits: 0m12,631s
9 digits: 2m9,607s

보시다시피 시작 시간은 최대 9,999까지 지배적이지만 각 숫자에 대한 시간은 처리할 숫자가 10배 더 많기 때문에 정확히 예상한 대로 약 10배 증가합니다. 그리고 그것은 계속될 것이다...

  8 digits:~   0.2 minutes
  9 digits:~   2   minutes
 10 digits:~  20   minutes
 11 digits:~ 120   minutes (2 hours)
 36 digits:~ 2e25  hours   (> 3,500 years)
136 digits:~ 2e125 --- never mind.

그것은 휴식 수명보다 훨씬 길다. 100배 더 빠르게(!) 만드는 방법을 찾았다면 1e136 자리는 말할 것도 없고 1e36을 얻으려면 여전히 3.5년을 기다려야 합니다. 이것은 단순히 지속 불가능합니다. (다른 사람들도 다 하는 말이지만 이해하는데 도움이 될 것 같습니다.)

실제로 무엇을 하려는지 알려주시면 더 나은 답변을 얻을 수 있습니다. 어쩌면 약속과 지연된 실행이 필요할 수도 있고, 데이터베이스가 필요할 수도 있습니다. 하지만 그것들을 모두 열거할 필요는 없다고 확신합니다.

관련 정보