TimeComplexityTester

/* * A tester for selected methods. You can write similar tests for other methods. * The original "music.csv" was downloaded from https://think.cs.vt.edu/corgis/csv/music/music.html. * I extracted three columns(title, artist, year) out of it, cleaned some invalid data and stored the output as "songdata.csv". * The total number of songs in "songdata.csv" is 9678. * * This tester outputs a CSV file which can be visualized by Excel. * * UPDATED on 2018/11/26: The pattern given by the put() method is linear because in testPut(), I used a for each loop to add all songs to the new * hash table, so it could be used by other tests later. However, the time complexity of put() is O(1), so if your result is linear, you should be * fine. Thank Hansen Liu for noticing it. * * Warning: This tester does not check your correctness. * * Date Created: 2018/11/25 * Author: Sixian Li * */ package assignment4; import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.FileWriter; import java.util.ArrayList; import java.util.Random; public class TimeComplexityTester { public static void main(String[] args) { Random randomKey = new Random(); try (FileWriter fw = new FileWriter("result.csv")) { // Header for the output csv file fw.append("size,put(),get(),keys(),values()\n"); // You can modify the size, but the MAXIMUM size is 9678. This may take quite a while to run. // The size should start from 1 or generateSongs() will give an error. for (int size=1; size<3000; size++) { ArrayList<Song> songs = generateSongs(size); //System.out.println(songs.size()); MyHashTable<String, Song> songTable; // Genrate a random key -- a random title from songlist. String key = songs.get(randomKey.nextInt(songs.size())).getTitle(); int numBuckets = (int) (size / 0.75); // Initialize the hash table. Key will be the song title. songTable = new MyHashTable<>(numBuckets); long putTime = testPut(songTable, songs); long getTime = testGet(songTable, key); long keysTime = testKeys(songTable); long valuesTime = testValues(songTable); fw.append(size + "," + putTime + "," + getTime + "," + keysTime + "," + valuesTime + "\n"); } } catch (Exception e) { e.printStackTrace(); } } public static long testPut(MyHashTable<String,Song> songTable, ArrayList<Song> songs){ long startTime = System.nanoTime(); for (Song song: songs) { songTable.put(song.getTitle(), song); } long endTime = System.nanoTime(); long duration = (endTime - startTime); return duration; } public static long testGet(MyHashTable<String,Song> songTable, String key){ long startTime = System.nanoTime(); songTable.get(key); long endTime = System.nanoTime(); long duration = (endTime - startTime); return duration; } public static long testKeys(MyHashTable<String,Song> songTable){ long startTime = System.nanoTime(); ArrayList<String> keys = songTable.keys(); long endTime = System.nanoTime(); long duration = (endTime - startTime); return duration; } public static long testValues(MyHashTable<String,Song> songTable){ long startTime = System.nanoTime(); ArrayList<Song> values = songTable.values(); long endTime = System.nanoTime(); long duration = (endTime - startTime); return duration; } public static ArrayList<Song> generateSongs(int size){ // Please don't modify this. String csvFile = "songdata.csv"; String line = ""; String cvsSplitBy = ","; ArrayList<Song> songs = new ArrayList<>(); try (BufferedReader br = new BufferedReader(new FileReader(csvFile))) { line=br.readLine(); for (int i=0; i<size; i++){ String[] info = line.split(cvsSplitBy); songs.add(new Song(info[0], info[1], Integer.parseInt(info[2]))); line=br.readLine(); } } catch (IOException e) { e.printStackTrace(); } return songs; } }

Be the first to comment

You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.