Оптимизация Java, выгода от HashMap?

StackOverflow https://stackoverflow.com/questions/1650514

  •  22-07-2019
  •  | 
  •  

Вопрос

Мне давали некоторые прелестный Java-код, в котором много подобных вещей (в цикле, который выполняется около 1,5 миллионов раз).

code = getCode();
for (int intCount = 1; intCount < vA.size() + 1; intCount++)
{
   oA = (A)vA.elementAt(intCount - 1);
   if (oA.code.trim().equals(code))
       currentName= oA.name;
}

Увижу ли я значительное увеличение скорости при переключении на что-то вроде следующего

code = getCode();
//AMap is a HashMap
strCurrentAAbbreviation = (String)AMap.get(code);

Редактировать: Размер vA составляет примерно 50.Отделка не должен даже необходимо, но определенно было бы неплохо назвать это 50 раз вместо 50 * 1,5 млн.Предметы в vA уникальны.

Редактировать: По предложению нескольких респондентов я протестировал его.Результаты приведены внизу.Спасибо, ребята.

Это было полезно?

Решение

Есть только один способ выяснить это.

Другие советы

Хорошо, хорошо, я проверил это.

Результаты следуют для вашего просвещения:

  

Цикл: 18391мс   Хэш: 218 мс

     

Цикл: 18735мс   Хеш: 234 мс

     

Цикл: 18359мс   Хеш: 219мс

Я думаю, что я буду рефакторинг этого бита ..

Каркас: 

public class OptimizationTest {
    private static Random r = new Random();
    public static void main(String[] args){
        final long loopCount = 1000000;
        final int listSize = 55;

        long loopTime = TestByLoop(loopCount, listSize);
        long hashTime = TestByHash(loopCount, listSize);
        System.out.println("Looping: " + loopTime + "ms");
        System.out.println("Hash: " + hashTime + "ms");
    }

    public static long TestByLoop(long loopCount, int listSize){
        Vector vA = buildVector(listSize);
        A oA;

        StopWatch sw = new StopWatch();
        sw.start();
        for (long i = 0; i< loopCount; i++){
            String strCurrentStateAbbreviation;
            int j = r.nextInt(listSize);
            for (int intCount = 1; intCount < vA.size() + 1; intCount++){
                oA = (A)vA.elementAt(intCount - 1);
                if (oA.code.trim().equals(String.valueOf(j)))
                    strCurrentStateAbbreviation = oA.value;
            }
        }
        sw.stop();
        return sw.getElapsedTime();
    }

    public static long TestByHash(long loopCount, int listSize){
        HashMap hm = getMap(listSize);
        StopWatch sw = new StopWatch();
        sw.start();
        String strCurrentStateAbbreviation;
        for (long i = 0; i < loopCount; i++){
            int j = r.nextInt(listSize);
            strCurrentStateAbbreviation = (String)hm.get(j);
        }
        sw.stop();
        return sw.getElapsedTime();
    }

    private static HashMap getMap(int listSize) {
        HashMap hm = new HashMap();
        for (int i = 0; i < listSize; i++){
            String code = String.valueOf(i);
            String value = getRandomString(2);
            hm.put(code, value);
        }
        return hm;
    }

    public static Vector buildVector(long listSize) 
    {
        Vector v = new Vector();
        for (int i = 0; i < listSize; i++){
            A a = new A();
            a.code = String.valueOf(i);
            a.value = getRandomString(2);
            v.add(a);
        }
        return v;
    }

    public static String getRandomString(int length){
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i< length; i++){
            sb.append(getChar());
        }
        return sb.toString();
    }

    public static char getChar()
    {
        final String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        int i = r.nextInt(alphabet.length());
        return alphabet.charAt(i);
    }
}

Да, есть хороший шанс, что вы бы это сделали, да. Извлечение из HashMap будет постоянным временем, если у вас есть хорошие хэш-коды.

Но единственный способ узнать это - попробовать.

Это зависит от того, насколько велика ваша карта и насколько хороша ваша реализация hashCode (чтобы у вас не было коллизий).

Вы действительно должны провести реальное профилирование, чтобы быть уверенным, что какие-либо изменения необходимы, так как вы можете потратить свое время на исправление чего-то, что не сломано.

Что на самом деле выделяет меня чуть больше, чем вызов elementAt, так это обрезка строк, которую вы выполняете на каждой итерации. Моя интуиция говорит мне, что это может быть большим узким местом, но только профилирование может сказать.

Удачи

Я бы сказал, что да, так как приведенное выше является линейным поиском по vA.size (). Насколько большой ва?

Почему бы вам не использовать что-то вроде YourKit (или вставить другой профилировщик), чтобы увидеть, насколько дорогая эта часть цикла.

Использование карты, безусловно, будет улучшением, которое поможет поддерживать этот код в дальнейшем.

Возможность использования карты зависит от того, содержит ли (вектор?) уникальные коды или нет. Данный цикл for запомнит объект последний в списке с заданным кодом, что будет означать, что хеш не является решением.

Для небольших (стабильных) размеров списков простое преобразование списка в массив объектов показало бы увеличение производительности в дополнение к некоторой лучшей читаемости.

Если ничего из вышеперечисленного не выполняется, по крайней мере, используйте итератор для проверки списка, обеспечивая лучшую читаемость и некоторое (вероятное) повышение производительности.

Зависит от обстоятельств.Сколько у тебя памяти?

Я бы догадался гораздо быстрее, но профилируйте это.

Я думаю, что доминирующим фактором является размер ВА, поскольку цикл должен выполняться n раз, где n - размер ВА. С картой нет петли, независимо от того, насколько велика ВА. Поэтому, если n мало, улучшение будет маленьким. Если оно будет огромным, улучшение будет огромным. Это особенно верно, потому что даже после нахождения соответствующего элемента цикл продолжает идти! Поэтому, если вы нашли свое соответствие в элементе 1 из списка из 2 миллионов элементов, вам все равно нужно проверить последние 1 999 999 элементов!

Да, это почти наверняка будет быстрее. Зацикливание в среднем 25 раз (на полпути через ваши 50) медленнее, чем поиск по хэш-карте, предполагая, что ваше содержимое vA прилично хэшируется.

Однако, говоря о содержимом вашего vA , вам придется обрезать их, когда вы вставляете их в aMap, потому что aMap.get (" somekey ") не найдет запись, ключ которой это "Somekey".

На самом деле, вы должны делать это при вставке в vA, даже если вы не переключаетесь на решение hashmap.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top