What's the complexity of getJSONObject and getJSONArray methods?Ask Question

问题:

I'm using org.json library as JSON-client for my Java application and I would like to know the complexity of some methods from this lib.

I'm retrieving thousands of JSON objects inside a JSON array inside another JSON objects (and so on) from a database via it's HTTP API. As an example (and only as an example, my case is much more complex), suppose that I'm doing something like that:

// Ignoring attributes types
import org.json.*;

public static void main(String[] args) {
    response = MyHTTPClient.post(url, query).asJSON();
    response = JSON.parse(response);
    data = response.getJSONObject(1).getJSONArray("results").getJSONObject(0);
}

What's the complexity of getJSONObject(int) and getJSONArray(String) methods from org.json library? Is it running in a constant [O(1)] or linear [O(n)] time? If none, what's the correct answer?

回答1:


org.json will parse the entire JSON document when you instantiate the JSONObject from a string (or JSONTokener). The getJSONObject() and getJSONArray() methods are just typed versions of the untyped get() methods (which return Object instance). if you look at the source you can see that JSONObject uses a HashMap while JSONArray uses an ArrayList for internal representations, so the execution times are close-to-constant (O(1))

回答2:


Both getJSONArray and getJSONObject and methods eventually call opt(String paramString) method which gets value from a HashMap. So they should work in close to constant time i.e. O(1) ideally. Here's a code snippet:

public Object opt(String paramString)
{
  return paramString == null ? null : map.get(paramString);
}

You can look at the source code yourself and dig in.

标签: json time-complexity asymptotic-complexity org.json
© 2014 TuiCode, Inc.