Modulo mit negativen Zahlen

[Rol]

Hi,
ich möchte einen Ringspeicher adressieren. Der Speicherbesteht aus einem Array das z.B. 512 Elemente lang ist und hat einen Zeiger der am Anfang auf dem Element 0, also array[0], steht. Wird ein Element eingeschrieben wird danach der Zeiger inkremetiert, ist der Zeiger >= 512 wird er wieder auf 0 gesetzt. Soweit, so gut!
Ein Problem trit jetzt auf wenn z.B. der Zeiger auf 100 steht und ich das 101. Element _VOR_ dem Zeiger adressieren möchte. Um die Position im Array zu berechnen wollte ich es so machen:

array[zeiger+gewünschtesElemet % Arraylänge]
=
array[100 - (-101) % 512]
=
array[-1 % 512]. Das sollte eigentlich 511 ergeben, ergibt in Java(!) aber -1!

Nun könnte ich das zu Fuß mit If(...) und so machen aber die Operation wird in meiner Anwendung sehr oft (>>100.000.000) verwendet und soll deshalb sehr performant sein.

Gibt es in Java eigentlich gar keinen "richtigen" Modulo Operator?

Gruß
Rol

 

[Firephoenix]

Hi,
hilft dir der Thread hier weiter?
http://www.java-forum.org/allgemeine-java-themen/68740-problem-modulo.html
Gruß

 

[Rol]

Hi,
hilft dir der Thread hier weiter?
http://www.java-forum.org/allgemeine-java-themen/68740-problem-modulo.html
Gruß

Das hatte ich schon gefunden aber aus o.g. Performancegründen gefällte es mir nicht so richtig.

 

[Ark]

Wenn dir Performance wirklich extremst wichtig ist, dann sieh zu, dass du nur mit Zweierpotenzen zu tun kriegst, denn so ein % dauert relativ lange (bei Zweierpotenzen kommt man mit & aus). Ansonsten: addiere einfach dann, wenn du in den negativen Bereich kommst, die Arraylänge hinzu:

Also so:

int i = (zeiger + gewünschtesElement) % Arraylänge;
if(i < 0) i += Arraylänge;
array[i] usw.

Wenn dir das dann immer noch zu langsam ist (weil du dich vllt. nicht auf Zweierpotenzen beschränken kannst), musst du versuchen, den Modulo-Operator komplett zu entfernen. Das geht aber nur mit eventuellen Einschränkungen und muss dann auch nicht immer performanter sein; ein Abwägen zur Laufzeit macht den Code aber vor allem unübersichtlich. Versuche also zunächst, an anderen Stellen schneller zu werden, wenn möglich. Um herauszufinden, wo sich das lohnt, gibt's Profiler.

Ark

 

[0x7F800000]

naja, bei 512 ist's doch perfekt!

Hab's mal die 3 methoden schnell getestet:

public class ModProblems {

	// most general version
	static int mod(int a, int b){
		int res = a % b;
		return res < 0 ? res + b : res;
	}
	
	// if absolute value of a is limited by limit with limit = 0 mod b, this should work faster
	static int modLimited(int a, int b, int limit){
		return (a + limit) % b; 
	}
	
	// if b is a power of 2
	static int modPow2(int a, int bMinusOne){
		return a & bMinusOne;
	}
	
	public static void main(String... _){
		
		int b = 512;
		int bMinusOne = b - 1;
		int limit = 512*16;
		
		// visual test: all three results should be equal and between 0 and 512
		for (int i = 0; i < 20; i ++){
			int a = (int)(java.lang.Math.random()*1000 - 500);
			System.out.println(mod(a, b) + "\t" + modLimited(a, b, limit) + "\t" + modPow2(a, bMinusOne));
		}
		
		System.out.println("\n");
		
		// shitty benchmark
		int N = 500000000;
		{
			long tStart = System.currentTimeMillis();
			for (int i = 0; i < N; i++){
				mod(i-100, b);
			}
			System.out.println("mod:\t" + (System.currentTimeMillis() - tStart));
		}
		{
			long tStart = System.currentTimeMillis();
			for (int i = 0; i < N; i++){
				modLimited(i-100, b, limit);
			}
			System.out.println("lim:\t" + (System.currentTimeMillis() - tStart));
		}
		{
			long tStart = System.currentTimeMillis();
			for (int i = 0; i < N; i++){
				modPow2(i-100, bMinusOne);
			}
			System.out.println("pow:\t" + (System.currentTimeMillis() - tStart));
		}
	}
}

Ergebnis:

mod:	4806
lim:	3724
pow:	436

Also ist die allgemeine Version nur unwesentlich lahmer, als die Version, wo die Indizes betragsmäßig beschränkt sind, aber das mit bitwise-AND ist zehn mal schneller.

 

[faetzminator]

Oder einfach vor dem Modulo ganz ohne Kontrolle noch schnell den Wert hinzufügen - in Ark's Beispiel also [c]int i = (zeiger + gewünschtesElement + Arraylänge) % Arraylänge;[/c]

 

[0x7F800000]

Oder einfach vor dem Modulo ganz ohne Kontrolle noch schnell den Wert hinzufügen - in Ark's Beispiel also [c]int i = (zeiger + gewünschtesElement + Arraylänge) % Arraylänge;[/c]

genau das tut modLimited, falls man sich darauf verlassen kann, dass Betrag von [c]zeiger + gewElem[/c] stets kleiner gleich [c]ArrayLänge[/c] ist. Wenn das so ist, dann sollte man es so machen, wenn die ArrayLänge keine Zweierpotenz ist.

 

[Ark]

falls man sich darauf verlassen kann, dass Betrag von [c]zeiger + gewElem[/c] stets kleiner gleich [c]ArrayLänge[/c] ist.

Dies ist aber nur dann von Interesse, wenn der Ausdruck negativ ist, und dann kann man auch gleich zu einer simplen if-Abfrage greifen und % komplett entfernen.

Gerade wegen solcher Schwierigkeiten sollte man die Repräsentanten erst nach der Modulo-Rechnung auswählen.

Ark

 

[0x7F800000]

Dies ist aber nur dann von Interesse, wenn der Ausdruck negativ ist, und dann kann man auch gleich zu einer simplen if-Abfrage greifen und % komplett entfernen.

Das stimmt. Aber im Unterschied zu einer einfachen if-Abfrage funktioniert es auch noch, wenn der Betrag kleiner gleich 2*ArrayLänge oder 10000*ArrayLänge ist. Da kommt man ohne % nicht weiter. Wie die obere Schranke aussieht, muss aber der Threadersteller selbst wissen.