Object's member access is O(n)

[miloyip]

From milo...@gmail.com on November 30, 2011 13:31:34

Object member access, i.e. Value::FindMember(), is in O(n) by linear searching.

Design a faster approach for member access.

Original issue: http://code.google.com/p/rapidjson/issues/detail?id=5

[miloyip]

From fasdfas...@gmail.com on July 23, 2013 02:28:40

I don't think it is possible to use a faster algorithm without ordering the keys.

Ordering the keys and putting them in a map also has a overhead so it is does not make sense to implement it.

Users should access a value once, then store it and re-use the value without calling Document::operator []. That will be faster than anything.

[miloyip]

From bas...@starynkevitch.net on November 05, 2013 02:00:59

With C++11 it is possible to use std::unordered_map see e.g. http://en.cppreference.com/w/cpp/container/unordered_map

[miloyip]

From drawtree@gmail.com on December 20, 2013 20:57:52

Just my opinion…

AFAIK, hash-map overhead is known to be a lot heavier than sorted B-trees if key count is small. And JSON object usually expected to have a few of keys - less than 10 keys for example - because large number of keys means there's something wrong with data structure design.

So I doubt on using hash-map for performance. If your object has dozens of keys, it would make sense, but I never seen such JSON object.

IMO, binary search is the best approach for a JSON object, and C++11 std::map is usually intended to be a b-tree.

[lukeworthtkbt]

I am comparing two JSON objects, each with ~180,000 elements and operator== is really slow because of this. Just my 2¢.