Anzahl gleicher Elemente in Array

K

Kabauter

Mitglied
Hallo,
wie kann ich in einem sortierten Array die Anzahl gleicher Elemente möglichst schnell (Binäre Suche) herausfinden? In dem Beispiel also die Anzahl von 5 in einem int-array.
Normalerweise (ohne binäre Suche) sieht der Code so aus:

Java: 
for (int i = 0; i < array.length; i++) {
    if (array[i]==5) {   
        anzahl++;
    }
}
 
Das hatte ich mir auch so gedacht, nur fällt mir dazu kein passender Code ein 😀
Hatte den Array in zwei Teile geteilt und so jeden Teil durchsucht, allerdings komme ich dann mit dem finden des ersten Elements nicht mehr klar.
tmp soll hier den kleinsten Index, der die 5 enthält, darstellen
Java: 
while (links < rechts) {
         int mid = (links+rechts) / 2;
         if (array[mid] == 5)
             tmp=middle;
         else if (array[mid] > 5)
             rechts = mid - 1;
         else
             links = mid + 1;
         }
}
 
Kabauter hat gesagt.:
Nein leider nicht, es soll in log(n) gesucht werden.
Zum Vergrößern anklicken....

Also, ich weiß zwar nicht, why ich mir das antue, aber es kann in log(n) herausgefunden werden, wie oft eine Zahl n im (sortiert) Array enthalten ist, dabei steht 0 == nicht enthalten:
Java: 
    // main method...
        for (int i = 0; i < 10; i++) {
            int[] ia = rando.ints(5, 0, 2).toArray();
            Arrays.sort(ia);
            System.out.println(Arrays.toString(ia));
            System.out.println(findNotNCount(ia, findIndex(ia, 0)));
            System.out.println(findNotNCount(ia, findIndex(ia, 1)));
            System.out.println("");
        }

    }

    /**
     * n/2....
     *
     * @param array
     * @param n
     * @return
     */
    static int findNaiv(int[] array, int n) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == n) {
                for (int j = i + 1; j < array.length; j++) {
                    if (array[j] != n) {
                        return j - i;
                    }
                }
                return array.length - i;
            }
        }
        return 0;
    }

    /**
     * log(n)..
     * @param array
     * @param n
     * @return
     */
    static int findIndex(int[] array, int n) {
        int i = 0, j = array.length - 1, k = i + (j - i) / 2;
        while (i <= j) {
            if (array[k] < n) {
                i = k + 1;
                k = i + (j - i) / 2;
            } else if (array[k] > n) {
                j = k - 1;
                k = i + (j - i) / 2;
            } else {
                return k;
            }
        }
        return -1;
    }

    /**
     * log(n)..
     * @param array
     * @param n
     * @return
     */
    static int findNotNCount(int[] array, int n) {
        int i = 0, j = n - 1, k = i + (j - i) / 2;
        while (i <= j) {
            if (array[k] == array[n]) {
                j = k - 1;
                k = i + (j - i) / 2;
            } else {
                i = k + 1;
                k = i + (j - i) / 2;
            }
        }
        if (k < 0) {
            return 0;
        }
        int a = k;
        i = n + 1;j = array.length - 1;k = i + (j - i) / 2;
        while (i <= j) {
            if (array[k] == array[n]) {
                i = k + 1;
                k = i + (j - i) / 2;
            } else {
                j = k - 1;
                k = i + (j - i) / 2;
            }
        }
        int b = k;
        return b - a;
    }

Ich muss aber gleich dazusagen, das es... unklug... ist, das auf ganze/volle 5 Elemente loszulassen; der Unterschied zu findNaiv macht sich vielleicht erst bei Tausenden von Elementen bemerkbar.

hth 😉

Aber hallo, was solls, ich habe auch etwas dabei gelernt. 🙂

Bearbeitung: Ich habe die Ausgabe vergessen:
Code: 
[1, 1, 1, 1, 1]
0
5

[0, 0, 0, 0, 1]
4
1

[0, 1, 1, 1, 1]
1
4

[0, 0, 0, 1, 1]
3
2

[0, 1, 1, 1, 1]
1
4

[0, 0, 0, 1, 1]
3
2

[0, 0, 0, 1, 1]
3
2

[0, 0, 0, 0, 1]
4
1

[0, 1, 1, 1, 1]
1
4

[0, 0, 1, 1, 1]
2
3

wenn man rando mit 4 initialisiert....
 
@Offtopic:
@DerWissende : kauf dir mal https://www.amazon.de/Clean-Code-Handbook-Software-Craftsmanship/dp/0132350882
Kannst du mir erklären wozu du die Kommentare an den Methoden brauchst?

Das sollte der Standard weg sein, der an der Unit gelehrt wird.
Java: 
public class BinarySearch { 
    public void searchBinary(int[] intArr, int anfang, int ende, int zahl) {   
        int grenze = anfang + ((ende - anfang) / 2); 
         
        if (intArr.length == 0) { 
            System.out.println("Array leer."); 
            return; 
        } 
         
        if (grenze >= intArr.length){ 
            System.out.println(zahl + " nicht im Array enthalten."); 
            return; 
        } 

        if (zahl > intArr[grenze]) { 
            searchBinary(intArr, grenze + 1, ende, zahl); 
        } else if (zahl < intArr[grenze] && anfang != grenze) { 
            searchBinary(intArr, anfang, grenze - 1, zahl); 
        } else if(zahl == intArr[grenze]) { 
            System.out.println(zahl + " an Position " + grenze + " enthalten."); 
        } else{ 
            System.out.println(zahl + " nicht im Array enthalten."); 
        } 
    } 

    public static void main(String[] args) { 
        int[] testArr = { 5, 3, 5, 228, 14, 69, 18, 27, 109, 85 }; 
        Arrays.sort(testArr); 
        BinarySearch bs = new BinarySearch(); 
        bs.searchBinary(testArr, 0, testArr.length - 1, 228); 
    } 
}
Zu finden unter:
https://javabeginners.de/Algorithmen/Suchalgorithmen/Binaere_Suche.php
 
Jardcore hat gesagt.:
Das sollte der Standard weg sein, der an der Unit gelehrt wird.
Zum Vergrößern anklicken....
Ja, der findige Fuchs (Student) kennt es am Ende des 1. Semesters. Den Anderen wird es später eingebläut.

aus der Praxis geht hervor, dass mehr als 1 Kommentar pro Methode unangebracht ist. (Methoden dürfen ja nicht beliebig lang werden.)

ABER 1. ist das eine rekursive Methode, 2. etwas langsamer, 3. entspricht das nicht der Aufgabenstellung, 4. sollte die Häufigkeit, mit der ein Element n vorkommt, ermittelt werden, 5. einfach einen Index eines Elements n zu ermitteln, ist nicht genug, 6. deine zwei Prüfungen, ob alle Parameter legal sind, braucht meine Methode *nicht* (das wird inklusiv geprüft).

Dennoch Danke, dass du nochmal die Basics aufzeigst.
 
Hallo,
schön binarySearch() selbst zu implementieren (dann hat man es auch verstanden)
aber es gibt doch java.util.Arrays.binarySearch() mit zahllosen Überladungen, sodass man auch
sortierte arrays mit eigenen Klassen durchsuchen kann, indem man als 3. Parameter einen Comperator
übergibt.
Leider kannst du die Haeufigkeit eines Wertes nicht mit der binarySearch() methode ermitteln. Wenn es einen Wert mehrfach gibt ist die gelieferte Position/Index je nach der Position des Wertes der zuerst geprüft wird ehr zufällig. Wenn der Wert noch nicht enthalten ist, bekommt man die Position abzüglich -1 wo man den noch
unbekannten Wert im Array aufnehmen müsste, damit die Liste sortiert bleibt.Also wenn -1 geliefert wird muss auf Pos 0 eingefügt werden, bei -3 an der Stelle 2.

Ich würde das so lösen:
Java: 
public static countValue(int[] array_sorted,int val)
{   
    int cnt=0; int i=0;
    for (i=0;i < array_sorted.length;i++)
    {
        if (array_sorted[i] == val)
        {
            cnt++; // jetzt nachfolgende werte untersuchen
            for (int k=i+1;k < array_sorted.length;k++)
            { if (array_sorted[k] != val) return cnt;
              cnt++;
            }
        }       
    }
    return cnt;
}
 
Außerdem macht das mein naiver Zählalgorithmus findNaiv bereits (damit (später) evtl. die Laufzeiten vergleichen werden können)...
Außerdem hab ich schon mit eine der besten Implementierungen hingeklatscht...
Soll nicht unfreundlich klingen, aber ich habe mir schon Mühe gegeben.^^
 
Aber findNotNCount ist echt unleserlich... ich sollte zwischendurch auf vernünftige Namensgebung usw.
----
Hallo aber, wenn es (unwahrscheinlich) den Algorithmus noch nicht gab, bin ich der Autor - und keiner darf ihn verwenden. 😀 (Sehr unwahrscheinlich)
 
(Er ist doch gar nicht rekursiv...) Ihr könnt das ja mal testen:
Java: 
    public static void main(String[] args) {
        Random rando = new Random(4);
        long t1 = 0, t2 = 0, t3 = 0;
        for (int i = 5_000; i < 10_000_000; i++) {
            int[] ia = rando.ints(i, 0, 3).toArray();
            Arrays.sort(ia);
            t1 = System.currentTimeMillis();
            int n1 = findNaiv(ia, 0);
            t2 = System.currentTimeMillis();
            int n2 = findNotNCount(ia, findIndex(ia, 0));
            t3 = System.currentTimeMillis();
            System.gc();
            System.out.println("i  = " + i);
            System.out.println("n1 = " + n1);
            System.out.println("n2 = " + n2);
            System.out.println(t2 - t1);
            System.out.println(t3 - t2);
            System.out.println("----");
            if (t2 - t1 > t3 - t2) {
                break;
            }
        }
    }

Das Programm läuft bei mir ca. 1 Minute und hält bei ca. 15_000 an.

Das Programm wird immer irgendwann anhalten (auch ohne Abbruchbedingung)!!!! Da es unterschiedliche Laufzeiten sind.

System.gc ist da, damit das vorherige Array 'aufgeräumt' wird.

Dann ein Fazit noch.... Es ist sinnvoll, diesen Algorithmus bei Elementen > 15_000 anzuwenden. Mir fällt aber keine Anwendung ein, in der es sinnvoll ist, >= 5_000mal dasselbe Element zu haben. 😉
 
Senftube hat gesagt.:
Wäre als Kompromiss zwischen n/2 und log(n) wenn man die Sortiertheit ausnutzen will und nicht das
ganze Array absuchen will. Wenn man von einer Normalverteilung der Werte ausgeht, kann man entscheiden, ob man den Wert von vorne oder von hinten im Array sucht.
Zum Vergrößern anklicken....
Das ist kein Kompromiss, das ist die quasi die Ursprungslösung mit stumpfem durchlaufen in hässlich.
 
DerWissende hat gesagt.:
System.gc ist da, damit das vorherige Array 'aufgeräumt' wird.
Zum Vergrößern anklicken....
Verbreite doch nicht immer diesen Unsinn mit händisch System.gc nutzen wäre irgendwie sinnvoll...

DerWissende hat gesagt.:
Dann ein Fazit noch.... Es ist sinnvoll, diesen Algorithmus bei Elementen > 15_000 anzuwenden. Mir fällt aber keine Anwendung ein, in der es sinnvoll ist, >= 5_000mal dasselbe Element zu haben. 😉
Zum Vergrößern anklicken....
Wäre in der heutigen Zeit auch ein ziemliches Wunder, wenn man plötzlich viele Daten hätte.
 
mrBrown hat gesagt.:
Verbreite doch nicht immer diesen Unsinn mit händisch System.gc nutzen wäre irgendwie sinnvoll...

Wäre in der heutigen Zeit auch ein ziemliches Wunder, wenn man plötzlich viele Daten hätte.
Zum Vergrößern anklicken....
gc: Ok, man müsste ihm noch 100 Millisekunden Zeit geben, damit es sinnvoll ist. Ich habe ja auch nicht behauptet, dass dieser Benchmark perfekt sei.... Aber theoretisch läufts nicht ewig 😉

Daten: Ok, bei DNA vielleicht, dann machts wiederum keinen Sinn, erst zu sortieren, dann zu zählen - anstatt einmal drüber zu laufen.

Das Szenario ist einfach nicht sinnvoll denkbar.

Außerdem.... Evtl. auf anderen nicht Beschimpfungen an den Kopf hauen, ich denke mal, viele sind einfach in der Lernphase.

Alle Hintergründe dazu werden in einer Komplexitätstheorievorlesung ausführlich behandelt 😉
 
DerWissende hat gesagt.:
gc: Ok, man müsste ihm noch 100 Millisekunden Zeit geben, damit es sinnvoll ist. Ich habe ja auch nicht behauptet, dass dieser Benchmark perfekt sei.... Aber theoretisch läufts nicht ewig 😉
Zum Vergrößern anklicken....
Ganz ehrlich: sag besser nie mehr was zu System.gc, da kommt nur Unsinn raus.

DerWissende hat gesagt.:
Daten: Ok, bei DNA vielleicht, dann machts wiederum keinen Sinn, erst zu sortieren, dann zu zählen - anstatt einmal drüber zu laufen.

Das Szenario ist einfach nicht sinnvoll denkbar.
Zum Vergrößern anklicken....
Dir fällt ersthaft nur DNA ein zu Daten mit mehr als 5000 "gleichen" Elementen? Ich kann mir kaum Datenverarbeitung mit weniger als tausenden Elementen vorstellen...
 
Vielleicht so:
Java: 
public static int countValue(int[] arr,int val)
{
    int cnt=0;
    int pos = Arrays.binarySearch(arr,val);
    if (pos < 0) return cnt;
    cnt++;
    // benachbarte werte ober- und unterhalb pos untersuchen
    for (int i=pos-1;i >= 0;i--) // unterhalb
    {
        if (arr[i] != val) break;
        cnt++;
    }
    for (int i=pos+1;i < arr.length;i++) // oberhalb
    {
        if (arr[i] != val) break;
        cnt++;
    }
    return cnt;
}
 
Yeah, nur dass das nicht log(n) ist 😉
Lass es doch einfach, das Verlangte steht ja schon oben. 🙂
----
Oder Übungszwecke, dann will ich nichts gesagt haben...
 
mrBrown hat gesagt.:
naja, angenommen m wächst ähnlich wie n: O(log(n)+m) = O(log(n)+n/x) = O(log(n)+n) = O(n)
Zum Vergrößern anklicken....
🙂Ja, das ist der worst case, beispielsweise wenn sämtliche Elemente gleich sind. Es kann aber nicht viele Zahlen geben, die fast n-mal im Array vorkommen. Im Durchschnitt wird es also schneller sein, es sei denn, man fragt immer wieder diese Zahl ab. Ich glaube, das wäre wirklich kein realistisches Szenario mehr.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

bei 2 Arrays Anzahl gleicher Elemente vergleichen?
Antworten: 49
Anzahl gleicher Elemente in ArrayList
Antworten: 5
JComboBox gleicher Inhalt bedeutet gleicher Index?
Antworten: 7
Ermitteln der Anzahl gleicher Nachkommastellen 2er Zahlen
Antworten: 9
JLayeredPane Elemente auf gleicher Position
Antworten: 7

Zurück
Oben