HashMap nach kleinstem Value durchsuchen

[f4814n]

Hallo,

ich brauche mal wieder eure Hilfe.

Die Aufgabe lautet wie folgt:

Ich habe eine Hashmap<Character, Integer> in der Buchstaben gespeichert sind und die Anzhal wie oft sie in einem Wort vorkommen.

ich soll die HashMap durchlaufen und den seltensten bzw. zweitseltensten Buchstaben in einem char Array speichern.

mit :

public char[] getRareChars() {
	
		
		for(Map.Entry<Character, Integer> e : counter.entrySet()){ //counter -name der hm                          
			
			char c = e.getKey();
			int i = e.getValue();
			 
			// und jetzt?
	
		}
		
		return new char[]{0,0};
	}

ich bin etwas überfragt. Freu mich auf Feedback! DANKE

 

[hüteüberhüte]

Aus der Map eine Liste machen, diese dann sortieren, und die dotierte Liste dann ins Array übertragen

 

[f4814n]

was ist der Unterschied zur ArrayList?

Kann ich darin nicht nur Objekte speichern?

kann ich da die chars mit entsprechendem Integer reinspeichern und dann NUR nach dem Integer sortieren??

DANKE!!

 

[nillehammer]

Problem 1: Die Map garantiert die Reihenfolge (wenn überhaupt) nur für die Keys. Die Reihenfolge der Values ist daher garantiert nicht so, wie wir sie haben wollen. Wir müssen also irgendwie durch die Map durchiterieren und dabei einfach und intelligent umsortieren. Wir bräuchten was, das die Sortierung nach dem Value des Entriys macht. Lösung: wir basteln uns einen

Comparator

dafür.

Als Container für die neu sortierten Entries nehmen wir ein

TreeSet

, dem wir unseren

Comparator

übergeben. Damit werden die Entries in diesem Set nun nach ihrem Value sortiert. Das ist die schnellste Sortiervariante. Collections.sort für Listen ist langsamer. Obwohl sich das wohl erst bei sehr vielen Elementen bemerkbar machen dürfte. Und das ist ja bei dem begrenzten Wertebereich von char ausgeschlossen. Egal, so werden die Entries jedenfalls gleich beim add sortiert und wir sparen uns den Aufruf von Collections.sort.

Problem 2: Der return type ist ein Array von primitiven chars. D.h. die Methoden des Collections-Frameworks, die Arrays erzeugen, bringen uns nichts, weil diese nie primitive Elemente enthalten können. Wir müssen also selbst Unboxen undas Array befüllen.

Nachfolgender Code macht das alles. Kopieren, compilieren, ausführen:

public class MapEntriesToCharArray {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		final Map<Character, Integer> charsToUseCount = new HashMap<>(3);

		charsToUseCount.put('a', 2);
		charsToUseCount.put('e', 8);
		charsToUseCount.put('f', 4);

		final char[] sortedByUseCount = getRareChars(charsToUseCount);
		System.out.println(Arrays.toString(sortedByUseCount));
	}

	public static char[] getRareChars(final Map<Character, Integer> charMap) {

		final Set<Map.Entry<Character, Integer>> valueSortedEntries = new TreeSet<>(
				MapEntryComparator.ASCENDING_VALUES);
		valueSortedEntries.addAll(charMap.entrySet());

		final char[] result = new char[valueSortedEntries.size()];

		int currentResultIndex = 0;
		for (final Map.Entry<Character, Integer> entry : valueSortedEntries) {

			result[currentResultIndex] = entry.getKey();
			currentResultIndex++;
		}

		return result;
	}

	private static enum MapEntryComparator implements
			Comparator<Map.Entry<Character, Integer>> {
		/**
		 * Diese Implementierung sortiert Map.Entries nach dem Wert ihres values
		 * (hier ein Integer).
		 */
		ASCENDING_VALUES;

		@Override
		public final int compare(final Entry<Character, Integer> first,
				final Entry<Character, Integer> second) {
			return first.getValue().compareTo(second.getValue());
		}
	}

}

 

[DrZoidberg]

Das geht aber auch einfacher.

public char[] getRareChars() {
    char[] result = new char[2];
    int[] count = {Integer.MAX_VALUE, Integer.MAX_VALUE};
    for(Map.Entry<Character, Integer> e : counter.entrySet()){                       
        char c = e.getKey();
        int i = e.getValue();
        if(i < count[1]) {
          count[0] = count[1];
          result[0] = result[1];
          count[1] = i;
          result[1] = c;
        }
    }
    return result;
}

 

[nillehammer]

Das geht aber auch einfacher. [...]

Wenn ich die Anforderung richtig verstanden habe, ging es darum, die Characters sortiert nach ihrer Anwendungshäufigkeit in einem char-Array auszugeben. Das ist zumindest das, was mein Code macht.
Den Zweck Deines Codes habe ich noch nicht ganz durchschaut...

 

[Marco13]

Der Code macht (soweit ich das überflogen habe) das, was im Eröffnungsbeitrag gefordert wurde - und zwar ohne Schnörkel.
[ot]
Als ich den Threadttitel gelesen habe, habe ich mich schon darauf "gefreut", wieder irgendwas zu lesen mit ~"in einem Array kopieren und sortieren" - nur um den Krampf zu sehen, den sich der Antwortende dann dafür antun würde
[/ot]
Vermutlich ist die Problembeschreibung zu ungenau. Geht wes wirklich IMMER NUR genau (!) um den seltensten und den zweitseltensten? Dann tut's das von DrZoidberg. Wenn es um eine nach Häufigkeit sortierte Map geht, könnte sowas wie http://www.java-forum.org/codeschnipsel-u-projekte/64510-map-treemap-sorted-values.html hilfreich sein.

 

[nillehammer]

, was im Eröffnungsbeitrag gefordert wurde

Den ich gerade noch mal gelesen habe... bei nur zwei chars im Array ist meine Lösung Overkill und erfüllt die Anfroderung auch nicht, da sie einen char-Array mit allen Elementen ausgibt. Die zwei seltenst verwendeten stehen zwar an index 0,1, aber der Array ist zu lang für die Anforderung... dann wohl doch das von DrZoidberg.

Ich merke, dass spät nachts meine Aufnahmefähigkeit wohl doch etwas nachlässt...

 

[f4814n]

ich bin eben erst nach hause kommen und kann mich jetzt erst dem ganzen widmen. Vielen Dank für das Feedback und dass ihr euch so kümmert. Das ist dfür jemanden wie mich super hilfreich!!!

Ich kann das glaube ich am ehesten auflösen indem ich mal die Aufgaben beschreibung poste, wollte euch den Text eigentlich gerne ersparen ;-)

Aufgabe 2 hier:

http://web.informatik.uni-mannheim.de/java10000/pi2/pi2-2012-pklausur-2nd.pdf

ich hab übrigens auch ein Thread zu Aufgabe 3 ;-) vielleicht kann mir da der eine oder andere vielleicht weiterhelfen. Die dortigen Helfer haben sich glaube ich verabschiedet nachdem ich etwas Verwirrung gestiftet habe hahaha

Thread zu Aufgabe 3:

http://www.java-forum.org/java-basi...7281-aufgabe-arrays-arraylist.html#post985499

Beste Grüße und tausend DANK!

 

[f4814n]

Problem 1: Die Map garantiert die Reihenfolge (wenn überhaupt) nur für die Keys. Die Reihenfolge der Values ist daher garantiert nicht so, wie wir sie haben wollen. Wir müssen also irgendwie durch die Map durchiterieren und dabei einfach und intelligent umsortieren. Wir bräuchten was, das die Sortierung nach dem Value des Entriys macht. Lösung: wir basteln uns einen

Comparator

dafür.

Als Container für die neu sortierten Entries nehmen wir ein

TreeSet

, dem wir unseren

Comparator

übergeben. Damit werden die Entries in diesem Set nun nach ihrem Value sortiert. Das ist die schnellste Sortiervariante. Collections.sort für Listen ist langsamer. Obwohl sich das wohl erst bei sehr vielen Elementen bemerkbar machen dürfte. Und das ist ja bei dem begrenzten Wertebereich von char ausgeschlossen. Egal, so werden die Entries jedenfalls gleich beim add sortiert und wir sparen uns den Aufruf von Collections.sort.

Problem 2: Der return type ist ein Array von primitiven chars. D.h. die Methoden des Collections-Frameworks, die Arrays erzeugen, bringen uns nichts, weil diese nie primitive Elemente enthalten können. Wir müssen also selbst Unboxen undas Array befüllen.

Nachfolgender Code macht das alles. Kopieren, compilieren, ausführen:

public class MapEntriesToCharArray {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		final Map<Character, Integer> charsToUseCount = new HashMap<>(3);

		charsToUseCount.put('a', 2);
		charsToUseCount.put('e', 8);
		charsToUseCount.put('f', 4);

		final char[] sortedByUseCount = getRareChars(charsToUseCount);
		System.out.println(Arrays.toString(sortedByUseCount));
	}

	public static char[] getRareChars(final Map<Character, Integer> charMap) {

		final Set<Map.Entry<Character, Integer>> valueSortedEntries = new TreeSet<>(
				MapEntryComparator.ASCENDING_VALUES);
		valueSortedEntries.addAll(charMap.entrySet());

		final char[] result = new char[valueSortedEntries.size()];

		int currentResultIndex = 0;
		for (final Map.Entry<Character, Integer> entry : valueSortedEntries) {

			result[currentResultIndex] = entry.getKey();
			currentResultIndex++;
		}

		return result;
	}

	private static enum MapEntryComparator implements
			Comparator<Map.Entry<Character, Integer>> {
		/**
		 * Diese Implementierung sortiert Map.Entries nach dem Wert ihres values
		 * (hier ein Integer).
		 */
		ASCENDING_VALUES;

		@Override
		public final int compare(final Entry<Character, Integer> first,
				final Entry<Character, Integer> second) {
			return first.getValue().compareTo(second.getValue());
		}
	}

}

Danke für die Mühe, die Aufgabe gibt jedoch vor eine HashMap verwenden zu müssen. Scheint aber mit einer Treemap tatsächlich besser zu funktionieren soweit ich das beurteilen kann...

 

[f4814n]

public class CharCounterXTest {

	private CharCounterX counterx;
	
	@Before
	public void init(){ 
		this.counterx = new CharCounterXImpl();
	}

	@Test
	public void testSimple1() {
		String text = "aaaa bbb cc d";
		this.counterx.parse(text);
		char[] cc = this.counterx.getRareChars();
		char c1 = cc[0];
		char c2 = cc[1];
		assertEquals('d', c1);
		assertEquals('c', c2);
	}

	
	@Test
	public void testSimple2() {
		String text = "abcdefg abcdefg abcdefg xx abcdefg yyy abcdefg abcdefg abcdefg abcdefg";
		this.counterx.parse(text);
		char[] cc = this.counterx.getRareChars();
		char c1 = cc[0];
		char c2 = cc[1];
		assertEquals('x', c1);
		assertEquals('y', c2);
	}
	
	@Test
	public void testNotEnough1() {
		String text = "";
		this.counterx.parse(text);
		char[] cc = this.counterx.getRareChars();
		assertNull(cc);
	}
	
	@Test
	public void testNotEnough2() {
		String text = "a";
		this.counterx.parse(text);
		char[] cc = this.counterx.getRareChars();
		assertNull(cc);
	}
	
	@Test
	public void testNotEnough3() {
		String text = "qqqqqqqqqqqqqqqqqqqqqqqqqq";
		this.counterx.parse(text);
		char[] cc = this.counterx.getRareChars();
		assertNull(cc);
	}

Das sind übrigens die ersten paar Tests zu der Aufgabe und mit der Lösung wird leider keiner grün...

 

[DrZoidberg]

Die Methode soll also null zurückliefern, wenn weniger als 2 verschiedene Buchstaben im Text vorkommen?
Dann must du den Code doch nur etwas ergänzen.

public char[] getRareChars() {
    if(counter.size() < 2) return null;
    char[] result = new char[2];
    int[] count = {Integer.MAX_VALUE, Integer.MAX_VALUE};
    for(Map.Entry<Character, Integer> e : counter.entrySet()){                       
        char c = e.getKey();
        int i = e.getValue();
        if(i < count[0]) {
            count[1] = count[0];
            result[1] = result[0];
            count[0] = i;
            result[0] = c;
        } else if(i < count[1]) {
            count[1] = i;
            result[1] = c;
        }
    }
    return result;
}