AmanBoronbaev commented on PR #55641:
URL: https://github.com/apache/arrow/pull/55641#issuecomment-6945350514

   Regarding the initialization-complexity question:
   
   `FindFieldIndex` uses the existing `std::unordered_map<std::string_view, 
int>` (`name_to_index_`), rather than scanning the accumulated fields. Its 
expected lookup cost is constant in the number of fields, so this adds one 
hash-table lookup per field and preserves expected linear initialization 
complexity (with string hashing also depending on field-name length). The hash 
table already exists and is populated by `AddField`.
   
   This does add a constant-factor cost: `AddField` performs its own lookup 
afterward. I have not benchmarked the percentage overhead, so I cannot quantify 
it yet. Pathological hash collisions can still produce worst-case quadratic 
behavior, as with the existing map-based implementation.
   
   Code at the submitted commit:
   
   - Lookup: 
https://github.com/apache/arrow/blob/7e7a876d27b1d02601ae42d9b488284bca70f959/cpp/src/arrow/json/parser.cc#L353-L356
   - Existing AddField lookup: 
https://github.com/apache/arrow/blob/7e7a876d27b1d02601ae42d9b488284bca70f959/cpp/src/arrow/json/parser.cc#L387-L395
   - Map declaration: 
https://github.com/apache/arrow/blob/7e7a876d27b1d02601ae42d9b488284bca70f959/cpp/src/arrow/json/parser.cc#L441
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to