☰

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のクロック周波数を意味します）、次の結果が得られます。1秒あたり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 分または約5です。 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と同じです。データを印刷するだけで計算もしないでください。！そして、この数字は理解しにくいので、長年にわたってこれが意味するところは次のとおりです。

3168873900000000000000000000000000000000000000000000000000000000000000000000

宇宙の熱死の予想時間は今から約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年を待たなければなりません。これは単に持続不可能です。 （他の人もやる言葉ですが、理解するのに役立ちそうです。）

実際に何をしたいのかを教えてください。より良い答えを得ることができます。おそらく、予定と遅延実行が必要な場合や、データベースが必要な場合があります。しかし、それらをすべて列挙する必要はないと確信しています。

関連情報