Binäre Suche gibt das erste, aber nicht das dichteste Element zurück

CyborgBeta · 13. August 2021 um 09:08

Kann ich binaryContains so ändern, dass das am dichtesten an x liegende Element zurückgegeben wird?

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Random;

public class BinarySearchWithAFuzzinessTest {
    private static int testAndGetIndex(double[] list, double x, double delta, int i) {
        if (Math.abs(x - list[i]) <= delta) {
            while (i - 1 >= 0 && Math.abs(x - list[i - 1]) <= delta) {
                i--;
            }
            return i;
        }
        return -1;
    }

    /**
     * Returns the first occurrence, that fulfills the constraints.
     */
    public static int binaryContains(double[] list, double x, double delta) {
        if (list == null || list.length == 0) {
            throw new NoSuchElementException("provide at least one element");
        }
        int i = 0;
        int j = list.length / 2;
        int k = list.length - 1;
        while (true) {
            System.out.println(i + " " + j + " " + k);
            if (x + delta < list[i]) {
                return -1;
            }
            int temp;
            if ((temp = testAndGetIndex(list, x, delta, i)) != -1) {
                return temp;
            }
            if ((temp = testAndGetIndex(list, x, delta, j)) != -1) {
                return temp;
            }
            if ((temp = testAndGetIndex(list, x, delta, k)) != -1) {
                return temp;
            }
            if (x < list[j]) {
                k = j;
                j = (i + j) / 2;
                if (j == k) {
                    return -1;
                }
            } else if (x < list[k]) {
                i = j;
                j = (j + k) / 2;
                if (i == j) {
                    return -1;
                }
            } else {
                return -1;
            }
        }
    }

    /**
     * Returns the first occurrence, that fulfills the constraints. This is for testing.
     */
    public static int linearContains(double[] list, double x, double delta) {
        for (int i = 0; i < list.length; i++) {
            if (Math.abs(x - list[i]) <= delta) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Random r = new Random(1234);

        for (int i = 0; i < 100000; i++) {
            double[] a = new double[1 + r.nextInt(20)];
            double x = r.nextInt(20) - 10;
            double delta = r.nextDouble();
            for (int j = 0; j < a.length; j++) {
                if (r.nextBoolean()) {
                    a[j] = x + r.nextDouble() * 5 * delta;
                } else {
                    a[j] = x - r.nextDouble() * 5 * delta;
                }
            }
            Arrays.sort(a);

            int c1 = binaryContains(a, x, delta);
            int c2 = linearContains(a, x, delta);
            if (c1 != c2) {
                System.out.println("OOPS " + x + " " + delta);
                System.out.println(Arrays.toString(a) + " " + c1 + " " + c2);
                break;
            }
        }
    }
}

CyborgBeta · 14. August 2021 um 05:10

Hab’s hinbekommen…

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Random;

public class BinarySearchWithAFuzzinessTest {
    /**
     * Returns the first occurrence, that fulfills the constraints.
     */
    public static int binaryContains(double[] list, double x, double delta) {
        if (list == null || list.length == 0) {
            throw new NoSuchElementException("provide at least one element");
        }
        int i = 0;
        int j = list.length / 2;
        int k = list.length - 1;
        int r = -1;
        if (x + delta < list[i]) {
            return r;
        }
        if (Math.abs(x - list[i]) <= delta) {
            r = i;
            delta = Math.nextAfter(Math.abs(x - list[i]), 0);
        }
        if (Math.abs(x - list[j]) <= delta) {
            r = j;
            delta = Math.nextAfter(Math.abs(x - list[j]), 0);
        }
        if (Math.abs(x - list[k]) <= delta) {
            r = k;
            delta = Math.nextAfter(Math.abs(x - list[k]), 0);
        }
        while (true) {
            System.out.println(i + " " + j + " " + k);
            if (x < list[j]) {
                k = j;
                j = (i + j) / 2;
                if (j == k) {
                    return r;
                }
                if (Math.abs(x - list[j]) <= delta) {
                    r = j;
                    delta = Math.nextAfter(Math.abs(x - list[j]), 0);
                } else if (Math.abs(x - list[k]) <= delta) {
                    r = k;
                    delta = Math.nextAfter(Math.abs(x - list[k]), 0);
                }
            } else if (x < list[k]) {
                i = j;
                j = (j + k) / 2;
                if (i == j) {
                    return r;
                }
                if (Math.abs(x - list[i]) <= delta) {
                    r = i;
                    delta = Math.nextAfter(Math.abs(x - list[i]), 0);
                } else if (Math.abs(x - list[j]) <= delta) {
                    r = j;
                    delta = Math.nextAfter(Math.abs(x - list[j]), 0);
                }
            } else {
                return r;
            }
        }
    }

    /**
     * Returns the first occurrence, that fulfills the constraints. This is for testing.
     */
    public static int linearContains(double[] list, double x, double delta) {
        for (int i = 0; i < list.length; i++) {
            if (Math.abs(x - list[i]) <= delta) {
                delta = Math.abs(x - list[i]);
                while (i + 1 < list.length && Math.abs(x - list[i + 1]) < delta) {
                    i++;
                    delta = Math.abs(x - list[i]);
                }
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Random r = new Random(1234);

        for (int i = 0; i < 100000; i++) {
            double[] a = new double[1 + r.nextInt(20)];
            double x = r.nextInt(20) - 10;
            double delta = r.nextDouble();
            for (int j = 0; j < a.length; j++) {
                if (r.nextBoolean()) {
                    a[j] = x + r.nextDouble() * 5 * delta;
                } else {
                    a[j] = x - r.nextDouble() * 5 * delta;
                }
            }
            Arrays.sort(a);

            int c1 = binaryContains(a, x, delta);
            int c2 = linearContains(a, x, delta);
            if (c1 != c2) {
                System.out.println("OOPS " + x + " " + delta);
                System.out.println(Arrays.toString(a) + " " + c1 + " " + c2);
                break;
            }
        }
    }
}

Ich weiß gar nicht, ob es das schon gibt… Wenn noch nicht, so gebührt die Erfindung mir.

@Marco13 Siehst du da vielleicht etwas, was man vereinfachen könnte?

CyborgBeta · 14. August 2021 um 16:25

Das musste Math.nextAfter(Math.abs(x - list[i]), -1); lauten, die -1 ist wichtig, wenn das Array z. B. nur gleiche Elemente enthält. Ich habe bis jetzt keinen Fall gefunden, für den es nicht funktioniert:

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Random;

public class BinarySearchWithAFuzzinessTest {
    /**
     * Returns the first occurrence, that fulfills the constraints.
     */
    public static int binaryContains(double[] list, double x, double delta) {
        if (list == null || list.length == 0) {
            throw new NoSuchElementException("provide at least one element");
        }
        int i = 0;
        int j = list.length / 2;
        int k = list.length - 1;
        int r = -1;
        if (x + delta < list[i]) {
            return r;
        }
        if (Math.abs(x - list[i]) <= delta) {
            r = i;
            delta = Math.nextAfter(Math.abs(x - list[i]), -1);
        }
        if (Math.abs(x - list[j]) <= delta) {
            r = j;
            delta = Math.nextAfter(Math.abs(x - list[j]), -1);
        }
        if (Math.abs(x - list[k]) <= delta) {
            r = k;
            delta = Math.nextAfter(Math.abs(x - list[k]), -1);
        }
        while (true) {
//            System.out.println(i + " " + j + " " + k);
            if (x < list[j]) {
                k = j;
                j = (i + j) / 2;
                if (j == k) {
                    return r;
                }
                if (Math.abs(x - list[j]) <= delta) {
                    r = j;
                    delta = Math.nextAfter(Math.abs(x - list[j]), -1);
                } else if (Math.abs(x - list[k]) <= delta) {
                    r = k;
                    delta = Math.nextAfter(Math.abs(x - list[k]), -1);
                }
            } else if (x < list[k]) {
                i = j;
                j = (j + k) / 2;
                if (i == j) {
                    return r;
                }
                if (Math.abs(x - list[i]) <= delta) {
                    r = i;
                    delta = Math.nextAfter(Math.abs(x - list[i]), -1);
                } else if (Math.abs(x - list[j]) <= delta) {
                    r = j;
                    delta = Math.nextAfter(Math.abs(x - list[j]), -1);
                }
            } else {
                return r;
            }
        }
    }

    /**
     * Returns the first occurrence, that fulfills the constraints. This is for testing.
     */
    public static int linearContains(double[] list, double x, double delta) {
        if (list == null || list.length == 0) {
            throw new NoSuchElementException("provide at least one element");
        }
        for (int i = 0; i < list.length; i++) {
            if (Math.abs(x - list[i]) <= delta) {
                delta = Math.abs(x - list[i]);
                while (i + 1 < list.length && Math.abs(x - list[i + 1]) < delta) {
                    i++;
                    delta = Math.abs(x - list[i]);
                }
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Random r = new Random(1234);

        for (int i = 0; i < 100000; i++) {
            double[] a = new double[1 + r.nextInt(20)];
            double x = r.nextInt(20) - 10;
            double delta = r.nextDouble();
            for (int j = 0; j < a.length; j++) {
                if (r.nextBoolean()) {
                    a[j] = x + r.nextDouble() * 5 * delta;
                } else {
                    a[j] = x - r.nextDouble() * 5 * delta;
                }
            }
            Arrays.sort(a);

            int c1 = binaryContains(a, x, delta);
            int c2 = linearContains(a, x, delta);
            if (c1 != c2) {
                System.out.println("OOPS " + x + " " + delta);
                System.out.println(Arrays.toString(a) + " " + c1 + " " + c2);
                break;
            }
        }

        double[] testArray2 = {4, 4, 4};
        System.out.println(binaryContains(testArray2, 4, 0));
        System.out.println(linearContains(testArray2, 4, 0));

        testArray2 = new double[]{Math.nextAfter(4, 3), 4, 4};
        System.out.println(binaryContains(testArray2, 4, 0));
        System.out.println(linearContains(testArray2, 4, 0));
        System.out.println(binaryContains(testArray2, Math.nextAfter(4, 3), 0));
        System.out.println(linearContains(testArray2, Math.nextAfter(4, 3), 0));
        System.out.println(binaryContains(testArray2, Math.nextAfter(4, 5), 0));
        System.out.println(linearContains(testArray2, Math.nextAfter(4, 5), 0));
    }
}

Auf Codereview Stackexchange hat mir jemand ein formales Review um die Ohren gehauen (https://codereview.stackexchange.com/questions/266047/binary-search-to-find-the-closest-element), es sind aber, so denke ich, keine gröberen Fehler enthalten.

Marco13 · 14. August 2021 um 20:04

Zu Recht.

Alles, was Pavlo Slavynskyy auf stack exchange gesagt hat (und sei froh, dass es dort immernoch „newbies“ gibt, die die Engelsgeduld aufbringen, die dafür notwendig ist - wenn er deine üblichen Posts hier kennte, hätte er die Antwort vielleicht nicht geschrieben).

Einer der „absurdesten“ Punkte ist das nextAfter. Ich habe in den letzten 25 Jahren geschätzt sicher mehr als eine Million Zeilen Code geschrieben, und davon überdurchschnittlich viel mathematiklastiges (zwar auch keine „Hardcore-Numerik“, aber immerhin), und NIE auch nur die Möglichkeit in Betracht gezogen, dass es sinnvoll sein könnte, diese Methode für irgendwas zu verwenden. (Sowas wie eine Github-Suche danach ist schon vielsagend).

Aber … gerade deswegen (nämlich weil man ~„so eine Funktion vielleicht in einem dieser mathematiklastigen Zusammenhänge ab und zu mal brauchen könnte“) habe ich sie auch mal implementiert:

public static int binaryContains(double[] list, double x, double delta) {
    
    int index = indexOfClosest(list, x);
    if (index == -1)
    {
        return -1;
    }
    if (Math.abs(x - list[index]) < delta)
    {
        return index;
    }
    return -1;
}
private static int indexOfClosest(double[] list, double x) {
    
    int index = Arrays.binarySearch(list, x);
    if (index >= 0)
    {
        return index;
    }
    int insertionPoint = -(index + 1);
    if (insertionPoint == list.length)
    {
        return list.length - 1;
    }
    if (insertionPoint > 0)
    {
        double absDiffCurr = Math.abs(x - list[insertionPoint]);
        double absDiffPrev = Math.abs(x - list[insertionPoint - 1]);
        if (absDiffPrev < absDiffCurr)
        {
            return insertionPoint - 1;
        }
    }
    return insertionPoint;
}

Was macht die Funktion?

Sie bestimmt den Index des Elementes, das dem gesuchten Element am nächsten liegt. Das ist eine eigenständige Funktion, die sinnvoll und nützlich sein könnte, isoliert entwickelt und getestet und dokumentiert werden kann
Sie prüft ob das Element an diesem Index innerhalb des „deltas“ liegt, und gibt entsprechend den index oder -1 zurück

^{Bevor du meckerst: Dass sie, wenn alle Zahlen im Array gleich sind, etwas anderes zurückgibt, als deine, ist ein Detail - ohne Spezifikation oder Begründung ist dieser Fall ziemlich beliebig, und könnte mit sowas wie if (isAllEqual(array)) return 42; abgefrühstückt werden.}

Was macht deine Implementierung?

Sie schaut sich das erste, mittlere und letzte Element an. Wenn …
Sie schaut, ob die Zahl, die … in der IEEE-754-Floating-Point Repräsentation vor einer Differenz zwischen …
Wenn die Zahl kleiner ist, als … wieder irgendwas mit Differenzen und Zahlen…
…

Im Ernst:

Beschreib’ mal, was deine Funktion MACHT!

Und danach könnten wir vielleicht noch ein bißchen darüber plaudern, was ein „Guter Programmierer“ und was ein „Schlechter Programmierer“ ist.

CyborgBeta · 15. August 2021 um 16:40

Naja, das Ding heißt Codereview Stackexchange, dann darf man doch, wenn auch alles auf freiwilliger Basis, ein solches erwarten? Von Volksvertretern würde man doch auch erwarten, dass sie das Volk vertreten.

Im Prinzip ist Programmieren doch wie Musik machen… man schreibt die Noten in sinnvoller Reihenfolge auf, die man im Kopf hat, auch, wenn es sie, also die spezielle Notenfolge, noch nicht gab. Nun weißt du, wofür man die Methode nextAfter gebrauchen könnte.

Dem einen gelingt das mehr oder weniger gut, der andere schreibt halt ab, und ein Dritter transferiert einfach etwas. Pattern und Anti-Pattern helfen uns dabei, den Code zu „verschönern“.

Das könnte ich zwar tun, aber nicht mehr heute. (Habe gestern ein bissel Alk zu mir genommen, der muss erst durch die Leber durch)

Merci für dein Feedback.

anon2594669 · 16. August 2021 um 12:04

Naja, der Code verstößt gegen so viele Dinge. Da würde ich in meiner Freizeit auch kein Review machen. Dein Code wirkt auf mich wie „ich lerne gerade coden“. Und klar, mathematische Aufgaben sind nicht unbedingt leicht in sauberen Code zu überführen, trotzdem ist Dein Code leider kaum lesbar.

Du möchtest mir doch nicht erzählen, dass Du den Code bei Deiner Erfahrung als sauber bzw. lesbar einstufst?

CyborgBeta · 16. August 2021 um 12:39

@anon2594669 : Viele der angeblichen „Verstöße“ liegen in einer subjektiven „Grauzone“…

Ich sehe es ja ein, dass r ungünstig gewählt wurde, aber i, j und k würde ich nicht unbedingt umbenennen wollen.

anon2594669 · 16. August 2021 um 15:16

Offensichtlich wurde Dir das im Review aber ja um die Ohren gehauen. Das hat wenig mit einer subjektiven Grauzone zu tun.

Gerade in der Mathematik gibt es ja viele Definitionen und Begriffe. Die dürfen natürlich benutzt werden. Dann gibt es Patterns (in diesem Fall z.B. Strategy), die die Lesbarkeit des Codes enorm verbessern.

Zum Naming ein paar Beispiele:
testAndGetIndex() Was genau tut diese Methode? Was wird getestet? Was für ein Index wird ermittelt?
double[] list, double x Hier wird nicht klar, in welchem Zusammenhang diese beiden Dinge stehen
int temp; Temp von was?
System.out.println(i + " " + j + " " + k); würde mir später nicht mehr helfen. Welche Variable ist welche?
int i, j, k natürlich geht das hier besser.

Der Code aus Binäre Suche – Wikipedia ist durchaus lesbarer.

Du darfst natürlich der Meinung sein, dass Dein Code les- und wartbar ist. Für mich ist er dies nicht. Und bei Stackexchange kommt es offensichtlich auch nicht an. Was Du daraus machst, ist Deine Sache.

Marco13 · 16. August 2021 um 15:27

Das ist ein passender Vergleich. Nur wenige sollten es öffentlich tun. Und du gehörst da sicher nicht dazu.

Nein.

Jeder hier sagt dir, dass dein Code Mist ist. Auf StackExchange wird dir das gesagt. Wer müßte es dir sagen, damit du es glauben und etwas daran ändern würdest? Es ist ungeheuer schwer, nicht anzunehmen, dass da „böser Wille“ dabei ist. Vielleicht ist es auch „nur“ Ignoranz. Aber es ist ungeheuer lästig, egal, was die Ursache ist.

CyborgBeta · 16. August 2021 um 17:54

Der Vergleich ist passend. Beethovens Symphonien haben seine Auftraggeber anfangs auch nicht verstanden, da sie zu kompliziert erschienen.

Oh doch. Ich hätte i,j,k low,mid,high nennen können, das legt aber schon die Reihenfolge der Buchstaben im Lateinischen Alphabet nahe. Davon ausgehen, dass Softwareentwickler das Alphabet können, darf man doch - oder?

Beziehe dich bitte auf den aktuellen, den auf Stackexchange und hier gezeigten Code - und nicht auf einen Prototyp. In der aktuellen Version kommt testAndGetIndex() gar nicht mehr vor.

Das ist ein gutes Beispiel für eine subjektive Einschätzung. Du darfst deine Meinung gerne für dich behalten, danach hatte ich eigentlich nicht gefragt.

Schönen Abend.

anon2594669 · 16. August 2021 um 19:12

Naja, ich mache Codereviews professionell. Und wenn Du hier im Forum solche Fragen stellst, möchtest Du doch Antworten haben, oder? Ich bin echt verwirrt und vermutlich wieder auf Dein Trolling reingefallen. Mach ruhig, wie Du meinst.

Btw. Deine letzte hier gezeigte Version finde ich beinahe noch schlimmer.

CyborgBeta · 16. August 2021 um 19:24

Wenn man gemein wäre, könnte man jetzt antworten, das merkt man nicht. Und wie gesagt, ich hatte nach einer „objektiven Einschätzung“ gefragt, keiner subjektiven. Ich habe auch kein Interesse daran, dass das Thema entgleist. Aber das liegt nicht an mir.

i, j und k sind geläufige Abkürzungen für Indexvariablennamen. Ab wann sie das nicht mehr sind, ist eine Grauzone. Mehr hab ich doch gar nicht behauptet. Insgesamt ist das Review auf Stackexchange an manchen Stellen überzogen. Zu drei der Review-Punkte könnte ich erwidern, dass sie zwar nicht falsch seien, aber auch nicht „absolut richtig“ seien.

Marco13 · 16. August 2021 um 20:01

Die objektive Einschätzung ist, das der Code, den du hier postest, IMMER schlecht ist. Und eben nicht „schlecht“ im Sinne von „Hey, da könnte man eine Kleinigkeit dran optimieren“, sondern „schlecht“ im Sinne von „Was soll das denn für’n Scheißdreck sein!?“. Und er ist „fraktal schlecht“, indem Sinne, dass er schlecht ist, egal ist, auf welcher Ebene man die Analyse vornimmt. Es wird dir immer wieder das gleiche gesagt, aber kein Ratschlag, von Leuten, die schon seit 20 Jahren 8 Stunden am Tag programmieren wird von dir auch nur ansatzweise aufgenommen. Stattdessen wird alles mit verstörender Ignoranz und Selbstgefälligkeit quittiert, wodurch die Threads immer wieder gleich verlaufen. Und und dann wird, als Sahnehäubchen, noch so ein beiläufiges „Aber das liegt nicht an mir.“ hier eingestreut. Doch. Tut es.

Dein nächster Beitrag (egal, ob hier im Thread oder woanders) entscheidet über eine mindestens 4-wöchige Sperre. Also pass’ auf. Und … wenn du gesperrt wirst, denk’ dran: „Das liegt nicht an mir“.

CyborgBeta · 16. August 2021 um 20:11

@Marco13 Du redest so, als hätte ich Sym dazu gezwungen, hier zu antworten. Muss ich jemandes Hand küssen, der einfach nur 20 Jahre Erfahrung hat? Ich bin sachlich, ihr nicht.

anon2594669 · 16. August 2021 um 21:02

Ich glaube, dass kannst du nicht beurteilen. In der Regel ist dein Code Mist. In der Regel suchst du hier Streit. Ich hoffe für dich, dass das nur Trolling ist und du im wahren Leben nicht genauso oft gegen die Wand läufst.

Landei · 17. August 2021 um 07:06

Ich denke, Dunning Kruger schlägt hier gewaltig zu. CB ähnelt Florence Foster Jenkins, der „schlechtesten Sängerin der Welt“, die auch nicht zu überzeugen war, dass sie einfach nicht singen konnte. Der einzige Unterschied ist, dass sie trotzdem eine Karriere daraus gemacht hat.

anon2594669 · 17. August 2021 um 08:12

Danke für den Hinweis! Ich kann den Dunning-Kruger-Effekt noch nicht.

Das Zitat von Dunning gefällt mir

„Wenn man inkompetent ist, kann man nicht wissen, dass man inkompetent ist […]. Die Fähigkeiten, die Sie benötigen, um eine richtige Antwort zu geben, sind genau die Fähigkeiten, die Sie benötigen, um zu erkennen, was eine richtige Antwort ist.“

Ich habe wieder etwas gelernt!

Marco13 · 17. August 2021 um 12:20

Ich kannte den natürlich schon. Ich bin schließlich Experte für Kognitionspsychologie

An sich hätte dieser Thread hier ja ein interessanter sein können. Aber … Müllcode zur Eröffnung, Beratungsresistenz, Anmaßung und Bashing sind bei CB-Threads offenbar unvermeidlich. Zumindest ist damit jetzt mal für zwei Wochen Ruhe.

TMII · 18. August 2021 um 15:23

CB lernt vielleicht nichts, aber andere vielleicht schon. Darf ich fragen wie bei dir so eine Methode heißen könnte unabhängig vom Thema? Wäre sowas wie
textIfInsideAndGetTreePosition()
in Ordnung oder zu lang?

Ich frage auch ein unter anderem vor dem Hintergrund, dass die Methode bei CB privat ist. Innerhalb eines Objektes, könnte man theoretisch davon ausgehen dass die Funktionsweise sich aus dem Kontext der generellen Funktion des Objektes ergibt?

Marco13 · 18. August 2021 um 17:14

Ich finde auch, dass bei so einer Methode ein name wie testAndGetIndex OK sein kann. Sowas wie findFirstIndexInRange(..., int startIndex) wäre besser (und dann müßte/sollte man auch das i nicht verändern), und ich als JavaDoc-Nazi würde dann halt noch ein JavaDoc dazuschreiben und die Parameter erklären und sagen, wann welche Exception geworfen wird und so. Aber … es gibt wichtigere, driftigere, und objektivere Dinge, die man kritisieren kann, als den namen einer privaten Methode.