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

 

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

什么启发了这个问题是StackOverflow文章（较小已知的有用数据结构）和Patrick Dussud在channel9（垃圾收集 - 过去，现在和未来）的采访 - 解释他们如何编写第一个CLR垃圾收集器（用Lisp编写，目标是JVM ，从CLP编译到C ++用于CLR）。

所以，在一天结束的时候，在我完成冲卡之后，我想知道这个问题可能是关于C编程语言设计的，而不是编程的方便性和时间复杂性。 例如，我可以在Prolog中实现一个高度复杂的算法，该算法非常优雅，并且很难用其他任何方式表达，但是我仍然受限于组装指令和计算机体系结构（开/关）棒，所以我会在这里整夜。

Shor在O((log n)^3)多项式时间中因式分解整数的算法不能在C中实现，因为它可以运行的计算机尚未正式存在。 也许有一天会有C的量子电路完整版本，我将不得不修改我的答案。

一边开玩笑，我认为没有人能给你一个令人满意的答案。 我将尽力涵盖一些方面：

  • 香草，标准C可能无法使用处理器的整个功能集。 例如，您无法明确使用最新Intel处理器的TSX功能。 您当然可以诉诸操作系统原语，内联汇编，语言扩展或第三方库来规避这种情况。
  • C本身并不擅长并行/异步/并发/分布式编程。 在这方面可能使得许多任务无限轻松的一些例子是Haskell（也许Data Parallel Haskell很快？），Erlang等，它们提供了非常快速和轻量级的线程/进程和异步I / O。 在C中使用绿色线程和严重异步I / O可能不太愉快，尽管我确信它可以完成。
  • 最后，在用户级别上，当然你可以用任何其他的模拟Turing完整的语言，正如你指出的那样正确。

    • 任何图灵完整机器或语言都可以实现任何其他图灵完备语言，这意味着如果没有其他方式，它可以通过解释来实现任何其他图灵语言的程序。 所以你问的问题是不健全的; 问题不在于是否能够完成任务，而在于如何努力完成任务。

    特别是C语言几乎作为“高级汇编语言”起作用，因为它可以让你摆脱许多更新近的语言所不具备的东西，从而可能允许在更强大的检查中实施起来更困难的解决方案语言。

    这并不意味着C是适合所有这些目的的最佳语言。 它迫使你在从内存管理到边界检查到面向对象的许多领域（你可以用C语言编写OO代码，但必须从头开始实现）来更多地关注细节。 您必须显式加载和调用库，以获得可能构建到其他语言中的内容。 C数据类型可能令人难以置信地复杂化（尽管typedef和宏可以隐藏很多复杂性）。 等等。

    对于任何给定的任务来说，最好的工具是（a）你或者可以变得舒适的; （b）非常适合手头的任务，并且（c）您有空。

    看看图灵的完整性：图灵的完整性

    基本上，任何Turing完成的语言都可以执行所有图灵计算功能。 C是一种图灵完备语言，所以理论上你可以在C中实现任何已知的可解算法（虽然它可能非常低效）。

    链接地址: http://www.djcxy.com/p/39847.html

    上一篇: What data structures and algorithms are not implementable in C?

    下一篇: State