URL reverse() function has something like O(n^2) behaviour. Could be better.
|Reported by:||mtredinnick||Owned by:||mtredinnick|
|Cc:||Triage Stage:||Ready for checkin|
|Has patch:||yes||Needs documentation:||no|
|Needs tests:||no||Patch needs improvement:||no|
Two improvements that we should implement in URL resolving:
- Both reverse() and resolve() construct a RegexURLResolver instance every time they are called. Since that instance only varies based on the value of urlconf, we can have a module-level cache that stores the instance using urlconf as the key and only creates it when the right key doesn't exist. That saves one scan through the list of URL patterns each time, on average.
- Reverse resolving does a linear scan through the list of patterns looking for a name to match. Since these names are known in advance, we can build up a hash table mapping view function names and url names to patterns, turning the linear scan into an O(1) lookup.
Change History (10)
comment:1 Changed 8 years ago by mtredinnick
- Needs documentation unset
- Needs tests unset
- Patch needs improvement unset
- Triage Stage changed from Unreviewed to Accepted
Changed 8 years ago by anonymous
Changed 8 years ago by smoo
comment:6 Changed 8 years ago by Simon G. <dev@…>
- Has patch set
- Triage Stage changed from Accepted to Ready for checkin