Airspeed Velocity
Reginald deBRAIDEWAD
@AirspeedSwift @rob_rix Building arrays with reduce and an On append operation is quadratic.
#NotAllBuildngArraysWIthReduce
Your reminder that building arrays with reduce, while fun, is accidentally quadratic.pic.twitter.com/5hmrpQkKBS
-
-
- View other replies
-
@raganwald@AirspeedSwift@rob_rix odd. Unless it's list, concat should be O(n) with n=postfix length=1, and no copy should happen. So why? -
@an0 Each step of the reduce generates a new Array in Swift, requiring an O(n) copy to be made.@raganwald@AirspeedSwift@rob_rix - View other replies
-
@an0 The + operator on Array has to make a copy because Arrays can't do partial sharing like Lists.@raganwald@AirspeedSwift@rob_rix -
@cocoaphony@raganwald@AirspeedSwift@rob_rix A + B can not be implemented by mutating A when A is unshared? - View other replies
-
@an0 The "A" in this case was passed to the closure. Hard to discover it's unshared.@raganwald@AirspeedSwift@rob_rix -
@an0 Not saying it's totally impossible for compiler to detect, but Swift doesn't encourage the pattern.@raganwald@AirspeedSwift@rob_rix - View other replies
-
@cocoaphony@an0@raganwald@AirspeedSwift I think it’s a missed ARC optimization. isUniquelyReferenced() should be able to deal. - View other replies
- Show more
-
-
@AirspeedSwift@rob_rix Come on, read an Erlang tutorial! (: The right way is to prepend to a cons-list and finally reverse for linear time. -
-
@AirspeedSwift wouldn't rewriting that closure as { $0.append($1); return $0 } solve that? - View other replies
-
@AirspeedSwift errr, { $0.append(transform($1)); return $0 } (whoops!)
-
-
@AirspeedSwift@nicklockwood except if you give up on purity a bit and use a side-effecting callback that actually appends to the array. -
@AirspeedSwift isn’t that what reserve capacity is for? -
Ouch. “
@AirspeedSwift: Your reminder that building arrays with reduce, while fun, is accidentally quadratic. pic.twitter.com/ga91qW6KJ3”
-
@AirspeedSwift Is it the same with Haskells foldl? Gotta test that when my Mac's back
an0
Rob Napier
Rob Rix
Joe Osborn
Luke Groeninger
Árpád Goretity
Samuel Giddins
Said M. Marouf
Kametrixom
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.