Array viel zu groß...andere Lösungen?

FabianLurz

Bekanntes Mitglied
Hallo Leute,
vllcht. hat der ein oder andere meinen Post schon gelesen; ich bin dabei, eine Recommendation Engine zu entwickeln. Dabei werden große Datenmengen verwendet; es müssen die Korrelationen von 817k zu 817k Filmen berechnet werden.
Um die MovieFeature Matrix zu erstellen verwende ich folgende Funktion:
Java:
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package main.java.math;

import java.util.ArrayList;
import main.java.ressources.PropertyReader;

/**
 *
 * @author Fabian
 */
public class ItemMatrixCreator {

    //Variables
    //All entinitys
    private ArrayList<String> values = new ArrayList<>();
    private int counter = 0;
    //Values for the single item
    private ArrayList<String> itemValue = new ArrayList<>();
    private int itemCounter = 0;
    PropertyReader mainconf = new PropertyReader();   
    
    /**
     * Assigns on the one hand all itemValues. On the other hand, it builds a
     * vector excluding all known values, so that no value exists twice.
     *
     * @param value String: get all values for creating the right matrix
     */
    public void assign(String value) {
        mainconf.getProb("conf/MainConfig.properties");
        itemValue.add(itemCounter, value);
        itemCounter++;
        boolean known = false;
        String[] valueSplit = value.split(mainconf.read("split"));
        for (int x = 0; x <= valueSplit.length-1; x++) {
            for (int i = 0; i <= values.size()-1; i++) {
                if (values.get(i) == null ? valueSplit[x] == null : values.get(i).equals(valueSplit[x])) {
                    known = true;
                    break;
                } else {
                    known = false;
                }

            }
            if (known == false) {
                if (!"".equals(valueSplit[x])) {
                    values.add(counter, valueSplit[x]);
                    counter++;
                }
            }
        }
    }

    /**
     * Creates a two-dimensional matrix for the item entinitys. For example a
     * genrearray for films like this: 101001 100000 011111 .......
     *
     * @param value Sets the importance of the item entinity. The entinity can
     * be a genre.
     * @return an two-dimensional String
     */
    public byte[][] fillMatrix(byte value) {
        System.out.print(itemValue.size()+" "+ values.size()+"\n");
        byte[][] array = new byte[itemValue.size()][values.size()];
        for (int i = 0; i <= itemValue.size()-1; i++) {
            String[] itemVal = itemValue.get(i).split(mainconf.read("split"));
            for (int x = 0; x <= values.size()-1; x++) {
                for (int y = 0; y <= (itemVal.length - 1); y++) {
                    if (itemVal[y] == null ? values.get(x) == null : itemVal[y].equals(values.get(x))) {
                        array[i][x] = value;
                        break;
                    } else {
                        array[i][x] = 0;
                    }

                }

            }
        }        
        return array;
    }

    /**
     * Returns all the entinity-values from all items excluding known once.
     *
     * @return ArrayList<String>
     */
    public ArrayList<String> returnMatrix() {
        return values;
    }

    /**
     * Deletes the created matrix so that a new matrix with new values and
     * entinitys can be created.
     */
    public void deleteMatrix() {
        counter = 0;
        itemCounter = 0;
        values.clear();
        itemValue.clear();
    }
}

Die Funktion assign wird wie folgt benutzt:
Java:
private byte[][] createArray(String query, ArrayList<Integer> id, Statement que, String getString, byte fillmatrix, boolean integer) throws SQLException {
        for (int j = 0; j < id.size(); j++) {
            String q = query + "" + id.get(j);
            ResultSet arr = que.executeQuery(q);
            String res = "";
            while (arr.next()) {
                if (integer == false) {
                    res += arr.getString(getString) + mainconf.read("split");
                } else if (integer == true) {
                    res += arr.getInt(getString) + mainconf.read("split");
                }
            }
            matrix.assign(res);
            System.out.print(res + "\n");
        }
        System.out.print("Array created\n");
        byte[][] array = matrix.fillMatrix(fillmatrix);
        matrix.deleteMatrix();
        return array;

    }

Die Funktion private byte[][] create Array() wird wie folgt aufgerufen:
Java:
 byte[][] genreArray = createArray(genreQ, id, query, "info", (byte) prop.readInt("genre"), false);
Soweit dazu. Es ergeben sich nun rießige Arrays...
Mein PC mit 8GB Arbeitsspeicher ist dafür nicht ausreichend.....
Seht ihr eine andere Möglichkeit, nicht so viel Speicher zu verbrauchen beim erstellen der Matrix? Ist irgendwo ein grober Fehler?
EDIT: Sehe gerade, dass die Kommentare noch nicht optimal sind 🙂 Bitte habt Nachsehen; die werden noch verbessert.
Gruß Fabian
 
Informationen sparst du dir weitgehend

wo und wie wird die Matrix genutzt? auf welche Weise welche Information daraus gewonnen?

und welche Informationen enthält sie konkret, vor allem wie viele Daten,
sind praktisch alle bei 0 und nur 100.000 Daten verstreut enthalten?
das wäre dann der Fachbegriff
Dünnbesetzte Matrix ? Wikipedia

denkbar wäre als alternative Datenstruktur eine Map, x+","+y als String zu einem Key zusammenbauen,
das kann auch der Auswerter später, die Map enthält genau die 100.000 Daten, liefert sonst null
 
Also wie läuft das Ganze ab:
1. Daten werden von der Mysql DB eingelesen:
Java:
 //Create the genreArray matrix
            String genreQ = "SELECT movie_id,info,info_type_id FROM movie_info WHERE info_type_id=3 AND movie_id=";
            byte[][] genreArray = createArray(genreQ, id, query, "info", (byte) prop.readInt("genre"), false);
            float[][] dist = new float[4][(genreArray.length-1)*(genreArray.length-1)];
            dist[0] = cosine.createCosineSimilarity(genreArray);
            Arrays.fill(genreArray,null);
Die Funktion createArray() steht ja im ersten Post.
2. Die Funktion createArray() fügt durch assign unbekannte Werte der ArrayList<String> values hinzu. Alle werte von den Filmen werden in der ArrayList<String> itemValue gespeichert.
3. Die Funktion fillMatrix wird aufgerufen. Es wird nun verglichen, welche Filme ein Wert enthält und an welcher Stelle von value eine 1 gesetzt werden muss.

Das Problem liegt aber aktuell hier:
Java:
float[][] dist = new float[4][(genreArray.length-1)*(genreArray.length-1)];
Bei 25k Filmen brauche ich schon ca. 10GB Arbeitsspeicher (etwas weniger). Leider ist aber die Kosinusähnlichkeit ein float....wüsste nicht, wie das anders gehen soll. Hoffe ihr habt noch eine Idee 🙂
 
für die dist-Berechnung musst du vielleicht weniger suchen, nur durchgehen,
da ginge dann auch bzw. wäre eher nützlich eine Liste von Einträgen (x,y,wert), aber schwer zu sagen ohne Details
 
Versuch das ganze doch gleich auf Datenbankebene umzusetzen. Diese sollte locker mit einer (185k)^2 großen Tabelle umgehen können, wenn du über genug Festplattenspeicher verfügst. Könnte dann sicherlich langsam werden. Aber immer noch besser, als alles im Arbeitsspeicher halten zu wollen 😉
 
Nein nein ich will das ja gar nicht im Arbeitsspeicher halten. Es wird eben alles berechnet und dann werden diese Korrelationen wieder in die DB geschrieben 🙂 Leider muss aber für die Berechnung ziemlich viel im Arbeitsspeicher gehalten werden; eine Zeit lang zumindest.
Bsp.:
item_id1 item_id2 corr
1 2 0.5
2 1 0.5
3 4 0.6
4 3 0.7
Gruß Fabian
 
Weniger Code und mehr Erklärungen (oder alternativ: Mehr Code, nämlich ein KSKB) wären vielleicht hilfreich. Jedenfalls hab ich's nicht im Detail nachvollzogen. Aber reicht es vielleicht, immer nur eine Zeile+Spalte im Speichern zu halten?
 
Ja, je nachdem, wie das ganze verwendet werden soll, gäbe es schon Möglichkeiten. Man soll ja vermutlich einen Film auswählen, und dann z.B. alle "ähnlichen" Filme angezeigt bekommen. Dazu braucht man nur 817k float-Werte, nämlich die Ähnlichkeit des EINEN Films zu ALLEN anderen. Wann braucht man alle paarweisen Ähnlichkeiten? Wo und wie sollen die gespeichert werden? (Ja wohl nicht bei jedem Start neu ausrechnen? 😉 ). Wie zeitkritisch sind die einzelnen Schritte, und welche Laufzeitanforderungen gibt es? Es gibt ja grob-abstrakt gesprochen drei mögliche Abstufungen:
float[][] getPairwiseSimilarities(); // 800k * 800k -> Unpraktikabel
float[] getSimilarities(int currentFilm); // 800k -> Vielleicht OK
float getSimilarity(int film0, int film1); // 1 float, aber vermutlich zu langsam in der Praxis?
 
Alle Korrelationen werden in der DB gespeichert. Von dort aus werden sie von einer weiteren API abgerufen...also keine Neuberechnung.
Spannend ist der Ansatz, erst alles für einen Film, dann für den nächsten Film zu berechnen. Das sollte möglich sein.
Eine Echtzeitberechnung kann nicht statt finden. Das wäre zu langsam 😉
 
Das Überschneidet sich jetzt schon mit http://www.java-forum.org/allgemeine-java-themen/143046-recommendation-engine.html#post952906 ... aber ... ohne genauer zu wissen, welche Rahmenbedinungen vorliegen, wird es schwierig, dazu etwas zu sagen. Vermutlich sind die allermeisten Korellationen 0 oder sehr klein, oder sie fallen in wenige Kategorien. Zumindest denke ich schonmal, dass man die Float-Werte (-1 bis 1) auch einfach auf byte-Werte (-128 bis 127) abbilden könnte. Evtl. zusätzlich dazu könnte man eine Art "Threshold" einfügen: Wenn die Korrelation zwischen -0.1 und 0.1 liegt (also ca. -12 bis 12 als byte), wird sie als 0 angenommen. Dann hättest du vermutlich eine Sparse Matrix, wie SlaterB schon angedeutet hat. Die kann man dann kompakter Speichern. Vielleicht könnte man auch ganz absurde Sachen mit einer Run length encoding machen, oder die Matrix irgendwie umsortieren, damit sie kompakter gespeichert werden kann, aber nochmal: Das ist alles Stochern im Nebel....
 
Natürlich ist es stochern im Nebel. Ich kann ja auch zu einem derart komplexen Thema nicht alles erklären 🙂 Das "stochern im Nebel" hat mir hier aber schon sehr weiter geholfen. Siehe dazu auch den anderen Post 😉
Also ich komme jedenfalls jetzt wieder weiter 🙂
Gruß und Danke Fabian
 

Neue Themen


Zurück
Oben