https://bz.apache.org/bugzilla/show_bug.cgi?id=58740
--- Comment #9 from Javen O'Neal <one...@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-unsubscr...@poi.apache.org For additional commands, e-mail: dev-h...@poi.apache.org