Sorting and Counting

[440bx]

However, there is a significant point. In our case, we need a binary search that, in the case of duplicate values, returns the position of the leftmost one.

Yes, that is definitely an important difference in this case. In such a case, when using bsearch, the resulting index when a match is found, has to be "manually adjusted" to ensure it is the index of the first instance match.

[avk]

And thus, the O(log N) algorithm (theoretically) turns into the O(N) algorithm?

[440bx]

And thus, the O(log N) algorithm (theoretically) turns into the O(N) algorithm?

It normally wouldn't be O(n), it would be (lg N) + (avg_dups_per_key/2).

Where avg_dups is the average number of duplicates per distinct element in the table.  Obviously, if that average is large for a large number of unixtimes (in this case) then it will likely be better from a performance viewpoint to create an index of distinct keys (unixtime) and search that index instead.  IOW, as the ratio of N/distinct gets larger, performance suffers.  In the worst case, for 1 element duplicated N times, then it would be O(N).

[avk]

...In the worst case, for 1 element duplicated N times, then it would be O(N).

yes it is, and for N/2, N/4, ... duplicated elements.

[440bx]

...In the worst case, for 1 element duplicated N times, then it would be O(N).

yes it is, and for N/2, N/4, ... duplicated elements.

Yes but, it depends on how the duplicates are distributed.  For instance, consider N elements and all the duplicates are clustered in, just for example, 4 elements.  Accessing any of those 4 elements is basically O(n), while accessing any other element is O(lg N).  For such a distribution (granted, it is an unusual one), the big O of the totality is neither O(n) nor O(lg N), for this example it would be (2n + (n - 4) * lg n)

In the specific case of tracking times across the world for what may be a fairly common event, the safe approach is to create an index of distinct unixtimes and bsearch that.   No undesirable cases that way.

Anyway, your point that the start of the duplicate list isn't returned by a normal bsearch is definitely valid.  I just wanted to point out that, if the duplicates are evenly distributed across the n elements _and_ the ratio of N/duplicates isn't very large (say under 10) then, giving the traditional bsearch "a hand" to find the start of the list is reasonable and, ntdll provides one.

[mpknap]

@mpknap, please test this version.

Yes Yes Yes!!! It works! And that was what I meant, this kind of sorting and displaying information.

Although there is a small problem, pressing F12 to enter the form shows (attachment 1 fot1.jpg), and after attempting installation shows attachment fot2.jpg.

In any case, the algorithm is ok. At the weekend I will check it.
Thank you once again.

[mpknap]

I don't understand why you can't install VirtualtreeView, I try in different ways and every time different errors. Even in the latest version of lazarus, OnlinePackageManager does not help.

I can't edit the form without it.

AVK, you can't write it in standard Lazarus packages?

If not, I give up ...

[avk]

I am glad to see some progress in your efforts, but I do not understand your failure to install VirtualTreeview. I installed VirtualTreeview from /lazarus/components/virtualtreeview. Compilation and installation are performed without any errors.

[mpknap]

finally, I was able to install. I had two other versions of Lazarus on the disk, I deleted them badly.
everything works, thank you again!