NSDictionary（obj-c）和HashMap（java）之間性能的差異

我用這兩種數據結構和這兩種不同的語言做了一些性能測試。結果不是我所期望的。我認爲obj-c程序會比java更快。我的測試說，Java的TreeMap比可可NSDictionary更快。用於測試的代碼是：
OBJ-C的NSDictionary：NSDictionary（obj-c）和HashMap（java）之間性能的差異

#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

爪哇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; 
    } 

}

和命令行輸出是這樣的：

明顯以毫秒爲單位，與obj-c一樣。爲什麼TreeMap速度如此之快？或...爲什麼NSDictionary如此緩慢？任何人都可以解釋給我？對不起，我的英語很差非常感謝。

**ADDING QUESTION* ** * **** 我作出修改，以這樣的代碼：
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

結果的樹圖

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 hashset相似的性能的地圖？謝謝

來源

2011-07-12 tmnd91

map.get（）大概北京時間太快以毫秒爲單位來測量。嘗試調用map.get（）100萬次或100萬次，看看它如何表現。 – Matt

您的「添加」基準大部分時間花費在創建隨機字符串上。如果您不在時間範圍內，速度要快10倍。看到我更新的答案。 –

另請注意，與8 ms相比，我的平均查找時間爲HashMap.get（）爲0.000015 ms。 ;） –

你不能真正比較這些值，因爲在Java中你有long s，而在可可你有double s。如果您要將NSTimeInterval（這是一個double）長時間，您會得到完全相同的結果。

此外，爲了獲得有用的結果，僅調用該方法的一次調用是不夠的。製作一個循環並至少稱它爲幾千次。

來源

2011-07-12 12:00:06 omz

明白了:)可可更快謝謝你！ – tmnd91

Java非常擅長優化不做任何事情的代碼。在這方面，它通常比C/C++快得多。然而，在實際工作中，差異通常要小得多。

map.get()沒有做任何事情，但new Date()確實，如果你想短期操作，您最好使用System.nanoTime()和計算未立即丟棄的結果，這是比System.currentTimeMillis()慢得多。

此外，值得運行測試約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

來源

2011-07-12 12:09:53

NSDictionary（obj-c）和HashMap（java）之間性能的差異

回答

相關問題