Recent

Author Topic: Sorting and Counting  (Read 8587 times)

440bx

  • Hero Member
  • *****
  • Posts: 1300
Re: Sorting and Counting
« Reply #165 on: November 14, 2019, 11:31:44 am »
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.



using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

avk

  • Full Member
  • ***
  • Posts: 171
    • my self-education project
Re: Sorting and Counting
« Reply #166 on: November 14, 2019, 12:24:39 pm »
And thus, the O(log N) algorithm (theoretically) turns into the O(N) algorithm?

440bx

  • Hero Member
  • *****
  • Posts: 1300
Re: Sorting and Counting
« Reply #167 on: November 14, 2019, 01:15:19 pm »
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).


« Last Edit: November 14, 2019, 01:30:23 pm by 440bx »
using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

avk

  • Full Member
  • ***
  • Posts: 171
    • my self-education project
Re: Sorting and Counting
« Reply #168 on: November 14, 2019, 02:20:05 pm »
...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

  • Hero Member
  • *****
  • Posts: 1300
Re: Sorting and Counting
« Reply #169 on: November 14, 2019, 03:31:21 pm »
...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. :)




using FPC v3.0.4 and Lazarus 1.8.2 on Windows 7 64bit.

mpknap

  • Jr. Member
  • **
  • Posts: 92
Re: Sorting and Counting
« Reply #170 on: November 14, 2019, 08:37:57 pm »
@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

  • Jr. Member
  • **
  • Posts: 92
Re: Sorting and Counting
« Reply #171 on: November 15, 2019, 07:47:30 am »
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

  • Full Member
  • ***
  • Posts: 171
    • my self-education project
Re: Sorting and Counting
« Reply #172 on: November 15, 2019, 08:15:11 am »
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

  • Jr. Member
  • **
  • Posts: 92
Re: Sorting and Counting
« Reply #173 on: November 16, 2019, 08:17:02 am »
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!