Monday 6 December 2010

Optimized search for enum lookup values

if you are mirroring Database Lookup tables in Enums in your code, you must also have a mechanism to search for those values effectively.
the first idea would be iterating the values and find the desired Enum value, but as you see below, you can optimize your code if you use a BidiMap to keep Enums and their lookup values.
Note that it is still recommended to iterate members instead of using this method, if you have less than 5 elements in your Enum.
to have a better time measurement, I used an Enum of Country names and their ISO2 Code.
the first Enum uses Iteration to find our requested ISO2 Code:



public enum CountryEnum {


Click to expand:


    EGYPT("AF"),
    EQUATORIAL_GUINEA("AF"),
    ETHIOPIA("AF"),
    AFGHANISTAN("AS"),
    ALBANIA("EU"),
    ALGERIA("AF"),
    ANGOLA("AF"),
    ANTIGUA_AND_BARBUDA("NA"),
    ARGENTINA("SA"),
    AUSTRALIA("OC"),
    BAHAMAS("NA"),
    BAHRAIN("AS"),
    BANGLADESH("AS"),
    BARBADOS("NA"),
    BELGIUM("EU"),
    BELIZE("NA"),
    BENIN("AF"),
    BERMUDA("NA"),
    BHUTAN("AS"),
    MYANMAR("AS"),
    BOLIVIA("SA"),
    BOTSWANA("AF"),
    BRAZIL("SA"),
    BRUNEI_DARUSSALAM("AS"),
    BULGARIA("EU"),
    BURKINA_FASO("AF"),
    BURUNDI("AF"),
    CHILE("SA"),
    CHINA("AS"),
    TAIWAN("AS"),
    COSTA_RICA("NA"),
    DENMARK("EU"),
    GERMANY("EU"),
    DOMINICA("NA"),
    DOMINICAN_REPUBLIC("NA"),
    DJIBOUTI("AF"),
    ECUADOR("SA"),
    COTE_D_IVOIRE("AF"),
    EL_SALVADOR("NA"),
    FALKLAND_ISLANDS("SA"),
    FIJI("OC"),
    FINLAND("EU"),
    FRANCE("EU"),
    GABON("AF"),
    GAMBIA("AF"),
    GHANA("AF"),
    GIBRALTAR("EU"),
    GRENADA("NA"),
    GREECE("EU"),
    GREAT_BRITAIN("EU"),
    GUATEMALA("NA"),
    GUINEA("AF"),
    GUINEA_BISSAU("AF"),
    GUYANA("SA"),
    HAITI("NA"),
    HONDURAS("NA"),
    INDIA("AS"),
    INDONESIA("AS"),
    IRAQ("AS"),
    IRAN("AS"),
    IRELAND("EU"),
    ICELAND("EU"),
    ISRAEL("AS"),
    ITALY("EU"),
    JAMAICA("NA"),
    JAPAN("AS"),
    YEMEN("AS"),
    TIMOR_LESTE("AS"),
    JORDAN("AS"),
    CAYMAN_ISLANDS("NA"),
    CAMEROON("AF"),
    CAMBODIA("AS"),
    CANADA("NA"),
    CAPE_VERDE("AF"),
    QATAR("AS"),
    KENYA("AF"),
    COLOMBIA("SA"),
    COMOROS("AF"),
    CONGO("AF"),
    NORTH_KOREA("AS"),
    SOUTH_KOREA("AS"),
    CUBA("NA"),
    KUWAIT("AS"),
    LAOS("AS"),
    LESOTHO("AF"),
    LEBANON("AS"),
    LIBERIA("AF"),
    LYBIA("AF"),
    LUXEMBOURG("EU"),
    MACAO("AS"),
    MADAGASCAR("AF"),
    MALAWI("AF"),
    MALAYSIA("AS"),
    MALDIVES("AS"),
    MALI("AF"),
    MALTA("EU"),
    MOROCCO("AF"),
    MAURITANIA("AF"),
    MAURITIUS("AF"),
    MEXICO("NA"),
    MONGOLIA("AS"),
    MOZAMBIQUE("AF"),
    NEPAL("AS"),
    NEW_CALEDONIA("OC"),
    NEW_ZEALAND("OC"),
    NICARAGUA("NA"),
    NETHERLANDS_ANTILLES("NA"),
    NETHERLANDS("EU"),
    NIGER("AF"),
    NIGERIA("AF"),
    NORWAY("EU"),
    AUSTRIA("EU"),
    OMAN("AS"),
    PAKISTAN("AS"),
    PANAMA("NA"),
    PAPUA_NEW_GUINEA("OC"),
    PARAGUAY("SA"),
    PERU("SA"),
    PHILIPPINES("AS"),
    POLAND("EU"),
    PORTUGAL("EU"),
    RWANDA("AF"),
    ROMANIA("EU"),
    SOLOMON_ISLANDS("OC"),
    ZAMBIA("AF"),
    SAMOA("OC"),
    SAO_TOME_AND_PRINCIPE("AF"),
    SAUDI_ARABIA("AS"),
    SWEDEN("EU"),
    SWITZERLAND("EU"),
    SENEGAL("AF"),
    SEYCHELLES("AF"),
    SIERRA_LEONE("AF"),
    ZIMBABWE("AF"),
    SINGAPORE("AS"),
    SOMALIA("AF"),
    MICRONESIA("OC"),
    SPAIN("EU"),
    SRI_LANKA("AS"),
    SAINT_KITTS_AND_NEVIS("NA"),
    SAINT_LUCIA("NA"),
    SAINT_VINCENT_AND_THE_GRENADINES("NA"),
    SUDAN("AF"),
    SOUTH_AFRICA("AF"),
    SURINAME("SA"),
    SWAZILAND("AF"),
    SYRIAN_ARAB_REPUBLIC("AS"),
    TANZANIA("AF"),
    THAILAND("AS"),
    TOGO("AF"),
    TONGA("OC"),
    TRINIDAD_AND_TOBAGO("NA"),
    CHAD("AF"),
    CZECH_REPUBLIC("EU"),
    TURKEY("AS"),
    TUNISIA("AF"),
    UGANDA("AF"),
    HUNGARY("EU"),
    URUGUAY("SA"),
    FAROE_ISLANDS("EU"),
    VENEZUELA("SA"),
    UNITED_ARAB_EMIRATES("AS"),
    USA("NA"),
    VIETNAM("AS"),
    CENTRAL_AFRICAN_REPUBLIC("AF"),
    CYPRUS("AS"),
    FRENCH_POLYNESIA("OC"),
    SAN_MARINO("EU"),
    VATICAN("EU"),
    LIECHTENSTEIN("EU"),
    MARTINIQUE("NA"),
    GUADELOUPE("NA"),
    ANDORRA("EU"),
    MONACO("EU"),
    PUERTO_RICO("NA"),
    UNITED_STATES_VIRGIN_ISLANDS("NA"),
    COOK_ISLANDS("OC"),
    VANUATU("OC"),
    NORTHERN_MARIANA_ISLANDS("OC"),
    REUNION("AF"),
    FRENCH_GUIANA("SA"),
    NAMIBIA("AF"),
    UKRAINE("EU"),
    SLOVENIA("EU"),
    CROATIA("EU"),
    SLOVAKIA("EU"),
    ESTONIA("EU"),
    RUSSIAN_FEDERATION("EU"),
    LATVIA("EU"),
    UZBEKISTAN("AS"),
    ARMENIA("AS"),
    AZERBAIJAN("AS"),
    BELARUS("EU"),
    BOSNIA_AND_HERZEGOVINA("EU"),
    ERITREA("AF"),
    GEORGIA("AS"),
    KAZAKHSTAN("AS"),
    KYRGYZ_REPUBLIC("AS"),
    KIRIBATI("OC"),
    LITHUANIA("EU"),
    MARSHALL_ISLANDS("OC"),
    MACEDONIA("EU"),
    MOLDOVA("EU"),
    NAURU("OC"),
    PALAU("OC"),
    TAJIKISTAN("AS"),
    TURKMENISTAN("AS"),
    TUVALU("OC"),
    ANGUILLA("NA"),
    MONTSERRAT("NA"),
    ARUBA("NA"),
    TURKS_AND_CAICOS_ISLANDS("NA"),
    BRITISH_VIRGIN_ISLANDS("NA"),
    GREENLAND("NA"),
    ALAND_ISLANDS("EU"),
    AMERICAN_SAMOA("OC"),
    WESTERN_SAHARA("AF"),
    GUAM("OC"),
    MONTENEGRO("EU"),
    MAYOTTE("AF"),
    NORFOLK_ISLAND("OC"),
    NIUE("OC"),
    PITCAIRN_ISLANDS("OC"),
    PALESTINIAN_TERRITORY("AS"),
    SAINT_HELENA("AF"),
    SVALBARD_AND_JAN_MAYEN_ISLANDS("EU"),
    SAINT_PIERRE_AND_MIQUELON("NA"),
    SERBIA("EU"),
    TOKELAU("OC"),
    WALLIS_AND_FUTUNA("OC"),
    ANTARCTICA("AN"),
    COCOS_ISLANDS("AS"),
    DEMOCRATIC_REPUBLIC_CONGO("AF"),
    CHRISTMAS_ISLAND("AS"),
    SOUTH_GEORGIA_AND_THE_SOUTH_SANDWICH_ISLANDS("AN"),
    FRENCH_SOUTHERN_TERRITORIES("AN");





    private final String lookupValue;

    private CountryEnum(final String idValue) {
        lookupValue = idValue;
    }

    public String getCountryValue() {
        return lookupValue;
    }

    public static CountryEnum getCountry(final String country) {
        for (final CountryEnum countryEnum : CountryEnum.values())
            if (countryEnum.getCountryValue().equalsIgnoreCase(country))
                return countryEnum;

        return null;
    }
}



here is the optimized Version which uses BidiMap to hold Enums and their lookup values:



public enum Country {


Click to expand:


    EGYPT("AF"),
    EQUATORIAL_GUINEA("AF"),
    ETHIOPIA("AF"),
    AFGHANISTAN("AS"),
    ALBANIA("EU"),
    ALGERIA("AF"),
    ANGOLA("AF"),
    ANTIGUA_AND_BARBUDA("NA"),
    ARGENTINA("SA"),
    AUSTRALIA("OC"),
    BAHAMAS("NA"),
    BAHRAIN("AS"),
    BANGLADESH("AS"),
    BARBADOS("NA"),
    BELGIUM("EU"),
    BELIZE("NA"),
    BENIN("AF"),
    BERMUDA("NA"),
    BHUTAN("AS"),
    MYANMAR("AS"),
    BOLIVIA("SA"),
    BOTSWANA("AF"),
    BRAZIL("SA"),
    BRUNEI_DARUSSALAM("AS"),
    BULGARIA("EU"),
    BURKINA_FASO("AF"),
    BURUNDI("AF"),
    CHILE("SA"),
    CHINA("AS"),
    TAIWAN("AS"),
    COSTA_RICA("NA"),
    DENMARK("EU"),
    GERMANY("EU"),
    DOMINICA("NA"),
    DOMINICAN_REPUBLIC("NA"),
    DJIBOUTI("AF"),
    ECUADOR("SA"),
    COTE_D_IVOIRE("AF"),
    EL_SALVADOR("NA"),
    FALKLAND_ISLANDS("SA"),
    FIJI("OC"),
    FINLAND("EU"),
    FRANCE("EU"),
    GABON("AF"),
    GAMBIA("AF"),
    GHANA("AF"),
    GIBRALTAR("EU"),
    GRENADA("NA"),
    GREECE("EU"),
    GREAT_BRITAIN("EU"),
    GUATEMALA("NA"),
    GUINEA("AF"),
    GUINEA_BISSAU("AF"),
    GUYANA("SA"),
    HAITI("NA"),
    HONDURAS("NA"),
    INDIA("AS"),
    INDONESIA("AS"),
    IRAQ("AS"),
    IRAN("AS"),
    IRELAND("EU"),
    ICELAND("EU"),
    ISRAEL("AS"),
    ITALY("EU"),
    JAMAICA("NA"),
    JAPAN("AS"),
    YEMEN("AS"),
    TIMOR_LESTE("AS"),
    JORDAN("AS"),
    CAYMAN_ISLANDS("NA"),
    CAMEROON("AF"),
    CAMBODIA("AS"),
    CANADA("NA"),
    CAPE_VERDE("AF"),
    QATAR("AS"),
    KENYA("AF"),
    COLOMBIA("SA"),
    COMOROS("AF"),
    CONGO("AF"),
    NORTH_KOREA("AS"),
    SOUTH_KOREA("AS"),
    CUBA("NA"),
    KUWAIT("AS"),
    LAOS("AS"),
    LESOTHO("AF"),
    LEBANON("AS"),
    LIBERIA("AF"),
    LYBIA("AF"),
    LUXEMBOURG("EU"),
    MACAO("AS"),
    MADAGASCAR("AF"),
    MALAWI("AF"),
    MALAYSIA("AS"),
    MALDIVES("AS"),
    MALI("AF"),
    MALTA("EU"),
    MOROCCO("AF"),
    MAURITANIA("AF"),
    MAURITIUS("AF"),
    MEXICO("NA"),
    MONGOLIA("AS"),
    MOZAMBIQUE("AF"),
    NEPAL("AS"),
    NEW_CALEDONIA("OC"),
    NEW_ZEALAND("OC"),
    NICARAGUA("NA"),
    NETHERLANDS_ANTILLES("NA"),
    NETHERLANDS("EU"),
    NIGER("AF"),
    NIGERIA("AF"),
    NORWAY("EU"),
    AUSTRIA("EU"),
    OMAN("AS"),
    PAKISTAN("AS"),
    PANAMA("NA"),
    PAPUA_NEW_GUINEA("OC"),
    PARAGUAY("SA"),
    PERU("SA"),
    PHILIPPINES("AS"),
    POLAND("EU"),
    PORTUGAL("EU"),
    RWANDA("AF"),
    ROMANIA("EU"),
    SOLOMON_ISLANDS("OC"),
    ZAMBIA("AF"),
    SAMOA("OC"),
    SAO_TOME_AND_PRINCIPE("AF"),
    SAUDI_ARABIA("AS"),
    SWEDEN("EU"),
    SWITZERLAND("EU"),
    SENEGAL("AF"),
    SEYCHELLES("AF"),
    SIERRA_LEONE("AF"),
    ZIMBABWE("AF"),
    SINGAPORE("AS"),
    SOMALIA("AF"),
    MICRONESIA("OC"),
    SPAIN("EU"),
    SRI_LANKA("AS"),
    SAINT_KITTS_AND_NEVIS("NA"),
    SAINT_LUCIA("NA"),
    SAINT_VINCENT_AND_THE_GRENADINES("NA"),
    SUDAN("AF"),
    SOUTH_AFRICA("AF"),
    SURINAME("SA"),
    SWAZILAND("AF"),
    SYRIAN_ARAB_REPUBLIC("AS"),
    TANZANIA("AF"),
    THAILAND("AS"),
    TOGO("AF"),
    TONGA("OC"),
    TRINIDAD_AND_TOBAGO("NA"),
    CHAD("AF"),
    CZECH_REPUBLIC("EU"),
    TURKEY("AS"),
    TUNISIA("AF"),
    UGANDA("AF"),
    HUNGARY("EU"),
    URUGUAY("SA"),
    FAROE_ISLANDS("EU"),
    VENEZUELA("SA"),
    UNITED_ARAB_EMIRATES("AS"),
    USA("NA"),
    VIETNAM("AS"),
    CENTRAL_AFRICAN_REPUBLIC("AF"),
    CYPRUS("AS"),
    FRENCH_POLYNESIA("OC"),
    SAN_MARINO("EU"),
    VATICAN("EU"),
    LIECHTENSTEIN("EU"),
    MARTINIQUE("NA"),
    GUADELOUPE("NA"),
    ANDORRA("EU"),
    MONACO("EU"),
    PUERTO_RICO("NA"),
    UNITED_STATES_VIRGIN_ISLANDS("NA"),
    COOK_ISLANDS("OC"),
    VANUATU("OC"),
    NORTHERN_MARIANA_ISLANDS("OC"),
    REUNION("AF"),
    FRENCH_GUIANA("SA"),
    NAMIBIA("AF"),
    UKRAINE("EU"),
    SLOVENIA("EU"),
    CROATIA("EU"),
    SLOVAKIA("EU"),
    ESTONIA("EU"),
    RUSSIAN_FEDERATION("EU"),
    LATVIA("EU"),
    UZBEKISTAN("AS"),
    ARMENIA("AS"),
    AZERBAIJAN("AS"),
    BELARUS("EU"),
    BOSNIA_AND_HERZEGOVINA("EU"),
    ERITREA("AF"),
    GEORGIA("AS"),
    KAZAKHSTAN("AS"),
    KYRGYZ_REPUBLIC("AS"),
    KIRIBATI("OC"),
    LITHUANIA("EU"),
    MARSHALL_ISLANDS("OC"),
    MACEDONIA("EU"),
    MOLDOVA("EU"),
    NAURU("OC"),
    PALAU("OC"),
    TAJIKISTAN("AS"),
    TURKMENISTAN("AS"),
    TUVALU("OC"),
    ANGUILLA("NA"),
    MONTSERRAT("NA"),
    ARUBA("NA"),
    TURKS_AND_CAICOS_ISLANDS("NA"),
    BRITISH_VIRGIN_ISLANDS("NA"),
    GREENLAND("NA"),
    ALAND_ISLANDS("EU"),
    AMERICAN_SAMOA("OC"),
    WESTERN_SAHARA("AF"),
    GUAM("OC"),
    MONTENEGRO("EU"),
    MAYOTTE("AF"),
    NORFOLK_ISLAND("OC"),
    NIUE("OC"),
    PITCAIRN_ISLANDS("OC"),
    PALESTINIAN_TERRITORY("AS"),
    SAINT_HELENA("AF"),
    SVALBARD_AND_JAN_MAYEN_ISLANDS("EU"),
    SAINT_PIERRE_AND_MIQUELON("NA"),
    SERBIA("EU"),
    TOKELAU("OC"),
    WALLIS_AND_FUTUNA("OC"),
    ANTARCTICA("AN"),
    COCOS_ISLANDS("AS"),
    DEMOCRATIC_REPUBLIC_CONGO("AF"),
    CHRISTMAS_ISLAND("AS"),
    SOUTH_GEORGIA_AND_THE_SOUTH_SANDWICH_ISLANDS("AN"),
    FRENCH_SOUTHERN_TERRITORIES("AN");
     



     private final String lookupValue;
     private static final BidiMap VALUE_TYPE_MAPPING = new DualHashBidiMap();

     static {
         for (final Country value : Country.values()) {
             Country.VALUE_TYPE_MAPPING.put(Country.valueOf(value.name()), value.getCountryValue());
         }
     }

     private Country(final String idValue) {
         lookupValue = idValue;
     }

     public String getCountryValue() {
         return lookupValue;
     }

     public static Country getCountry(final String country) {
         return (CountryCountry.VALUE_TYPE_MAPPING.getKey(country);
     }
}



and here is a test to compare results:



public class CountryEnumTest {

    private final static int DATA_SIZE = 1000000;
    private final static List<String> testStrings = new ArrayList<String>(DATA_SIZE);
    
    @BeforeClass
    public static void initMap() {
        System.out.println("Initializing test data ...");
        
        final Random random = new Random();
        for (int i = 0; i < DATA_SIZE; i ++) {
            final int index = random.nextInt(CountryEnum.values().length);
            final CountryEnum randomEntry = CountryEnum.values()[index];
            
            testStrings.add(randomEntry.getCountryValue());
        }
    }
    
    @Test
    public void testEnum() {
        final long startTime = System.currentTimeMillis();

        //Search values using iteration
        for (final String entry : testStrings)
            CountryEnum.getCountry(entry);
        final long elapsedTime = System.currentTimeMillis();
        System.out.println("testEnum, search by strings -> Time elapsed: " (System.currentTimeMillis() - startTime));

        //Search values using map
        for (final String entry : testStrings)
            Country.getCountry(entry);
        System.out.println("testOptimizedEnum, search by strings -> Time elapsed: " (System.currentTimeMillis() - elapsedTime));
    }
}




the optimization difference is huge, 63 milliseconds against 1015 !!


Initializing test data ...
testEnum, search by strings -> Time elapsed: 1015
testOptimizedEnum, search by strings -> Time elapsed: 63

 

 

No comments:

Post a Comment