标签: knuth

长话短说:1986年,一位采访者要求Donald Knuth写一个输入文本和数字N的程序,并列出按频率排序的N个最常用的单词.Knuth制作了一个10页的Pascal程序,Douglas McIlroy用以下6行shell脚本回复:

tr -cs A-Za-z '\n' |
tr A-Z a-z |
sort |
uniq -c |
sort -rn |
sed ${1}q

请阅读http://www.leancrew.com/all-this/2011/12/more-shell-less-egg/阅读全文.

当然,他们有着截然不同的目标:Knuth展示了他的文学编程概念,并从零开始构建了所有内容,而McIlroy使用了一些常见的UNIX实用程序来实现最短的源代码.

我的问题是:那有多糟糕？
(纯粹从运行时速度的角度来看,因为我很确定我们都同意6行代码比10页更容易理解/维护,有文化编程与否.)

我可以理解,这sort -rn | sed ${1}q可能不是提取常用词的最有效方法,但有什么不对tr -sc A-za-z '\n' | tr A-Z a-z？它看起来对我很好.关于sort | uniq -c,这是一种非常慢的确定频率的方法吗？

一些注意事项:

• tr 应该是线性时间(？)
• sort我不确定,但我认为它不是那么糟糕
• uniq 也应该是线性时间
• 产卵过程应该是线性时间(在过程数量上)

最初的MIX架构具有6位字节,存储器被寻址为31位字(5个字节和一个符号位).作为一个思考练习,我想知道C语言如何在这种环境中发挥作用,给出:

• char至少有8位(C99规范附件E)
• C99规范6.3.2.3节("指针")第8段说"当指向对象的指针转换为指向字符类型的指针时,结果指向对象的最低寻址字节.结果连续增加,向上到对象的大小,产生指向对象剩余字节的指针." 我对这个要求的解释是它支持"memcpy(&dst_obj,&src_obj,sizeof(src_obj))".

我能想到的方法:

1. 使char为31位,因此通过"char*"间接是简单的内存访问.但这会使字符串浪费(并且意味着它不符合POSIX标准,因为它显然需要8位字符)
2. 将3个8位字符打包成一个字,7个忽略位:"char*"可能由字地址和字符索引组成.然而,这似乎违反了6.3.2.3,即memcpy()必然会跳过忽略的位(这对于真实对象类型可能有意义)
3. 将字符完全打包成单词,例如第四个8位字符在字0中有7位,在字1中有一位.但是这似乎要求所有对象都是8位字符大小,例如"uint31_t"不能声明匹配单词长度,因为这又有memcpy()问题.

所以这似乎留下了使用31位字符的第一个(浪费)选项,所有对象的大小都是char的倍数 - 我是否正确地阅读它？

我在回顾Knuth的"计算机编程艺术"时阅读了以下内容:

"非常'实用性'意味着想成为CS的专业人员必须学习Kernighan在设计C时的错误,特别是一个臭名昭着的事实,即for循环反复评估for条件,这与大多数其他语言的行为重复并且无法匹配它实现了for循环."

(http://www.amazon.com/review/R9OVJAJQCP78N/ref=cm_cr_pr_viewpnt#R9OVJAJQCP78N)

这家伙在说什么？你怎么能实现一个for循环不仅仅是一个while循环的语法糖？

我正在看一些Don Knuth教授的代码,用CWEB编写,转换为C.具体的例子是dlx1.w,可从Knuth的网站获得

在一个阶段,struct nd [cc]的.len值递减,并且以一种笨重的方式完成:

  o,t=nd[cc].len-1;
  o,nd[cc].len=t;

(这是一个特定于Knuth的问题,所以也许你已经知道"o"是一个预处理器宏,用于递增"mems",这是通过访问64位字来衡量的累计工作量.) "t"中剩余的值绝对不会用于其他任何事情.(此处的示例位于dlx1.w的第665行,或者是ctangle之后的dlx1.c的第193行.)

我的问题是:为什么Knuth这样写,而不是

nd[cc].len--;

他确实在其他地方使用过(dlx1.w第551行):

oo,nd[k].len--,nd[k].aux=i-1;

(而"oo"是一个类似的宏,用于递增"mems"两次 - 但这里有一些细微之处,因为.len和.aux存储在相同的64位字中.为S.len和S分配值. aux,通常只计算mems的一个增量.)

我唯一的理论是减量包括两个内存访问:首先查找,然后分配.(这是正确的吗？)这种写作方式提醒了这两个步骤.这对于Knuth来说会非常冗长,但也许这是一种本能的备忘录,而不是说教.

为了它的价值,我在没有找到答案的情况下搜索了CWEB文档.我的问题可能更多地与Knuth的标准实践有关,我正在逐渐采用.我会对这些实践被布局(并且可能被批评)作为一个块的任何资源感兴趣 - 但是现在,让我们关注为什么Knuth以这种方式编写它.

我正在练习TAOCP第1版第3版,并且无法理解下面练习答案中使用的语法.

第1章练习8

通过指定T _j,s _j,a _j,b _j来计算正整数m&n的最大公约数

让你的输入用字符串a ^m b ^n表示(ma后跟n b)

回答:

设A = {a,b,c},N = 5.该算法将以字符串a ^{gcd(m,n)结束}

    j     Tj     sj    bj    aj
    0     ab  (empty)  1    2   Remove one a and one b, or go to 2.
    1   (empty)  c     0    0   Add c at extreme left, go back to 0.
    2     a      b     2    3   Change all a's to b's
    3     c      a     3    4   Change all c's …

在32位整数数学中,add和multiply的基本数学运算隐式计算mod 2 ^ 32,这意味着你的结果将是add或multiply的最低位.

如果要使用不同的模数计算结果,您当然可以使用不同语言的任意数量的BigInt类.对于值a,b,c <2 ^ 32,您可以计算64位长整数的中间值,并使用内置的%运算符减少到右侧的答案

但是我被告知,当C的形式为(2 ^ N)-1或(2 ^ N)+1时,有一些特殊的技巧可以有效地计算a*b mod C,它们不使用64位数学或一个BigInt库,非常高效,比任意模数评估更有效,并且还可以正确计算在包含中间乘法时通常会溢出32位int的情况.

不幸的是,尽管听说这种特殊情况有快速的评估方法,但实际上我还没有找到该方法的描述."那不是在Knuth吗？" "这不就是维基百科上的某个地方吗？" 是我听到的咕噜声.

它显然是随机数生成器中的常用技术,其执行a*b mod 2147483647的乘法,因为2147483647是等于2 ^ 31 -1的素数.

所以我会问专家.什么是这个聪明的特殊情况乘法与mod方法,我找不到任何讨论？

我一直在阅读Donald Knuth第1卷的计算机程序设计艺术.现在我完成了第一部分,所有的数学都被解释了,这是非常愉快的.不幸的是,在p.他开始解释这种MIX基于真实机器语言的虚构机器语言,随后他将解释所有算法,而Knuth先生完全失去了我.

我希望这里有人"说话" MIX,可以帮助我理解它.具体来说,他失去了我开始解释不同操作和展示例子的地方(第125页).

Knuth使用以下形式的"指令格式":

他还解释了不同字节的含义:

因此,右字节是要执行的操作(例如,LDA"加载寄存器A").F字节是操作代码的修改,具有8L + R的字段规范(L:R)(例如,C = 8且F = 11产生"加载具有(1:3)字段的寄存器).然后+/- AA是地址,我是修改地址的索引规范.

这对我来说有点道理.但是Knuth带来了一些例子.第一个我理解除了几个位,但我无法绕过第二个例子的最后三个,而在下面的例子3中的更困难的操作中没有任何东西.

这是第一个例子:

LDA 2000只加载完整的单词,我们完全在寄存器A中看到它rA.第二个LDA 2000(1:5)加载从第二个位(索引1)到结尾(索引5)的所有内容,这就是加载除加号之外的所有内容的原因.第三个LDA 2000(3:5)只加载从第三个字节到最后一个字节的所有内容.另外LDA 2000(0:3)(第四个例子)有点理解.应复制-803并取 - 并将80和3放在最后​​.

到目前为止这么好,在number5中,如果我们遵循相同的逻辑,LDA2000(4:4)它只传输第四个字节.它确实对最后一个位置做了什么.但是,LDA 2000(1:1)应该只复制第一个字节(符号).这很奇怪.为什么第一个值是+而不是 - (我只想要 - 被复制).为什么其他值都是0而最后一个是问号？

然后他给出了第二个例子的操作STA(商店A):

同样,STA 2000,STA 2000(1:5)和STA 2000(5:5)有意义的逻辑相同.但是,Knuth确实如此STA 2000(2:2).你希望在寄存器A中复制第二个字节等于7.但不知怎的,我们最终会得到- 1 0 3 4 5.我一直在看这些几个小时,并且不知道这是怎么回事,或者跟随这一个(STA 2000(2:3)和STA 2000(0:1))的两个例子可以导致显示的位置的内容.

我希望这里有人可以对这三个人发光.

此外,我也有在那里,他解释了操作的页面大麻烦ADD, …

唐纳德克努特的计算机编程艺术系列使用他自己的程序汇编语言MIX.现在,问题变成了:Knuth是否应该使用函数式语言来描述他的算法？TeX是否应该用函数式语言编写？

计算机具有程序架构.计算的根源是否意味着最好的分支？

最初的AoCP是用MIX编写的.更新后的AoCP使用了基于更现代架构的MMIX.

但是,基本点仍然存在.Knuth从一个程序架构转到另一个......显然不需要函数式编程.

在与Google进行的45分钟技术访谈中,我被问到了Leaper Graph问题.我编写了工作代码,但后来拒绝了工作机会,因为我缺乏数据结构知识.我想知道我能做得更好.

问题如下:"给定一个N尺寸的板,并告诉一件可以水平(左或右)和j垂直(向上或向下)的位置(即,有点像国际象棋中的马),可以电路板上的每个地方到达哪个？"

我写了以下算法.它递归地通过标记图表上访问过的所有点来查明板上的每个位置是否可达.如果无法访问,则至少有一个字段为false,该函数将返回false.

      static boolean reachable(int i, int j, int n) {
        boolean grid[][] = new boolean[n][n];
        reachableHelper(0, 0, grid, i, j, n - 1);
        for (int x = 0; x < n; x++) {
          for (int y = 0; y < n; y++) {
            if (!grid[x][y]) {
              return false;
            }
          }
        }
        return true;
      }

      static void reachableHelper(int x, int y, boolean[][] grid, int i, int j, int max) {
        if (x > max || y > max …

我一直试图弄清楚 Donald Knuth 的WEB是什么，但它真的很矛盾。我从网页上了解到它类似于 doxygen，但我阅读的所有资料都坚持认为它是一种编程语言。但是，它看起来不像我见过的任何编程语言。

那么WEB究竟是什么？是否有一些文档可以解释它？