1

Here's the scenario.

I have one hundred car objects. Each car has a property for speed, and a property for price. I want to arrange images of the cars in a grid so that the fastest and most expensive car is at the top right, and the slowest and cheapest car is at the bottom left, and all other cars are in an appropriate spot in the grid.

What kind of sorting algorithm do I need to use for this, and do you have any tips?

EDIT: the results don't need to be exact - in reality I'm dealing with a much bigger grid, so it would be sufficient if the cars were clustered roughly in the right place.

4

8 回答 8

7

只是受Cantor 先生启发的一个想法：

  • 计算最大（速度）和最大（价格）
  • 将所有速度和价格数据标准化到 0..1 范围内
  • 对于每辆车，计算“距离”到可能的最大值

基于 a²+b²=c²，距离可能类似于

sqrt( (speed(car[i])/maxspeed)^2 + (price(car[i])/maxprice)^2 )

根据需要（视觉上）应用加权

  • 按距离排序汽车
  • 将“最佳”汽车放在“最佳”广场（在您的情况下位于右上角）
  • 以之字形走网格并在排序列表中填充下一辆车

结果（镜像，左上角最好）：

1 - 2   6 - 7
  /   /   /
3   5   8
| /
4
于 2010-01-08T12:35:05.557 回答
5

将此视为两个问题：

1：生成排序列表 2：将排序列表的成员放入网格

排序只是您更精确地定义规则的问题。“最快最贵的优先”是行不通的。首先是我的 100,000 英镑的劳斯莱斯，最高时速 120，还是我的升级版 Mini，价格为 50,000 英镑，最高时速 180？

拿到清单后，你将如何填写？第一个和最后一个很容易，但是第二个去哪里呢？沿着顶部还是向下？那么接下来在哪里，沿着行，沿着列，之字形？你必须做出决定。之后编码应该很容易。

于 2010-01-08T11:51:35.443 回答
2

我想你想要的是让具有“相似”特征的汽车聚集在附近，而且成本通常会向右增加，而速度通常会向上增加。

我会尝试以下方法。假设你有 N 辆汽车，你想把它们放在 X * Y 网格中。假设 N == X * Y。

  1. 将所有 N 辆汽车放在网格中的随机位置。
  2. 定义一个计算网格中总的错误排序的度量；例如，计算汽车对 C1=(x,y) 和 C2=(x',y') 的数量，使得 C1.speed > C2.speed 但 y < y' 加上汽车对 C1=(x,y)和 C2=(x',y') 使得 C1.price > C2.price 但 x < x'。
  3. 运行以下算法：
    1. 计算当前的无序度量 M
    2. 枚举网格中的所有汽车对并计算交换汽车时获得的排序错误度量 M'
    3. 交换最能降低指标的汽车对（如果找到任何这样的汽车对）
    4. 如果您交换了两辆车，请从步骤 1 开始重复
    5. 结束

这是优化问题的标准“局部搜索”方法。您在这里所拥有的基本上是一个简单的组合优化问题。另一种尝试的方法可能是在矩阵中使用具有预置速度和成本梯度的自组织映射 (SOM)。

于 2010-01-08T20:13:30.210 回答
1

Basically you have to take one of speed or price as primary and then get the cars with the same value of this primary and sort those values in ascending/descending order and primaries are also taken in the ascending/descending order as needed.

Example:

c1(20,1000) c2(30,5000) c3(20, 500) c4(10, 3000) c5(35, 1000)

Lets Assume Car(speed, price) as the measure in the above list and the primary is speed.

1 Get the car with minimum speed

2 Then get all the cars with the same speed value

3 Arrange these values in ascending order of car price

4 Get the next car with the next minimum speed value and repeat the above process

c4(10, 3000)
c3(20, 500)
c1(20, 1000)
c2(30, 5000)
c5(35, 1000)

If you post what language you are using them it would we helpful as some language constructs make this easier to implement. For example LINQ makes your life very easy in this situation.

cars.OrderBy(x => x.Speed).ThenBy(p => p.Price);

Edit:

Now you got the list, as per placing this cars items into the grid unless you know that there will be this many number of predetermined cars with these values, you can't do anything expect for going with some fixed grid size as you are doing now.

One option would be to go with a nonuniform grid, If you prefer, with each row having car items of a specific speed, but this is only applicable when you know that there will be considerable number of cars which has same speed value.

So each row will have cars of same speed shown in the grid.

Thanks

于 2010-01-08T11:43:22.847 回答
1

10x10 约束是否必要？如果是，您必须有十个速度和十个价格，否则图表将没有多大意义。例如，如果最快的车不是最贵的会怎样？

我宁愿建议您使网格大小等于

  (number of distinct speeds) x (number of distinct prices),

那么这将是一个（相当）简单的按两个轴排序的情况。

于 2010-01-08T11:58:21.467 回答
0

如果数据源自数据库，那么您应该在从数据库中获取它们时对它们进行排序。这应该只意味着ORDER BY speed, price在查询末尾附近添加，但在LIMIT部分之前（其中“速度”和“价格”是相应字段的名称）。

正如其他人所说，“最快和最昂贵”是一件很难做到的事情，你应该先挑一个来排序。但是，可以使用此算法进行近似：

  1. 找到最高的价格和最快的速度。
  2. 将所有价格和速度标准化为例如 1 的一小部分。您可以通过将价格除以在步骤 1 中找到的最高价格来做到这一点。
  3. 将标准化价格和速度相乘以创建一个“价格和速度”数字。
  4. 按此编号排序。

这确保了汽车 A 比汽车 B 更快且更昂贵，它会在列表中领先。一个值较高但另一个值较低的汽车会被粗略分类。我建议将这些值存储在数据库中并根据您的选择进行排序。

将它们放在 10x10 的网格中很容易。开始输出项目，当你达到 10 的倍数时，开始一个新行。

于 2010-01-08T12:10:56.310 回答
0

另一种选择是对0 .. 200%每辆车应用一个分数，并按该分数排序。

例子： 

score_i = speed_percent(min_speed, max_speed, speed_i) + price_percent(min_price, max_price, price_i)
于 2010-01-08T12:11:02.643 回答
0

嗯...一种冒泡排序在这里可能是简单的算法。

  1. 制作一个随机的 10x10 数组。
  2. 找到两个“顺序错误”的邻居（水平或垂直），并交换它们。
  3. 重复（2）直到找不到这样的邻居。

两个相邻元素在以下情况下处于“错误顺序”：a）它们是水平相邻元素，左侧元素比右侧元素慢，b）它们是垂直元素元素，顶部元素比底部元素便宜。

但我实际上并不确定这个算法是否对每个数据都停止。我几乎可以肯定它很慢:-)。它应该很容易实现，并且经过一些有限次数的迭代后，部分结果可能足以满足您的目的。您也可以从使用此处提到的其他方法之一生成数组开始。它还将保持您对阵列形状的状态。

编辑：现在证明任何事情都为时已晚，但我在 python 中做了一些实验。看起来可以在几秒钟内以这种方式对 100x100 的随机数组进行排序，并且我总是设法获得完整的 2d 排序（即：最后我得到了错误排序的邻居）。假设 OP 可以预先计算这个数组，他可以将任意合理数量的汽车放入数组中并得到合理的结果。实验代码：http : //pastebin.com/f2bae9a79（你需要matplotlib，我也推荐ipython）。iterchange是那里的排序方法。

于 2010-01-09T01:34:35.747 回答