重力排序:这可以通过编程实现吗? [英] Gravity Sort : Is this possible programmatically?
问题描述
我最近一直在考虑在排序算法中使用面向对象的设计.但是，我无法找到合适的方法来使这种排序算法在O(n)时间内完成排序.
I've been thinking recently on using the Object Oriented design in the sorting algorithm. However I was not able to find a proper way to even come closer in making this sorting algorithm that does the sorting in O(n) time.
好的，这是我一个星期以来一直在想的事情.我有一组输入数据.我将为每个输入数据分配一个质量(假设输入数据的类型为Mass和类型为Sphere.如果我们假设所有对象都是形状与它们的质量成比例的完全球形的对象，则最重的一个首先.我将所有输入数据都放置在距离地球相同距离的空间中.我会让他们自由落体.根据引力定律，最重的首先撞到地面.他们命中的顺序将给我排序后的数据.从某种程度上讲这很有趣，但是在我下面，我可以使用迄今为止学到的面向对象的方法来实现这一点
Ok, here is what I've been thinking for a week. I have a set of input data. I will assign a mass to each of the input data (assume input data a type of Mass and a type of Sphere. If we assume all objects to be perfectly spherical objects with shapes proportional to their mass, the heaviest one touches the ground first.). I will be placing all my input data in the space all at same distance from earth. And I will make them free fall. According to gravitational law, the heaviest one hits the ground first. And the order in which they hit will give me the sorted data. This is funny in some way, but underneath I feel that this should be possible using the OO that I have learnt till date
真的有可能做出一种使用重力引力的排序技术吗?还是我很愚蠢/疯狂?
Is it really possible to make a sorting technique that uses gravitational pull like scenario or am I stupid/crazy?
编辑:将所有物体同时击中地面，因此我引入了球形物体的概念.
Turns out all objects hit the ground at the same time hence I introduced the spherical object concept.
推荐答案
问题是，尽管OOP的想法之一可能是对现实世界进行建模，但这并不意味着有一个在现实世界中需要花费多长时间与使用计算机进行模拟需要花费多长时间之间存在直接的对应关系.
The thing is, though one of the ideas of OOP may be to model the real world, that doesn't mean there's a direct correspondence between how long something takes in the real world and how long it would take to simulate it with a computer.
想象一下您的程序所需的实际步骤:
Imagine the actual steps required for your procedure:
- 必须为数据集中的每个项目构造一个对象.在大多数现代硬件上，仅此一项就需要迭代，因此会使您的策略O(n)处于最佳状态. .
- 对于每个对象，都需要模拟重力作用.同样，最明显，最直接的实现方法是迭代.
- 必须捕获每个对象降落在编程模型中地球"表面的时间，并且通过某种实现特定的机制，需要将相应的对象插入到有序列表中
考虑到该问题，进一步带来了更多的复杂性.问问自己:您需要将这些对象定位到多高才能开始?显然足够高，以至于最大的一个实际上掉落了；即，离地球比最大物体的半径更远.但是你怎么知道那有多远呢?您需要首先确定集合中最大的对象；再次，这将(可能)需要迭代.同样，人们可能会想像这种仿真可以是多线程的，以尝试仿真实际上掉落的对象概念的实时行为.但随后您可能会发现自己有可能试图在检测到新的冲突的同时将项目添加到集合中(该操作显然花费了非零时间).因此，这也会造成线程问题.
Considering the problem further introduces additional complications. Ask yourself this: how high up do you need to position these objects to start? Obviously high enough so that the largest one actually falls; i.e., farther from the Earth than the radius of the largest object. But how do you know how far that is? You'd need to first determine the largest object in the collection; this, again, would (probably) require iterating. Also, one might imagine that this simulation could be multithreaded to attempt to simulate the real-time behavior of the notion of objects actually falling; but then you will find yourself attempting to add items to a collection (an operation which obviously takes a non-zero amount of time) potentially at the same time that new collisions are being detected. So this will create threading issues as well.
简而言之，我很难想象仅使用OOP而无需特殊硬件就可以正确实现这个想法.也就是说，这确实是一个好主意.实际上，这让我想起了 Bead Sort -一种算法，尽管该算法与您的想法也是一种利用重力的物理概念进行排序的解决方案，毫不奇怪，它需要专用的硬件.
In short, I have trouble imagining how this idea could be properly implemented simply using OOP without special hardware. That said, it really is a good idea. It reminds me, in fact, of Bead Sort--an algorithm which, though not the same as your idea, is also a sorting solution that takes advantage of the very physical concept of gravity and, not surprisingly, requires specialized hardware.
这篇关于重力排序:这可以通过编程实现吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
