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
Attachment:
signature.asc
Description: PGP signature