As the faster solution I found on forum for the challenge 2, was that one using NSSet, I was deeply frustrated, asking myself whay the words file and the proper names files are kept alphabetically ordered on my Mac.
So I found two solutions that work faster than NSSet based solution and even faster than the solution using binary search.
I based my solution on asking myself how I would solve the challenge without using a computer.
I would never search from the first page, everybody jump when looking in a dictionary and surely once found a name, after testing the next item for being a word, case insensitive equal to the name, I would start a new search for the next name, not from the beginning but from the index where I found the last name.
Working like that, even the nested loops solution can be lot more faster than everything on this forum.
The second approach was to use a binary search in a lazy way, not using my own code but the " index of object in sorted range options: NSBinary search option " method of NSArray class.
//
// main.m
// WordsAndNamesV5
//
// Created by Silviu Toderici on 02.06.2014.
// Copyright © 2014 bignerdranch. All rights reserved.
//
#import <Foundation/Foundation.h>
//****************
int main(int argc, const char * argv[])
{
@autoreleasepool {
// insert code here...
NSDate *startTime = [NSDate date];
//SET THE START OF APP THE TIME WHEN THE APP START TO RUN
//Some Initialisations
NSString *words = [NSString stringWithContentsOfFile:@"/usr/share/dict/words" encoding: NSUTF8StringEncoding error:NULL];
NSArray *wordList = [words componentsSeparatedByString:@"\n"];
NSString *names = [NSString stringWithContentsOfFile:@"/usr/share/dict/propernames" encoding: NSUTF8StringEncoding error:NULL];
NSArray *nameList = [names componentsSeparatedByString:@"\n"];
NSDate *endReading = [NSDate date];
NSMutableArray *properNamesInCommonWordsAndAsociatedWordsIfExist = [[NSMutableArray alloc] init];//A pointer to a
NSUInteger kStop = [wordList count];
NSUInteger kStart = 180;
for (int i =0; i<([nameList count]-1); i++) {
NSString *n = nameList[i];
// JUMP FORWARD
while(([n compare: wordList[kStart] options: NSCaseInsensitiveSearch] !=NSOrderedAscending)){
kStart+=180;
}
// JUMP BACKWARD
while(([n compare:wordList[kStart] options:NSCaseInsensitiveSearch] != NSOrderedDescending)){
kStart-=20;
}
for (NSUInteger k = kStart; k<kStop; k++) {
if ([n compare:wordList[k] options:NSCaseInsensitiveSearch]==NSOrderedDescending) {
continue;
}
if ([n compare:wordList[k] options:NSCaseInsensitiveSearch]==NSOrderedSame){
//kStart = k;
[properNamesInCommonWordsAndAsociatedWordsIfExist addObject:wordList[k]];//
}
else if ([n compare:wordList[k] options:NSCaseInsensitiveSearch]==NSOrderedAscending){//*
if((kStop - k)>180)
// RESUME
kStart = k+180;
else
kStart = k;
break;
}
}
}
[properNamesInCommonWordsAndAsociatedWordsIfExist removeObjectsInArray:nameList];
NSLog(@"Found %lu matches", [properNamesInCommonWordsAndAsociatedWordsIfExist count]);
NSDate *endProgram = [NSDate date];
float f1 = [endReading timeIntervalSinceDate:startTime];
float f2 = [endProgram timeIntervalSinceDate: endReading];
float f3 = [endProgram timeIntervalSinceDate: startTime];
NSLog(@" \nReading: %f secs\nTotal: %f secs\nSearching:%f secs\n", f1, f3, f2);
}
return 0;
}
And the performance on my old 2012 Mac Mini was:
2017-06-14 10:52:14.976354+0100 WordsAndNamesV5[778:81267] Found 293 matches
2017-06-14 10:52:14.976545+0100 WordsAndNamesV5[778:81267]
Reading: 0.124604 secs
Total: 0.129015 secs
Searching:0.004411 secs
Program ended with exit code: 0
And the binary search based solution, using Jump and Resume was:
//
// main.m
// BNRNamesFromWordsBinarySearchResumeAndJump
//
// Created by Silviu Toderici on 07/05/2017.
// Copyright © 2017 bignerdranch. All rights reserved.
//
#import <Foundation/Foundation.h>
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSDate *startAp = [NSDate date];
//READING FROM FILES
NSString *words = [NSString stringWithContentsOfFile:@"/usr/share/dict/words" encoding: NSUTF8StringEncoding error:NULL];
NSArray *wordList = [words componentsSeparatedByString:@"\n"];
NSString *names = [NSString stringWithContentsOfFile:@"/usr/share/dict/propernames" encoding: NSUTF8StringEncoding error:NULL];
NSArray *nameList = [names componentsSeparatedByString:@"\n"];
NSDate *endReading = [NSDate date];
//VARIABLES DECLARATIONS TO KEEP TRACK OF MATCHES AND TO SETUP THE RANGE FOR BINARY SEARCH
NSUInteger countMatches =0;
NSUInteger max = [wordList count]-2;
__block NSUInteger start = 0;
__block NSMutableArray *matches = [[NSMutableArray alloc] init];
NSUInteger jump = [wordList count]/[nameList count];
//NSLog(@"The jump value is: %lu", jump);
for (NSString *n in nameList){
if([n length]>0)
{
NSUInteger stop = 0;
if((start + jump)< max)
//JUMP (SETING UP THE STOP FOR THE RANGE TO BE USED IN THE BINARY SEARCH)
stop = start + jump;
else
stop = max;
while(([wordList[stop] compare:n options: NSCaseInsensitiveSearch]!= NSOrderedDescending)&&((stop+jump)<max)){
start = stop;
stop+=jump;
}
//MAKING THE RANGE, FROM THE RESUMING START AND JUMPING STOP
NSRange r = NSMakeRange(start, (stop - start));
//SEARCH USING BINARY SEARCH IN THE RANGE
NSUInteger index = [wordList indexOfObject:n inSortedRange:r options:NSBinarySearchingFirstEqual usingComparator:^NSComparisonResult(id obj1, id obj2){
return [(NSString *)obj1 compare: (NSString *)obj2 options:NSCaseInsensitiveSearch];
}];
if(index != NSNotFound){
//RESUME
start = index ;
//TEST FOR MATCH
if(([wordList[index+1] compare: n options:NSCaseInsensitiveSearch]==NSOrderedSame)||([wordList[index-1] compare:n]==NSOrderedSame)){
countMatches++;
//count++;
[matches addObject:n];
}
//ALL PROPER NAMES ARE IN BETWEN WORDS, THE LINE DOWN WIL LOG ONLY IN CASE OF A BUG
}
else{
NSLog(@"\n\n\n************************************************Name: %@ NOT FOUND\n\n\n", n);
}
}
}
//LOG RESULTS
//NSLog(@"Matches: %@", matches);
NSLog(@"Found %lu matches", countMatches);
NSDate *endProgram = [NSDate date];
float f1 = [endReading timeIntervalSinceDate:startAp];
NSLog(@"Reading: %f secs", f1);
float f3 = [endProgram timeIntervalSinceDate:startAp];
NSLog(@"Total: %f secs", f3);
float f2 = [endProgram timeIntervalSinceDate:endReading];
NSLog(@"Searching:%f secs", f2);
}
return 0;
}
That was even faster:
2017-06-14 10:44:27.707961+0100 BNRNamesFromWordsBinarySearchResumeAndJump[696:39364] Found 293 matches
2017-06-14 10:44:27.708140+0100 BNRNamesFromWordsBinarySearchResumeAndJump[696:39364] Reading: 0.131396 secs
2017-06-14 10:44:27.708165+0100 BNRNamesFromWordsBinarySearchResumeAndJump[696:39364] Total: 0.135040 secs
2017-06-14 10:44:27.708177+0100 BNRNamesFromWordsBinarySearchResumeAndJump[696:39364] Searching:0.003644 secs
Program ended with exit code: 0