271–280 of 419 posts
Loving the progression here. Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. A week from now, someone will prove P=NP because all the problems we thought were NP were just running strlen() on the whole input.
You owe me a keyboard!
Earlier quoted context omitted.
> assuming the map doesn't need resizing This isn't a big difficulty; it's still amortized O(1). > and there isn't a hash collision This is a real difficulty, unless you allow map resizing. Luckily, we do. > but it's generally not true in respect to the key length. OK, but in most cases the key length is constant, making anything that depends on the key length O(1) by definition.
Key length must necessarily be O(log(N)) to be able to identify N different keys.
I am writing an app for iOS in Swift and I have an array of structs with some 70,000 elements or thereabouts and for some bizarre reason the compiler uses so much memory if I define it as such directly in the source, that I run out of memory. So instead as a workaround for now I am storing the data as a JSON string that I parse at runtime. It’s very sad, but it’s the only option I had because I have a ton of other co…
8140 swift::ASTVisitor::visit(swift::Stmt*) (in swift-frontend) + 125 [0x110560f9d]
8140 (anonymous namespace)::StmtChecker::typeCheckASTNode(swift::ASTNode&) (in swift-frontend) + 1043 [0x11055dcc3]
8140 (anonymous namespace)::DeclChecker::visit(swift::Decl*) (in swift-frontend) + 4497 [0x1104e0721]
8140 swift::TypeChecker::typeCheckPatternBinding(swift::PatternBindingDecl*, unsigned int, swift::Type) (in swift-frontend) + 250 [0x11049648a]
8140 swift::TypeChecker::typeCheckBinding(swift::Pattern*&, swift::Expr*&, swift::DeclContext*, swift::Type, swift::PatternBindingDecl*, unsigned int) (in swift-frontend) + 140 [0x1104962bc]
8140 swift::TypeChecker::typeCheckExpression(swift::constraints::SolutionApplicationTarget&, swift::OptionSet) (in swift-frontend) + 897 [0x110495e71]
8140 swift::constraints::ConstraintSystem::solve(swift::constraints::SolutionApplicationTarget&, swift::FreeTypeVariableBinding) (in swift-frontend) + 974 [0x11032cb1e]
8140 swift::constraints::ConstraintSystem::solve(llvm::SmallVectorImpl&, swift::FreeTypeVariableBinding) (in swift-frontend) + 52 [0x11032d8b4]
8140 swift::constraints::ConstraintSystem::solveImpl(llvm::SmallVectorImpl&) (in swift-frontend) + 372 [0x11032aa14]
8135 swift::constraints::ComponentStep::take(bool) (in swift-frontend) + 2911 [0x1103393af]
+ 4015 swift::constraints::ConstraintSystem::finalize() (in swift-frontend) + 5258,5080,... [0x110325a7a,0x1103259c8,...]
+ 1819 swift::constraints::ConstraintSystem::finalize() (in swift-frontend) + 5291 [0x110325a9b]Based on Jonathon Blow's tweet it seems like he want to purge the web from existence.
I don‘t get the heat of this topic. Yes they wrote some very slow code because it‘s easy to shoot in your foot with scanf. It‘s nothing new that most software could be heavily optimized by just benchmarking slow parts. There is no reason for this shit storm than to feel better than other developers. The real problem is that they shipped a game with a loading screen which is taking minutes and not looking whether they…
Earlier quoted context omitted.
personally, I think I wouldn't even bother to check the algorithmic complexity of every external function I call. I'd just use the logical choice (like sscanf) and only consider optimising if things started to slow down and profiling the application highlighted it as a bottleneck.
Yes, I absolutely think profiling and then only optimizing the actual problems is always a sound choice. I don't check the docs for every library function I use. I'm just saying, it wouldn't hurt if, when you do read the docs for standard library functions, the algorithmic complexity was mentioned in passing.
Earlier quoted context omitted.
It makes me chuckle when hash maps are stated to be O(1) insertions. Which is true, in respect to the number of items in the map, assuming the map doesn't need resizing and there isn't a hash collision... but it's generally not true in respect to the key length. (I think most implementations are O(ln), where l is the length of the key and n is the number of inserted items, assuming the hash function is O(l) - the _am…
> assuming the map doesn't need resizing This isn't a big difficulty; it's still amortized O(1). > and there isn't a hash collision This is a real difficulty, unless you allow map resizing. Luckily, we do. > but it's generally not true in respect to the key length. OK, but in most cases the key length is constant, making anything that depends on the key length O(1) by definition.
Loving the progression here. Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. A week from now, someone will prove P=NP because all the problems we thought were NP were just running strlen() on the whole input.
You're joking, but now I'm thinking about the XML we parse at work and the library we're using to do it. We parse a lot of it, but I've always had this vague feeling that it takes a bit too long (given the codebase is C++). The XML library we use is rather well-known, so if someone found a bug like this there, I'd suspect a general improvement of performance across the board in the entire industry. Efficient Market H…
Earlier quoted context omitted.
Calculating the key may take longer for the long string Right, that’s exactly what they are warning about. Not typical. e.g. Java takes the hash key of an object to be its address in memory No, that’s just the base implementation in Object (and arguably it was a bad idea). All useful “value type” classes will override it with a real hash of the content, including String. There are some cases in Java where you do want…
> All useful “value type” classes will override it with a real hash of the content Well, this is necessary for a lot of sensible things you'd want to do with non-numeric value types as hash keys... > including String ...except String is something of an intermediate case. There are loads of use cases where what you're really using is a set of constant strings, not variables that contain arbitrary character data. In th…