Tworzę grę na Androida. W tej chwili piszę kod, który powinien obliczyć najlepszą trasę między dwoma obiektami, korzystając z algorytmu A*. Wewnątrz algorytmu używam podwajania do obliczenia wszystkiego.

Kiedy uruchamiam czasochłonne algorytmy na moim komputerze, różnica czasu między obliczeniami za pomocą liczb całkowitych i podwójnych jest prawie zerowa (może kilka nanosekund).

Pytanie pierwsze:

Czy to zachowanie jest również widoczne na telefonach z Androidem? Wiem, że mój komputer ma wiele jednostek ALU dla liczb całkowitych dla liczb zmiennoprzecinkowych itp. Ale co z telefonami? Telefony z Androidem mogą być bardzo różne, jeśli chodzi o sprzęt. Mam tylko dwa telefony testowe, ale dziś na rynku dostępne są setki telefonów, co oznacza, że ​​uruchomienie testów na dwóch moich telefonach nie dałoby mi wiarygodnych danych, przynajmniej tak mi się wydaje.

Pytanie drugie:

Dla mojej gry nie ma znaczenia, czy przejdę na liczby całkowite, obliczona trasa może mniej idealna, ale to mi nie przeszkadza. Czy warto więc przejść na liczby całkowite? A może przejście na liczby całkowite złamałoby algorytm? Czy ktoś ma z tym doświadczenie?

3
Rolf ツ 1 marzec 2012, 16:27

3 odpowiedzi

Najlepsza odpowiedź

Zgodnie z ogólną zasadą, arytmetyka na liczbach całkowitych jest szybsza niż arytmetyka zmiennoprzecinkowa, ponieważ jest prostsza w implementacji. (W przypadku liczby zmiennoprzecinkowej sprzęt musi radzić sobie zarówno z częściami mantysowymi, jak i wykładnikami, i (AFAIK) nie może tego robić równolegle.)

Jednak współczynnik wydajności będzie się różnić w zależności od implementacji sprzętowej i trudno jest przewidywać, które są lepsze niż zgadywanie. (Na początek zależy to od strategii marketingowych i kompromisów między wydajnością a żywotnością baterii).


Ale szczerze mówiąc, skupiłbym się bardziej na tym, która z liczb całkowitych i zmiennoprzecinkowych będzie działać najlepiej z algorytmami twojej gry. Jeśli wymagają jednego, a Ty używasz drugiego, czeka Cię wiele kłopotów (niepotrzebne kodowanie, testowanie, naprawianie błędów itp.).

A może myślicie, że przejście na liczby całkowite złamie algorytm?

Mogłoby to zrobić. Może to również znacznie je skomplikować. Wszystko zależy od charakteru algorytmów. Z pewnością czeka Cię dużo przekodowywania i ponownego testowania.

Osobiście rozważałbym zrobienie tego tylko wtedy, gdyby gra była po prostu zbyt wolna, nawet po próbie profilowania i dostrajania hotspotów wydajności. I zrobiłbym to tylko wtedy, gdybym był przygotowany na ryzyko, że wysiłek ponownego kodowania może nie przynieść żadnych korzyści… lub gorzej.

2
Stephen C 1 marzec 2012, 17:18

Arytmetyka liczb całkowitych ma kilka zalet:

  • Zwykle jest szybszy. Zależy to od sprzętu, ale większość sprzętu ma bardziej wydajne operacje na liczbach całkowitych. Również niektóre urządzenia nie mają możliwości FPU i faktycznie muszą emulować instrukcje zmiennoprzecinkowe, co jest znacznie wolniejsze.
  • Nie musisz się martwić o problemy z zaokrąglaniem. Niedokładność liczby zmiennoprzecinkowej może powodować drobne błędy i problemy.
  • To prostsze - nie musisz się martwić o specjalne przypadki, takie jak NaN i Infinity, a także łatwiej wyświetlać/formatować liczby.

Ogólnie rzecz biorąc, jeśli nie potrzebujesz ściśle liczb zmiennoprzecinkowych, powinieneś trzymać się liczb całkowitych w swoich algorytmach.

Aby odpowiedzieć na Twoje pytania:

  1. Nie masz gwarancji dotyczącej obsługi sprzętu w telefonach z systemem Android. W nowoczesnych telefonach obsługa FPU jest prawdopodobna, ale nie można na niej polegać. Więc używaj liczb całkowitych, jeśli możesz.
  2. A* pathfinding działa dobrze z liczbami całkowitymi, zakładając strukturę danych mapy podobną do siatki i dodatnie koszty ruchu liczb całkowitych. Więc powinieneś być w stanie przełączyć się na liczby całkowite, a prawdopodobnie będzie to szybsze. Zwróć uwagę, że może być konieczne odpowiednie zwiększenie kosztów ruchu, więc zamiast kosztu ruchu 1,0 za pole możesz na przykład ustawić 100. Ale poza tym algorytm powinien być taki sam.
1
Community 23 maj 2017, 15:23