diff options
| author | battre@chromium.org <battre@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2013-04-23 08:12:27 +0000 |
|---|---|---|
| committer | battre@chromium.org <battre@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2013-04-23 08:12:27 +0000 |
| commit | 342a79f2385be0c176cc9a175709061ab91a35ad (patch) | |
| tree | 741cd7dbf74db03ebb15e07be0438b2cea17066e /cloud_print/service/win | |
| parent | 50833ddb63f44b1b4e4661b713940c9d17ecfd64 (diff) | |
| download | chromium_src-342a79f2385be0c176cc9a175709061ab91a35ad.zip chromium_src-342a79f2385be0c176cc9a175709061ab91a35ad.tar.gz chromium_src-342a79f2385be0c176cc9a175709061ab91a35ad.tar.bz2 | |
Use std::map<int, int> instead of SparseArray<int> to save memory.
The PrefilterTree used a SparseArray<int> for pointers to "parents" (think of
this as pointers to ancestors). Despite its name, each SparseArray that is
allocated in such a way that is can store up to N element actually consumes
O(N) memory. Always! Regardless of its utilization! Given that in a tree with
N nodes, each node could have up to O(N) ancestors, this makes the
PrefilterTree consume O(N^2) memory for N nodes. In practice PrefilterTree
nodes have only few ancestor pointers ("parents"). Therefore, it is more
economic to use a std::map<int, int> which consumes less memory.
BUG=112155
NOTRY=true
Review URL: https://chromiumcodereview.appspot.com/14120010
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@195762 0039d316-1c4b-4281-b951-d872f2087c98
Diffstat (limited to 'cloud_print/service/win')
0 files changed, 0 insertions, 0 deletions