Hi,
ich habe ein Problem, ich beschreibe es am besten mal durch ein Beispiel.
Ich habe eine Liste mit Zahlen:1,4,5,8,9
Jetzt muss ich folgendes tun:
Ich bekomme eine Zahl: 8 Prüfen ob sie in der Liste ist —> Kein Problem
Mein Problem: Die kleinste Freie Zahl finden, in diesem Fall die 2!
Wie kann man das in Java Bewerkstelligen?
Du hast doch schon die Methode “enthaeltZahl”. Darauf kannst du aufbauen und in einer Zählschleife bei 1 beginnend so lange hochzählen, bis die zu prüfende Zahl nicht mehr enthalten ist.
Noch einfacher: wann ist das erste mal a[0]+i nicht das gleiche wie a**
Das setzt aber eine sortierte Liste voraus. Das ist hier aufgrund der Aufgabenfolge wahrscheinlich auch nicht gemeint 
Aber so könnte man das tatsächlich machen:
[spoiler]```package net.byte_welt;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
public class ZahlenSpielchen {
private List inhalt;
public ZahlenSpielchen(Collection<Integer> inhalt) {
this.inhalt = new ArrayList<>(inhalt);
Collections.sort(this.inhalt);
}
public boolean enthaeltZahl(int zahl) {
return inhalt.contains(zahl);
}
public int kleinsteFreieZahl() {
int ergebnis = 1;
for (Integer listenZahl : inhalt) {
if (listenZahl != ergebnis)
break;
ergebnis++;
}
return ergebnis;
}
public static void main(String... args) {
List<Integer> zahlen = new ArrayList<>();
zahlen.add(1);
zahlen.add(4);
zahlen.add(5);
zahlen.add(8);
zahlen.add(9);
ZahlenSpielchen spielchen = new ZahlenSpielchen(zahlen);
System.out.println("Enthält 8: " + spielchen.enthaeltZahl(8));
System.out.println("Kleinste freie Zahl: " + spielchen.kleinsteFreieZahl());
}
}```[/spoiler]
Danke an ALle!
Ja
int id = 1;
boolean hasFound = false;
while(!hasFound) {
if(!containsSenderID(id)) {
hasFound = true;
break;
}
id++;
}
return id;
}
public static int getFreeReceiverID() {
int id = 1;
boolean hasFound = false;
while(!hasFound) {
if(!containsReceiverID(id)) {
hasFound = true;
break;
}
id++;
}
return id;
}
public static boolean containsSenderID(int id) {
Set<Integer> allIds = instance.senderMap.keySet();
return allIds.contains(id);
}
public static boolean containsReceiverID(int id) {
Set<Integer> allIds = instance.receiverMap.keySet();
return allIds.contains(id);
}```Ok. Das ist eine ziemlich hässliche Variante eines Gang of Four-Singletons.
Die Methoden könntest du alle nicht-statisch machen. Dadurch sparst du dir im Objekt selbst das instance.-Präfix.
Außerdem ist es nicht so schön, dass du den Code duplizieren musstest. Da du sowieso intern eine Map benutzt, kannst du auch gleich direkt auf die containsKey-Methode zugreifen.
Das Statusflag sollte auch vermieden werden. Statt des break unddes Flags kannst du auch einfach ein return verwenden.
Zusammengenommen ergibt sich in etwa:
import java.util.HashMap;
import java.util.Map;
public class ZahlenSpielchen {
public static final ZahlenSpielchen INSTANCE = new ZahlenSpielchen();
private final Map<Integer, Object> senderMap = new HashMap<>();
private final Map<Integer, Object> receiverMap = new HashMap<>();
private ZahlenSpielchen() {
}
public int getFreeSenderID() {
return findFirstFreeId(senderMap);
}
public int getFreeReceiverID() {
return findFirstFreeId(receiverMap);
}
private int findFirstFreeId(Map<Integer, ?> map) {
for (int id = 1; ; id++) {
if (!map.containsKey(id))
return id;
}
}
public boolean containsSenderID(int id) {
return senderMap.containsKey(id);
}
public boolean containsReceiverID(int id) {
return receiverMap.containsKey(id);
}
}```Okay Danke, aber das static muss bleiben, da ich mit anderen Klassen drauf zugreif
Dann solltest du die verwendenden Klassen refaktorisieren. Die static-Methoden implizieren, dass es Klassenmethoden sind (sind es ja eigentlich auch, durch das static-Schlüsselwort). In Wirklichkeit verwendest du sie aber als Instanzmethoden der einzigen Instanz.
Der aufrufende Code sollte so aussehen: Klassenname.INSTANCE.getFreeSenderId() anstatt das instance in den Methoden zu verbergen. So wird wenigstens klar, dass es ein GoF-Singleton ist.
*** Edit ***
Falls dir das INSTANCE nicht gefällt, dann kannst du dafür auch eine Wrappermethode einfügen: public static Klassenname getInstance() { return INSTANCE; }
und dann das INSTANCE-Feld private machen.
Okay nochmals vielen Dank
[quote=Blackbyte]das static muss bleiben, da ich mit anderen Klassen drauf zugreif[/quote]Das Singelton ist zwar eine einfache aber nicht die beste Lösung. Besser ist, die einzige Instanz der Klasse ZahlenSpielchen in der main-Methode zu erzeugen und den Objekten, die damit umgehen müssen diese im Konstruktor mitzugeben.
“Dependancy Injection”-Frameworks wie Spring oder Guice helfen bei so was.
bye
TT
Mal eine Andere Frage… Ist für die IDs überhaupt eine Map erforderlich? Wie taugt denn ein BitSet?
private static final Identities INSTANCE = new Identities();
private final BitSet senderIDs = new BitSet();
private final BitSet receiverIDs = new BitSet();
public static Identities getInstsnce() {
return INSTANCE;
}
public int nextSenderID() {
return nextSenderID(0);
}
public int nextSenderID(int fromIndex) {
int rc = senderIDs.nextClearBit(fromIndex);
senderIDs.set(rc);
return rc;
}
public void freeSenderID(int id) {
senderIDs.clear(id);
}
public int nextReceiverID() {
return nextReceiverID(0);
}
public int nextReceiverID(int fromIndex) {
int rc = receiverIDs.nextClearBit(fromIndex);
receiverIDs.set(rc);
return rc;
}
public void freeReceiverID(int id) {
receiverIDs.clear(id);
}
}```
BTW.: Ich würde die Zugriffe auf die Datencontainer unbedingt synchronisieren.Naja, vom Namen „senderMap“ ausgehend würde ich annehmen, dass sich in der Map Sender- bzw. Empfängerobjekte verbergen.
Das erscheint mir auch ziemlich sinnvoll. Allerdings würde ich wahrscheinlich eine ConcurrentHashMap verwenden und die IDs auf andere Weise generieren (AtomicInteger). Dadurch erreicht man ein deutlich besseres Nebenläufigeitsverhalten.
Algo: Finde ich die erste 0 einer Bitfolge erst, wenn ich n+1 Bits durchgehe, wobei n die Anzahl der 1en am Anfang der Folge ist - wenn ich beim Setzen usw. mir nicht merke, wo die erste freie Stelle ist (und das BS nicht sortiert ist)?
Singleton: Methoden sind statisch, greifen aber auf genau eine Instanz zu - besser umgekehrt: Instanz ist statisch, greift aber auf Objektmethoden zu. Um zu vermeiden, dass es immer eine Instanz gibt -sondern nur genau Eine wenn benötigt-, statische Fabrikmethode.
Zudem: Je größer der kritische, zu synchronisierende Bereich ist, desto langsamer - thread-sichere Datenstrukturen und wirklich atomare Wrapperklassen sind also schneller. 
;/
Also es geht um IDs für irgendwas?
Also das ganze ist so:
Es ist ein Bukkit(Minecraft) Plugin für WirlessRedstone.(WirlessKabel)
Jeder Sender und jeder Empfänger hat eine ID.
Man brauch die ID,da jeder Sender auch mehrere Empfänger haben kann.
Das mit der main-Methode klappt nicht,da keine Main-Methode sowie kein Konstruktor aufgerufen wird, sondern nur 2 Methoden: onEnable und onDisable
Aus http://jd.bukkit.org/rb/doxygen/d7/deb/classorg_1_1bukkit_1_1plugin_1_1java_1_1JavaPlugin.html geht hervor, dass es auch noch eine onLoad-Methode gibt, in der du die Klasse initialisieren kannst. Dort kannst du eine Instanz der Klasse erstellen, die du sonst in der main-Methode erzeugt hättest.
Aus rein theoretischem Interesse mal meine Implementierung:
import java.util.*;
public class Smallest {
public static int smallestFree(List<Integer> list) {
return list.isEmpty() ? 1 : smallestFree(1, list);
}
private static int smallestFree(int from, Collection<Integer> collection) {
int pivot = collection.iterator().next();
Set<Integer> smaller = new LinkedHashSet<>();
for(int i : collection) {
if(i < pivot) smaller.add(i);
}
if (smaller.size() == pivot - from) {
Set<Integer> bigger = new LinkedHashSet<>();
for(int i : collection) {
if(i > pivot) bigger.add(i);
}
return bigger.isEmpty() ? pivot + 1 : smallestFree(pivot + 1, bigger);
} else if (smaller.isEmpty()) {
return from;
} else {
return smallestFree(from, smaller);
}
}
}
Annahmen: Die Liste ist ungeordnet (sonst wäre mit einfachen Durchgehen erledigt) und kann Duplikate enthalten. Werte kleiner eins dürfen nicht enthalten sein.
Sieht erst mal kompliziert aus, sollte aber theoretisch schneller als Sortieren und Durchgehen sein, weil es im Prinzip ein “halber” Quicksort ist: Ich teile die übergebene Collection in zwei Sets kleiner und größer als das Pivotelement ein. Ist das kleinere Set so groß wie der “Zwischenraum” von Untergrenze (from) und Pivotelemet, sind dort alle Zahlen da, und es kann unter Anhebung der Untergrenze im größeren Set gesucht werden (wenn es leer ist, haben wir die Lücke). Ist das nicht der Fall, wird im kleineren Set weitergesucht (wenn es leer ist, haben wir auch hier die Lücke). LinkedHashSet ist notwendig, weil der Hashcode von Integers der Wert selbst ist, ein HashSet<Integer> also wie ein TreeSet geordnet ist (was den Algorithmus zur linearen Suche entarten lässt). Ist die Eingangsliste garantiert ohne Duplikate, könnte auch mit Listen gearbeitet werden.
Ich möchte auch noch meinen Senf dazu-geben:
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication1;
import java.util.Arrays;
import java.util.HashSet;
import java.util.TreeSet;
/**
* @author CB
*/
public class IDsGen {
private static IDsGen idsGen = null;
private HashSet<Integer> hsi = new HashSet<Integer>();
private TreeSet<Integer> tsi = new TreeSet<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)); // keine PriorityQueue
public static synchronized IDsGen newIDsGen() {
if (idsGen == null) {
return idsGen = new IDsGen();
}
return idsGen;
}
private IDsGen() {
}
public synchronized int nextID() {
while (tsi.size() < 10) {
int i = tsi.last() + 1;
while (hsi.contains(i)) {
i++;
}
tsi.add(i);
}
int i = tsi.pollFirst();
hsi.add(i);
return i;
}
public synchronized boolean removeID(int id) {
if (hsi.contains(id)) {
hsi.remove(id);
tsi.add(id);
return true;
}
return false;
}
public static void main(String[] args) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
System.out.println("IDsGen.newIDsGen().nextID() = " + IDsGen.newIDsGen().nextID());
}
for (int j = 5; j >= 3; j--) {
System.out.println("IDsGen.newIDsGen().removeID(" + j + ") = " + IDsGen.newIDsGen().removeID(j));
}
}
}
}```
Ausgaben
[spoiler]
run:
IDsGen.newIDsGen().nextID() = 1
IDsGen.newIDsGen().nextID() = 2
IDsGen.newIDsGen().nextID() = 3
IDsGen.newIDsGen().nextID() = 4
IDsGen.newIDsGen().nextID() = 5
IDsGen.newIDsGen().removeID(5) = true
IDsGen.newIDsGen().removeID(4) = true
IDsGen.newIDsGen().removeID(3) = true
IDsGen.newIDsGen().nextID() = 3
IDsGen.newIDsGen().nextID() = 4
IDsGen.newIDsGen().nextID() = 5
IDsGen.newIDsGen().nextID() = 6
IDsGen.newIDsGen().nextID() = 7
IDsGen.newIDsGen().removeID(5) = true
IDsGen.newIDsGen().removeID(4) = true
IDsGen.newIDsGen().removeID(3) = true
IDsGen.newIDsGen().nextID() = 3
IDsGen.newIDsGen().nextID() = 4
IDsGen.newIDsGen().nextID() = 5
IDsGen.newIDsGen().nextID() = 8
IDsGen.newIDsGen().nextID() = 9
IDsGen.newIDsGen().removeID(5) = true
IDsGen.newIDsGen().removeID(4) = true
IDsGen.newIDsGen().removeID(3) = true
IDsGen.newIDsGen().nextID() = 3
IDsGen.newIDsGen().nextID() = 4
IDsGen.newIDsGen().nextID() = 5
IDsGen.newIDsGen().nextID() = 10
IDsGen.newIDsGen().nextID() = 11
IDsGen.newIDsGen().removeID(5) = true
IDsGen.newIDsGen().removeID(4) = true
IDsGen.newIDsGen().removeID(3) = true
IDsGen.newIDsGen().nextID() = 3
IDsGen.newIDsGen().nextID() = 4
IDsGen.newIDsGen().nextID() = 5
IDsGen.newIDsGen().nextID() = 12
IDsGen.newIDsGen().nextID() = 13
IDsGen.newIDsGen().removeID(5) = true
IDsGen.newIDsGen().removeID(4) = true
IDsGen.newIDsGen().removeID(3) = true
BUILD SUCCESSFUL (total time: 0 seconds)
[/spoiler]
Anmerkungen:
5*5=25 werden hineingesteckt, 4*3=12 werden hinausgesteckt, es verbleiben 25-12=13 = IDs 1 ...bis... 13 .
Wir gehen davon aus, dass alle Elemente <= tsi.last() und nicht in tsi (nicht Element von tsi) IN hsi SIND. Dh tsi.last()+1 ist das nächste freie Element, welches nicht in hsi und tsi ist (Kandidat ,der wartet).
Zeile 33 - 35 ist eigentlich überflüssig.
Anstatt 10 hätte man auch 3 oder 1 Elemente wählen können, wichtig ist nur, dass at the beginning mind. eins drinne ist.
Alle Operationen sind in O/T(log(n)) [wenn tsi.last() keinen Strich durch die Rechnung macht :( ].
*** Edit ***
Ich denk die ganze Zeit über die Invariante nach, ihr auch?
Sei n der Index des größten Elements in tsi, das noch nicht in hsi enthalten ist. Dann sind alle Elemente in hsi kleiner n.
Denn wenn in nextID n aus tsi entnommen wird, wird n+1 in tsi eingefügt und n+1 ist das neue n. Wegen der Annahme oben ist n und n+1 noch nicht in hsi enthalten und es gilt: n+1 > n.
In removeID wird n niemals verändert, denn wegen der Annahmen oben wird in tsi nur ein aus hsi entferntes Element eingefügt, das kleiner n ist.
entnommen == entfernt
Ist das schlüssig?
Edit: Hier ist das Richtige mit PriorityQueue
[spoiler]```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication1;
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
/**
* @author CB
*/
public class IDsGen {
private static IDsGen idsGen = null;
private HashSet<Integer> hsi = new HashSet<Integer>();
private PriorityQueue<Integer> pqi = new PriorityQueue<Integer>(Arrays.asList(1));
private int big = 2;
public static synchronized IDsGen newIDsGen() {
if (idsGen == null) {
return idsGen = new IDsGen();
}
return idsGen;
}
private IDsGen() {
}
public synchronized int nextID() {
if (pqi.isEmpty()) {
pqi.add(big++);
}
int i = pqi.remove();
hsi.add(i);
return i;
}
public synchronized boolean removeID(int id) {
if (hsi.contains(id)) {
hsi.remove(id);
pqi.add(id);
return true;
}
return false;
}
public static void main(String[] args) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
System.out.println("IDsGen.newIDsGen().nextID() = " + IDsGen.newIDsGen().nextID());
}
for (int j = 5; j >= 3; j--) {
System.out.println("IDsGen.newIDsGen().removeID(" + j + ") = " + IDsGen.newIDsGen().removeID(j));
}
}
}
}```[/spoiler]