0

わかりました、ここに詳細があります: 私は Java で Nth Hardy's Taxi 番号(2 つの立方数の 2 つの異なるセットで合計できる数) を見つけるクラスを作成しています。ディスカバリー自体はダウンしていますが、スペースを節約する必要があります。そのためには、contains() のようなメソッドを比較的簡単に使用または作成できる、可能な限り最小のデータ構造が必要です。私の現在のソリューションは確かに時間制限内でうまく計算できるので、速度については特に心配していません。

つまり、データ構造には次のものが必要です。

  • contains() メソッドを比較的簡単に実装できるようにするため
  • 少量のメモリを使用するには
  • 非常に多くのエントリを保存できるようにするため
  • プリミティブな long 型で使いやすいように

何か案は？ハッシュ マップから始めて (正確さを確保するために、合計につながる値をテストする必要があったため)、信頼できる答えが保証されたら、ハッシュ セットに移動しました。

スペースを節約する方法に関する他の一般的なアイデアは大歓迎です!

質問に答えるのにコードは必要ないと思いますが、興味がある場合はここにあります。

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

これは、特定の数値が 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

標準ツリーの使用を検討しましたか? Javaでは、TreeSet. 速度を犠牲にすることで、ツリーは通常、ハッシュよりもスペースを取り戻します。

さらに言えば、線形演算を対数演算に変換するでsumsある可能性があります。自然に並べられているので、後で並べ替える必要もありません。TreeMaparrayContains

編集

Java ツリー構造を使用することに対する不満sumsは、Java のツリー タイプが k-select アルゴリズムをサポートしていないことです。Hardy 数がまれであると仮定すると、おそらく、このコンテナーの複雑さを気にする必要はありません (その場合、配列は問題ありません)。

この側面の時間パフォーマンスを改善する必要がある場合は、ここで言及されているような選択可能なツリーの使用を検討できます。ただし、そのソリューションは、スペース要件を下げるのではなく、増やすことで機能します。

あるいは、不要であることがわかっている Hardy の数値を段階的に破棄することもできます。アルゴリズムの実行中に、sumsすでにnハーディ数が含まれていて、新しいものを発見したとします。それを挿入し、コレクションの順序を維持するために必要なことをすべて行うため、n+1ソートされた要素が含まれるようになりました。

その最後の要素を考えてみましょう。より小さなハーディ数については既に知っているnので、この最後の要素が答えになる可能性はありません。なぜそれを保つのですか？この時点で、sums再度サイズnを縮小して、最大の要素を捨てることができます。これは、ソートされた順序で維持する要素が少なくなるため、スペースの節約と時間の節約になります。

sumsそのアプローチの自然なデータ構造はmax heapです。Javaでは利用可能なネイティブ実装はありませんが、いくつかのサード パーティの実装が浮かんでいます。最終的には遅くなりますTreeMap::lastKeyが、 quadratic よりも高速ですbubbleSort。

于 2012-09-15T06:09:52.517 に答える
0

非常に多数の要素があり、基礎となるデータセットに含まれているかどうかを迅速にテストできるインデックスが効果的に必要な場合は、Bloom Filtersをご覧ください。これらは、データセットに格納するための高速テストを可能にすることだけを目的としたスペース効率の良いインデックスです。

ブルーム フィルターは確率論的です。つまり、包含に対して true を返す場合、その要素が実際に存在することを確認するために、基になるデータセットを実際に確認する必要があります。

それらが false を返す場合、その要素は基礎となるデータセットに含まれていないことが保証され、その場合、含まれているかどうかのテストは非常に安価になります。

したがって、ほとんどの場合、候補が実際にデータセットに含まれていると予想されるかどうかによって異なります。

于 2012-11-19T21:09:42.887 に答える