Date: prev next · Thread: first prev next last
2017 Archives by date, by thread · List index


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


Context


Privacy Policy | Impressum (Legal Info) | Copyright information: Unless otherwise specified, all text and images on this website are licensed under the Creative Commons Attribution-Share Alike 3.0 License. This does not include the source code of LibreOffice, which is licensed under the Mozilla Public License (MPLv2). "LibreOffice" and "The Document Foundation" are registered trademarks of their corresponding registered owners or are in actual use as trademarks in one or more countries. Their respective logos and icons are also subject to international copyright laws. Use thereof is explained in our trademark policy.