iOS面接の道はメモを読む(2)

詳細なデータ構造
チェーン?メーター
一方向リンクノード:

class ListNode {
    var val: Int
    var next: ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

双方向ならprevをもう一つ追加します.
チェーンの問題を解決するのはよく使うテクニックです.

dummy head:補助的なチェーンブロックを作成して、リターンする時はreturn dummy.nextです.この技術は頭の結点がnilかどうかを判断することを省くために、プログラムのエラーを減らします.

fast and slow pointer:減速ポインタ、スローポインタが1ステップずつ移動し、速いポインタが2ステップずつ移動します.スピードポインタを使って、チェーンテーブルの中間ノードを簡単に取得し、チェーンテーブルにリングがあるかどうかを判断することができます.

スタックとキュー
スタックスタック、後進先出(LIFO).Swiftには既存のStockはありませんが、Arayで簡単に実現できます.
「iOS面接の道」では、すべての異なるデータタイプのStockを作成し、一つのStock Protoctocalに従って、Asociated Typesで異なるデータタイプを設定します.これはとてもSwiftyです.ここではSwiftが持参したGenercでもできます.

struct Stack {
    var store = [Element]()
    
    var size: Int {
        return store.count
    }
    
    var peek: Element? {
        return store.last
    }
    
    mutating func push(_ item: Element) {
        store.append(item)
    }
    mutating func pop() {
        store.removeLast()
    }
}

var intStack = Stack()
intStack.push(1)

キューQue、先入れ先出し(FIFO).同様にArayでも実現できる.

struct Queue {
    var store = [Element]()
    
    var size: Int {
        return store.count
    }
    
    var isEmpty: Bool {
        return store.count == 0
    }
    
    mutating func enqueue(_ e: Element) {
        store.append(e)
    }
    
    mutating func dequeue() -> Element? {
        return store.first
    }
}

var queue = Queue()

簡単な説明は二つのStockで一つのQueueを実現します.Stock AとStock Bがあると仮定して、Stock AはEqueueの中に入る元素を保存します.StocBはDequeueの元素を処理します.

Equeue:直接に新しい元素をStock A

に入れます.

Dequeue:

もしStocBが空だったら、StocAの中の全ての元素dequeueをStock Bに入れます.この時、先にStockAの元素に入ると、Stock Bの一番上に着きます.そして、dequeueがStockBの中の一つの要素を出して戻ってきます.

StocBが空いていないなら、直接dequeueに戻ります.

二つのQueueでStockを実現するにはちょっと難しいです.二つのQueueはshiftたちの機能を必要とします.
詳細:
どのようにスレッドの安全を実現するかというと、スレッドの安全を実現するためには、iOSで様々な方法があります.主にロック関連の技術と、スレッドの先オフを運用する技術に分けられます.アップルのマルチスレッドプログラミングに関するドキュメントを読んでいると、アップルの公式推奨エンジニアがスレッド関連の技術、特にGCDを使ってスレッドセキュリティを行うことが分かります.理由は、iOSシステムはアプリケーション層とカーネル層に分けられているからです.ロックの処理はカーネル層で、プログラムがロックを作るたびに、アプリケーション層からカーネル層に移動して操作します.このプロセスの消耗は大きいです.もちろん、ロックでスレッドの安全を実現すると、多くの建設ロックと解除のプログラムがあります.アップルのGCDは違っています.基本的にはアプリケーション層だけで実行されています.本当に必要な時だけカーネル層に入れます.
また、CGDをライン層の安全にする方法を説明します.

シリアル・キューを用いる方法

.

並列キュー(Concerent dispatch queue)＋フェンス(Barrier)を使用する方法

以前は第二の方法がもっと効率的だと思っていましたが、やはり合併ですよね.しかし、あるアップルエンジニアと話をしてから、アップルの文書を読んで、問題点を発見しました.第二の方法を使う時、プログラムはBarrierを創建してBarrierを解除して、状況は錠に類似して、この過程は多くの性能を消耗します.このスレッドが安全なStockに大量のデータがあると、自然に遅くなります.
こんなにたくさん見ましたが、実はアップルの公式文書にはこんな言葉があります.
Serial dispatch queue officient alternative to locks and other synchronization prmitives.
シリアルの列が一番素晴らしいという意味です.だから、なぜ前にこんなにたくさん話しましたか?
例をあげます.これは以前書いたThread Safe Stockです.ObjCを使っていますが、見てもいいです.ここはLinkListでStockを実現します.すべてのプログラムはObjCですが、より優れたやり方はLinkListとObjCをCまたはC++で混ぜて書くことです.ListNode.h

#import 

@interface ListNode : NSObject 

@property (nonatomic, strong, nullable) id value;
@property (nonatomic, strong, nullable) ListNode *next;

- (nullable instancetype)initWithValue:(nullable id)value andNext:(nullable ListNode *)next;

@end

ListNode.m

#import "ListNode.h"

@implementation ListNode

- (instancetype)init
{
    self = [super init];
    if (self) {
        self.next = NULL;
        self.value = NULL;
    }
    return self;
}

- (instancetype)initWithValue:(id)value andNext:(ListNode *)next {
    self = [super init];
    if (self) {
        self.next = next;
        self.value = value;
    }
    return self;
}

#pragma mark - NSCoding

#define kValueKey @"valueKey"
#define kNextKey @"nextKey"

- (void)encodeWithCoder:(nonnull NSCoder *)aCoder {
    [aCoder encodeObject:_value forKey:kValueKey];
    [aCoder encodeObject:_next forKey:kNextKey];
}

- (nullable instancetype)initWithCoder:(nonnull NSCoder *)aDecoder {
    id value = [aDecoder decodeObjectForKey:kValueKey];
    id next = [aDecoder decodeObjectOfClass:[ListNode class] forKey:kNextKey];
    
    self = [super init];
    
    if (self) {
        self.value = value;
        self.next = next;
    }
    return self;
}

+ (BOOL)supportsSecureCoding {
    return YES;
}

@end

ThreadSafeStack.h

#import 

@protocol ThreadSafeStackProtocol

- (void)test;

@end

@interface ThreadSafeStack<__covariant objecttype=""> : NSObject 

// MARK: initializer
- (instancetype)init;

// MARK: public motheds
- (void)push:(ObjectType)object;
- (ObjectType)pop;
- (ObjectType)peek;


@property (nonatomic, weak) id delegate;
@property (nonatomic, strong) NSArray> * array;

@property (readonly) NSUInteger count;

@end

ThreadSafeStack.m

#import "ThreadSafeStack.h"
#import "ListNode.h"

@interface ThreadSafeStack()

@property (nonatomic, strong) ListNode *head;
@property (nonatomic, strong) dispatch_queue_t isolationQueue;

@end

@implementation ThreadSafeStack

- (instancetype)init {
    self = [super init];
    if (self) {
//        head = (ListNodeC *)malloc(sizeof(ListNodeC));
        _head = NULL;
        NSString *name = [NSString stringWithFormat:@"com.ThreadSafeStack.dispatchQueue.%@", [[NSUUID UUID] UUIDString]];
        _isolationQueue = dispatch_queue_create([name cStringUsingEncoding:NSASCIIStringEncoding], DISPATCH_QUEUE_CONCURRENT);
    }
    return self;
}

#pragma mark - setter and getter

- (NSUInteger)count {
    __block NSInteger res = 0;
    dispatch_sync(self.isolationQueue, ^{
        ListNode *temp = self.head;
        while (temp != NULL) {
            res += 1;
            temp = temp.next;
        }
        
#if DEBUG
        NSLog(@"count %ld", (long)res);
#endif
    });
    return res;
}

#pragma mark - public methods

- (id)peek {
    __block id res;
    dispatch_sync(self.isolationQueue, ^{
        res = self.head.value;
        
#if DEBUG
        NSLog(@"peek %@", res);
#endif
    });
    return res;
}

- (id)pop {
    __block id res = NULL;
    dispatch_sync(self.isolationQueue, ^{
        if (self.head == NULL) {
        } else {
            res = self.head.value;
            self.head = self.head.next;
        }

    });
    
#if DEBUG
    NSLog(@"pop %@", res == NULL ? @"Null" : res);
#endif
    return res;
}

- (void)push:(id)object {
    dispatch_async(self.isolationQueue, ^{
        self.head = [[ListNode alloc] initWithValue:object andNext:self.head];
#if DEBUG
        NSLog(@"push %@", object);
#endif
    });
}

#pragma mark - override methods

- (NSString *)description {
    NSMutableString *des = [NSMutableString stringWithFormat:@"%@: ", [super description]];
    dispatch_sync(self.isolationQueue, ^{
//    struct ListNodeC * temp = head;
        ListNode *temp = self.head;
        while (temp != NULL) {
            [des appendString:[NSString stringWithFormat:@"%@ ", [temp.value description]]];
            temp = temp.next;
        }
    });
    return [des copy];
}

#pragma mark - NSCopy and NSMutableCopy

- (id)copyWithZone:(NSZone *)zone {
    
    ThreadSafeStack *copy = [[[self class] allocWithZone:zone] init];
    
    copy.head = self.head;
    
    return copy;
}

- (id)mutableCopyWithZone:(NSZone *)zone {
    return [self copyWithZone:zone];
}

#pragma mark - NSCoding

#define kHeadKey @"headKey"

- (void)encodeWithCoder:(nonnull NSCoder *)aCoder {
    [aCoder encodeObject:_head forKey:kHeadKey];
}

- (nullable instancetype)initWithCoder:(nonnull NSCoder *)aDecoder {
    id head = [aDecoder decodeObjectOfClass:[ListNode class] forKey:kHeadKey];
    
    self = [super init];
    if (self) {
        _head = head;
        NSString *name = [NSString stringWithFormat:@"com.ThreadSafeStack.dispatchQueue.%@", [[NSUUID UUID] UUIDString]];
        _isolationQueue = dispatch_queue_create([name cStringUsingEncoding:NSASCIIStringEncoding], DISPATCH_QUEUE_SERIAL);
    }
    return self;
}

+ (BOOL)supportsSecureCoding{
    return YES;
}

何か質問がありましたら、メッセージをください.
Reference:故胤道長と唐巧の二人の大神の本『iOS面接の道』Concerency programming/GCDhttps://developer.apple.com/documentation/dispatch https://developer.apple.com/library/content/documentation/General/Conceptual/ConcurrencyProgrammingGuide/Introduction/Introduction.html#//apple_ref/doc/uid/TP 400809 1-CH 1-SW 1
Threadinghttps://developer.apple.com/library/content/documentation/Cocoa/Conceptual/Multithreading/Introduction/Introduction.html#//apple_ref/doc/uid/1000057 i-CH 1-SW 1