Hi Dennis, On Thursday, 2017-08-24 15:33:26 +0530, Dennis Francis wrote:
> One way to improve the situation is > to store absolute > position of first element of each block in the block instead of the block > size member. This > can improve the lookup time up to log(log(N)) using linear interpolation > search or at least log(N) > if we fallback to binary search after a few initial passes of > linear-interpolation search. > > Down side of this approach is that in the worst case, insert/deletes incur > O(N) cost because > absolute positions stored in each block subsequent to the delete/insert > block have to be changed, > but this still would be way better than old cell storage case when there > was no concept of blocks. Does not sound very appealing to me. A better lookup time is certainly desirable by means of interpolation or binary search, but at the cost of insertion/deletion time that's not gonna fly. We still have bottlenecks where inserting and especially changing type of a cell, which leads to shrinkage of one block and enlargement or insertion of another, can build up to looong waiting times. I don't have the bug number at hand right now, but the worst case is a Find&Replace that changes string cells to numeric (or vice versa) in a column of data. I think these should be addressed first. Eike -- LibreOffice Calc developer. Number formatter stricken i18n transpositionizer. GPG key 0x6A6CD5B765632D3A - 2265 D7F3 A7B0 95CC 3918 630B 6A6C D5B7 6563 2D3A Care about Free Software, support the FSFE https://fsfe.org/support/?erack
signature.asc
Description: PGP signature
_______________________________________________ LibreOffice mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/libreoffice
