algorithm - 优化算法 : Fastest Way to Derive Sets

Question

我正在为比赛编写程序，我需要比所有其他参赛者都快。为此，我需要一些算法帮助；理想情况下，我会使用最快的算法。

对于这个问题，我得到了两件事。第一个是元组列表，每个元组恰好包含两个元素(字符串)，每个元素代表一个项目。第二个是一个整数，表示总共有多少个唯一项。例如:

项目数 = 3

[("球","椅子"),("球","盒子"),("盒子","椅子"),("椅子","盒子")]

相同的元组可以重复/它们不一定是唯一的。)我的程序应该计算出当项目被分为两组时可以“一致”的最大元组数。这意味着，如果将所有项目分成两个理想的组，第 1 组和第 2 组，那么第一个项目在第 1 组中，第二个项目在第 2 组中的元组的最大数量是多少。

例如，我之前示例的答案是 2，“球”在第 1 组，“椅子”和“盒子”在第 2 组，满足前两个元组。我不一定需要知道哪些项目属于哪个组，我只需要知道满意的元组的最大数量是多少。

目前我正在尝试一种递归方法，但它在 (n^2) 上运行，在我看来效率太低了。有没有人有可以产生更快算法的方法？

谢谢!!!!!!!!!!!!

Answer 1

加快完成任务的速度:

<强>1。使用整数

将字符串转换为整数(将字符串存储在数组中并使用元组的位置。

String[] words = {"ball", "chair", "box"};

在 tuppls 中，球现在有编号 0(数组中的位置 0)、椅子 1、盒子 2。比较整数比字符串更快。

<强>2。避免递归

由于递归开销，递归很慢。
例如，查看递归实现中的二进制搜索算法，然后查看 java 如何实现 binSearch()(使用 while 循环和迭代)

如果问题非常复杂以至于非递归实现对于人脑而言过于复杂，则递归很有用。

迭代速度更快，但在您通过实现自己的堆栈来模仿递归调用的情况下则不然。

但是你可以开始使用递归算法来实现，一旦它工作并且它是一个合适的算法，然后尝试转换为非递归实现

<强>3。如果可能的话，避开物体

如果你想要最快的，现在它变得丑陋了!

tuppel 数组可以存储在类 Point(x,y) 的数组中，或者可能更快，作为整数数组:
例子:(1,2), (2,3), (3,4) 可以存储为数组:(1,2,2,3,3,4)这需要更少的内存，因为一个对象至少需要 12 个字节(在 Java 中)。更少的内存变得更快，当数组非常大时，您的结构有望适合处理器缓存，而对象数组则不会。

<强>4。编程语言

在 C 中它会比在 Java 中更快。