タプルをComparableプロトコルに準拠させる一工夫【swift】

はじめに

• swiftにはタプルという型がある。("a",123)みたいな奴ね。
• でも、例えば、配列[1,2,3,4]に対する正式な型名「Array<Int>」のようなモノがない。つまり、("a",123)に対する、「Tuple<String,Int>」みたいなモノがない。なんでかは、よく知らないけどね。
• そして、Tupleみたいな正式名称がないからなのか、このタプルは「extension」で何かのプロトコルに準拠させることが出来ないのよね。
• で、困ったことに、このタプルは「Comparable」に準拠しないから、タプルで配列を作ったときに、sort出来ない！！。
• 重要なことなので、もう一度言います。タプルで配列を作ったときに、sort出来ない！！。
• ふざけんな〜〜〜！！！（全国50人くらいの swiftで競技プログラムしている人達 の声）
• なので、タプルの配列をsortしたい人のために、このコードを捧げます。まぁ、swiftで競技プログラミングしてる人なら、とっくの昔に自作してると思うけど、将来、この沼に足を踏み入れた人のために残しておきます。

swiftで苦労している君に捧げるコード

• extension出来ないから、新たに構造体を作るしかない。
• で、第1要素だけ好きな型Tを使えることにして、第2要素は汎用的なInt型としました。他の型が良ければ、自分でイジってね。
• Comparableプロトコルに準拠する場合、必須メソッドは、「==」と「<」だけ。しかも、タプル自体は、両方とも対応してるから簡単にコードが書ける。....それなら、最初からComparableに準拠させろ(大激怒）！

struct CpTpl<T:Comparable> : Comparable,CustomStringConvertible { // Comparable Tuple でCpTplにしたよ。

    var tpl : (T,Int)
    var description: String {
        return "(\(tpl.0),\(tpl.1))"
    }
    
    init(_ t:T,_ i:Int){
        self.tpl = (t,i)
    }
    init(_ tpl:(T,Int)){
        self.tpl = tpl
    }

    static func == (l: Self, r: Self) -> Bool {l.tpl == r.tpl}    
    static func < (l: Self, r: Self) -> Bool {l.tpl < r.tpl}

}

var tpls = [("a",123),("z",12),("c",4),("c",3)]
// print(tpls.sorted()) -- error: type '(String, Int)' cannot conform to 'Comparable'

var cptpls = tpls.map{CpTpl($0)}
print(cptpls.sorted()) // [(a,123), (c,3), (c,4), (z,12)]

• はい、出来上がり！

おわりに

• swift6.0はまだかなぁ。このクソ仕様が治ってないかなぁ。
  →→→　swift6.0対応のxcode16をインストールしたけど、相変わらず、swift-collectionsもswift-algorithmsもPackage対応でした...駄目だコリャ！！！paiza.ioを使うのを止めて、AtCoderのコードテストを使うしかないのかな？paiza.ioは一度走らせたコードは入力欄の値も一緒に記憶されるから、複数のpcを使い回してる自分にとって使い勝手が良かったんだけどなぁ
  

【追記】Hashableにも対応version

• hash(into hasher: inout Hasher)を追加するだけ！

struct ChTpl<T:Comparable & Hashable> : Comparable,Hashable,CustomStringConvertible { // Comparable Hashable Tuple でChTplにしたよ。

    var tpl : (T,Int)
    var description: String {
        return "(\(tpl.0),\(tpl.1))"
    }

    var fst:T {tpl.0}
    var snd:Int {tpl.1}
    
    init(_ t:T,_ i:Int){
        self.tpl = (t,i)
    }
    init(_ tpl:(T,Int)){
        self.tpl = tpl
    }

    static func == (l: Self, r: Self) -> Bool {l.tpl == r.tpl}    
    static func < (l: Self, r: Self) -> Bool {l.tpl < r.tpl}

    func hash(into hasher: inout Hasher) {
        hasher.combine(tpl.0)
        hasher.combine(tpl.1)
    }
}

• この問題で配列をSetに変えて実行したら、AC出来たけど、配列を使って解いたときの時間が80ms程度だったのが集合(Set)使ったら、100ms程度になって遅くなっちゃったよ。

func pmt_gen<T>(_ ary: [T]) -> Set<[T]> {･･･}
extension Sequence {･･･}
struct ChTpl<T:Comparable & Hashable> : Comparable,Hashable,CustomStringConvertible {･･･}

let N = Int(readLine()!)!

let Mg = Int(readLine()!)!
var Gs : [ChTpl<Int>] = []
for _ in 0..<Mg {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    Gs += [ ChTpl(a,b) , ChTpl(b,a) ]
}

var SG = Set(Gs) 

let Mh = Int(readLine()!)!
var Hs : [ChTpl<Int>] = []
for _ in 0..<Mh {
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0]
    Hs += [ ChTpl(a,b) ]
}

var SH = Set(Hs)

var A = [[Int]](repeating:[Int](repeating:0,count:N),count:N)
for i in 0..<(N-1) {
    let vs = readLine()!.split(separator:" ").map{Int($0)!}
    for (j,v) in vs.enumerated() {
        A[i][i+1+j] = v
    }
}

var P = (0..<N).map{$0}
var Ps = pmt_gen(P)

var ans = Int.max

for p in Ps {
    var sum = 0
    for i in 0..<N {
        for j in i..<N {
        
        if SH.contains(ChTpl(i,j)) != SG.contains(ChTpl(p[i],p[j])) { sum += A[i][j] } 
            
        }
    }
    ans = min(ans,sum)
}

print(ans)

• c++では、集合でのcontainsの計算量がO(logN)だったから、swiftの配列での計算量O(N)より早くなるかな？とおもって集合に入れ替えたのになぁ。遅くなるとは想定外。まぁそもそもN=8くらいだと、logNとＮの差なんて屁みたいなものだから、余り意味なかったのかも。

【追記】

• こんな風にシンプルに書けました。要素がHashableであると明示しておけば、tplがhash関数を持つと宣言しなくて良いのね。「hashableな要素を持つタプルはhashableである」と定義づけられたのかな？でも、Comparableについては、==と<の定義が必要であることに変わりなかった...

struct ChTpl<T:Comparable & Hashable>: Hashable,Comparable,CustomStringConvertible {
    var fst: T
    var snd: Int
    var tpl:(T,Int) {(fst,snd)}

    var description: String { "(\(fst),\(snd))" }  

    init(_ fst: T, _ snd: Int) {
        self.fst = fst
        self.snd = snd
    }
    
    static func == (l: Self, r: Self) -> Bool {l.tpl == r.tpl}    
    static func < (l: Self, r: Self) -> Bool {l.tpl < r.tpl}
}