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

Question 1

不可能。无论你如何削减，根本无法枚举 10 ^{136 。}

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

Answer

不可能。无论你如何削减，根本无法枚举 10 ^{136 。}

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

Question 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 代码，时间也与排列的长度成正比。 136 排列长度约为 10 ^136-9 = 10 ¹²⁷乘以 1 分钟或大约 19025875190258751902587519025875190258751902587519025875190258751902587519025 8751902587519025875190258751902587519

年。或者，用更短的方式写（但处理时间也不能短一点）大约 10 ¹²⁹年。据推测，宇宙始于 138 亿年前 (13.8*10 ⁹ )。我们谈论的是大约 10 ¹²¹个宇宙生命。祝你好运！

请理解，一切都需要时间。即使是非常短的时间，每个数字也有一个飞秒（光线在 1 飞秒内传播大约 0.3 μm（微米），这个距离与病毒的直径相当），并且计算机数量非常多（与原子一样多）在宇宙中）将产生：

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

Answer

答案已经写在

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

使用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 代码，时间也与排列的长度成正比。 136 排列长度约为 10 ^136-9 = 10 ¹²⁷乘以 1 分钟或大约 19025875190258751902587519025875190258751902587519025875190258751902587519025 8751902587519025875190258751902587519

年。或者，用更短的方式写（但处理时间也不能短一点）大约 10 ¹²⁹年。据推测，宇宙始于 138 亿年前 (13.8*10 ⁹ )。我们谈论的是大约 10 ¹²¹个宇宙生命。祝你好运！

请理解，一切都需要时间。即使是非常短的时间，每个数字也有一个飞秒（光线在 1 飞秒内传播大约 0.3 μm（微米），这个距离与病毒的直径相当），并且计算机数量非常多（与原子一样多）在宇宙中）将产生：

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

Question 3

让我们采取稍微不同的方法。假设确实可以做到这一点。那么，如何打印呢？以这个简单的 C 程序为例：

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

这只是简单地打印出数字1一百次。我运行了 100 次并计时，每次运行的平均时间是：

$ time ./printOne >/dev/null

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

因此，大约 0.004 秒，对于我功能相对强大的笔记本电脑来说，相当于一毫秒。不过，让我们慷慨地想象一台机器的速度要快几个数量级，假设它可以在一纳秒（10 ^-9秒，或 0.000000001 秒）内打印 100 行，所以速度快了 1000000 倍。

现在，我们也忽略实际计算数字所需的时间，让我们想象一个神奇的解决方案可以立即计算它们。所以现在，我们所要做的就是使用我们的超快速打印程序打印出这些数字。因为我们知道它可以在一纳秒内打印出 100 行，这意味着打印 10 ¹³⁶行需要 10 ¹³⁶ / 100 = 10 ¹³⁴纳秒。 10 ¹³⁶纳秒等于 3.1688739 x 10 ¹¹⁷年，只是打印出数据，甚至不计算它！而且，因为这个数字不容易理解，所以它意味着这么多年：

31688739000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000

宇宙热寂的估计时间是从现在起大约¹⁰¹⁰⁶年。这意味着仅打印您的数据需要一台比任何东西都快几个数量级的计算机，我们拥有的时间比整个宇宙的其余生命都多。事实上，它所花费的时间比宇宙的寿命还要多几个数量级。

所以可以肯定的是，虽然你可能会说这实际上是可能的，但“可能”这个词的含义是非常无用的，因为无论你如何看待它，我们或我们所乘坐的宇宙在它结束时都不会存在。印刷。

Answer

让我们采取稍微不同的方法。假设确实可以做到这一点。那么，如何打印呢？以这个简单的 C 程序为例：

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

这只是简单地打印出数字1一百次。我运行了 100 次并计时，每次运行的平均时间是：

$ time ./printOne >/dev/null

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

因此，大约 0.004 秒，对于我功能相对强大的笔记本电脑来说，相当于一毫秒。不过，让我们慷慨地想象一台机器的速度要快几个数量级，假设它可以在一纳秒（10 ^-9秒，或 0.000000001 秒）内打印 100 行，所以速度快了 1000000 倍。

现在，我们也忽略实际计算数字所需的时间，让我们想象一个神奇的解决方案可以立即计算它们。所以现在，我们所要做的就是使用我们的超快速打印程序打印出这些数字。因为我们知道它可以在一纳秒内打印出 100 行，这意味着打印 10 ¹³⁶行需要 10 ¹³⁶ / 100 = 10 ¹³⁴纳秒。 10 ¹³⁶纳秒等于 3.1688739 x 10 ¹¹⁷年，只是打印出数据，甚至不计算它！而且，因为这个数字不容易理解，所以它意味着这么多年：

31688739000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000

宇宙热寂的估计时间是从现在起大约¹⁰¹⁰⁶年。这意味着仅打印您的数据需要一台比任何东西都快几个数量级的计算机，我们拥有的时间比整个宇宙的其余生命都多。事实上，它所花费的时间比宇宙的寿命还要多几个数量级。

所以可以肯定的是，虽然你可能会说这实际上是可能的，但“可能”这个词的含义是非常无用的，因为无论你如何看待它，我们或我们所乘坐的宇宙在它结束时都不会存在。印刷。

Question 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（包括 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 倍（！），你仍然需要等待 3.5 年才能得到 1e36——更不用说 1e136 位数字了。这根本就是不可持续的。（这是其他人都这么说的，但这也许可以帮助您理解。）

如果您能告诉我们您实际尝试做什么，您可能会得到更好的答案。也许您需要承诺和延迟执行，也许您需要一个数据库，...但我确信您不需要枚举所有这些。

Answer