8

ほとんどが C++ のバックグラウンドから来て、私は今、怒って Java を書いています。STL を使用して C++ で基本的に見つけたものは、Java では思ったよりも扱いにくいようです。私の結論は、私がまだ理解していないより良い Java イディオムがおそらくあるということです。擬似コードを使用した例を次に示します。

たまたま文字列であるいくつかのメンバー変数に基づいて、自然な順序関係を持つもののコレクションがあります。

class Thing
{
   String key1;
   String key2;
}

C++ では、順序付け演算子 <(Thing,Thing) を定義して、これらを std::set に入れることができます。例えば

///
/// @brief
/// provide a total order for 'Things' using key1 and key2
///
bool operator<(const Thing& a, const Thing& b)
{
  if (a.key1 < b.key1) return true; 
  else if (a.key1 > b.key1) return false; 
  else return a.key2 < b.key2;
}

モノがある場合は、set::find を使用して O(log N) 時間で要素を見つけることができます。operator<() の追加のオーバーロードを使用します。std::lower_bound または std::equal_range を使用して、key1 のみ、または key1 と key2 の両方を検索できます。例えば：

struct Ordering
{
   /// A strict weak ordering not a total ordering
   bool operator()(const Thing& A,const std::string& key1) const;
}

const_iterator iter = std::lower_bound(someThings.begin(),
                                       someThings.end(),
                                       key1,
                                       Ordering());

この抽象度を下げるために、key1 が名前で、key2 がバージョンであると想像してください。Foobar と呼ばれるソフトウェアはありますか、具体的には Foobar v1.0 はありますか。

一見すると、Java の std::set に最も直接的に相当するものは TreeSet のように見えますが、順序付けは Comparator インターフェイスをサブクラス化することで実装できます。ただし、私が話していることについては、Java でこれを行うには複数のマップが必要なようです。C++ では、値を変更したい場合にのみ、std::map のような連想コンテナーを使用するだけです。C++ std::set では、Java TreeSet と同様に、値は独自のキーです。ただし、C++ では、必要に応じて key1 または key2 を使用して "Thing" と "std::string" を比較し、それらの std::set で特定のものを見つけるコンパレータを作成できます。Javaでこれを行うには Map を使用する必要があるようです。それ以外の場合 ( Comparator には型パラメーターが 1 つしかないため)、次のような混乱が生じます。

public static class Order implements Comparator<Object>
{
  @Override
  @Constant
  public int compare(Object a, Object b)
  {
     String aString;
     String bString;         
     if (a instanceof String)
     {
        aString = (String)a;
     }
     else if (a instanceof Thing)
     {
        aString = ((Field)a).getKey1();
     }
     else
     {
        throw new ClassCastException("String or Field object expected.");
     }
     if (b instanceof String)
     {
        bString = (String)b;
     }
     else if (b instanceof Thing)
     {
        bString = ((Field)b).getKey1();
     }
     else
     {
        throw new ClassCastException("String or Field object expected.");
     }
     return aString.compareTo(bString);
  }
};

ただし、それを行うと、(Thing クラスで) 次のように記述できます。

Set<Thing> things = new TreeSet<Thing>(new Order());

boolean hasFieldWithKey1(final String key1) 
{
   return this.fields.contains(key1);
}

Java Set を使用すると、存在をテストすることはできますが、検索しているオブジェクトを取得することはできません。たとえば、あなたはできません

Field getFieldWithKey1(final String key1) 
{
   return this.fields.floor(key1);
}

floor() のようなメソッドは、値型のオブジェクト (つまり Thing) のみを受け入れるためです。

明らかな解決策は、各キーに Map を使用することです。

Map<String,Thing> thingsByKey1 = new TreeMap<Thing>(new Order());

C++ のバックグラウンドから来ると、これは不必要に肥大化しているように見えます。すでにキーが含まれているのに、キーを再度保存する必要があるのはなぜですか? 鍵が 2 つあると、さらに悪化します。2つのマップが必要になります。

Map<String,Thing> thingsByKey1 = new TreeMap<Thing>(new OrderByKey1());
Map<String,Thing> thingsByKey2 = new TreeMap<Thing>(new OrderByKey2());

キーを複製するだけでなく、追加の不要なツリー データ構造 (またはランタイム パフォーマンスが向上した HashMaps) も作成しています。上記の順序付けの実装では、これは「単純に間違っている」可能性もあります。各キー自体は、一連のものの全体的な順序ではなく、部分的な順序のみを形成するからです。

ここでの検索に関する質問は、ほとんどの場合最悪の選択である線形検索を使用して回答されているのを見てきました。例えば

コレクション内の特定のプロパティを持つすべてのオブジェクトを検索する

Comparator オブジェクトを引数として受け入れるが、要素自体ではなく要素のインデックスを返す BinarySearch のバージョンがあることに注意してください。これは、使用後に get() への不要な呼び出しがあることを意味します (コレクションがサポートしていると仮定します)。

では、時間と空間の両方でこれを効率的に行う Java の方法は何でしょうか?

4

1 に答える 1

4

これを行う Java の方法は、はい、使用することMapです。

C++ のバックグラウンドから来ると、これは不必要に肥大化しているように見えます。すでにキーが含まれているのに、キーを再度保存する必要があるのはなぜですか?

これは、あなたが考えるほど多くのオーバーヘッドではありません。への追加の参照を 1 つ保存しているStringため、合計コストは 4 バイトです。(実際には、コストはゼロです。TreeSet実装には とまったく同じ量のメモリが必要TreeMapです。)

両方のキーで検索する場合は、Comparator<Thing>両方のキーを比較する a を使用するか、ThingimplementComparable<Thing>を作成してから a を維持しTreeSet<Thing>ます。Comparatorそれはあなたが上で書いた...不快なものよりもはるかにコンパクトです。1 つのキーで検索したい場合は、Map<String, Thing>. 本当に両方で検索したい場合は、両方を維持してください。(実際には、これを行う必要はほとんどありませんでした...そして、JDK Collections フレームワークの作成者も、これを頻繁に行う必要があるとは考えていませんでした。)

于 2012-08-01T18:15:58.790 に答える