search

byzhang / rapidjson

Automatically exported from code.google.com/p/rapidjson
MIT License
0 stars 0 forks source link

Object's member access is O(n) #5

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
Object member access, i.e. Value::FindMember(), is in O(n) by linear searching.

Design a faster approach for member access.

Original issue reported on code.google.com by milo...@gmail.com on 30 Nov 2011 at 5:31

GoogleCodeExporter commented 9 years ago 
[deleted comment]
GoogleCodeExporter commented 9 years ago 
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.

Original comment by fasdfas...@gmail.com on 23 Jul 2013 at 9:28

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

Original comment by bas...@starynkevitch.net on 5 Nov 2013 at 10:00

GoogleCodeExporter commented 9 years ago 
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.

Original comment by drawtree@gmail.com on 21 Dec 2013 at 4:57

GoogleCodeExporter commented 9 years ago

Original comment by milo...@gmail.com on 20 Jun 2014 at 8:28

GoogleCodeExporter commented 9 years ago 
Added an analysis on this issue.
https://github.com/miloyip/rapidjson/issues/102

Original comment by milo...@gmail.com on 11 Aug 2014 at 5:32