различия в производительности между NSDictionary (obj-c) и HashMap (java) - PullRequest
Новая
       2

различия в производительности между NSDictionary (obj-c) и HashMap (java)

2 голосов
/ 12 июля 2011

Я провел несколько тестов производительности с этими двумя структурами данных и этими двумя разными языками.Результаты не те, что я ожидал.Я думал, что программа obj-c будет быстрее, чем Java.Мои тесты говорят, что Java TreeMap быстрее, чем какао NSDictionary.для проверки используется следующий код:
obj-c NSDictionary: 

#import <Foundation/Foundation.h>
NSString * getRandomString();
int main (int argc, const char * argv[]) {
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    NSMutableDictionary * dict = [NSMutableDictionary dictionary];
    unsigned long i;
    NSString * string1;
    NSString * string2;
    NSString * string3;
    NSString * lastString;
    //dictionary with 100'000 elements 
    srand(time(NULL));
    for (i=0;i<100000;i++){
        NSString * aString = getRandomString();
        [dict setObject:aString forKey:aString];
        if (i == 100) 
            string1 = aString;
        if (i == 1000)
            string2 = aString;
        if (i == 10000)
            string3 = aString;
        if (i == 100000-1)
            lastString = aString;
    }
    NSDate * now;

    now = [NSDate date];
    [dict objectForKey:string1];
    NSTimeInterval interval = [now timeIntervalSinceNow];
    NSLog(@"%f",interval *-1000);

    now = [NSDate date];
    [dict objectForKey:string2];
    interval = [now timeIntervalSinceNow];
    NSLog(@"%f",interval *-1000);


    now = [NSDate date];
    [dict objectForKey:string3];
    interval = [now timeIntervalSinceNow];
    NSLog(@"%f",interval *-1000);

    now = [NSDate date];
    [dict objectForKey:lastString];
    interval = [now timeIntervalSinceNow];
    NSLog(@"%f",interval *-1000);


    [pool drain];
    return 0;
}
NSString * getRandomString(){
    NSString * tmp = [NSString string];
for (int i = 0 ; i < 10;i++){
    tmp = [NSString stringWithFormat:@"%@%c",tmp,rand()%128];
}
return tmp;
}

Вывод командной строки: 

2011-07-12 13:11:48.299 TestBench[1178:a0f] 0.008047
2011-07-12 13:11:48.302 TestBench[1178:a0f] 0.005007
2011-07-12 13:11:48.302 TestBench[1178:a0f] 0.003040
2011-07-12 13:11:48.303 TestBench[1178:a0f] 0.003994

Java TreeSet: 

import java.util.Date;
import java.util.TreeMap;


public class Main {
    public static void main(String[] args) {
        String string1="",string2="",string3="",lastString="";
        TreeMap<String,String> map = new TreeMap<String,String>();
        for (long i=0;i<100000;i++){
            String aString = getRandomString();
            map.put(aString, aString);
            if (i == 100) 
                string1 = aString;
            if (i == 1000)
                string2 = aString;
            if (i == 10000)
                string3 = aString;
            if (i == 100000-1)
                lastString = aString;
        }
        Date start,end;

        start = new Date();
        map.get(string1);
        end = new Date();
        System.out.println(end.getTime()-start.getTime());

        start = new Date();
        map.get(string2);
        end = new Date();
        System.out.println(end.getTime()-start.getTime());

        start = new Date();
        map.get(string3);
        end = new Date();
        System.out.println(end.getTime()-start.getTime());

        start = new Date();
        map.get(lastString);
        end = new Date();
        System.out.println(end.getTime()-start.getTime());
    }
    public static String getRandomString(){
        String toRet = "";
        for (int i=0;i<10;i++){
            toRet+=(char)(Math.random()*128);
        }
        return toRet;
    }

}

и вывод командной строки таков: 

0
0
0
0

очевидно в миллисекундах, как для obj-c.Почему TreeMap так быстро?или ... Почему NSDictionary такой медленный?Кто-нибудь может мне это объяснить ??Извините за мой очень плохой английский. Большое спасибо.

** ВОПРОС ДОБАВЛЕНИЯ ******** Я сделал следующие изменения в коде:
obj-c 

#import <Foundation/Foundation.h>
NSString * getRandomString();
int main (int argc, const char * argv[]) {
    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
    NSMutableDictionary * dict = [NSMutableDictionary dictionary];
    long int i;
    NSString * string1;
    NSString * string2;
    NSString * string3;
    NSString * lastString;
    //dictionary with 100'000 elements 
    srand(time(NULL));
    double sum = 0;
    for (int j = 0 ;j<10;j++){
        NSDate * now;
        now = [NSDate date];
        for (i=0;i<100000;i++){
            NSString * aString = getRandomString();
            [dict setObject:aString forKey:aString];
            if (i == 100) 
                string1 = aString;
            if (i == 1000)
                string2 = aString;
            if (i == 10000)
                string3 = aString;
            if (i == 100000-1)
                lastString = aString;
        }
        NSLog(@"Finished adding elements in %f ms",[now timeIntervalSinceNow]*-1000);
        now = [NSDate date];
        for (int i = 0;i<1000000;i++)
            [dict objectForKey:string1];
        for (int i = 0;i<1000000;i++)
            [dict objectForKey:string2];
        for (int i = 0;i<1000000;i++)
            [dict objectForKey:string3];
        for (int i = 0;i<1000000;i++)
            [dict objectForKey:lastString];
        NSTimeInterval interval = [now timeIntervalSinceNow];
        sum+=interval;
    }
    NSLog(@"medium lookup time: %f ms",sum/10/4*-1000);
    [pool drain];
    return 0;
}
NSString * getRandomString(){
    NSString * tmp = [NSString string];
    for (int i = 0 ; i < 10;i++){
        tmp = [NSString stringWithFormat:@"%@%c",tmp,rand()%128];
    }
    return tmp;
}

вывод: 

2011-07-12 14:48:36.519 TestBench[974:a0f] Finished adding elements in 1950.287998 ms
2011-07-12 14:48:38.722 TestBench[974:a0f] Finished adding elements in 1899.537027 ms
2011-07-12 14:48:41.340 TestBench[974:a0f] Finished adding elements in 1939.461946 ms
2011-07-12 14:48:43.681 TestBench[974:a0f] Finished adding elements in 1991.870999 ms
2011-07-12 14:48:45.854 TestBench[974:a0f] Finished adding elements in 1857.455015 ms
2011-07-12 14:48:48.636 TestBench[974:a0f] Finished adding elements in 2205.457032 ms
2011-07-12 14:48:50.782 TestBench[974:a0f] Finished adding elements in 1866.232991 ms
2011-07-12 14:48:53.106 TestBench[974:a0f] Finished adding elements in 1847.414017 ms
2011-07-12 14:48:55.537 TestBench[974:a0f] Finished adding elements in 1982.506990 ms
2011-07-12 14:49:00.629 TestBench[974:a0f] Finished adding elements in 4536.152005 ms
2011-07-12 14:49:00.962 TestBench[974:a0f] medium lookup time: 107.704024 ms

Java 

import java.util.Date;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;


public class Main {

    /**
     * @param args
     */

    public static void main(String[] args) {
        String string1="",string2="",string3="",lastString="";
        Map<String,String> map = new HashMap<String,String>();
        long sum=0;
        for (int j=0;j<10;j++){
            Date start,end;
            start = new Date();
            for (long i=0;i<100000;i++){
                String aString = getRandomString();
                map.put(aString, aString);
                if (i == 100) 
                    string1 = aString;
                if (i == 1000)
                    string2 = aString;
                if (i == 10000)
                    string3 = aString;
                if (i == 100000-1)
                    lastString = aString;
            }
            end = new Date();
            System.out.println("Finished adding elements in "+(end.getTime()-start.getTime())+" ms");
            start = new Date();
            for (int i = 0;i<1000000;i++)
                map.get(string1);
            for (int i = 0;i<1000000;i++)
                map.get(string2);
            for (int i = 0;i<1000000;i++)
                map.get(string3);
            for (int i = 0;i<1000000;i++)
                map.get(lastString);
            end = new Date();
            sum+=end.getTime()-start.getTime();
        }
        System.out.println("medium lookup time: "+sum/10/4+" ms");
    }
    public static String getRandomString(){
        String toRet = "";
        for (int i=0;i<10;i++){
            toRet+=(char)(Math.random()*128);
        }
        return toRet;
    }

}

результат для hashmap: 

Finished adding elements in 314 ms
Finished adding elements in 275 ms
Finished adding elements in 263 ms
Finished adding elements in 285 ms
Finished adding elements in 309 ms
Finished adding elements in 284 ms
Finished adding elements in 270 ms
Finished adding elements in 395 ms
Finished adding elements in 320 ms
Finished adding elements in 1804 ms
medium lookup time: 8 ms

результат для treemap 

Finished adding elements in 400 ms
Finished adding elements in 430 ms
Finished adding elements in 474 ms
Finished adding elements in 581 ms
Finished adding elements in 562 ms
Finished adding elements in 599 ms
Finished adding elements in 654 ms
Finished adding elements in 625 ms
Finished adding elements in 638 ms
Finished adding elements in 1750 ms
medium lookup time: 194 ms

Так что я думаю, что NSDictionary создан не с хэш-функцией, а с деревом.И почему для добавления элементов в NSDictionary требуется так много времени?Есть ли в какао карта с похожими характеристиками java хэшсета?спасибо

Ответы [ 2 ]

3 голосов
/ 12 июля 2011

Вы не можете реально сравнивать значения, потому что в Java у вас есть long с, а в какао у вас есть double с. Если вы разыгрываете NSTimeInterval (то есть double) на long, вы получите точно такой же результат.

Кроме того, чтобы получить полезные результаты, недостаточно лишь одного вызова метода. Сделайте цикл и назовите его как минимум несколько тысяч раз.

1 голос
/ 12 июля 2011

Java очень хорош в оптимизации кода, который ничего не делает.В этом отношении он часто намного быстрее, чем C / C ++.Однако, когда дело доходит до выполнения реальной работы, разница обычно намного меньше.

map.get() ничего не делает, а new Date() делает, и это намного медленнее, чем System.currentTimeMillis() Если вы хотите выполнять короткие операциивам лучше использовать System.nanoTime() и вычислять результаты, которые не сразу отбрасываются.

Кроме того, для получения наилучшего результата стоит провести тест в течение примерно 2 секунд. 

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

public class Main {
    public static void main(String[] args) {
        testMap(new TreeMap<String, String>());
        testMap(new HashMap<String, String>());
    }

    private static void testMap(Map<String, String> map) {
        System.out.println("Using " + map.getClass().getSimpleName());

            String[] strings = new String[100000];
            for (int i = 0; i < 100000; i++)
                strings[i] = getRandomString();

            {
                long start = System.nanoTime();
                for (int i = 0; i < 100000; i++) {
                    String aString = strings[i];
                    map.put(aString, aString);
                }
                long time = System.nanoTime() - start;
                System.out.printf("... added elements in %.6f ms%n", time / 1e6);
            }
            String string1 = strings[100], string2 = strings[1000], string3 = strings[10000], string4 = strings[100000 - 1];
        final int runs = 3000000;
        {
            long start = System.nanoTime();
            for (int i = 0; i < runs; i++)
                string1 = map.get(string1);
            long time = System.nanoTime() - start;
            System.out.printf("... average get() time was %.6f ms%n", time / 1e6 / runs);
        }
        {
            long start = System.nanoTime();
            for (int i = 0; i < runs; i++)
                string2 = map.get(string2);
            long time = System.nanoTime() - start;
            System.out.printf("... average get() time was %.6f ms%n", time / 1e6 / runs);
        }
        {
            long start = System.nanoTime();
            for (int i = 0; i < runs; i++)
                string3 = map.get(string3);
            long time = System.nanoTime() - start;
            System.out.printf("... average get() time was %.6f ms%n", time / 1e6 / runs);
        }
        {
            long start = System.nanoTime();
            for (int i = 0; i < runs; i++)
                string4 = map.get(string4);
            long time = System.nanoTime() - start;
            System.out.printf("... average get() time was %.6f ms%n", time / 1e6 / runs);
        }
    }

    public static String getRandomString() {
        String toRet = "";
        for (int i = 0; i < 10; i++) {
            toRet += (char) (Math.random() * 128);
        }
        return toRet;
    }
}

отпечатки 

Using TreeMap
... added elements in 85.856512 ms
... average get() time was 0.000095 ms
... average get() time was 0.000121 ms
... average get() time was 0.000124 ms
... average get() time was 0.000119 ms
Using HashMap
... added elements in 20.189437 ms
... average get() time was 0.000016 ms
... average get() time was 0.000015 ms
... average get() time was 0.000012 ms
... average get() time was 0.000012 ms
...