Use TreeMap in Response #1198
Use TreeMap in Response #1198
Conversation
|
Good catch. iterating through the map elements does not make any sense. Using the default However, I do not understand why we should specifically use a |
|
I've revised the code a bit, to reuse the map if it is already a SortedMap. That way, no extra objects need to be created in that scenario, such as with OkHttp's header map implementation. |
ShareASmile
added
enhancement
TobiGr
force-pushed
the
Response-TreeMap
branch
from
7fb4dbe to
8921c32
Compare
TobiGr
left a comment
TobiGr
left a comment
There was a problem hiding this comment.
A related test is failing, something is wrong with the changes
Invalid response type (got "null", excepted a JSON response) (response code 200)
org.schabi.newpipe.extractor.exceptions.ExtractionException: Invalid response type (got "null", excepted a JSON response) (response code 200)
at org.schabi.newpipe.extractor.services.youtube.extractors.YoutubeSuggestionExtractor.suggestionList(YoutubeSuggestionExtractor.java:71)
at org.schabi.newpipe.extractor.services.youtube.YoutubeSuggestionExtractorTest.testIfSuggestions(YoutubeSuggestionExtractorTest.java:55)
Isira-Seneviratne
force-pushed
the
Response-TreeMap
branch
from
8921c32 to
1933e94
Compare
I wasn't able to reproduce the issue locally, the header value is being returned as expected. |
|
The Exception is only thrown when running with mocks and happens here: The mock response has the header |
Stypox
left a comment
Stypox
left a comment
There was a problem hiding this comment.
Somewhere we have to iterate through all headers anyway: either in the Response constructor, or in the getHeader() function, since we don't know with which Map the Response is being built (it might be a SortedMap sorted according to a wrong criterion). So I would suggest recreating a new TreeMap every time in the Response constructor, since that's called only once, while getHeader might be called multiple times.
Replying to @TobiGr, I think we can't use a HashMap if we want a sorted map. But in any case, given the small amount of headers that there usually are (<20), the O(log n) of the TreeMap is actually much faster than the O(1) of the HashMap: hash maps have a big constant in the O(1) and get faster only after n grows large enough.
Another option would be to create a hash map where keys are already lowercased in the constructor, and then just accessing the map with name.lowercase() in getHeader().
In general I don't think this change is so important anyway, since the O(n) we had in getHeader() is not so bad given that n is small, and getHeader() is basically never used anyway:
So I would just keep the old O(n) behavior in getHeader(), but O(1) in the constructor, rather than switching to O(n) in the constructor (which is executed all the time) and O(log n)/O(1) in getHeader() (which is basically never called).
| public Response(final int responseCode, | ||
| final String responseMessage, | ||
| @Nullable final Map<String, List<String>> responseHeaders, | ||
| @Nonnull final Map<String, List<String>> responseHeaders, |
There was a problem hiding this comment.
Why is this changed to be @Nonnull? Isn't this a breaking change?
| if (responseHeaders instanceof SortedMap) { | ||
| this.responseHeaders = (SortedMap<String, List<String>>) responseHeaders; | ||
| } else { | ||
| this.responseHeaders = new TreeMap<>(String.CASE_INSENSITIVE_ORDER); | ||
| this.responseHeaders.putAll(responseHeaders); | ||
| } |
There was a problem hiding this comment.
Mmmh, this still means that all items are reprocessed when building a Response in case the headers were not already in a SortedMap. Also, how can you be sure that responseHeaders was built using String.CASE_INSENSITIVE_ORDER?
I would just build a new TreeMap every time.
4 participants
Store the response headers in a
TreeMap. This allows the header value retrieval to be optimised asTreeMaporders its keys using a comparator.