哪些数据结构和算法不能在C语言中实现？

Question

哪些数据结构和算法不能在C语言中实现？

8

这可能听起来有些幼稚，但是在足够的代码基础上，是否有任何数据结构/算法不能在C中构建？我理解图灵完备的论点。我也知道拥有优雅的解决方案以及时间复杂度的重要性（即在Ruby / Java / C# / Haskell / Lisp中实现更具表现力或简洁）。我研究或使用过的所有语言似乎都是基于C编译器、解释器和/或虚拟机创建或随后重构的。一些复杂的数据结构只能通过解释器和/或虚拟机实现吗？如果该虚拟机或解释器是基于C的，那么这不就是底层C代码的另一种数据结构抽象吗？即C具有简单的类型系统，但作为动态类型系统的基础。我惊讶地发现可以使用预处理器（ioccc.org Immanuel Herrmann）在C中实现元编程。我还看到了一些迷人的C算法，模仿Erlang的并发模型，但不记得来源了。

这个问题的灵感来自于StackOverflow帖子（不太知名但有用的数据结构）和Patrick Dussud在channel9上的采访（垃圾回收 - 过去、现在和未来），解释了他们如何编写第一个CLR垃圾回收器（用Lisp编写，针对JVM，从Lisp编译为C++用于CLR）。

所以说，归根结底，在我完成打卡后，我想这个问题可能更多地涉及C编程语言设计，而不是编程方便性和时间复杂度。例如，我可以在Prolog中实现一个非常优雅且难以通过其他方式理解的高度复杂的算法，但我仍然受限于另一端的汇编指令和计算机架构（开/关），所以我会在这里待一整晚。

- Stix

在C语言中可能没有什么是做不到的，但有很多情况下，纯粹的C语言都不是一个好选择，因为它要么太原始和昂贵难以编写，要么太危险和容易出错。 - Hot Licks

@ooga - 这是一个语音合成应用程序。 - Hot Licks

@EricLippert - 我大致理解它的意思。我对图灵机的限制感到困惑（例如http://en.wikipedia.org/wiki/Turing_machine似乎暗示它们不能很好地模拟计算复杂性或并发性）。从技术上讲，丘奇-图灵论题是一个猜想/假设（尽管在表征有效可计算函数时已被证明为公理http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146.5402）。我理解你的观点，只是想知道在C不再是选项（香草或作为中间目标）之前我可以抽象多高？ - Stix

@HotLicks - 不是语音应用程序，而是非常复杂的图论和物理学。 - Stix

1

基本上，如果你不能用C语言做到它（且问题不是由于需要访问机器级别的汇编），那么你就无法用任何其他语言做到它。 - Hot Licks

显示剩余3条评论

3个回答

5

任何图灵完备的机器或语言都可以实现任何其他图灵完备语言，这意味着如果没有其他方法，它可以通过解释来实现任何其他图灵完备语言中的任何程序。所以你正在问的问题是不合适的；问题不在于任务是否能够完成，而在于你必须付出多少努力才能完成它们。

特别是C语言几乎可以被看作是“高级汇编语言”，因为它会让你得逞于许多最新的语言无法做到的事情，因此可能允许更难以在更强大的检查语言中实现的解决方案。

这并不意味着C语言是所有这些目的的最好语言。它迫使你在许多领域（从内存管理到边界检查到面向对象）付出更多的注意细节（你可以在C中编写OO代码，但你必须从头开始实现）。你必须明确地加载和调用库，而这些库在其他语言中可能已经内置了。C数据类型可能非常复杂（尽管typedefs和macros可以隐藏大部分复杂性）。等等。

任何任务的最佳工具是（a）您已经或可以变得熟悉的工具；（b）适合当前任务的工具；（c）您可以使用的工具。

- keshlam

感谢回复，关于C语言的许多优点都很棒。 - Stix

1

看一下图灵完备性：图灵完备性

基本上，任何图灵完备的语言都可以执行所有图灵可计算的函数。C语言是一种图灵完备的语言，因此理论上你可以用C语言实现任何已知的可解算法（尽管可能效率非常低）。

- George

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Niklas B. · Accepted Answer

Shor算法用于在O((log n)^3)的多项式时间内分解整数，但C语言无法实现，因为它需要运行的计算机尚未正式存在。也许将来会有一个量子电路完整版本的C语言，我将不得不修改我的回答。

开玩笑的说，我认为没有人能给你一个令人满意的答案。我会试着覆盖一些方面：

普通的标准C语言可能无法充分利用处理器的全部功能集。例如，您无法显式地使用最新英特尔处理器的TSX功能。当然，您可以通过操作系统原语、内联汇编、语言扩展或第三方库来规避这种限制。
C语言本身并不擅长并行/异步/并发/分布式编程。在这个领域中，一些可能会使很多任务变得无限容易的语言包括Haskell（也许很快就会有Data Parallel Haskell？）、Erlang等，它们提供非常快速和轻量级的线程/进程以及异步I/O。在C语言中使用绿色线程和大量的异步I/O可能不太愉快，尽管我相信它是可以做到的。
最终，在用户级别的事情上，当然您可以用任何其他语言来模拟每个图灵完备的语言，正如您所正确指出的那样。