Witam,
szukam najszybszego sposobu na przeszukiwaniu longa. Już tłumaczę o co mi chodzi
załóżmy, że mam liczbę: 0b000000000010000100000010000001000000000100010000000001000000000L
Potrzebuję znaleźć pozycje wszystkich jedynek występujących w liczbie. Czy jest do tego jakaś biblioteka lub szybszy sposób niż pętla i sprawdzanie pojedynczo każdego bitu?
Pozdrawiam
- Rejestracja:około 9 lat
- Ostatnio:prawie 5 lat
- Postów:44
0
Java - Rejestracja:ponad 6 lat
- Ostatnio:18 dni
- Postów:3561
1
Przesuwanie maski bitowej 0x8000...000, bitowe mnożenie i pętla może być dość szybkie na JVM, Po iluś przekręceniach się pętli zostanie mocno zoptymalizowane - ale POD WARUNKIEM że w pętli nie powołujesz obiektów.
Pokaż co wymyśliłeś do tej pory, również sposób skorzystania z wyniku
edytowany 1x, ostatnio: AnyKtokolwiek
yarel
Dokładnie, sposób w jaki chce korzystać z wyniku może zabić tę optymalizację na wyszukiwanie 1.
- Rejestracja:około 8 lat
- Ostatnio:około 5 godzin
- Postów:4902
1
Wedle mojej wiedzy nie ma jakiegoś szybszego sposobu niz sprawdzenie wszystkich bitów. A po co Ci to? Przecież złożoność nie jest duża (64 bity). Przykładowy kod (na wyjściu jest lista, listę Możesz sobie przekonwertować do czego tam Chcesz):
import java.util.ArrayList;
import java.util.List;
public class SearchLong {
private static List<Long> positions_of_one(long number) {
List<Long> ones = new ArrayList<>();
int position = 1;
while (number != 0) {
if ((number & 1L) != 0) {
ones.add(position);
}
position++;
number = number >>> 1;
}
return ones;
}
public static void main(String [] args)
{
System.out.println(positions_of_one(7L)); // [1, 2, 3]
}
}
edytowany 1x, ostatnio: lion137
Rzeczywiście, po co tam dałem long? Edycja.
- Rejestracja:ponad 6 lat
- Ostatnio:około 4 godziny
- Postów:296
1
Najszybsze są metody najstarsze ;-) czyli lookup. Utwórz tablicę z liczbami jedynek dla kolejnych wartości np. bajtu lub słowa. Dzielisz longa na kolejne bajty, słowa, które dają Ci indeksy do komórek w lookup i w ośmiu albo czterech krokach masz liczbę jedynek.
- Rejestracja:ponad 8 lat
- Ostatnio:około 2 godziny
- Lokalizacja:U krasnoludów - pod górą
- Postów:4707
1
jarekczek napisał(a):
Optymalne wyszukiwanie pierwszej jedynki jest dostępne z poziomu C. Wspiera to procesor. W Javie się nie da. Ale może wcześniej należało coś zoptymalizować, zanim dostałeś te "longi".
To nieprawda. Jeśli chodzi Ci o **bsr **i bsf to masz je w javie dostępne przez:
https://docs.oracle.com/javase/8/docs/api/java/lang/Long.html#numberOfTrailingZeros-long-
https://docs.oracle.com/javase/8/docs/api/java/lang/Long.html#numberOfLeadingZeros-long-
A to ciekawostka, że Java tak bardzo zbliża się do instrukcji procesora. W sumie dobrze, można programować ala real-time. W zasadzie
AtomicInteger.incrementAndGet też jest z rodziny instrukcji procesora, czyli aż tak nie powinno to dziwić :)
Java jest strasznie niskopoziomowa. Normalnie assembler z nieco wygodniejszą składnią :-) Można czasem sobie pooglądać co tworzy -XX:+PrintAssembly, tylko trzeba podegrać symbole (mnemoniki) (odpowiednia biblioteka .so lub .dll). Widać, że całkiem ostro korzysta z SIMD, rejestrów i instrukcji (czasem nieoptymalnie, ale korzysta :-) ). Z drugiej strony to oczywiście strata czasu - można zrozumiec czemu coś wolno działa czasem, ale zwykle trudno coś z tym zrobić( czyli może nie całkiem assembler).