int[] eindeutig durch eine Zahl repräsentieren

[Nico(Gast)]

Hallo,

ich muss in meinem Programm int[] der selben Länge und von gleichem Inhalt vergleichen. Dabei kommt es auf die Reihenfolge der Zahlen an. Meine Arrays sind dabei bis zu mehreren tausend Zahlen groß, und müssen ziemlich oft verglichen werden. Daher schließt sich auf Grund der Laufzeit ein "eins zu eins" Vergleich aus.
Meine Frage ist nun, lässt sich eine eindeutige (oder zumindest hinreichend eindeutig) Zahl berechnen, sodass ich auf Grund der Zahl ausschließen kann, dass zwei Arrays genau die selbe Form haben? Es kann dabei durchaus vorkommen, dass die Arrays bis auf wenige Stellen genau gleich sind.

Anwendung:
Ich habe eine Liste von Arrays, die schon einmal betrachtet wurden. Nun wird ein neuer Array erstellt. Dieser soll mit allen Arrays der immer größer werdenden Liste verglichen werden und nur wenn die Zahlen in der vorliegenden Reihenfolge so noch nie betrachtet wurden, soll der Array weiter verarbeitet werden.

Bisher verwende ich die folgende Formel um einen Vergleichswert zu erhalten:

double value =0;
for (int i = 0; i < array.length; i++) {
	value += Math.sqrt(((i+1)*array[i]))/Math.sqrt(array.length);
}

wobei ich nicht sicher bin ob die so berechnete Zahl durch die Rundung zumindest annähernd eindeutig ist. Die Wurzel und der Bruch sind notwendig um die Zahl nicht zu groß werden zu lassen.

Ich hoffe jemand hat eine Idee, wie man das besser machen kann.

Gruß Nico

 

[Gast]

wie wird denn das neue array erstellt? wenn da werte nacheinander reinkommen, könnte man ja bei jedem insert, prüfen, ob an der gleichen Stelle in anderem array auch diese zahl steht.

 

[SlaterB]

zunächst mal ist eine eindeutige Abbildung nicht möglich,
selbst wenn pro Array-Feld nur Zahlen von 0-9 zugelassen sind,
sind 1000-Felder lange Arrays entsprechend 1000stellige Zahlen,
während ein int gerade mal 10stellig ist oder so,

bei gleichverteilten Werten haben also mindestens 100 Arrays den gleichen int-Wert, den gleichen Hash,

das ist aber nicht so schlimm, das sollte bei einer guten Hash-Funktion eh nur passieren, wenn du bereits Millionen und Millarden dieser großen Arrays hast,
abgesehen davon dass so viele gar nicht in den Speicher passen, wäre es dann ja schon recht tröstlich, dass man nur noch 100 Arrays intensiver vergleichen muss statt alle

-----

die Hashfunktion sollte möglichst einfach sein, verwende Bitoperationen wie <<,
adde jeden array-Wert und shifte dann den value (falls er int oder long ist) << 1 (entspricht * 2) oder ähnlich,

die Hashfunktion von String ist so ähnlich, denn ein String ist ja auch nur ein langes Array von chars, praktisch ein langes Array von ints

    /**
     * Returns a hash code for this string. The hash code for a
     * <code>String</code> object is computed as
     * <blockquote><pre>
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     * </pre></blockquote>
     * using <code>int</code> arithmetic, where <code>s[i]</code> is the
     * [i]i[/i]th character of the string, <code>n</code> is the length of
     * the string, and <code>^</code> indicates exponentiation.
     * (The hash value of the empty string is zero.)
     *
     * @return  a hash code value for this object.
     */
    public int hashCode() {
	int h = hash;
	if (h == 0) {
	    int off = offset;
	    char val[] = value;
	    int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }

allgemein kannst du dich ja über 'Hashfunktionen' schlau machen

-------

die Wurzel ist in jedem Fall eher schlecht, dauert zu lange,
wenn überhaupt, dann musst du ja zumindest nicht den immer gleichen Wert Math.sqrt(array.length);
in jedem Schleifendurchlauf neu berechnen

 

[Verjigorm]

edit: Slater war mal wieder schneller

 

[Nico(Gast)]

@Gast
Das wüde ja wieder bedeuten dass ich in allen Arrays alle Stellen anschauen muss...

@SlaterB
ich habe vergessen zu erwähnen, dass jede Zahl im Array 100% nur einmal vorkommt und im Array dann Zahlen im 4- bis 5-stelligen Bereich stehen können.

Habe ich bei deinem Vorschlag dann nicht das Problem, dass die Vergleichszahl viel zu groß werden würde?

 

[FArt]

Lange Rede kurzer Sinn: ein Hash (wie von SlaterB vorgeschlagen) ist die Lösung. Nur bei gleichen Hashwerten muss voll verglichen werden, das ist aber nicht tragisch, weil das sehr selten vorkommen wird (bei der Wahl eines geeignetetn Hashalgorithmus, der z.B. auch Zahlendreher berücksichtigt).

Google hilft weiter.

 

[Landei]

Brauchste nicht selber schreiben, nimm Arrays.hashCode

 

[SlaterB]

> Habe ich bei deinem Vorschlag dann nicht das Problem, dass die Vergleichszahl viel zu groß werden würde?

die Rechnung erfolgt (automatisch) quasi Modulo MAX_VALUE

wenn der MaxWert von int 1000 wäre und du 901*411 = 370.311 rechnest, dann kommt am Ende 311 raus,
ganz so ist es nicht, es werden eher die führenden Bits abgeschnitten so dass auch negative Werte herauskommen können, aber das nur als grobe Vorstellung

 

[Nico(Gast)]

Noch eine Frage zum Abschluss:
Bei zunehmender Dauer werden sich die Arrays immer ähnlicher, nimmt dann die Wahrscheinlichkeit einen gleichen Hashwert zu bekommen ebenfalls zu, oder ist das unabhängig davon wieviele Stellen verschieden sind?

Ansonsten danke für die schnellen und hilfreichen Antworten. Werde mich dann mal nach einer geeigneten Hashfunktion umschauen.

 

[FArt]

Google mal nach Hashfunktion, da steht die Antwort.

 

[SlaterB]

das kommt ganz auf die jeweilige Implementierung der Hashfunktion an,
die genau aufgrund solcher Fragen teilweise individuell angelegt wird,

grundsätzlich kann man aber davon ausgehen, dass ein Standard wie das von Landei vorgeschlagene Arrays.hashCode() (so ähnlichh wie von String oben gepostet)
ausreichend ist und gerade dafür sorgt, dass geringe Ähnlichkeinen sofort zu großen Hashcode-Unterschieden führen,

normalerweise sind die Hashes von Elementen gleich, von denen man es am allerwenigsten erwartet,
ein gewisser Zufall/ Streuung läßt sich bei ganz einfachen und damit schnellen Hashfunktionen aber auch nicht ausschließen,

was rede ich eigentlich die ganze Zeit?
du sollst doch bei google alles nachschlagen
(edit: genau, FArt)

 

[Nico(Gast)]

Danke an alle

 

[tuxedo]

Also ich mache ähnliches bei meinem "dirty rectangle detection" für ein selbstgeschriebenes ScreenScraping.

Ich mache einen Screenshot und teile den in Blöcke ein. Der wird zuerst komplett übertragen.
Dann mach ich wieder einen Screenshot und teile den wieder in Blöcke ein. Aber um nicht nichtmal alles komplett zu übertragen, vergleiche ich die einzelnen Blöcke des ersten und zweiten Screenshots.

Da ist das Pixelweise vergleichen der Blöcke bei mir doppelt so schnell wie wenn ich von von beiden Blöcken den HashCode bilde und diesen dann vergleiche.

Allerdings bricht der Pixelvergleich schon dann ab, wenn ein erster Pixelunterschied zwischen den Blöcken gefunden wurde. Im Worst-Case ist das beim lettzten Pixel des Blocks, im BestCase beim ersten Pixel.

Vielleicht ist deshalb bei mir das Pixelweise vergleichen im Endeffekt schneller.

Man sollte also wirklich schauen mit was man besser fährt ...