面接のために準備中のObjective-C

Question

の配列から重複を削除する最速の方法は何ですか。私は、次の問題を解決することによって練習しようとしています。いくつかの数値が重複するNSNumbersの入力配列が与えられた場合、元の配列に一意の値しか持たない別の配列を作成する方法、一致がある場合、要素に、ユニークなリストの番号のセットに対してそれを比較しながら、アレイ内の各要素をループ：

1. ブルートフォース：

   私は2つのアプローチを参照しますそれを保存せず、それを一意のリストに追加してください。 O（n^2）最悪の場合の時間？

2. ハッシュテーブルベースのアプローチ：長さNのハッシュテーブルが有するテーブルの各要素はNSSetあります。すべての数は、ハッシュ関数を使用して0、... N-1にマップされます。 "mapped-index"に対応するNSSetに存在する場合、 "unique array"には追加されません。そうでなければ、それはセットと一意の配列に追加されます。

このO（N）の複雑さはありますか？

• 私はすべての開始時に[nsnullをヌル]オブジェクトに初期化Nのサイズとアプローチ2 A. NSMutableArrayのを実装する2つの方法を見ました。 B. NSMutableDictionaryのkey =ハッシュマッピング整数

各アプローチのコードは以下のとおりです。

私は私は ことを気づいています。 2A（アレイアプローチ）の実行時間は、以下に示す長さ403の入力配列（0.055ms対12ms）の2B（Mutabledictionaryアプローチ）の半分です。 ii。 1の実行時間は~5倍悪い0.25msです。重複がない場合、この矛盾はさらに悪化します。

私Qsがある：

1. 2より良いアルゴリズムがありますか？
2. アルゴリズム2のより高度な実装はありますか？
3. なぜ辞書アプローチが遅くなりますか？インストゥルメントプロファイリングを使用して、どうすればこのように答えてください私はどのようにしてInstrumentsを使用して各ステップにかかる正確な時間を知ることができますか？

コード

ハッシュコード機能

#define NUM_BUCKETS 127 
#define RANDOMIZER 11 
#define NUM_ITER 40000 

int hashcode(int value) 
{ 
    int retVal = (value*RANDOMIZER)%NUM_BUCKETS ; 
    if(retVal<0) 
    { 
     retVal+=NUM_BUCKETS ; 
    } 
    return retVal ; 
} 

1.ブルートフォースアプローチ

NSMutableArray *smooshedArr=[[NSMutableArray alloc] init] ; 
    double startTime ; 

    startTime=CFAbsoluteTimeGetCurrent() ; 
    for(int iter=0;iter<=NUM_ITER;iter++) 
    { 
     [smooshedArr removeAllObjects] ; 
     [smooshedArr addObject:ints[0]] ; 

     int i,j ; 
     for(i=1;i<[ints count];i++) 
     { 
      for(j=0;j<[smooshedArr count];j++) 
      { 
       if([ints[i] intValue] == [smooshedArr[j] intValue]) 
       { 
        break ; 
       } 
      } 
      if(j==[smooshedArr count]) 
      { 
       [smooshedArr addObject:ints[i]] ; 
      } 
     } 
    } 
    NSLog(@"Bruteforce took %.3fms to remove duplicates from array of length %lu",(CFAbsoluteTimeGetCurrent()-startTime)*1000/NUM_ITER,(unsigned long)[ints count]) ; 
    NSLog(@"Smooshed arary is %@",smooshedArr) ; 

2A。アレイベースのハッシュテーブル

NSMutableArray *hashTable = [[NSMutableArray alloc] init] ; 

    startTime=CFAbsoluteTimeGetCurrent() ; 
    for(int iter=0;iter<=NUM_ITER;iter++) 
    { 
     [smooshedArr removeAllObjects]; 
     for (NSInteger i = 0; i < NUM_BUCKETS; ++i) 
     { 
      [hashTable addObject:[NSNull null]]; 
     } 

     [smooshedArr addObject:ints[0]] ; 

     int indexToInsert = hashcode([ints[0] intValue]) ; 
     hashTable[indexToInsert]=[[NSMutableSet alloc] init] ; 
     [hashTable[indexToInsert] addObject:ints[0]] ; 

     int i ; 
     for(i=1;i<[ints count];i++) 
     { 
      //Find hascode of element i 
      //If the list at index = hashcode in hashCodeArary is empty, then create a NSMutableSet, set toInsert = True 
      //If not empty, check if the element exists in the set. If yes, setToInsert=False. If no, setToInsert=True 
      int indexToInsert = hashcode([ints[i] intValue]) ; 
      BOOL toInsert=false ; 

      if(hashTable[indexToInsert] == [NSNull null]) 
      { 
       hashTable[indexToInsert]=[[NSMutableSet alloc] init] ; 
       toInsert=true ; 
      } 
      else 
      { 
       if(![hashTable[indexToInsert] containsObject:ints[i]]) 
        toInsert=true ; 
      } 
      if(toInsert) 
      { 
       [hashTable[indexToInsert] addObject:ints[i]] ; 
       [smooshedArr addObject:ints[i]] ; 
      } 
     } 
    } 
    NSLog(@"MutableArray (no cheat) took %.3fms to remove duplicates from array of length %lu",(CFAbsoluteTimeGetCurrent()-startTime)*1000/NUM_ITER,(unsigned long)[ints count]) ; 

2B。辞書ベースのハッシュテーブル

NSMutableDictionary *hashDict = [[NSMutableDictionary alloc] init] ; 
    //NSLog(@"Start of hashcode approach %.6f", CFAbsoluteTimeGetCurrent()) ; 
    startTime=CFAbsoluteTimeGetCurrent() ; 
    for(int iter=0;iter<=NUM_ITER;iter++) 
    { 
     //if(iter <4) NSLog(@"iter start: %.6f", CFAbsoluteTimeGetCurrent()) ; 

     //if(iter <4) NSLog(@"init start: %.6f", CFAbsoluteTimeGetCurrent()) ; 
      [smooshedArr removeAllObjects]; 
      [hashDict removeAllObjects] ; 
     //if (iter<4) NSLog(@"init end: %.6f", CFAbsoluteTimeGetCurrent()) ; 


     [smooshedArr addObject:ints[0]] ; 

     int indexToInsert = hashcode([ints[0] intValue]) ; 
     hashDict[@(indexToInsert)]=[[NSMutableSet alloc] init] ; 
     [hashDict[@(indexToInsert)] addObject:ints[0]] ; 

     int i ; 
     for(i=1;i<[ints count];i++) 
     { 
      //Find hascode of element i 
      //If the list at index = hashcode in hashCodeArary is empty, then create a NSMutableSet, set toInsert = True 
      //If not empty, check if the element exists in the set. If yes, setToInsert=False. If no, setToInsert=True 
      int indexToInsert = hashcode([ints[i] intValue]) ; 
      BOOL toInsert=false ; 

      if(hashDict[@(indexToInsert)] == nil) 
      { 
       hashDict[@(indexToInsert)]=[[NSMutableSet alloc] init] ; 
       toInsert=true ; 
      } 
      else 
      { 
       if(![hashDict[@(indexToInsert)] containsObject:ints[i]]) 
        toInsert=true ; 
      } 
      if(toInsert) 
      { 
       [hashDict[@(indexToInsert)] addObject:ints[i]] ; 
       [smooshedArr addObject:ints[i]] ; 
      } 
     } 
    } 
    NSLog(@"Dictionary approach: %.3fms to remove duplicates from array of length %lu",(CFAbsoluteTimeGetCurrent()-startTime)*1000/NUM_ITER,(unsigned long)[ints count]) ; 

入力は、いくつかのアップデートパッケージと430個の要素をONテストし、あなたが面接のために準備をしている場合は、私はあなたに助言する40000以上の反復

NSArray *ints = @[@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(2727272),@(112),@(3),@(4),@(1),@(612211),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(7272),@(1232),@(3),@(4),@(1),@(60),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(2727272),@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(2727272),@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(72),@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(13272),@(2),@(3),@(4),@(18),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(972),@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(3272),@(2),@(3),@(4),@(1),@(69),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(1272),@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(2272),@(2),@(3),@(4),@(1),@(6),@(91),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(7272),@(2),@(3),@(4),@(12),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(111),@(27272),@(2),@(321),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(4545411),@(12341),@(34210),@(123),@(1234),@(1111),@(727272),@(11187),@(9086),@(876543),@(74532),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(13272),@(2),@(3),@(4),@(18),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(658),@(45454),@(12934),@(38421),@(1243),@(12345),@(1112),@(72),@(52),@(3),@(498),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(650),@(45454),@(1234),@(3421),@(123),@(1234),@(111),@(27272),@(2),@(321),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(4545411),@(12341),@(34210),@(123),@(1234),@(1111),@(727272),@(11187),@(9086),@(876543),@(74532),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(13272),@(2),@(3),@(4),@(18),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(658),@(45454),@(12934),@(38421),@(1243),@(19992345),@(119875412),@(72),@(52),@(3),@(498),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(450454),@(46908764642),@(6753435),@(45498754),@(100234),@(65)] ; 

Answer 1

平均しましたすでに実装されているフレームワーククラスを使用します。ホイールを再実装しないでください。問題を上から下へ解決してください。詳細（ハッシュ関数）について考えてはいけない、アルゴリズムの構造を考える：

擬似コードで：我々は持っている

for number in input { 
    if number appears for the first time { 
     add number to output 
    } 
} 

唯一の問題はnumber appears for the first timeを実装する方法です。それはここでいくつかのパフォーマンスの影響がある唯一のポイントです。

Objective-Cでは、この問題に対して正確に作成されたクラスNSSetを使用できます。

NSArray *input = @[... array of numbers]; 

NSMutableSet *foundNumbers = [NSMutableSet set]; 
NSMutableArray *output = [NSMutableArray array]; 

for (NSNumber *number in input) { 
    if (![foundNumbers containsObject:number])) { 
     [foundNumbers addObject:number]; 
     [output addObject:number]; 
    } 
} 

NSLog(@"Output: %@", output); 

入力配列のパスは1つだけ必要です。パフォーマンスを向上させる唯一の方法は、NSSetとは異なる構造を使用していますが、NSSetは既に高度に最適化されており、より良いオプションを見つけることはできません。

入力した数字が十分小さい（たとえば0 ... 65000）範囲に限定されている場合は、BOOLの65000項目の配列を作成し、すべてNOに初期化し、これを高速セット実装として使用します。 しかし、それは多くのメモリを取るだろうし、input配列が非常に長い場合を除き、それは報われない。

確かに独自のハッシュテーブルを実装しないでください。NSDictionaryはすでにハッシュテーブルです。 2番目の実装では、NSDictionaryという非常に難読化された再実装が行われます。バケットは、単純な配列として保持できる場合にのみ機能します。ハッシュ関数を追加すると、パフォーマンスが低下します。

コードの全体的な品質は、インタビューのために非常に重要です。定数を宣言するのに#defineを使用しないでください。良いコーディングスタイルを維持する（私は、オペレーターの周りにスペースを入れることを強く勧めます）。 for(;;)の代わりにイテレータを使用するhashDictよりも変数の名前を付けてみてください（変数に含まれているデータの名前を指定してください）。今

小さな秘密は、また、1つのオブジェクトにNSArrayとNSSetを組み合わせて、あなたの問題を解決することができ、クラスNSOrderedSetがあっても簡単に：

NSOrderedSet *orderedSet = [NSOrderedSet orderedSetWithArray:ints]; 
NSLog(@"Output: %@", orderedSet); 

Answer 2

実際NSOrderedSetも必要ありません使用して - 1は逃げることができます

NSSet *set = [NSSet setWithArray:ints]; 

あなたが出力として配列が必要な場合は、キー値コーディングを助けるためにここにある：

0だけNSSetと

Answer 3

余分なスペース（ハッシュ）を使用したくない場合、配列内の数字のシーケンスは問題ではありませんが、依然として強引な力ほど遅くならないようにするには、配列を並べ替えることができます1回のパスで重複を削除します。時間の複雑さnlog（n）+ n