جافا الأمثل, الربح من hashMap?

Question

لقد تم إعطاء بعض جميل كود جافا يحتوي على الكثير من مثل هذه الأمور (في حلقة التي ينفذ حوالي 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 مليون دولار.العناصر في فرجينيا هي فريدة من نوعها.

تحرير: في اقتراح العديد من المستجيبين ، اختبرته.النتائج في الأسفل.شكرا لكم أيها الرجال.

Answer 1

ليس هناك سوى طريقة واحدة لمعرفة ذلك.

Answer 2

حسنا, حسنا, لقد اختبرت ذلك.

نتائج متابعة التنوير الخاصة بك:

حلقات:18391ms التجزئة:218ms

حلقات:18735ms التجزئة:234ms

حلقات:18359ms التجزئة:219ms

أعتقد أنني سوف تكون إعادة بيع ديون قليلا ..

إطار:

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);
    }
}

Answer 3

صحيح, هناك فرصة جيدة أن كنت نعم.استرجاع من HashMap سيكون وقت ثابت إذا كان لديك جيدة تجزئة رموز.

ولكن الطريقة الوحيدة التي يمكنك أن تجد حقا هو من يحاول ذلك.

Answer 4

هذا يعتمد على كيفية كبيرة الخريطة و كيف جيدة hashCode التنفيذ (مثل أن ليس لديك colisions).

Answer 5

يجب أن تفعل بعض التنميط أن يكون متأكدا مما إذا كان أي تعديل مطلوب, كما كنت قد ينتهي قضاء بعض الوقت الخاص بك تحديد ما لم يتم كسر.

ما تبرز في الواقع لي أكثر قليلا من elementAt دعوة سلسلة تقليم كنت تفعل مع كل التكرار.حدسي يقول لي أن هذا قد يكون أكبر من عنق الزجاجة ، ولكن فقط التنميط يمكن أن أقول حقا.

حظا سعيدا

Answer 6

أنا أقول نعم ، منذ أعلاه يبدو أن البحث الخطي أكثر vA.حجم().كيف كبيرة هو va ؟

Answer 7

لماذا لا تستخدم شيئا مثل YourKit (أو إدراج آخر التعريف) لمعرفة مدى تكلفة هذا الجزء من الحلقة.

Answer 8

باستخدام خريطة سيكون بالتأكيد تحسنا التي تساعد على الحفاظ على هذا الرمز في وقت لاحق.

إذا كان يمكنك استخدام خريطة يعتمد على ما إذا كان (ناقلات?) يحتوي على رموز فريدة من نوعها أم لا.لحلقة معينة سوف تذكر آخر كائن في القائمة مع رمز معين ، وهو ما يعني تجزئة ليس هو الحل.

الصغيرة (مستقر) قائمة الأحجام ببساطة تحويل القائمة إلى مجموعة من الكائنات تظهر زيادة في الأداء على رأس بعض قراءة أفضل.

إذا كان أي من أعلاه يحمل على الأقل استخدام itarator لفحص القائمة ، وإعطاء أفضل من قراءة بعض (محتملة) زيادة في الأداء.

Answer 9

يعتمد.مقدار الذاكرة لديك ؟

اعتقد أسرع بكثير ، ولكن الشخصي ذلك.

Answer 10

أعتقد أن العامل المهيمن هنا هو كيف كبيرة vA منذ حلقة يحتاج إلى تشغيل مرات n, حيث n هو حجم vA.مع الخريطة ، لا يوجد حلقة, بغض النظر عن كيفية كبيرة فا هو.حتى إذا كان n هو صغير ، وتحسين سوف تكون صغيرة.إذا كانت ضخمة ، وتحسين سوف تكون ضخمة.هذا ينطبق بشكل خاص لأنه حتى بعد العثور على مطابقة عنصر حلقة يستمر!حتى إذا كنت في العثور على الشريك في العنصر 1 من 2 مليون عنصر القائمة لا تزال تحتاج إلى التحقق من الماضي 1,999,999 العناصر!

Answer 11

نعم, فهذا يكاد يكون أسرع.حلقات بمعدل 25 مرة (في منتصف الطريق خلال 50) هو أبطأ من hashmap البحث ، على افتراض vA محتويات لائق hashable.

ومع ذلك يتحدث من vA محتويات, عليك أن تقليم لهم عند إدراج ملف aMap, لأن aMap.الحصول على("somekey") لن تجد الدخول الذي هو مفتاح "somekey ".

في الواقع, يجب أن لا تضاف إلى vA, حتى لو كنت لا التبديل إلى hashmap الحل.