枚举数字比 GNU seq 更快的方法？

Question

我想枚举数字（在 1 到 10 ¹³⁶之间的范围内），但到目前为止，我尝试过的大多数工具和技巧都会在 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( $_ );
}

withperl script.pl "0123456789" 10* 但是虽然它看起来比 seq 快（当做任何小于 10 ^{10 的}事情时），它仍然很挣扎，似乎需要很长时间才能完成......

我不需要将枚举的数字写入文件，但我确实需要它在标准输出上，以便我可以处理它。

编辑：

@Isaac 在他的回答（和评论中）中提到了一些可以工作的东西，虽然它确实比其他任何东西都快10 ¹⁰，但它仍然在任何大于 10 ¹⁰（以及扩展为 10 ¹³⁶）的范围内挣扎.

值得一提，因为有人提到它可能与这篇文章重复（技术上不是）。

我如何比 GNU seq 更快地从 0 枚举到 10 ¹³⁶？

Answer 1

不可能。根本无法枚举 10 ¹³⁶，无论您如何切割它。

在可观测的宇宙中总共有大约10 ^{80 个}原子。想象一下总并行化的极限，您设法利用那里的每个原子的力量。如果每个原子需要 100 皮秒来吐出一个数字（这意味着 10 GHz 的时钟频率，比当前的计算机快得多），那么您每秒会得到10 ^{90 个}数字。以这种令人难以置信的速度枚举您的序列仍然需要 10 ⁴⁶秒，或大约10 ³⁸年。我不认为你准备等那么久。

Answer 2

答案已经写在

字符和数字的所有可能组合

使用 c 源代码，将字符集更改为 only0123456789并执行。

它只需要

? 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 代码，时间也与排列的长度成正比。A 136排列长度为10的顺序^136-9 = 10 ¹²⁷ 1分钟或周围19025875190258751902587519025875190258751902587519025875190258751902587519025875190258751902587519025875190258751902587519倍

年。或者，以更短的方式（但在处理时间上不是更短）大约 10 ¹²⁹年。据推测，宇宙开始于 138 亿年前（13.8*10 ⁹）。我们谈论的是大约 10 ^{121 个}宇宙生命。祝你好运！！

请理解，一切都需要时间。即使在很短的时间内，每个数字和极高数量的计算机（多达原子宇宙中有）将产生：

10 ¹⁵ × 10 ⁸⁰ = 10 ⁹⁵

这仍然需要 10 ^136-95 =10 ⁴¹秒才能完成。

源代码

源代码编辑：

#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;
}