Datastrukturer och databaser för STS

och

Programmeringsteknik II för F

Laborations- och programmeringsuppgift 1: en jämförelse av datastrukturer för lagring och sökning.

Java-dokumentation hittar du på http://java.sun.com/docs/

Uppgifter består av att jämföra tre olika datastrukturer för attt lagra data. De tre metoderna är

länkad lista
balanserat binärt sökträd
hashtabell

Exakt hur dessa fungerar kommer att gås igenom under kursen. Du behöver dock inte känna till detaljerna för att göra uppgiften. Alla tre datastrukturer finns implementerade i javabiblioteket. Du skall använda dig av följande klasser (kolla detaljerna i Java-dokumentationen):

Class LinkedList. Du lagrar data med metoden add (använd den variant som lägger det nya elementet sist i listan). Du kontrollerar om ett element finns lagrat med metoden contains.
Class TreeMap. Du lagrar data med metoden put. Du kontrollerar om ett element finns lagrat med metoden containsKey.
Class Hashtable. Du lagrar data med metoden put. Du kontrollerar om ett element finns lagrat med metoden contains eller containsKey.

I klassen System finns en metod currentTimeMillis(), som returnerar nuvarande tid i millisekunder (vad betyder nuvarande tid?). I klassen Random finns slumptalsfunktioner. Även klasserna String och Character innehåller metoder som kan vara användbara.

Uppgiften är att genomföra följande experiment:

Upprepa för n = 10, 100, 1000, .... så långt datorn klarar på rimlig tid (under c:a en halvtimme):
1. Skapa en vektor (array) med n objekt. Varje objekt skall innehålla
  - en söknyckel (key) som i detta fall är en slumpmässigt genererad sträng. Varje sträng skall vara 10 tecken lång och innehålla bokstäver (stora och små) och siffror, som exempelvis "g5AkL88KGx".
  - ett datavärde (value) som är ett slumpmässigt genererat heltal mellan 0 och 1000. Värt att notera är att put tar två argument, en nyckel och ett datavärde, som båda måste vara objekt. Ett rent tal (en int) är inte ett objekt. Tips: Klassen Integer är användbar.
2. För varje av de tre datastrukturerna (lista, träd, hashtabell) genomför följande:
  1. Starta tidmätningen.
  2. Sätt in de n strängarna.
  3. Stoppa tidmätningen, registrera tiden.
  4. Starta tidmätningen.
  5. För varje sträng, fråga om den finns i mängden.
  6. Stoppa tidmätningen, registrera tiden.
  7. Starta tidmätningen.
  8. Tag bort de n strängarna, en efter en.
  9. Stoppa tidmätningen, registrera tiden.
När expeimenten är genomförda, presentera resultatet i en tabell.

Tänk på

När ett Random-objekt skapas initieras dess slumptalsfrö med ett värde från klockan. Om man skapar flera Random-objekt i tät följd kommer därför flera av dem att få samma slumpfrö och därför generera samma slumptalsföljd. För att garantera att era nycklar blir unika bör ni därför se till att inte skapa flera Random-objekt i en loop eller liknande. Allra bäst är naturligtvis om det bara finns ett random-objekt som gäller för hela programmet.
Läs mer om slumptal här.