目标C中从数组中删除重复项的最快方法是什么？
目标C中从数组中删除重复项的最快方法是什么？
提问于 2016-04-16 17:39:28
为面试做准备。我试图通过解决以下问题来实践:给定一个NSNumbers的输入数组，其中一些数字是重复的，那么如何创建另一个只具有原始数组中唯一值的数组。
我看到两种方法：
- 蛮力:循环遍历数组中的每个元素，而在元素处将其与唯一列表中的一组数字进行比较，如果有匹配，则不要存储它，否则将其添加到唯一列表中。0(n^2)最坏的时间？
- 基于哈希表的方法:有一个长度为N的散列表。使用散列函数将每个数字映射到0，.n-1。如果它存在于对应于“映射索引”的NSSet中，则不会将其添加到“唯一数组”中。如果没有，则将其添加到set和唯一数组中。
这是O(N)的复杂性吗？
- 我研究了实现方法2的两种方法。NSMutableArray的大小为N，开始时初始化为NSNull空对象。B. NSMutableDictionary，其中key =散列映射整数
每种方法的代码如下。
我注意到，对于长度为403的输入数组(0.055ms vs .12ms)，2A (数组方法)的运行时间是2B (Mutable字典方法)的一半。
二、运行时间1~5倍，差0.25ms。如果没有重复，这种差异就更严重了。
我的问题是：
- 有比2更好的算法吗？
- 算法2有更好的实现吗？
- 为什么字典的处理要慢些？我如何使用仪器分析来回答这个问题。也就是说，我如何才能知道每一步使用仪器所采取的确切时间？
码
哈希码函数
#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]) ;输入测试了一些dups的，430个元素，平均超过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)] ;回答 3
Stack Overflow用户
回答已采纳
发布于 2016-04-16 20:29:59
如果您正在准备面试，我建议您使用已经实现的框架类。不要重新实现车轮。设法自上而下地解决这个问题。不要考虑细节(散列函数)，考虑算法结构：
伪码：
for number in input {
if number appears for the first time {
add number to output
}
}我们面临的唯一问题是如何实现number appears for the first time。这是这里唯一对性能有影响的地方。
在Objective中，我们可以使用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);您只需要输入数组的一次传递。提高性能的唯一方法是使用与NSSet不同的结构，但是NSSet已经高度优化，不太可能找到更好的选择。
如果您想要开箱即用，并且输入中的数字限制在足够小的范围内(例如0. 65000 )，您可以创建一个包含65000项的BOOL数组，所有项都初始化为NO，并将其用作快速集实现。但是，这将占用大量内存，除非input数组非常长，否则不会有回报。
绝对不要实现您自己的哈希表，NSDictionary已经是一个哈希表。您在第二个实现中所做的只是对NSDictionary的一个非常模糊的重新实现。只有当您可以将其保持为一个简单的数组时，桶才能工作。一旦向其添加了哈希函数，就会失去性能增益。
还请注意，代码的整体质量对面试非常重要。不要使用#define来声明常量。保持良好的编码风格(我强烈建议在操作符周围使用空格)。使用迭代器代替for(;;)，尝试将变量命名为比hashDict更好的名称(为它们包含的数据命名变量)。
现在有一个小秘密，还有一个类NSOrderedSet，它将NSArray和NSSet组合成一个对象，可以更容易地解决问题：
NSOrderedSet *orderedSet = [NSOrderedSet orderedSetWithArray:ints];
NSLog(@"Output: %@", orderedSet);Stack Overflow用户
发布于 2016-04-17 02:32:22
实际上，使用NSOrderedSet并不是必要的--人们只需使用NSSet就可以了：
NSSet *set = [NSSet setWithArray:ints];如果需要一个数组作为输出，键值编码就是为了帮助：
NSArray *array = [ints valueForKeyPath:@"@distinctUnionOfObjects.self"];Stack Overflow用户
发布于 2016-04-30 03:36:53
如果您不想使用额外的空间(散列)，如果数组中的数字序列并不重要，但仍然不想像蛮力那样慢，那么您可以对数组进行排序，然后在一次传递中删除重复的数据。时间复杂度nlog(n) +n
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36667483
复制相关文章
相似问题
腾讯云开发者
