前言

最近面試了幾家公司, 我總結(jié)出來了兩點與大家共勉, 該文章就是圍繞以下兩點開展:

• 個人發(fā)展和工資想更上一層樓, 必須熟悉算法和數(shù)據(jù)結(jié)構(gòu)
• 程序員的英文水平很重要

1.出乎我所料的很多公司都問到了有關(guān)topK的問題. 所謂topK問題就是在海量數(shù)據(jù)中, 找到頻率最高的K個數(shù)據(jù).例如在淘寶中選擇'價格由高到低' , 就會在所有相關(guān)的物品中把價格最高的前K個展示給用戶.
一般topK問題會使用堆(heap)和快速排序, 面試時答上來這兩點, 基本就已經(jīng)滿足面試官想要的回答了.使用OC的實現(xiàn)代碼我會在下面講解.但是我有一點愚見,OC因為語言的局限性, 可能不適用于上億數(shù)據(jù)的搜索和排序, 但是在萬級別的topK中效率也是很高的
2.強烈給大家安利一個我最近在用的背單詞神器墨墨背單詞, 這個App最吸引我的是可以自定義文本題詞. 我之前再用扇貝和百詞斬的時候, 推送給我的單詞百分之80對我現(xiàn)在的工作沒有意義. 但是墨墨可以自定義想背的單詞, 可是如何獲取到有效的單詞呢. 我在閱讀英文文檔的時候, 會把不會的單詞寫入墨墨中. 可是一個一個查找效率低, 所以我寫了一個計算文本中所有單詞的頻率, 并按頻率大小進行排序的工具.源碼已經(jīng)上傳到Github, 方便大家進行理解.

正文

1.效果展示

將txt文本的內(nèi)容進行展示

文本展示

計算單詞頻率并按需求排序

人往高處走, 水往低處流.

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對英文內(nèi)容進行處理, 拆分出每一個英文單詞, 使用NSPredicate去空

- (NSArray *)getWordArray
{
    NSString *txtStrings = [self getWordData];
    NSCharacterSet *characterSet = [NSCharacterSet characterSetWithCharactersInString:@", . ; ( ) : — \n-"];
    NSArray *originalWordArray = [txtStrings componentsSeparatedByCharactersInSet:characterSet];

    //使用謂語對數(shù)據(jù)進行去空, 使用forin對數(shù)組進行遍歷去空雖然也行, 但是使用謂語性能更好
    NSArray *noBlankArray = [originalWordArray filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"self <> ''"]];
    return noBlankArray;
}

計算每一個單詞的頻率, 并將結(jié)果保存到字典中. key為單詞, value為單詞的頻率. 判斷是否支持大小寫敏感
我曾經(jīng)看過一篇技術(shù)文章, forin是iOS中遍歷性能最高的一個函數(shù). 使用雙層遍歷. 外層遍歷每一個單詞, 內(nèi)層遍歷計算該單詞的頻率.
有一種特殊的情況, 如果一個單詞文檔中包含100個heap單詞和100stack單詞, 這種情況如果外層遍歷仍然遍歷200次的話, 那么性能極差.所以我用了一行代碼來優(yōu)化這個算法: [tempArray removeObject:word];. 這行代碼會將計算過頻率的單詞從元數(shù)組中刪除, 所以優(yōu)化后的代碼的外層循環(huán)只會循環(huán)兩次. 時間復雜度沒有變, 但是N(優(yōu)) < N(原), 在乘以內(nèi)層遍歷的所需的時間, 性能差別就很明顯了.

- (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(@"%計算次數(shù)zd>>>>>", times);
    }
    return dict;
}

排序本來想用快排來實現(xiàn), 可是在數(shù)據(jù)量不是很多的. 用系統(tǒng)自帶的排序方法性能會更好.
排序前需要了解NSComparisonResult, 它是一個枚舉類型, 有三個成員變量.

• NSOrderedAscendingThe left operand is smaller than the right operand. 左邊的操作對象小于右邊的
• NSOrderedSameThe two operands are equal.兩個操作對象相同
• NSOrderedDescendingThe left operand is greater than the right operand.左邊的操作對象大于右邊的操作對象

排序

- (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é)尾

以上就是我的代碼. 因為我相信大家的水平都很高, 就沒有講的很細. 想深入了解的話, 可以看我的源碼歡迎大家fork and pull requests, 因為個人水平所限, 性能還可以在提升, 如果pull request被我接受, 我會發(fā)一個6.66的紅包表示感謝的~~~
希望大家能通過我的這篇文章有一些收貨.在職的努力提高英文水平和算法水平, 找工作的可以找到理想的工作,
加油

                2017夏天的某一天于家中