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]
