Liste mit Map abgleichen extrem langsam

[newnoise]

Hallo,

ich habe eine Map<String, Foo> aus der ich einige nicht genutzte Einträge löschen möchte. Dazu habe ich eine Liste<String> in der der alle Werte stehen, die in der Map stehen bleiben sollen:

		for (Foo foo : foos.values()) { // foos ist die Map aus der gelöscht werden soll
                        //otherFoos ist die Liste deren Einträge in der Map bleiben sollen
			if (!otherFoos.contains(foo.getId().toString())) {
				foos.remove(foo);
			}
		}

Funktioniert auch tendenziell, dauert aber bei einer Größe von über 100TSD Einträgen in jeweils Liste und Map Ewigkeiten! Das wird wohl am contains liegen, nehme ich an?

Gibt es da eine effizientere Lösung?

Danke
noise

 

[faetzminator]

Du schreibst deine [c]List[/c] vorgängig in ein [c]Set[/c], dann hast du eine Laufzeit [c]O(m + n)[/c] an Stelle von [c]O(m * n)[/c] (Davon ausgegangen, dass hinzufügen und getten jeweils [c]O(1)[/c] ist).

 

[XHelp]

Öhm, warum leerst du nicht die Map und schreibst einfach deine Liste darein? Im Endeffekt passiert doch das gleiche, oder habe ich was falsch verstanden? Dann wäre das (imho)

O(n)

[EDIT]Ne, schon gut, habe nicht bedacht dass in der Liste nur die ID ist[/EDIT]

 

[SlaterB]

meine Güte, da hast du eine Map, die das contains() extrem schnell macht, und dann nutzt du sie nicht,
das ganze schreit ja nach einem netten kleinen Testprogramm:

public class Test
{

    public static void main(String[] args)
    {
        List<Integer> fooList = new ArrayList<Integer>();
        Map<Integer, Integer> fooMap = new HashMap<Integer, Integer>();

        int k = 30000;
        int kk = k * 10;
        Random r = new Random();
        for (int i = 0; i < k; i++)
        {
            fooList.add(r.nextInt(kk));

            int x = r.nextInt(kk);
            fooMap.put(x, x);
        }

        int count = 0;
        long time = 0;

        time = System.currentTimeMillis();
        count = 0;
        for (Integer foo : fooMap.values())
        {
            if (fooList.contains(foo))
            {
                count++;
            }
        }
        System.out.println("found: " + count + ", time: " + (System.currentTimeMillis() - time));


        time = System.currentTimeMillis();
        count = 0;
        for (Integer foo : fooList)
        {
            if (fooMap.containsKey(foo))
            {
                count++;
            }
        }
        System.out.println("found: " + count + ", time: " + (System.currentTimeMillis() - time));
    }
}

Map-Elemente in Liste suchen: 14 sec
Listen-Elemente in Map suchen: 15 ms, das ist quasi unter der Messtoleranz, kann vielleicht noch darunter liegen,

inwiefern du die Daten dann weiter verarbeitest ist eine andere Frage,
aber selbst wenn du noch ein paar Listen erstellen und die 100.000 Elemente hin und herkopieren muss,
ist nicht weiter schlimm sofern nur wenige einzelne Male,
was du verhindern musst ist 100.000x in einer langen Liste zu suchen!

 

[newnoise]

Öhm, warum leerst du nicht die Map und schreibst einfach deine Liste darein? Im Endeffekt passiert doch das gleiche, oder habe ich was falsch verstanden? Dann wäre das (imho)

O(n)

ja danke ... da hab ich mal wieder zu kompliziert gedacht 🙂

aber noch eine Frage: ich habe eine Klasse Id. Diese beinhaltet immoment nur einen String ... Diese Klasse benutze ich als Keys für die Map. Wenn ich nun ein map.get(id) mache, bekomme ich immer null zurück. Ich weiß aber, dass die Strings enthalten sind, es wird also irgendwie an der Suche liegen, die sucht wohl nach gleichen Objekten und nicht inhalten.
via compareTo() in der Id Klasse hab ich das auch nicht hinbekommen.

kann ich es irgendwie so hinkriegen, dass er die Id als Schlüssel in der Map findet, auch wenn es 2 unterschiedlich angelegte objekte sind, die aber den gleichen inhalt haben?

danke!

 

[SlaterB]

kommt auf die Map an, für eine HashMap wäre z.B. die hashcode()-Methoden heftig entscheidend,
die könnte den hashcode() des Strings direkt weiterreichen,
equals() dann natürlich auch nicht vergessen

 

[Lexi]

Collection<?> AbstractMap.values()
Collection.retainAll(Collection<?>)

Sollte auch gehen, oder ?