のJava：フィルタの収集と私はクラスのフィールドが複数

Question

によってデータを取得：

public class Address { 
    private String country; 
    private String state; 
    private String city; 
} 

をそしてPersonオブジェクトのリストがあります。私はPersonオブジェクトをフィルタし、最も適切なものを取得する必要があります

public class Person { 
    private String country; 
    private String state; 
    private String city; 
    //other fields 
} 

：のようなPersonクラスを探します。 Addressオブジェクトには、少なくとも1つのNULLでないフィールドを含めることができます。 Personオブジェクトは、初期化されたフィールドの一部または全部を持つことができません。

は、ここで可能な入力例の1つである：フィルタリング後

Three Person objects: 
a. PersonA: country = 'A' 
b. PersonB: country = 'A', state = 'B' 
c. PersonC: country = 'A', state = 'B', city = 'C' 

Address object: 
a. Address: country = 'A', state = 'B' 

期待される結果がPersonBです。 PersonAとPersonCオブジェクトだけが存在する場合、PersonAがより望ましいです。

私はこれをやろうとしましたが、実際は純粋なブルートフォースアルゴリズムであり、嫌いです。新たに追加されたフィールドと共にアルゴリズムの複雑さが増します。私はまた、述語でグアバフィルタを使用することについて考えましたが、どの述語がすべきか分かりませんでした。

ブルートフォース以外にもこのようなフィルタリングに適したアルゴリズムは何ですか？

Answer 1

ブルートフォースを避けるには、人物を住所で索引付けする必要があります。良い検索のためには、あなたは確かに国を必要とするだろう（それを推測するか、何らかの理由でデフォルトする、そうでなければ結果はとにかく不正確だろう）。

インデックスは、国の場合は最初の3桁、都市の場合は次の3桁、都市の場合は最後の4桁になります。このような場合は、213カ国（only 206 as of 2016）、最大999の州と9999の都市を保存することができます。

これは、私たちに、Personインスタンスを索引付けし、フィールドに触れずにO（log（n））の方法でアドレスを部分的に検索するためにhashCodeとTreeSetを使用できるようにします。フィールドはTreeSetの構築で触れられ、インデックスを損なわれないようにするために、Personを変更するために余分なロジックを追加する必要があります。

指数は、国からあなたはint型の自然な順序に基づかのhashCodeとのcompareToを定義し、あなたの人とアドレスクラスの場合

import java.util.HashMap; 
    import java.util.Map; 

    public class PartialAddressSearch { 

     private final static Map<String, AddressPartHolder> COUNTRY_MAP = new HashMap<>(200); 

     private static class AddressPartHolder { 
      int id; 
      Map<String, AddressPartHolder> subPartMap; 

      public AddressPartHolder(int id, Map<String, AddressPartHolder> subPartMap) { 
       this.id = id; 
       this.subPartMap = subPartMap; 
      } 
     } 

     public static int getCountryStateCityHashCode(String country, String state, String city) { 
      if (country != null && country.length() != 0) { 
       int result = 0; 
       AddressPartHolder countryHolder = COUNTRY_MAP.get(country); 
       if (countryHolder == null) { 
        countryHolder = new AddressPartHolder(COUNTRY_MAP.size() + 1, new HashMap<>()); 
        COUNTRY_MAP.put(country, countryHolder); 
       } 
       result += countryHolder.id * 10000000; 

       if (state != null) { 
        AddressPartHolder stateHolder = countryHolder.subPartMap.get(state); 
        if (stateHolder == null) { 
         stateHolder = new AddressPartHolder(countryHolder.subPartMap.size() + 1, new HashMap<>()); 
         countryHolder.subPartMap.put(state, stateHolder); 
        } 
        result += stateHolder.id * 10000; 

        if (city != null && city.length() != 0) { 
         AddressPartHolder cityHolder = stateHolder.subPartMap.get(city); 
         if (cityHolder == null) { 
          cityHolder = new AddressPartHolder(stateHolder.subPartMap.size() + 1, null); 
          stateHolder.subPartMap.put(city, cityHolder); 
         } 
         result += cityHolder.id; 
        } 
       } 

       return result; 
      } else { 
       throw new IllegalArgumentException("Non-empty country is expected"); 
      } 
    } 

を開始し、各部分のためにsequntially計算されます。

public class Person implements Comparable { 
     private String country; 
     private String state; 
     private String city; 

     @Override 
     public boolean equals(Object o) { 
      //it's important but I removed it for readability 
     } 

     @Override 
     public int hashCode() { 
      return getCountryStateCityHashCode(country, state, city); 
     } 

     @Override 
     public int compareTo(Object o) { 
      //could be further improved by storing hashcode in a field to avoid re-calculation on sorting 
      return hashCode() - o.hashCode(); 
     } 

    } 

    public class Address implements Comparable { 
     private String country; 
     private String state; 
     private String city; 


     @Override 
     public boolean equals(Object o) { 
      //removed for readability 
     } 

     @Override 
     public int hashCode() { 
      return getCountryStateCityHashCode(country, state, city); 
     } 

     @Override 
     public int compareTo(Object o) { 
      //could be further improved by storing hashcode in a field to avoid re-calculation on sorting 
      return hashCode() - o.hashCode(); 
     } 

    } 

    public class AddressPersonAdapter extends Person { 
     private final Address delegate; 

     public AddressPersonAdapter(Address delegate) { 
      this.delegate = delegate; 
     } 

     @Override 
     public boolean equals(Object o) { 
      return delegate.equals(o); 
     } 

     @Override 
     public int hashCode() { 
      return delegate.hashCode(); 
     } 
    } 

後あなたのフィルタリングコードは、あなたの部分的な住所のためにインデックスを埋めると床を計算することに縮小するだろう住所：

TreeSet<Person> personSetByAddress = new TreeSet<>(); 
    Person personA = new Person(); 
    personA.setCountry("A"); 
    personSetByAddress.add(personA); 
    Person personB = new Person(); 
    personB.setCountry("A"); 
    personB.setState("B"); 
    personSetByAddress.add(personB); 
    Person personC = new Person(); 
    personC.setCountry("A"); 
    personC.setState("B"); 
    personC.setCity("C"); 
    personSetByAddress.add(personC); 

    Address addressAB = new Address(); 
    addressAB.setCountry("A"); 
    addressAB.setState("B"); 

    System.out.println(personSetByAddress.floor(new AddressPersonAdapter(addressAB))); 

    Yields: 
    Person{hashCode=10010000, country='A', state='B', city='null'} 

そして、あなたはPersonBを持っていない場合：

TreeSet<Person> personSetByAddress = new TreeSet<>(); 
    Person personA = new Person(); 
    personA.setCountry("A"); 
    personSetByAddress.add(personA); 
    Person personC = new Person(); 
    personC.setCountry("A"); 
    personC.setState("B"); 
    personC.setCity("C"); 
    personSetByAddress.add(personC); 

    Address addressAB = new Address(); 
    addressAB.setCountry("A"); 
    addressAB.setState("B"); 

    System.out.println(personSetByAddress.floor(new AddressPersonAdapter(addressAB))); 

    Yields: 
    Person{hashCode=10000000, country='A', state='null', city='null'} 

EDIT：

コーナーケース内に大きい（または小さい私たちは天井が必要な場合）の要素の不在になり、追加の検証が必要になります同じ国。例：

TreeSet<Person> personSetByAddress = new TreeSet<>(); 
    Person personA = new Person(); 
    personA.setCountry("D"); 
    personSetByAddress.add(personA); 
    Person personC = new Person(); 
    personC.setCountry("A"); 
    personC.setState("B"); 
    personC.setCity("C"); 
    personSetByAddress.add(personC); 

    Address addressAB = new Address(); 
    addressAB.setCountry("A"); 
    addressAB.setState("B"); 

    System.out.println(personSetByAddress.floor(new AddressPersonAdapter(addressAB))); 

    Yields: 
    Person{hashCode=10000000, country='D', state='null', city='null'} 

e。我々は最も近い国に落ちる。これを修正するには、国の数字が同じであることを確認する必要があります。我々はStrictCountryTreeSetをintialize後に今私達のテストケースがnullをもたらすであろう

//we need this class to allow flooring just by id 
public class IntegerPersonAdapter extends Person { 
    private Integer id; 
    public IntegerPersonAdapter(Integer id) { 
     this.id = id; 
    } 

    @Override 
    public boolean equals(Object o) { 
     return id.equals(o); 
    } 

    @Override 
    public int hashCode() { 
     return id.hashCode(); 
    } 

    @Override 
    public int compareTo(Object o) { 
     return id.hashCode() - o.hashCode(); 
    } 

    @Override 
    public String toString() { 
     return id.toString(); 
    } 
} 

public class StrictCountryTreeSet extends TreeSet<Person> { 

    @Override 
    public Person floor(Person e) { 
     Person candidate = super.floor(e); 
     if (candidate != null) { 
      //we check if the country is the same 
      int candidateCode = candidate.hashCode(); 
      int eCode = e.hashCode(); 
      if (candidateCode == eCode) { 
       return candidate; 
      } else { 
       int countryCandidate = candidateCode/10000000; 
       if (countryCandidate == (eCode/10000000)) { 
        //we check if the state is the same 
        int stateCandidate = candidateCode/10000; 
        if (stateCandidate == (eCode/10000)) { 
         //we check if is a state 
         if (candidateCode % 10 == 0) { 
          return candidate; 
         } else { //since it's not exact match we haven't found a city - we need to get someone just from state 
          return this.floor(new IntegerPersonAdapter(stateCandidate * 10000)); 
         } 

        } else if (stateCandidate % 10 == 0) { //we check if it's a country already 
         return candidate; 
        } else { 
         return this.floor(new IntegerPersonAdapter(countryCandidate * 10000000)); 
        } 
       } 
      } 
     } 
     return null; 
    } 

を：私たちは、TreeSetのをサブクラス化し、そこには、このチェックを追加することによってそれを行うことができます

TreeSet<Person> personSetByAddress = new StrictCountryTreeSet(); 
    Person personA = new Person(); 
    personA.setCountry("D"); 
    personSetByAddress.add(personA); 
    Person personC = new Person(); 
    personC.setCountry("A"); 
    personC.setState("B"); 
    personC.setCity("C"); 
    personSetByAddress.add(personC); 

    Address addressAB = new Address(); 
    addressAB.setCountry("A"); 
    addressAB.setState("B"); 

    System.out.println(personSetByAddress.floor(new AddressPersonAdapter(addressAB))); 

    Yields: 
    null 

と異なる状態のためのテスト同様nullをもたらすであろう：

TreeSet<Person> personSetByAddress = new StrictCountryTreeSet(); 
    Person personD = new Person(); 
    personD.setCountry("D"); 
    personSetByAddress.add(personD); 

    Person personE = new Person(); 
    personE.setCountry("A"); 
    personE.setState("E"); 
    personSetByAddress.add(personE); 

    Person personC = new Person(); 
    personC.setCountry("A"); 
    personC.setState("B"); 
    personC.setCity("C"); 
    personSetByAddress.add(personC); 

    Address addressA = new Address(); 
    addressA.setCountry("A"); 

    Address addressAB = new Address(); 
    addressAB.setCountry("A"); 
    addressAB.setState("B"); 

    Address addressABC = new Address(); 
    addressABC.setCountry("A"); 
    addressABC.setState("B"); 
    addressABC.setCity("C"); 

    System.out.println(personSetByAddress.floor(new AddressPersonAdapter(addressAB))); 

    Yields: 
    null 

をこのケースでは、あなたがA内のhashCode結果を格納する必要があることに注意してくださいddressとPerson clasessを使用して再計算を回避します。

Answer 2

私が理解しているように、ブルートフォースとは、すべてのエンティティのすべてのフィールドをチェックするという意味です。まあ、あなたのクラスをリファクタリングしないなら、それは不可能ですが、助けとなる簡単なトリックがあります。それはstateパターンを使用します。

あなたは、両方のクラスにフラグnotNullsを追加することができます。

public class Address { 
    private int notNulls = 0; 
    private String country; 
    private String state; 
    private String city; 
} 

public class Person { 
    private int notNulls = 0; 
    private String country; 
    private String state; 
    private String city; 
    //other fields 
} 

残りは類似しているとして、私はあなたに1つのセッターの可能な実装を紹介します：

public void setCountry(String s) { 
    if (country == null { 
     if (s != null) { 
      country = s; 
      notNulls++; 
     } 
    } else { 
     if (s == null) { 
      country == null; 
      notNulls--; 
     } else { 
      country = s; 
     } 
    } 
} 

public boolean isValid() { 
    return notNulls != 0; 
} 

を通して今あなたができるだけでループオブジェクト。