2016-08-06 2 views
1

Stringindexをアクセスする場合の複雑さは、swift 3.0にありますか?Swift 3.0のインデックスを持つ文字列にアクセスする大きな問題

複雑さはアレイアクセスまたはO(N)などと同じですか? 「文字列のインデックス」の下documentationから

let greeting = "Guten Tag!" 
let index = greeting.index(greeting.startIndex, offsetBy: 7) 
greeting[index] 
. 
. 
. 
for index in greeting.characters.indices { 
    print("\(greeting[index]) ", terminator: "") 
} 
// Prints "G u t e n T a g ! " 

最後の例(文字を反復処理)は、ちょうどそのように希望の文字を反復処理するため、インデックス付きのアクセスはO(N)であった場合は、かなりひどいだろうO(n^2)

私が確信しているのは、「異なる文字[...]は異なる量のメモリを格納する必要があります」という文です。

複雑さがO(n)以外であれば、メモリ内の文字に到達するために定数にオフセットを掛けることはできないため、どのように機能しますか?

答えて

3

特に明記しない限り、Collectionの実装subscriptの要件には常にO(1)時間の複雑さがあります。それはCollectionとの契約の一部です。

the documentationとして状態(強調鉱山):Collectionに準拠

タイプはstart​Indexend​Index特性及びOなどの元素(1)操作に添字のアクセスを提供することが期待されます。あなたは、このようなindex(_:offsetBy:)のように事前インデックス、に来たときに期待される性能が出発を文書化しなければならないことを保証することはできませんタイプ[...]

潜在的に高価な部分が発生します。この複雑さは、RandomAccessCollectionの場合はO(1)、その他の場合はO(n)です(nはオフセットの大きさです)。

String.CharacterViewRandomAccessCollectionではないため、前進インデックスはO(n)です。あなたが言うように、これの理由は、文字は異なるバイト長を持つことができるからです。しかし、一度インデックス(which internallyは、文字列のユニコードスカラーのオフセット値であり、与えられた拡張書記素クラスターの長さはUTF-16コード単位で表されます)を取得すると、一定時間内に添字を付けることができます。

したがって

for index in greeting.characters.indices { 
    print("\(greeting[index]) ", terminator: "") 
} 

はO(N)です。ループの各繰り返しは現在のインデックスを1だけ進め、添字はインデックスのオフセットを使用して拡張書記素クラスタの先頭にジャンプし、そのインデックスの文字を取得します。

しかし、我々は言った場合:

for offset in 0..<greeting.characters.count { 
    let index = greeting.index(greeting.startIndex, offsetBy: offset) 
    print("\(greeting[index]) ", terminator: "") 
} 

我々は今、(ないように、ループの各繰り返しで開始インデックスからインデックスを進めているのでは、O(nは)になること文字のうちcountが始まるようにするためにO(n)歩行をすることを言及してください)。

+1

私のものを削除し、質問を誤解しました。Nice explanation mate :) –

関連する問題