System.Generics.Collections.TList.BinarySearch if there are duplicates

[Uwe Raabe 1890]

15 minutes ago, Vandrovnik said:

Has someone created it on QP, so that we can vote?

Currently I cannot find one. Seems like @dummzeuch is the right person. If he refuses I will be happy to step in.

 

The reference to the TStringList.Find implementation should definitely be mentioned. I also suggest a separate QP entry for updating the documentation.

[Stefan Glienke 1905]

13 hours ago, Anders Melander said:

It's fine that there are corner cases that performs worse than optimal, like with quick sort

Which has been a solved problem for quite some - it's called IntroSort - no language I know uses plain QuickSort as their default standard library sort these days. If not IntroSort they might use TimSort.

Edited December 9, 2022 by Stefan Glienke

[David Heffernan 2300]

37 minutes ago, Uwe Raabe said:

It is just my personal opinion that if everybody is going to avoid the standard routines in favor of writing its own, we may never see any improvement in that area.

I don't think that's right. You suggest we should just use broken code because that's likely to persuade Emba to change it? I want the program that I ship to be good. 

[Uwe Raabe 1890]

57 minutes ago, David Heffernan said:

You suggest we should just use broken code

Neither did I say so, nor is the code broken. It may have a bad performance in some cases, but if I can rule out these cases, why should I dismiss that code?

[David Heffernan 2300]

44 minutes ago, Uwe Raabe said:

Neither did I say so, nor is the code broken. It may have a bad performance in some cases, but if I can rule out these cases, why should I dismiss that code?

It's broken in my view because binary search should be O(log n). And this code isn't. It isn't binary search. It's a hybrid binary and linear search. Obviously people can do what they want. I won't be using this code though. 

[Uwe Raabe 1890]

Here is the QP entry: https://quality.embarcadero.com/browse/RSP-40174

[Attila Kovacs 617]

Why did they change it in the first place?

[Uwe Raabe 1890]

Because it didn't return the first matching element but an arbitrary one.

 

I was pretty sure someone requested it, but I cannot find any QP entry for that. It is also possible that it was initiated internally.

[Attila Kovacs 617]

20 minutes ago, Uwe Raabe said:

Because it didn't return the first matching element but an arbitrary one.

 

I'm not sure on that. Look the code in Berlin, it's searching from the left and returning the first matching element.

 

Edit: oh no, I see.

 

Edit edit, well, no-oh no, can't see again. 😄

 

If the list is sorted I can't create a list where binsearch would not return the first element in the list. Berlin U2.

 

 

Edited December 9, 2022 by Attila Kovacs

[Uwe Raabe 1890]

Seems you are right. The implementation up to 10.4 looks like it is already satisfying the requirement. In that case the change made in 11 may as well be reverted.

 

I will ask for the reason of that change.

[Uwe Raabe 1890]

On 12/8/2022 at 11:08 AM, dummzeuch said:

OK, so it depends on the Delphi version.

As we now found out: it doesn't. While the implementation changed in Delphi 11 it always made a lower bound binary search even in Delphi versions below 11.

[dummzeuch 1392]

1 hour ago, Uwe Raabe said:

As we now found out: it doesn't. While the implementation changed in Delphi 11 it always made a lower bound binary search even in Delphi versions below 11.

OK, so there are two bugs:

1. the documentation is (and has always been) wrong.
2. the implementation in Delphi 11 was "verschlimmbessert" (made worse by trying to improve it).
3. The function BinarySearch should have been called differently (yes, off by one)

Goes to show that I should simply have done what I did while the quality of the docs was even worse than it is today: Look at the sources.

Edited December 10, 2022 by dummzeuch

[Tommi Prami 123]

On 12/9/2022 at 4:42 PM, Uwe Raabe said:

Here is the QP entry: https://quality.embarcadero.com/browse/RSP-40174

Voted...