0

好吧，这是内幕：我正在用 Java 编写一个类，它可以找到第 N 个Hardy 的出租车号码（一个可以由两组不同的两个立方数相加的数字）。我有发现本身，但我迫切需要节省一些空间。为此，我需要尽可能小的数据结构，以便我可以相对轻松地使用或创建像 contains() 这样的方法。我并不特别担心速度，因为我目前的解决方案当然可以让它在时间限制内很好地计算。

简而言之，数据结构需要：

  • 为了能够相对简单地实现一个 contains() 方法
  • 使用少量内存
  • 能够存储大量条目
  • 易于与原始长类型一起使用

有任何想法吗？我从哈希图开始（因为我需要测试导致总和的值以确保准确性），然后在我保证可靠答案后转移到哈希集。

任何其他关于如何节省空间的一般想法将不胜感激！

我认为您不需要代码来回答问题，但如果您好奇的话，这里是：

public class Hardy {
//  private static HashMap<Long, Long> hm;


/**
 * Find the nth Hardy number (start counting with 1, not 0) and the numbers
 *      whose cubes demonstrate that it is a Hardy number.
 * @param n
 * @return the nth Hardy number
 */
public static long nthHardyNumber(int n) {
//      long i, j, oldValue;
    int i, j;
    int counter = 0;
    long xyLimit = 2147483647; // xyLimit is the max value of a 32bit signed number
    long sum;
//      hm = new HashMap<Long, Long>();
    int hardyCalculations = (int) (n * 1.1);
    HashSet<Long> hs = new HashSet<Long>(hardyCalculations * hardyCalculations, (float) 0.95);
    long[] sums = new long[hardyCalculations];

//      long binaryStorage, mask = 0x00000000FFFFFFFF;

        for (i = 1; i < xyLimit; i++){
            for (j = 1; j <= i; j++){
//                  binaryStorage = ((i << 32) + j);
//                  long y = ((binaryStorage << 32) >> 32) & mask;
//                  long x = (binaryStorage >> 32) & mask;

                sum = cube(i) + cube(j);
                if (hs.contains(sum) && !arrayContains(sums, sum)){
//                      oldValue = hm.get(sum);
//                      long oldY = ((oldValue << 32) >> 32) & mask;
//                      long oldX = (oldValue >> 32) & mask;
//                      if (oldX != x && oldX != y){
                    sums[counter] = sum;
                    counter++;
                    if (counter == hardyCalculations){
//                          Arrays.sort(sums);
                        bubbleSort(sums);
                        return sums[n - 1];
                    }
                } else {
                    hs.add(sum);
                }
            }
        }
        return 0;
}

private static void bubbleSort(long[] array){
    long current, next;
    int i;
    boolean ordered = false;

    while (!ordered) {
        ordered = true;
        for (i = 0; i < array.length - 1; i++){
            current = array[i];
            next = array[i + 1];
            if (current > next) {
                ordered = false;
                array[i] = next;
                array[i+1] = current;
            }
        }
    }
}

private static boolean arrayContains(long[] array, long n){
    for (long l : array){
        if (l == n){
            return true;
        }
    }
    return false;
}

private static long cube(long n){
    return n*n*n;
}
}
4

3 回答 3

0

您是否考虑过使用标准树？在 java 中，这将是一个TreeSet. 通过牺牲速度，树通常会比散列获得更多空间。

就此而言，sums可能是TreeMap将线性arrayContains转换为对数运算。顺其自然，以后也不用再重新排序了。

编辑

对使用 java 树结构的抱怨sums是 java 的树类型不支持 k-select 算法。假设 Hardy 数字很少见，也许您不需要担心这个容器的复杂性（在这种情况下，您的数组很好。）

如果您确实需要提高这方面的时间性能，您可以考虑使用启用选择的树，例如此处提到的树。然而，该解决方案通过增加空间需求而不是降低空间需求来起作用。

或者，我们可以逐步丢弃我们知道不需要的 Hardy 数字。假设在算法运行期间，sums已经包含n哈代数，我们发现了一个新数。我们插入它并做任何我们需要保持集合顺序的事情，因此现在包含已n+1排序的元素。

考虑最后一个元素。我们已经知道n较小的哈代数，因此最后一个元素不可能是我们的答案。为什么要保留它？在这一点上，我们可以sums再次缩小到大小n并扔掉最大的元素。这既节省了空间，又节省了时间，因为我们要按排序顺序维护的元素更少。

该方法的自然数据结构sums是最大堆。在java中没有可用的本地实现，但有一些第 3 方的实现。你可以“让它工作” TreeMap::lastKey，它最终会慢一些，但仍然比 quadratic 快bubbleSort。

于 2012-09-15T06:09:52.517 回答
0

这是查找给定数字是否为 HR 数字的核心功能：它在 C 中，但应该明白这一点：

bool is_sum_of_cubes(int value)
    {
    int m = pow(value, 1.0/3);
    int i = m;
    int j = 1;

    while(j < m && i >= 0)
        {
        int element = i*i*i + j*j*j;
        if( value == element )
            {
            return true;
            }
        if(element < value)
            {
            ++j;
            }
        else
            {
            --i;
            }
        }

    return false;
    }
于 2014-07-03T06:15:04.523 回答
0

如果您有非常多的元素，并且您实际上想要一个索引来允许快速测试底层数据集中的包含，那么看看Bloom Filters。这些是节省空间的索引，其唯一目的是实现数据集中包含的快速测试。

布隆过滤器是概率性的，这意味着如果它们为包含返回 true，那么您实际上需要检查您的基础数据集以确认该元素确实存在。

如果它们返回 false，则保证该元素不包含在基础数据集中，在这种情况下，包含测试将非常便宜。

因此，这取决于您在大多数情况下是否期望候选人真正包含在数据集中。

于 2012-11-19T21:09:42.887 回答