blocks|key|584574|text|您可以生成较大的(256位)数字并对它们进行分解；这是“压力测试”工具中常用的。如果您特别想练习浮点计算，您可以使用Runge-Kutta积分器构建一个基本的n-body模拟器并运行它。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|584575|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

You could generate large (256-bit) numbers and factor them; that's commonly used in "stress-test" tools. If you specifically want to exercise floating point computation, you can build a basic n-body simulator with a Runge-Kutta integrator and run that.

blocks|key|4367786|text|你能做的是|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4367787|4367788|声明一个整型|ordered-list-item|4367789|的std：：|4367790|，用N-1填充它，继续重复使用std::next_permutation，直到它们再次排序，i..e..next_permutation返回false。|offset|length|style|CODE|4367791|4367792|对于N整数，这将需要O(N+!)计算，而且是确定性的|4367793|entityMap^0|0|0|0|0|2|3|0|0|2|1|A|6|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|T|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|U|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|V|8|@]|9|@]|A|$]]|$1|H|3|I|5|E|7|W|8|@$J|X|K|Y|L|M]]|9|@]|A|$]]|$1|N|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|10|8|@$J|11|K|12|L|M]|$J|13|K|14|L|M]]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|15|8|@]|9|@]|A|$]]]|R|$]]

What you can do is

<ol>
<li>Declare a std::vector of int</li>
<li>populate it with <code>N-1</code> to <code>0</code></li>
<li>Now keep using std::next_permutation repeatedly until they are sorted again i..e..next_permutation returns false.</li>
</ol>

With <code>N</code> integers this will need <code>O(N !)</code> calculations and also deterministic

blocks|key|893285|text|PageRank可能是一个很好的选择。作为一个线性代数问题，一个人反复地对一个大小可控的浮点矩阵进行平方运算，直到收敛。在图形化的比喻中，一个“涟漪”变化进入每个节点到其他边。这两种处理方法可以并行进行。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|893286|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Page_rank^0|0|8|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

<a href="http://en.wikipedia.org/wiki/Page_rank" rel="nofollow">PageRank</a> may be a good fit. Articulated as a linear algebra problem, one repeatedly squares a certain floating-point matrix of controllable size until convergence. In the graphical metaphor, one "ripples" change coming into each node onto the other edges. Both treatments can be made parallel.

blocks|key|887005|text|你可以做一个最小修剪平方拟合。它的一个用途是识别数据集中的异常值。例如，您可以从一些平滑函数(例如多项式)生成样本，并向一些样本添加(大)噪声，然后问题是找到给定大小的样本的子集H，该子集H最小化残差的平方和(对于H中的样本拟合的多项式)。由于存在大量这样的子集，因此您需要进行大量的拟合！对于这一点，有近似的算法，例如here。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|887006|entityMap|0|LINK|mutability|MUTABLE|url|http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.97.6828^0|4G|4|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

You could do a least trimmed squares fit. One use of this is to identify outliers in a data set. For example you could generate samples from some smooth function (a polynomial say) and add (large) noise to some of the samples, and then the problem is to find a subset H of the samples of a given size that minimises the sum of the squares of the residuals (for the polynomial fitted to the samples in H). Since there are a large number of such subsets, you have a lot of fits to do! There are approximate algorithms for this, for example <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.97.6828" rel="nofollow">here</a>.

blocks|key|893273|text|好的，一种方法是在一些M-空间(M>+1)中实现暴力求解器来解决旅行商问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|893274|暴力解决方案是尝试每个可能的排列，然后计算每个排列的总距离，而不进行任何优化(包括没有像memoization这样的动态编程技巧)。|893275|对于N个点，有(N!)排列(冗余因子至少为(N-1)，但请记住，没有优化)。每一对点都需要(M)减法、(M)乘法和一个平方根运算来确定它们之间的勾股距离。每个排列有(N-1)对要计算的点并与总距离相加。|893276|因此，计算的顺序是O(M((N%2B1)!))，而存储空间只有O(N)。|893277|此外，这既不应该太难，也不应该太密集而不能跨核心并行，尽管它确实需要一些开销。(如果需要，我可以演示)。|893278|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

Well one way to go would be to implement brute-force solver for the Traveling Salesman problem in some M-space (with M > 1). 

The brute-force solution is to just try every possible permutation and then calculate the total distance for each permutation, without any optimizations (including no dynamic programming tricks like memoization). 

For N points, there are (N!) permutations (with a redundancy factor of at least (N-1), but remember, no optimizations). Each pair of points requires (M) subtractions, (M) multiplications and one square root operation to determine their pythagorean distance apart. Each permutation has (N-1) pairs of points to calculate and add to the total distance. 

So order of computation is O(M((N+1)!)), whereas storage space is only O(N).

Also, this should not be either too hard, nor too intensive to parallelize across the cores, though it does take some overhead. (I can demonstrate, if needed).

blocks|key|2900824|text|另一个想法可能是计算分形映射。基本上，选择一个你想要的任何维度的网格。然后，对于每个网格点，进行分形迭代以获得该值。有些点可能只需要几次迭代；我相信有些点将永远迭代(混乱；当然，当您有有限数量的浮点数时，这不会真正发生，但仍然如此)。那些没有停止的，你将不得不在一定的迭代次数后“切断”...只要将其设置得高得离谱，您就应该能够演示高质量的分形贴图。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2900825|这样做的另一个好处是网格单元是完全独立处理的，因此您永远不需要进行通信(甚至不需要在边界处进行通信，就像在模板计算中一样，并且绝对不需要像在直接N-body模拟中那样O(成对地))。您可以使用O(gridcells)个处理器来实现并行化，尽管在实践中，通过使用grid+/factor处理器并在准备就绪的基础上将网格点动态调度到处理器，您可能会获得更好的利用率。计算基本上都是浮点运算。|2900826|Mandelbrot/Julia和Lyupanov被认为是潜在的候选人，但任何人都应该这样做。|2900827|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Another idea might be to compute a fractal map. Basically, choose a grid of whatever dimensionality you want. Then, for each grid point, do the fractal iteration to get the value. Some points might require only a few iterations; I believe some will iterate forever (chaos; of course, this can't really happen when you have a finite number of floating-point numbers, but still). The ones that don't stop you'll have to "cut off" after a certain number of iterations... just make this preposterously high, and you should be able to demonstrate a high-quality fractal map.

Another benefit of this is that grid cells are processed completely independently, so you will never need to do communication (not even at boundaries, as in stencil computations, and definitely not O(pairwise) as in direct N-body simulations). You can usefully use O(gridcells) number of processors to parallelize this, although in practice you can probably get better utilization by using gridcells/factor processors and dynamically scheduling grid points to processors on an as-ready basis. The computation is basically all floating-point math.

Mandelbrot/Julia and Lyupanov come to mind as potential candidates, but any should do.

I am trying to write a demo for an embedded processor, which is a multicore architecture and is very fast in floating point calculations. The problem is that the current hardware I have is the processor connected through an evaluation board where the DRAM to chip rate is somewhat limited, and the board to PC rate is very slow and inefficient.

Thus, when demonstrating big matrix multiplication, I can do, say, 128x128 matrices in a couple of milliseconds, but the I/O takes (lots of) seconds kills the demo.

So, I am looking for some kind of a calculation with higher complexity than n^3, the more the better (but preferably easy to program and to explain/understand) to make the computation part more dominant in the time budget, where the dataset is preferably bound to about 16KB per thread (core).

Any suggestion?

PS: I think it is very similar to <a href="https://stackoverflow.com/questions/8951454/increasing-cpu-rendering-load-in-game-code">this</a> question in its essence.

What algorithms have high time complexity, to help "burn" more CPU cycles?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我正在尝试写一个嵌入式处理器的演示，它是一个多核架构，在浮点计算中非常快。问题是，我目前的硬件是通过评估板连接的处理器，其中DRAM到芯片的速率在某种程度上是有限的，而板到PC的速率非常慢，效率很低。因此，在演示大矩阵乘法时，我可以在几毫秒内完成128x128矩阵，但是I/O需要(很多)秒来完成演示。因此，我正在寻找一种比n^3更高复杂度的计算，越多越好(但最好是易于编程和解释/理解)，以使计算部

问哪些算法具有很高的时间复杂度，可以帮助“燃烧”更多的CPU周期？
EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问哪些算法具有很高的时间复杂度，可以帮助“燃烧”更多的CPU周期？EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问哪些算法具有很高的时间复杂度，可以帮助“燃烧”更多的CPU周期？
EN