[Java] Wie bei boolean[] schnell bestimmen, ob alle Elemente true sind?

[Gast]

ja das topic ist eigentlich schon aussagekräftig genug X-D

mich interessiert eine möglichst effiziente methode

würde jetzt einfach alle elemente durchgehen und beim ersten false eben false zurückgegeben, sonst true.

[Monger]

Ich glaube, schneller kann es auch nicht gehen.

Ist das nicht ein Fall für eine binäre Suche? Geht die irgendwie schneller als mit linearem Aufwand?
Vielleicht kann man sich durch geschickte Vorsortierung und irgendwelche statistischen Verfahren die Wahrscheinlichkeit erhöhen gleich einen richtigen Treffer zu machen, aber ich glaubs irgendwie nicht so wirklich...

[Senior Sanchez]

Es gebe ne andere Variante, die das eventuell um den Faktor 32 beschleunigen könnte, was aber immer noch zur Klasse der linearen Probleme gehört, zumindest bei n boolean Elemente gegen unendlich. Für 32 boolean-Werte hätte es aber ne konstante Laufzeit.

Verwende anstatt von booleans doch einfach 32 Bit ints.
Die einzelnen Bits eines ints stellen dabei eben boolsche Werte dar und somit kann ein int 32 booleans ersetzen ;)
Natürlich müssteste dir dann bei mehr booleans natürlich nen int array erschaffen.

Nun kannste bitweise, mithilfe entsprechender Masken und entsprechender Oder-Verknüpfung ein Bit im int auf 1 setzen, was dann eben true entspricht, wohingegen 0 eben false ist. Das ganze klingt jetzt komplizierter als es eigentlich ist, aber vllt ist es auch etwas oversized ;)

Jedenfalls kommt am Ende der Clou, wenn du testen willst ob alle bits true ist ;)
Wenn das nämlich der Fall ist hat der int den Wert von 2^33 - 1 ;)

[Der Namenlose]

Monger[/POST]']
Vielleicht kann man sich durch geschickte Vorsortierung und irgendwelche statistischen Verfahren die Wahrscheinlichkeit erhöhen gleich einen richtigen Treffer zu machen, aber ich glaubs irgendwie nicht so wirklich...

Klar, wenn die zuerst alle false und danach die true kommen, dann braucht man nur das erste Element zu testen.

[AlSvartr]

Senior Sanchez[/POST]']Jedenfalls kommt am Ende der Clou, wenn du testen willst ob alle bits true ist ;)
Wenn das nämlich der Fall ist hat der int den Wert von 2^33 - 1 ;)
Du meinst 2^31-1, oder? ;) ... aber wenn alle true sind, dürfte es eher -1 sein (Vorzeichenbit).

Jetzt sag aber nichts von unsigned, sonst weine ich! :D

[noid]

AlSvartr[/POST]']Du meinst 2^31-1, oder? ;) ... aber wenn alle true sind, dürfte es eher -1 sein (Vorzeichenbit).

Jetzt sag aber nichts von unsigned, sonst weine ich! :D

"Unsigned"

@Threadersteller: nen schnelleren Check wirds wohl nicht geben als eine Art boolsches Register zu haben.

[Coda]

Was auch immer man macht, das wird O(n) bleiben.

[Senior Sanchez]

AlSvartr[/POST]']Du meinst 2^31-1, oder? ;) ... aber wenn alle true sind, dürfte es eher -1 sein (Vorzeichenbit).

Jetzt sag aber nichts von unsigned, sonst weine ich! :D

Natürlich meinte ich das, war ein Vertipper.

Ja, Coda, ansich haste da halt schon richtig zumindest gegen große n bleibts bei dieser Komplexitätsklasse und bei kleinen n lohnt sich der Aufwand nicht.

Insgesamt gesehen ist es aber deutlich performanter als die boolean-Lösung da der Speicher erstens wesentlich effizienter genutzt wird und zweitens entsprechende Bit-Operationen schneller unter Java ablaufen als son krams mit boolean.

[Coda]

Äh Bit-Ops sind ganz sicher nich schneller als nen Bool-Array. Da must ja rumshiften und Zeug.

[Trap]

Coda[/POST]']Äh Bit-Ops sind ganz sicher nich schneller als nen Bool-Array. Da must ja rumshiften und Zeug.
Es kommt auf das Nutzungsmuster an. Sauber implementierte bit-arrays können auch schneller sein, siehe nsieve vs. nsieve-bits hier: http://shootout.alioth.debian.org/debian/benchmark.php?test=all&lang=sbcl&lang2=sbcl
Beim Feststellen ob alle Werte wahr sind, sind bit-arrays auf jeden Fall schneller.

Unter Umständen kann es auch sinnvoll sein ein extra Flag (allTrue) einzuführen und mit zu aktualisieren. Oder einen Counter (numTrue).

[PatkIllA]

Coda[/POST]']Äh Bit-Ops sind ganz sicher nich schneller als nen Bool-Array. Da must ja rumshiften und Zeug.Wenn es nur um das Testen des wie im Threadtitel geht muss man da nichts shiften. Da reicht ein Vergleich pro Block. Dürfte noch mal um ein Vielfaches schneller sein, als die Breite der Register.
Wahrscheinlich macht es im Endeffekt aber eh nichts nennenswertes aus, wenn die Anwendung das nicht grade die Hälfte der Zeit macht.

[noid]

Coda[/POST]']Äh Bit-Ops sind ganz sicher nich schneller als nen Bool-Array. Da must ja rumshiften und Zeug.

muss man nix shiften... (^, & und | reichen vollkommen)

[Gast]

hey, hätte nicht gedacht das die frage so viel anklang findet :D

das array umsortieren fällt aus, da die position der elemente für mich wichtig ist (sprich ein element muß immer an der selben pos. stehen)

ich hab in java die klasse BitSet (http://java.sun.com/j2se/1.5.0/docs/api/java/util/BitSet.html) gefunden.
wenn ich da einfach vergleiche, ob cardinality() == length() ist, dann weiß ich das alle elemente true sind.

ich hoffe mal das ist schnell, denn der test wird recht oft ausgeführt werden müssen.

[Coda]

Oh mann Leute ich weiß dass es in dem Fall schneller ist bit-arrays zu nehmen, aber irgendwann muss man die Dinger ja auch füllen und darauf zugreifen, nicht? Ganz blöd bin ich auch nicht.

noid[/POST]']muss man nix shiften... (^, & und | reichen vollkommen)
Du must shiften wenn du auf bit n per Funktion zugreifen willst.

[noid]

Coda[/POST]']Oh mann Leute ich weiß dass es in dem Fall schneller ist bit-arrays zu nehmen, aber irgendwann muss man die Dinger ja auch füllen und darauf zugreifen, nicht? Ganz blöd bin ich auch nicht.


Du must shiften wenn du auf bit n per Funktion zugreifen willst.

warum du da nicht mit logischen funktionen zurecht kommst ist mir ein rätsel.

zum setzen brauch ich ein bitweise-oder und zum löschen braucht man nur ein bitweise-und. wenn man togglen will, dann ein xor. ein zugriffsfunktion braucht kein shift.
auch kein abfrage, da reicht ein maskieren mit einem bitmuster. shift zum auslesen braucht man auch nicht.

vllt schreibst du mal wozu man den shift braucht, mir ist das vollkommen schleierhaft.

[Coda]

noid[/POST]']warum du da nicht mit logischen funktionen zurecht kommst ist mir ein rätsel.
bool getBit(int n,unsigned int &bits) {
}Bitte mit logischen Funktionen ausfüllen (und zwar ohne Switch mit 32 Unterpunkten X-D)

[PatkIllA]

einmal nen Array mit den passenden Bitmuster-Konstanten bauen und dann jeweils das passende benutzen.
Dann braucht man nur vorher einmal nen Shift oder man verdrahtet es gleich hart.
Wobei ein Shift so ziemlich mit das schnellste sein dürfte, was ein Prozessor ausführen kann.

[Coda]

Mal wieder ein Anwärter auf die sinnloseste Diskussion des Monats. Jeder normale Mensch wird an der Stelle einen bitshift verwenden, abgesehen davon war das gar nicht mein Punkt.

Der Zugriff auf ein stinknormales bool-array ist schneller als auf ein bitset. Basta. (und bevor einer damit kommt: Ja es kann sein dass das eine noch in den Cache passt und das andere nicht - dann könnte das Gegenteil der Fall sein. Und nein ich glaube nicht dass das hier gegeben ist. *seufz*)

[Gast]

Genau@Coda.
Und die echten Fehler findet hier schon gar keiner mehr. Es ist weder 2^33-1 noch 2^31-1, sondern 2^32-1. Und auch das ist noch idiotisch, weil nicht praxistauglich. Im Code sollte man -1u oder ~0u schreiben.

Wer dafür ein int deklarieren wollte möge sich nun bitte vorstellen dass ich ihm ein Roggenbrötchen an die Stirn werfe.

-zecki

[Xmas]

Coda[/POST]']Der Zugriff auf ein stinknormales bool-array ist schneller als auf ein bitset. Basta. (und bevor einer damit kommt: Ja es kann sein dass das eine noch in den Cache passt und das andere nicht - dann könnte das Gegenteil der Fall sein. Und nein ich glaube nicht dass das hier gegeben ist. *seufz*)
Du könntest wirklich ein wenig an deinem Ton arbeiten.

Ja, einzelne Zugriffe auf ein bool-array sind schneller. Bei mehreren Zugriffen in Folge kann sich das allerdings schnell umkehren, selbst wenn das bool-Array vollständig im L1-Cache liegt.

[AlSvartr]

Gast[/POST]']Und die echten Fehler findet hier schon gar keiner mehr. Es ist weder 2^33-1 noch 2^31-1, sondern 2^32-1.
Da es hier um Java geht, ist 2^32-1 mal überhaupt nicht richtig, weil java kein unsigned kennt...also gehts von -(2^31) bis 2^31-1 ;)

[Coda]

Xmas[/POST]']Du könntest wirklich ein wenig an deinem Ton arbeiten.
Der is mir hier ziemlich vergangen (ich meine nicht dieses Unterforum).

Xmas[/POST]']Ja, einzelne Zugriffe auf ein bool-array sind schneller. Bei mehreren Zugriffen in Folge kann sich das allerdings schnell umkehren, selbst wenn das bool-Array vollständig im L1-Cache liegt.
Gibts dafür auch eine Begründung? L1-Cache hat eine Latenz von 2 Takten, wie soll da ein (Modulo 32) + Load + Shift + Logische Op + Store schneller sein?

[Xmas]

Coda[/POST]']Gibts dafür auch eine Begründung? L1-Cache hat eine Latenz von 2 Takten, wie soll da ein (Modulo 32) + Load + Shift + Logische Op + Store schneller sein?
Es gibt nicht nur Schreibzugriffe, dazu noch einzeln, und es gibt nicht nur den Pentium 4.
In Schleifen kann man mit Bitarrays üblicherweise sehr schnell arbeiten, und ein Load plus 32 BT ist oft schneller als 32 Loads.

Ohne die üblichen Zugriffsmuster (und die Zielplattform) zu kennen kann man einfach nicht sagen was schneller ist.

[Senior Sanchez]

AlSvartr[/POST]']Da es hier um Java geht, ist 2^32-1 mal überhaupt nicht richtig, weil java kein unsigned kennt...also gehts von -(2^31) bis 2^31-1 ;)

Genau das ist der Punkt, zecki ;)

@all
Ich habe mal nen Primzahltestprogramm geschrieben, dass für das Sieb eben int-arrays nutzt wo einzelne bits umgeklappt werden könnten usw.
Vorher wurden natürlich schnell entsprechende masken erzeugt und es war definitiv schneller, lass es faktor 2-3 gewesen sein.
Sicher ist das für die Praxis meist völlig irrelevant, aber es war einfach ein test.

[Shink]

Wie schnell wär das dann eigentlich, wenn ich eine AMD64-Version von Java und den Datentyp long hernehme? Sind Bit-Shifts dann genauso schnell?

[SimonX]

Gast[/POST]']ja das topic ist eigentlich schon aussagekräftig genug X-D

mich interessiert eine möglichst effiziente methode

würde jetzt einfach alle elemente durchgehen und beim ersten false eben false zurückgegeben, sonst true.

Zu dem boolean array einfach auch eine Counter verwalten. Er wird um Eins erhöht, wenn du ein boolean wert von false auf true setzt und um Eins veringert, wenn du von true auf false setzt. Beim array reset wird er auf 0 gesetzt.

Dann: Counter == size -> alles true.

[SimonX]

Und wenn es dir nur um die Aussage geht: "Alles True" oder "Nicht alles True" ohne genauere Details wissen zu müssen, dann reichen zweit Counter aus: Ein Counter zählt alle Vergleiche, der Zweite die Vergleiche die True waren. Da braucht man dann überhaupt kein boolean array mehr.