c生成随机数代码(const类型变量)

c生成随机数代码(const类型变量)

【CSDN编者按】:C语言尽管长期占据TIOBE排行榜前10,但不用来直接编写实际应用已经成了不争的事实。这个诞生了近40年的C语言,像一个老兵,老兵不死,只是逐渐凋零。

以下为译文:

有人问我用C来实现XYZ是否有意义,尤其是与使用一些更高级的语言(c 、Julia、Python、Haskell、Rust或Lisp)相比。

我怀疑一些人都被C吓到了,需要某种超人的黑客能力才会使用。至少我在真正开始使用C之前是这种感觉。另一些人认为C语言是一种可怕的语言,它似乎天生就有缺陷,应该把它扔回到UNIX的深渊中去(这么认为也有一定的道理)。我个人认为,C语言的简单性是一个优点,它的缺点往往大于它的优点,虽然在某些领域,C语言可能是一个糟糕的选择;但C语言也有运行良好的领域,选择C语言取决于个人偏好。

在这篇文章中,关于什么时候应该/不应该使用C,我将给出一些建议,希望对你有所帮助。这是基于自己用C语言开发数学软件(主要是Flint、Arb和Calcium)的经验。这种经验未必能很好地适用于其他环境。

为什么会使用C语言

我提出以下四个简单的论点:

实用性

第一个原因是C语言是稳定的,受到广泛支持,并且有可靠的工具。C库几乎可以在任何地方编译和运行,可以在任何地方开发,并且需要的依赖性最小。实际上,任何其他编程语言的用户都可以通过其C外部函数接口轻松地与C代码进行交互。不仅现在可以在任何地方运行,20年后它仍然会运行。

速度

第二个原因是它运行得非常快。不仅是基准测试循环会有空间;而且软件将立即启动,没有隐藏的开销(自动垃圾收集)等。当然,前提是编写高效的C语言,虽然不是很复杂,但确实需要熟练使用该语言,并对基本算法和数据结构有扎实的理解。

易读性

第三个原因是,你自己写的代码,也便于其他人阅读。有些人可能不同意我的观点,他们认为高级语言更易于阅读。从高级语言提供的抽象的意义上说,这是完全正确的,它允许更简洁地表达复杂的思想。一个简单的例子是操作符重载,这样你就可以编写A b * c,而不需要这样add(A, mul(b, c)),或者编一些更冗长的代码:

这对于数学软件来说是特别重要的。因为隐藏细节也会隐藏有用的信息。在面向对象的、内存管理的、操作符重载的语言中,可能被中缀表达式隐藏的信息包括:内存分配的位置和方式;当操作数具有不同类型或涉及到类层次结构时,如何解决以及如何进行强制转换;使用的什么算法来执行算术操作。中缀表达式通常有助于理解代码的意图,但看似冗长的表示法可能更有利于对性能的推理和处理抽象中的缺陷。简而言之,当实现细节很重要的时候,C语言可以使实现细节变得清晰。

从这个角度来看,C对命名空间、重载和泛型等便利的省略实际上是一种特性,而不是bug。想知道任何给定的C代码在做什么往往是一个简单的过程,函数和类型都是透明的(使用grep)。我不记得自己在钻研别人的C代码或阅读很久以前写的C代码时遇到过什么困难。即使是像相当密集和特殊的Pari/GP这样的代码库,经过短暂的熟悉过程也可以理解。但对于Python来说就不是这样了,例如,它很难理解哪个类上的哪个方法被调用,以及如何、何时以及在什么上下文中被调用。

教育价值

第四个原因是,在编写C语言的过程中,你会学到很多东西。用C语言而不是更高级的语言来实现算法可以让你有更深的理解,因为你需要自己做更多的基础工作。你也可能需要更仔细地考虑事情。当我编写Python时,通常可以很快实现一些不完整的功能,然后一点一点地修复它,但C语言会经常迫使我在一开始就正确。

为什么不使用C语言

接下来是对C语言的弱点进行公平和客观的评估。

数学理解

由于我们谈论的是数学软件,那么实现XYZ实际上涉及到两个问题:一是理解XYZ的数学问题;二是将这种理解转化为具体的算法和代码。如果你不懂数学,最好使用高级语言来探索这个问题。

可移植性和部署

在实践中,关于C语言惊人的可移植性的说法有些言过其实。作为一名C程序员,你会发现对于不同的操作系统和硬件配置,构建的系统或标准库执行结果不一致,偶尔也会遇到编译器错误(尽管C语言算是在这方面做得比较好了)。这样以来,渐渐地你的头文件可能会积累数百个#ifdef,以解决可能存在也可能不存在的兼容性问题。

其实大多数潜在用户可能无法或不愿意从源代码构建和安装库,因此您要么自己发布binaries文件,要么依赖于第三方软件包库发布。出于稳定性的考虑,或者因为缺乏人力,这样的软件库通常1-10年都不会更新。换句话说,您不能指望用户实时访问库中的最新特性和进行bug修复,所以试图保持向后兼容性。

还有一个好主意是将您的数学库导入SageMath。SageMath由一个大型社区维护,并在许多平台上进行测试,SageMath中的包通常几个月更新。

用更现代的编程语言编写的软件通常部署更容易,因为它们有更健全的构建过程和标准库,避免了大多数C平台相关的麻烦。如今,许多语言也有它们自己易于使用的打包系统和集中的包存储库。在实践中,目前可移植性最好的易于分发的语言可能是JavaScript和Python。Julia也不相上下,而且在许多方面设计得比Python更好,不过Python可以预先安装在许多系统上。如果你认为基于浏览器的界面比以传统方式将库和运行代码链接在终端上更有意义,Emscripten也是一种很好的C代码发布方法。

安全性

C语言经常以漏洞百出、容易崩溃甚至灾难性的安全问题而出名。包括它的手动内存管理、弱符号系统等。但我认为问题通常与C语言本身无关,而是存在一些糟糕的历史代码和库(包括C的标准库)。我相信C语言的弱点可以通过良好的基础和现代的软件开发实践来克服。然而,C语言经常需要开发人员付出大量的努力,来避免许多其他语言中不存在的bug,这一点是毋庸置疑的。

使用C语言的主要安全问题在于,要防范各种形式的错误输入是极其困难的。幸运的是,我开发的数学软件不像网络软件、内核驱动程序等是安全至上的,数学软件通常是由受信任的用户在受控环境中运行,并将合理的数据作为输入(这显然不包括专门为在战场上进行加密而设计的数学软件)。

换句话说,我们需要保证正确输入下结果的正确性,不正确输入的安全性并不是优先考虑的问题。相反,我们让用户承担输入的责任。但要C代码完全不受错误输入的影响,需要大量的工作;在其他自动捕捉整数溢出和越界访问的语言中,这要容易得多。

泛型

C语言是最适合编写处理特定类型数据的特殊函数。C语言特别缺乏对泛型编程的内置支持(允许单个函数处理多种类型的数据)。据我所知,C语言有四种基本的泛型编程方法,但没有一种是完美的:

使用宏的静态(编译时)泛型。

使用函数指针的动态(运行时)泛型。

God-objects:使用一种数据类型,但要使其具有足够的通用性,以表示所需的任何类型的数据。

使用c 。

前三种方法的泛型编程,会牺牲代码的清晰性,并丢失掉C(公认的)类型系统中提供的许多正确性和文档优势。最好的建议是,如果你需要泛型,最好避免使用C语言;要么在需要的每种类型中重复使用功能,或使用其他语言。如果您有特定需求,则用C实现自己的对象系统是有意义的,但如果您的目标只是为了能够编写泛型函数,那么这是一个糟糕的想法。

我不喜欢c ,但是c 标准模板库中的泛型集合非常简洁(出于这个原因,我已多次使用c 了)。上面的第四点并不完全是一个笑话;您当然可以编写“C-style”c 。

还有一种可能是用C编写专门的代码,并通过高级语言与之交互以进行泛型编程。这基本上就是我们最终使用Flint所做的事情。Flint为每种数学方法实现了一个C类型:fmpz_t for \mathbb{Z}Z、 fmpz_poly_t for \mathbb{Z}[x]Z[x]、fmpq_t for \mathbb{Q}Q、fmpq_poly_t for \mathbb{Q}[x]Q[x]等等,并且每种操作(加法、乘法、赋值、打印等)都需要针对C中的每种类型分别实现。出于性能原因,算法倾向于针对每种类型进行专门处理,因此涉及的代码重复性比听起来少,但显然我们不想将数以百万计的新类型添加到flint中,以涵盖数学家写下的所有代数结构,我们也不想对已有的每种类型做数百个数学运算。幸运的是,现在我们可以为大多数Flint类型提供Julia封装器,您可以使用Julia来实现更多的通用算法。Python中也有Python-Flint,SageMath封装了一些Flint类型。

并行性、内存管理

关于C语言中的多线程,类似的话是:可行,但不方便。使用C进行并行计算的最简单方法是编写单线程代码,并将输入拆分为可以在单独进程中运行的独立批处理作业。幸运的是,数学计算问题通常本质上是大规模并行的,因此这往往效果很好。您还可以用C编写线程安全内核函数,并使用高级语言封装器实现线程级并行。对于异构并行计算、gpu等,如果您拥有实现它的专业知识,C也许是值得的,但是硬件和外部工具的变化速度可能比您适应代码的速度要快得多。

内存管理本身就是一堆麻烦。如果你能按照时间和空间对数据进行分层结构化,从而很明显的分配和释放内存,例如根据需要自动调整字符串或数组的大小,那么C就能很好地工作。如果您需要对象相互交叉引用,尤其是在生命周期不可预测的情况下,那么使用具有自动内存管理的语言将会非常方便。根据我的经验,C语言的手动内存管理在99%的情况下都很简单,只是冗长乏味。当然,您的情况可能有所不同。

开发时间

总体而言,用C实现东西并不一定比其他语言难,但通常需要很多时间。如果你喜欢分解问题,然后构建一个解决方案来控制所有细节,并且你有时间这么做,那么C是一种很好的语言。如果你只是想快速完成任务,那就不用想那么多了。我通常喜欢将想法转化为C语言的智力挑战,但这有时是一件苦差事。

对C语言开发的几点建议

你决定写C,太好了!你怎样才能避免搬起石头砸自己的脚,或者更好地实现你的目标呢? 互联网上有很多学习C语言的资源,下面是个人的一些建议。

文档

首先,如果有代码,就应该有文档。或许文档在您的工作中并不是必须的,但这真的很重要。我见过太多糟糕的项目文档。如果有一个函数,我想知道它的输出是什么,它对输入做了什么假设,以及在什么情况下使用了什么算法。完整的API文档是最低要求,强烈建议即使你只是为自己编写代码也应该这么做;对于用户,您还需要在文档中陈述详尽的示例代码、教程和一般说明。现在就着手为自己的代码编写文档吧,虽然一开始它并不完美,但可以作为一个起点。

版本控制和构建系统

使用版本控制(例如git)自动构建系统和持续集成。想必大家都很了解了。一旦有了稳定的代码库,测试、集成、发布新版本就应该有版本控制。而在git中更新版本号、变更日志、标记版本显得容易许多。

组织代码

因为C提供的内置功能很少,而且它提供的许多工具都是有缺陷的,您如果用C语言进行软件开发,不能只是为了实现最终目标功能。你必须从基础做起,首先构建架构,然后在此基础上来构建特性。

实际上,您可能需要实现自己特定的C“方言”,包括非正式的编码约定(如何命名,如何进行内存管理等等),以及用于基本功能的自定义“标准库”。如果您为现有项目做开发,则不必从头开始做所有这些工作,但您需要花一些时间来学习该项目的C“方言”。毋庸置疑,在任何语言中,一致的编码约定都是一个好主意:其优点不仅在于整洁而统一的代码库更易于理解,而且当你有了一个约定好的构造代码的思维模板时,就不需要浪费时间去考虑其他的组织方式。

下面举一个例子,让我们看看项目中Flint家族的代码的组织方式(包括Flint、Arb、Antic、Calcium)。其他C项目的组织方式可能与此完全不同,而且这只是不同的编码风格而已,不存在孰优孰劣。

首先,Flint在Flint.h和几个相关的头文件中定义了一些全局函数。包括下列各项:

版本号。

内存分配函数。

类型定义和支持32位/64位系统的宏。

自定义打印函数。

生成随机数的函数。

线程助手。

用于声明、交换变量以及MIN/MAX/ABS等宏。

位计数,溢出检查等功能。

基于堆栈的安全临时分配的宏。

GMP函数库,以解决不同系统上的兼容性问题。

用于分析和测试代码的助手。

任何大型C项目都可能需要类似的支持代码。在其他使用Flint作为基础库的项目中,因为所有这些基本功能都可以从flint.h中导入,所以从头开始需要做的工作就少了很多。

Flint是模块化的组织方式。大多数模块对应于一种数学类型。每个模块都包含一个头文件(fmpz_poly.h)以及源文件目录(fmpz_poly/add.c、fmpz_poly/mul.c等)和测试文件(fmpz_poly/test/t-add.c、fmpz_poly/test/t-mul.c等)。文档中每个模块都有自己的页面来描述完整的API。

通常,每个公共功能(比如fmpz_poly_add)都有自己的文件,并有一个相应的测试程序,其文件名与函数名称相对应。每个函数对应一个文件似乎有些小题大做,但当模块中有100多个公共函数时,这确实有助于使代码井井有条并易于浏览。

Flint定义了fmpz_poly_t类型如下:

该结构包含一个指向fmpz类型(Flint任意大小的整数类型)的系数数组的指针,关于数组分配大小的信息,以及关于数组使用大小的信息(多项式的长度)。下面是关于内存管理的一些注意事项:

最后一行将fmpz_poly_t定义为类型为fmpz_poly_struct、长度为1的数组。这是一个巧妙的C编程技巧,它允许fmpz_poly_t引用传递。

fmpz_poly_t存放了内部分配的所有数据。调用fmpz_poly_set(f,g)创建g的副本。

fmpz_poly_t类型会自动管理数组大小,这样操作起来会安全得多。

在内部,许多Flint函数都对原始系数数组进行操作,而不是对fmpz_poly_t对象进行操作。事实上,大多数函数都有两个版本:比如fmpz_poly_add具有相应的内部下划线版本“_fmpz_poly_add”。下划线版本执行实际的计算,它将原始系数数组(指针)及其大小作为输入,并对数据进行某些假设;非下划线版本是一个处理特殊情况的封装器,确保在调用下划线方法之前输出正确的数组。下划线方法更适合内部使用,因为他们开销较小,无需复制数据即可用来处理多项式,但非下划线方法更适合做公共API。

使用fmpz_poly_t类型的代码如下:

按照惯例,首先使用输出变量调用Flint函数,然后使用const输入变量以及可能的其他参数来调用。内存管理很简单:用户调用init方法来初始化对象,并在完成后调用clear。这些操作几乎总是在同一个函数或代码块的开头和结尾成对出现。在此期间,可以将这个初始化的对象传递给函数进行读写,而不是让函数返回新对象会极大的提高性能:避免分配/初始化/复制对象可以轻松地将代码速度提高两倍或更多。C语言趋于“快”的一个主要原因是这类代码是惯用的,而许多高级语言中的自动内存管理工具和对象系统却鼓励类似的初始化/副本。

Flint中的许多操作都有几种不同的算法。例如有多种版本的多项式乘法:fmpz_poly_mul_classical(经典乘法)、fmpz_poly_mul_karatsuba (Karatsuba算法)、fmpz_poly_mul_KS(Kronecker分段)和fmpz_poly_mul(Sch??nhage-Strassen算法)。这对于数学软件来说是非常典型的设计。Flint的设计决策是所有方法都是公共的:所有可选的乘法函数和文档都是公共API的一部分。实际上,我们为用户和开发人员提供了相同的API。这使得测试代码更容易(例如对各种算法进行基准测试),并且如果专业的用户所了解的算法比默认算法更多时,他们可以编写一个特定的算法。我相信这也为新贡献者降低了入门门槛。

Flint、Arb、Antic和Calcium中的大多数模块在命名空间、组织文件、调用函数、管理内存等方面都遵循相似的约定。这些项目总共有大约80万行代码,但是这些代码的结构复杂性加在一起差不多是单个模块大小的1/100。当你仔细观察时,这些项目就像任何软件一样,几乎没有任何不一致和令人遗憾的设计错误。总体而言,Flint在10年来保持了良好的发展。

测试代码

测试代码甚至比文档更重要。正如布鲁斯·埃克尔(Bruce Eckel)所说:“如果不进行测试,它就会坏掉。”

测试数学软件相对容易,因为数学运算往往是定义明确的,从而提供了明显的检查方式。Flint在很大程度上依赖于随机单元测试,大多数测试代码使用两种或两种以上不同的方式(例如使用泛函方程、交换参数的顺序、改变精度或其他算法参数)计算相同的数学策略,并验证结果是否一致。例如,要测试多项式乘法函数,我们可以生成随机输入多项式,并检查诸如 A(B C) = AB AC、A(BC) = (AB)C等属性。

有效的测试是一门艺术,也是一门科学。错误往往发生在输入的临界处,因此非均匀地生成随机输入非常重要。GMP、Flint、Arb为每种类型提供随机生成函数,旨在产生良好的测试输入:稀疏对象,具有多个零的对象,具有很多小因子的对象,根本没有任何因子的对象,量级很小的对象,量级很大的对象等等。设计好的测试用例和选择好的测试参数是很棘手的。一个久经考验的策略是故意在代码中引入错误,特别是对代码的所有关键部分,要进行迭代测试。当然,速度是一个重要因素,某些函数可能需要运行数千或数百万次的测试迭代,但这就得花几个小时来完成,所以最好测试少量输入。除非是大量输入时才会出现问题的算法。

原型设计和交互测试

相对来说,用C进行交互测试或快速创建原型比较困难。有针对C语言的REPL工具,但在我看来它们不是很有用。原因是C语言的冗长性和手动内存管理不利于REPL的使用。

我有两种解决方案:第一个是建立一个非常容易运行C程序的环境。就我个人而言,我在~/src/test有一个“scratch”目录,如果我需要快速测试某些想法或为某些功能创建原型,我在这个目录中创建了一个.c文件。当我有了可行的、相当干净的代码时,我会将它迁移到实际的项目目录中(例如~ / src / arb),并将其置于版本控制之下。我从不急于删除或整理旧的缓存文件。到现在,~/src/test包含了约800个可追溯到2014年的.c文件,其名称包括bundesliga.c(Calcium的对数的旧测试代码),megamul.c(测试矩阵乘法算法的代码)和agamemnon.c(Arb的Legendre多项式求值的早期版本)。如果我需要重温一些旧的想法,可以只搜索文件内容。在scratch目录中,我保存了一些可以轻松地运行C文件的脚本。例如,我使用下面名为go的shell脚本来测试Arb文件:

运行./go foobar.c,如果它不是最新的,则需要重建Arb,然后编译运行(以确保我不会意外地测试错误版本)。编译运行周期只需要几分之一秒,基本上和交互式REPL一样快,但这种设置对我来说效果很好。

第二种解决方法是使用其他语言。为了测试Flint和Arb的新功能并为其设计原型,我一般使用Python或Julia,偶尔使用SageMath。我习惯用Python也主要使用Python,因为Julia有烦人的JIT编译延迟。我大约50%的工作使用基于终端的REPL,其余时候使用Jupyter notebook。现在,实际上很多好的Calcium永久测试代码都是用Python编写的,这使得某些类型的测试比只使用C时容易得多。

很难就如何实现数学算法给出一般性建议,因为我自己的工作流程差异很大。有时,我只是在没有任何原型的情况下开始用C编程;有时,我用Python编写一个完整的功能,在确保Python版本完全正确的情况下再将其逐字转换为C。后一种方法对于容易出错的复杂算法是有用的,Python对于C代码也有非常宝贵的参考价值。

调试工具

我个人不大使用像GDB之类的调试器,我习惯使用Valgrind。Valgrind是一款出色的软件,可以通过在运行时检测内存错误来在很大程度上弥补C语言中内存安全性的不足。Valgrind将检测程序何时读取未初始化的内存、何时读取内存分配,或者内存泄漏等。Valgrind还可以用于分析代码和检测其他类型的错误。

Valgrind相当具体地显示了关于问题在哪里以及如何发生的信息,这样修复bug就比较简单。事实上,Valgrind能够很好的捕捉内存泄漏,可以说用C/Valgrind编写无泄漏的软件比用某些具有自动内存管理的语言更容易。您也可以将Valgrind与其他语言一起使用,但必须理解该语言的内存管理器(而不仅仅是知道自己的代码在做什么),否则调试代码将变得更加困难。

我总是使用Valgrind运行新的测试代码。可能因为Valgrind很少误报,而且Valgrind的输出是完全合理的。我印象中的一个误报例子(也算是正确的误报):Valgrind报告说某些GMP汇编函数无法在某些计算机上读取。Valgrind实际上在技术上是正确的(GMP确实读取溢出),因为一些微妙的原因(由于数据对齐的复杂性,它的边界读取是有意且安全的),GMP也是正确的。

需要强调的是,Valgrind仅检测某些特定类型的bug,并且仅检测实际由测试触发的bug,所以只有结合高质量的测试代码,Valgrind才会有效。认真对待软件正确性和安全性的开发人员,还应该考虑使用工具来进行静态代码分析、形式验证、模糊测试。我对此类工具的经验要少得多。我尝试在Arb上运行程序,没有发现任何错误(除了一些误报)。这并不是因为我编写了无bug的C代码,而是因为我一直在努力编写测试代码并运行Valgrind。话虽如此,有些更精通C/C 的程序员,他们笃信静态分析工具,对于那些负担得起的人来说,专业工具显然比免费工具更好。

保持简单性

在文章最后,提供一些个人的建议供您参考:

对函数使用描述性的名称。

避免使用复杂的宏。

当数据具有某些不变性时,将其封装为一种类型。

无分支的多行代码比具有复杂分支条件的少行代码要好。

如果区分大小写仅产生很小的差异,考虑消除差异。

使用函数式方法。

使用简单的数据结构。

除非必要,否则不要缓存数据。

原始指针通常是好的,可以接受指向指针的显式指针。

选择任何可以带来更简单界面的选项。

替代C

如果不是C,你应该用什么?

如果你想要更高层次的、更数学化的、更函数化的、更面向对象的或者更动态的东西,那么这个问题太宽泛了,无法回答。您必须研究不同语言的特性,选择一种适合您的语言。

如果您想要C语言的性能和可移植性,那么选择就更少了。只要符合您的审美情趣,C 是显而易见的选择。Fortran和C一样成熟,对于纯粹的数值应用程序来说非常出色。目前为止,对我个人来说,最有希望取代C语言的竞争者是Zig,但这只是我自己的想法(我还没试过用它)。D和Rust看起来也可以,比C更符合C 。使用Zig、D或Rust代替C或C 的一个缺点是,潜在贡献者较少,即使是最流行的语言,数学软件开发人员也短缺。Rust和Zig似乎也在迅速发展,势必给C/ C 带来不小的压力。

将C与动态高级语言(Python或Julia等)相结合是一个比较好的解决方案。许多语言都试图实现“两全之美”,但我还没有看到一种语言能真正成功地同时适用于各种编程,也许以后会出现,一起来探索吧!

??Rust 要“进驻” Linux 内核了?Linux 之父:保持观望

??苹果搞“双标”:员工要隐私,工人信息在“裸奔”!

??像 C 一样快,Ruby 般丝滑的 Crystal 发布 1.0 版本,你看好吗?

发表评论

登录后才能评论