前言
最近面試了幾家公司, 我總結(jié)出來了兩點(diǎn)與大家共勉, 該文章就是圍繞以下兩點(diǎn)開展:
- 個(gè)人發(fā)展和工資想更上一層樓, 必須熟悉算法和數(shù)據(jù)結(jié)構(gòu)
- 程序員的英文水平很重要
1.出乎我所料的很多公司都問到了有關(guān)topK的問題. 所謂topK問題就是在海量數(shù)據(jù)中, 找到頻率最高的K個(gè)數(shù)據(jù).例如在淘寶中選擇'價(jià)格由高到低' , 就會(huì)在所有相關(guān)的物品中把價(jià)格最高的前K個(gè)展示給用戶.
一般topK問題會(huì)使用堆(heap)和快速排序, 面試時(shí)答上來這兩點(diǎn), 基本就已經(jīng)滿足面試官想要的回答了.使用OC的實(shí)現(xiàn)代碼我會(huì)在下面講解.但是我有一點(diǎn)愚見,OC因?yàn)檎Z(yǔ)言的局限性, 可能不適用于上億數(shù)據(jù)的搜索和排序, 但是在萬(wàn)級(jí)別的topK中效率也是很高的
2.強(qiáng)烈給大家安利一個(gè)我最近在用的背單詞神器墨墨背單詞, 這個(gè)App最吸引我的是可以自定義文本題詞. 我之前再用扇貝和百詞斬的時(shí)候, 推送給我的單詞百分之80對(duì)我現(xiàn)在的工作沒有意義. 但是墨墨可以自定義想背的單詞, 可是如何獲取到有效的單詞呢. 我在閱讀英文文檔的時(shí)候, 會(huì)把不會(huì)的單詞寫入墨墨中. 可是一個(gè)一個(gè)查找效率低, 所以我寫了一個(gè)計(jì)算文本中所有單詞的頻率, 并按頻率大小進(jìn)行排序的工具.源碼已經(jīng)上傳到Github, 方便大家進(jìn)行理解.
正文
1.效果展示
將txt文本的內(nèi)容進(jìn)行展示
計(jì)算單詞頻率并按需求排序
2.代碼講解
使用NSFileManager和NSFileHandle獲取txt的文字內(nèi)容
- (NSString *)getWordData
{
NSFileManager *manager = [NSFileManager defaultManager];
NSString *filePath = [[NSBundle mainBundle] pathForResource:@"word" ofType:@"txt"];
if ([manager fileExistsAtPath:filePath]) {
NSString *str = [self getStringFrom:filePath];
return str;
} else {
[NSException raise:NSGenericException format:@"word.txt did not exist in filePath"];
return nil;
}
}
- (NSString *)getStringFrom:(NSString *)filePath
{
NSString *txtStrings = nil;
NSFileHandle *fileHandle = [NSFileHandle fileHandleForReadingAtPath:filePath];
if (fileHandle != nil) {
NSData *wordData = fileHandle.availableData;
txtStrings = [[NSString alloc] initWithData:wordData encoding:NSUTF8StringEncoding];
}
[fileHandle closeFile];
return txtStrings;
}
使用NSCharacterSet對(duì)英文內(nèi)容進(jìn)行處理, 拆分出每一個(gè)英文單詞, 使用NSPredicate去空
- (NSArray *)getWordArray
{
NSString *txtStrings = [self getWordData];
NSCharacterSet *characterSet = [NSCharacterSet characterSetWithCharactersInString:@", . ; ( ) : — \n-"];
NSArray *originalWordArray = [txtStrings componentsSeparatedByCharactersInSet:characterSet];
//使用謂語(yǔ)對(duì)數(shù)據(jù)進(jìn)行去空, 使用forin對(duì)數(shù)組進(jìn)行遍歷去空雖然也行, 但是使用謂語(yǔ)性能更好
NSArray *noBlankArray = [originalWordArray filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"self <> ''"]];
return noBlankArray;
}
計(jì)算每一個(gè)單詞的頻率, 并將結(jié)果保存到字典中. key為單詞, value為單詞的頻率. 判斷是否支持大小寫敏感
我曾經(jīng)看過一篇技術(shù)文章, forin是iOS中遍歷性能最高的一個(gè)函數(shù). 使用雙層遍歷. 外層遍歷每一個(gè)單詞, 內(nèi)層遍歷計(jì)算該單詞的頻率.
有一種特殊的情況, 如果一個(gè)單詞文檔中包含100個(gè)heap單詞和100stack單詞, 這種情況如果外層遍歷仍然遍歷200次的話, 那么性能極差.所以我用了一行代碼來優(yōu)化這個(gè)算法: [tempArray removeObject:word];. 這行代碼會(huì)將計(jì)算過頻率的單詞從元數(shù)組中刪除, 所以優(yōu)化后的代碼的外層循環(huán)只會(huì)循環(huán)兩次. 時(shí)間復(fù)雜度沒有變, 但是N(優(yōu)) < N(原), 在乘以內(nèi)層遍歷的所需的時(shí)間, 性能差別就很明顯了.
- (NSMutableDictionary *)getWordFrequencyDictIsCaseSensitive:(BOOL)isCaseSensitive
{
NSArray *wordArray = [self getWordArray];
NSMutableArray *originalArray = [wordArray mutableCopy];
NSMutableDictionary *dict = [NSMutableDictionary dictionary];
NSMutableArray *tempArray = [originalArray mutableCopy];
NSInteger times = 0;
for (NSInteger i = 0; i <= originalArray.count; i++) {
i = 0;
NSString *compareWord = originalArray[i];
NSInteger count = 0;
for (NSString *word in originalArray) {
if (isCaseSensitive == YES) {
if ([compareWord isEqualToString:word]) {
count += 1;
times += 1;
[tempArray removeObject:word];
}
} else {
if ([compareWord caseInsensitiveCompare:word] == NSOrderedSame) {
count += 1;
times += 1;
[tempArray removeObject:word];
}
}
}
originalArray = [tempArray mutableCopy];
dict[compareWord] = [NSString stringWithFormat:@"%zd", count];
NSLog(@"%計(jì)算次數(shù)zd>>>>>", times);
}
return dict;
}
排序本來想用快排來實(shí)現(xiàn), 可是在數(shù)據(jù)量不是很多的. 用系統(tǒng)自帶的排序方法性能會(huì)更好.
排序前需要了解NSComparisonResult, 它是一個(gè)枚舉類型, 有三個(gè)成員變量.
-
NSOrderedAscendingThe left operand is smaller than the right operand. 左邊的操作對(duì)象小于右邊的 -
NSOrderedSameThe two operands are equal.兩個(gè)操作對(duì)象相同 -
NSOrderedDescendingThe left operand is greater than the right operand.左邊的操作對(duì)象大于右邊的操作對(duì)象
排序
- (NSArray *)getSortKeysFromDictionary:(NSMutableDictionary *)dictionary withSortType:(SortType)type
{
NSMutableDictionary *dict = dictionary;
NSArray *sortArray = [dict keysSortedByValueUsingComparator:^NSComparisonResult(id _Nonnull obj1, id _Nonnull obj2) {
if ([obj1 integerValue] > [obj2 integerValue]) {
if (type == KLowerType) {
return (NSComparisonResult)NSOrderedAscending;
} else {
return (NSComparisonResult)NSOrderedDescending;
}
}
if ([obj1 integerValue] < [obj2 integerValue]) {
if (type == KLowerType) {
return (NSComparisonResult)NSOrderedDescending;
} else {
return (NSComparisonResult)NSOrderedAscending;
}
}
return (NSComparisonResult)NSOrderedSame;
}];
return sortArray;
}
結(jié)尾
以上就是我的代碼. 因?yàn)槲蚁嘈糯蠹业乃蕉己芨? 就沒有講的很細(xì). 想深入了解的話, 可以看我的源碼歡迎大家fork and pull requests, 因?yàn)閭€(gè)人水平所限, 性能還可以在提升, 如果pull request被我接受, 我會(huì)發(fā)一個(gè)6.66的紅包表示感謝的~~~
希望大家能通過我的這篇文章有一些收貨.在職的努力提高英文水平和算法水平, 找工作的可以找到理想的工作,
加油
2017夏天的某一天于家中