poi-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bugzi...@apache.org
Subject [Bug 58740] [PATCH] Fix O(n^2) behavior when generating XLSX files with large number of styles
Date Mon, 12 Sep 2016 14:58:40 GMT
https://bz.apache.org/bugzilla/show_bug.cgi?id=58740

--- Comment #9 from Javen O'Neal <onealj@apache.org> ---
Created attachment 34239
  --> https://bz.apache.org/bugzilla/attachment.cgi?id=34239&action=edit
MappedList data structure that combines a List and a TreeSetValuedHashMap to
improve list reverse lookup speed

I wrote a general-purpose class using commons-collections4.1 (this patch was
generated off the commons collections trunk, not POI). The indexOf and contains
methods were significantly faster, but insertion and removal were pitifully
slow (it's slow to shift all the elements in an array by 1 for an ArrayList
implementation, but this class is even slower because it has to shift the
values of a map--from my trials, it's faster to rebuild the entire map when an
insertion or deletion happens that isn't at the end of the list.

Some sample timing:
Each list was initialized with 10,000 elements and 10,000 operations of each
type were performed in succession. Timing is relative and seems to be
influenced by JIT. Repeatability is around +/-10%, so I have rounded to 2
significant figures. Low numbers are better.
>                        add; toArray; iterator; insert; get; indexOf; contains; remove
>             ArrayList = 2;   1200;       68;    100;    9;    310;      220;      81;
>            LinkedList = 3;   1800;     1500;    350;  420;   1000;     1000;     400;
> NodeCachingLinkedList = 4;   2600;     1900;    250;  350;    860;      830;     370;
>              TreeList = 4;   1300;     3400;     68;   10;   1500;     1500;      55;
>            MappedList = 52;  1600;     1900;  20000;    0;     64;        6;   21000;
> Elapsed time: 1m8s

-- 
You are receiving this mail because:
You are the assignee for the bug.

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@poi.apache.org
For additional commands, e-mail: dev-help@poi.apache.org


Mime
View raw message