VPF::[Java] Протестирвать данные словаря

KatrinIceLand

Дата 2.11.2007, 12:29 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

Даны две программы. Первая с заданием, вторая измененная.

Задание протестировать данные словаря с помощью измененной программы и старой, и сравнить runtime для этих двух программ используя разные размеры словаря.

(Test the improved efficiency of your solution by comparing its runtime against the old implementation for different sized dictionaries.)

Программа 1:

Код


//
//  table.java
//

import java.lang.*;

public class Table {

    public static final int Empty    = 0;
    public static final int Occupied = 1;

    // Table entry.
    class TableEntry {
        int        status;
        String    key;
        int        value;
    }

    protected int         m_capacity;    // Table capacity.
    protected int         m_size;        // Current number of elements the table holds.
    protected TableEntry  m_data[];     // Elements.

    // Returns true if key found, idx is then set to the index of 
    // element with that key in data array.
    // If key is not found, returns false and set index to an empty
    // location in the array (except array is full, then idx is set
    // to the table capacity).
    boolean findKey( String key, int [] idx ) {
        int empty = m_capacity;
        for (int i=0; i<m_capacity; ++i ) {
            if ( (m_data[i].status == Empty) && (empty == m_capacity) ) {
                empty = i;
            }
            else if ( (m_data[i].status == Occupied) && (key.equals(m_data[i].key)) ) {
                idx[0] = i;
                return true;
            }
        }
        idx[0] = empty;
        return false;
    }


    // Create a new table with given capacity.
    Table( int capacity ) {
        m_capacity = capacity;
        m_data = new TableEntry[m_capacity];
        clear();
    }
    

    // Clears the table (erase all elements)
    void clear() {
        for (int i=0; i<m_capacity; ++i ) {
            m_data[i] = new TableEntry();        
            m_data[i].status = Empty;
            m_data[i].key = null;
            m_data[i].value = 0;
        }
        m_size = 0;
    }


    // Returns the number of elements in the table.
    int  size() {
        return m_size; 
    };


    // Returns true if table empty, otherwise false.
    boolean isEmpty() 
    { 
        return m_size == 0; 
    }
    
    
    // Insert an element into the table, if key already exists
    // overwrite the value. Returns true if element found, otherwise flase.
    boolean insert( String key, int value) {
        int [] arr = { 0 };
        int idx;
        if ( findKey(key, arr) ) {
            idx = arr[0];
            // Key already in table, update value associated with key.
            m_data[idx].value = value;
        } else {    
            // Key not in table, add entry.
            idx = arr[0];
            if (idx < m_capacity ) {
                m_data[idx].status = Occupied;
                m_data[idx].key    = new String(key);
                m_data[idx].value  = value;
                m_size++;
            }
            else return false;    // Table full.
        }
        return true;  // Successful insertion!
    }


    // Delete element with key. Returns true if element found, otherwise false.
    boolean erase( String key) {
        int [] arr = { 0 };
        if ( findKey(key, arr) ) {
            int idx = arr[0];
            m_data[idx].status = Empty;
            m_data[idx].key    = null;
            m_data[idx].value  = 0;
            return true;
        }
        return false;
    }


    // Retrieve element with key (set value). Returns true if element found, 
    // otherwise false.
    boolean retrieve( String key, int [] value) { 
        int [] arr = { 0 };
        if ( findKey(key, arr) ) {
            int idx = arr[0];
            value[0] = m_data[idx].value;
            return true;
        }    
        return false;
    }

    // Collects n "first" elements in table into arrays key[] and value[]. Returns 
    // how many elements are collected (can be less than n). Note that the collected
    // elements are not necessarily sorted.
    int  collect( int n, String key[], int value[] ) {
        int collected = 0;
        for (int idx=0; idx < m_capacity; ++idx ) {
            if ( m_data[idx].status == Occupied ) {
                if ( collected < n ) {
                    key[collected]   = m_data[idx].key;
                    value[collected] = m_data[idx].value;
                    collected++;
                }
                else 
                    return collected;
            }
        }
        return collected;
    }

}

Программа 2:

Код


public class HashMap
{
  private final Entry[] entries;

  public HashMap()
  {
    this(1024);
  }

  public HashMap(int size)
  {
    entries = new Entry[size];
  }

  public boolean contains(Object key)
  {
    Entry entry = entries[getIndex(key.hashCode())];
    while(entry != null)
    {
      if(entry.key.equals(key))
        return true;
      entry = entry.next;
    }
    return false;
  }

  public Object find(Object key)
  {
    Entry entry = entries[getIndex(key.hashCode())];
    while(entry != null)
    {
      if(entry.key.equals(key))
        return entry.value;
      entry = entry.next;
    }
    return null;
  }

  public void put(Object key, Object value)
  {
    int idx = getIndex(key.hashCode());
    Entry entry = entries[idx];
    if(entry == null)
    {
      entries[idx] = new Entry(key, value);
    }
    else
    {
      while(entry != null)
      {
        if(entry.key.equals(key))
        {
          entry.value = value;
          return;
        }
        if(entry.next == null)
        {
          entry.next = new Entry(key, value);
          return;
        }
        entry = entry.next;
      }
    }
  }

  public Object remove(Object key)
  {
    int idx = getIndex(key.hashCode());
    Entry entry = entries[idx];
    if(entry == null)
    {
      return null;
    }
    else
    {
      if(entry.key.equals(key))
      {
        entries[idx] = entry.next;
        return entry.value;
      }

      Entry prev = entry;
      entry = entry.next;
      while(entry != null)
      {
        if(entry.key.equals(key))
        {
          prev.next = entry.next;
          return entry.value;
        }
        prev = entry;
        entry = entry.next;
      }
      return null;
    }
  }

  private int getIndex(int hash)
  {
    return hash % entries.length;
  }

  private class Entry
  {
    private Entry next;
    private Object key;
    private Object value;

    public Entry(Object key, Object value)
    {
      this.key = key;
      this.value = value;
    }
  }
}

Дата словаря:

abbad�
abbast
Adda
Adolf
Adolfi
Adolfs
a?
...
...
и так далее

Это сообщение отредактировал(а) KatrinIceLand - 2.11.2007, 12:30

--------------------

[... кто изобрел математику? А зачем?...

LSD

Дата 2.11.2007, 17:22 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 9
Всего: 538

А как вообще первый класс работает? И что именно надо тестировать?

--------------------

Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it.

KatrinIceLand

Дата 2.11.2007, 18:31 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

Цитата(LSD @ 2.11.2007, 17:22

)

А как вообще первый класс работает? И что именно надо тестировать?

В этом то и состоит вопрос smile

, мне совсем не понятно как можно протестировать и сравнить данные.

Но суть задания я постаралась описать. Даны программы, дан словарь со словами. Надо сравнить runtime (это время потраченное на executing the program, насколько я понимаю) затраченное в первом варианте и во втором.

Еще мне удалось достать класс Тест, который тоже участвует в этой курсовой:

Код


//
//  testTable.java
//  RR-Assignment2
//


import java.util.*;
import java.io.*;

public class testTable {

    public static void main( String[] args ) {

        // Check number of arguments.
        if ( args.length != 2 ) {
            System.out.println("Error: incorrect use, filename parameter expected."); 
            return;
        }

        Scanner sc = null;
        try {    
            sc = new Scanner( new FileReader(args[1]) );
        } catch (IOException e) {
                System.out.println("Error: could not open file"); 
                return;
        }
    
        // Keywords to check.
        String keywords[] =    { "int", "double", "const", "class", "char", 
                               "for", "if", "switch", "return", "while" };
        Table T = new Table( 20 ); 

        for (int i=0; i<keywords.length; ++i) {
            if ( ! T.insert(keywords[i],0) ) {
                System.out.println("Error: could not insert a value"); 
                return;
            }
        }
        System.out.print( T.size() );
        System.out.println(" keywords added to table." );

        //
        // Parse the input, word by word.
        //
        String word;
        while ( sc.hasNext() ) { 
            int [] value = { 0 };
            word = sc.next();
            if ( T.retrieve(word, value) ) {
                value[0] = value[0] + 1;  // Update word count.
            }
            else value[0] = 1;  // New word.
    
            // Now update corresponding entry in table.
            T.insert(word, value[0]);
        }   

        // Now list all the keywords (in no particular order) and how many times
        // they were found in the input.
        String keys[] = new String[keywords.length];
        int    values[] = new int[keywords.length];
        int n = T.collect(keys.length, keys, values);
        System.out.println( "-----------------------------------------------" );
        System.out.println( "\tKeyword\t\tOccurence" );
        System.out.println( "-----------------------------------------------" );
        for ( int i = 0; i < n ; ++i ) {
            System.out.print( "\t" );
            System.out.print( keys[i] );
            System.out.print( "\t\t" );
            System.out.println( values[i] );
        }
        System.out.println( "-----------------------------------------------" );

    }
    
    public static boolean readWord( String string )
    {
        try {
    //        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            int    c = System.in.read();        
            while ( c != -1 ) {
                c = System.in.read();
            }
        } catch (IOException e) {
        }
        return    true;
    }
}

Как же теперь все это запустить и задокументировать??

--------------------

[... кто изобрел математику? А зачем?...

LSD

Дата 4.11.2007, 20:03 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 9
Всего: 538

Ты меня еще больще запутала smile

1. Где в твоем тесте словарь используется?
2. Что именно надо проверить, вхождение ключевых слов, количество вхождений каждого слова, количество неправильных слов?

--------------------

KatrinIceLand

Дата 5.11.2007, 11:18 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

Цитата(LSD @ 4.11.2007, 20:03

)

Ты меня еще больще запутала

извини, не хотела.

Вот оригинал задания:

We provide an implementation of a dictionary (table.java). This implementation is unfortunately very inefficient when used with a large number of data items because it uses a linear search for finding, deleting, and inserting elements. Your task is to change it such that it uses hashing. Use linear-probing to resolve conflicts. Make sure to thoroughly test your solution.

Test the improved efficiency of your solution by comparing its runtime against the old implementation for different sized dictionaries. Report your findings.

Цитата(LSD @ 4.11.2007, 20:03

)

2. Что именно надо проверить, вхождение ключевых слов, количество вхождений каждого слова, количество неправильных слов?

runtime - время прогона программы, рабочий цикл.

--------------------

[... кто изобрел математику? А зачем?...

LSD

Дата 7.11.2007, 12:45 (ссылка)

(нет голосов)

Загрузка ...

Leprechaun Software Developer

Профиль
Группа: Модератор
Сообщений: 15718
Регистрация: 24.3.2004
Где: Dublin

Репутация: 9
Всего: 538

Вот что у меня получилось:

Код


public class HashMap
{
  private final Entry[] entries;
  private int size = 0;

  public HashMap()
  {
    this(1024);
  }

  public HashMap(int size)
  {
    entries = new Entry[size];
  }

  public int getSize()
  {
    return size;
  }

  public boolean contains(String key)
  {
    Entry entry = entries[getIndex(key.hashCode())];
    while(entry != null)
    {
      if(entry.key.equals(key))
        return true;
      entry = entry.next;
    }
    return false;
  }

  public int find(String key)
  {
    Entry entry = entries[getIndex(key.hashCode())];
    while(entry != null)
    {
      if(entry.key.equals(key))
        return entry.value;
      entry = entry.next;
    }
    return -1;
  }

  public void put(String key, int value)
  {
    int idx = getIndex(key.hashCode());
    Entry entry = entries[idx];
    if(entry == null)
    {
      entries[idx] = new Entry(key, value);
      size++;
    }
    else
    {
      while(entry != null)
      {
        if(entry.key.equals(key))
        {
          entry.value = value;
          return;
        }
        if(entry.next == null)
        {
          entry.next = new Entry(key, value);
          size++;
          return;
        }
        entry = entry.next;
      }
    }
  }

  public int remove(String key)
  {
    int idx = getIndex(key.hashCode());
    Entry entry = entries[idx];
    if(entry == null)
    {
      return -1;
    }
    else
    {
      if(entry.key.equals(key))
      {
        entries[idx] = entry.next;
        size--;
        return entry.value;
      }

      Entry prev = entry;
      entry = entry.next;
      while(entry != null)
      {
        if(entry.key.equals(key))
        {
          prev.next = entry.next;
          size--;
          return entry.value;
        }
        prev = entry;
        entry = entry.next;
      }
      return -1;
    }
  }

  private int getIndex(int hash)
  {
    int i = hash % entries.length;
    return i < 0 ? i + entries.length : i;
  }

  private class Entry
  {
    private Entry next;
    private String key;
    private int value;

    public Entry(String key, int value)
    {
      this.key = key;
      this.value = value;
    }
  }
}

Код


public class Table
{
  public static final int Empty = 0;
  public static final int Occupied = 1;

  protected int m_capacity;// Table capacity.
  protected int m_size;// Current number of elements the table holds.
  protected TableEntry m_data[];// Elements.

  // Returns true if key found, idx is then set to the index of
  // element with that key in data array.
  // If key is not found, returns false and set index to an empty
  // location in the array (except array is full, then idx is set
  // to the table capacity).
  public boolean findKey(String key, int[] idx)
  {
    int empty = m_capacity;
    for(int i = 0; i < m_capacity; ++i)
    {
      if((m_data[i].status == Empty) && (empty == m_capacity))
      {
        empty = i;
      }
      else if((m_data[i].status == Occupied) && (key.equals(m_data[i].key)))
      {
        idx[0] = i;
        return true;
      }
    }
    idx[0] = empty;
    return false;
  }

  // Create a new table with given capacity.
  public Table(int capacity)
  {
    m_capacity = capacity;
    m_data = new TableEntry[m_capacity];
    clear();
  }

  // Clears the table (erase all elements)
  public void clear()
  {
    for(int i = 0; i < m_capacity; ++i)
    {
      m_data[i] = new TableEntry();
      m_data[i].status = Empty;
      m_data[i].key = null;
      m_data[i].value = 0;
    }
    m_size = 0;
  }

  // Returns the number of elements in the table.
  public int size()
  {
    return m_size;
  }

  // Returns true if table empty, otherwise false.
  boolean isEmpty()
  {
    return m_size == 0;
  }


  // Insert an element into the table, if key already exists
  // overwrite the value. Returns true if element found, otherwise flase.
  public boolean insert(String key, int value)
  {
    int[] arr = {0};
    int idx;
    if(findKey(key, arr))
    {
      idx = arr[0];
      // Key already in table, update value associated with key.
      m_data[idx].value = value;
    }
    else
    {
      // Key not in table, add entry.
      idx = arr[0];
      if(idx < m_capacity)
      {
        m_data[idx].status = Occupied;
        m_data[idx].key = key;
        m_data[idx].value = value;
        m_size++;
      }
      else
        return false;// Table full.
    }
    return true;// Successful insertion!
  }

  // Delete element with key. Returns true if element found, otherwise false.
  public boolean erase(String key)
  {
    int[] arr = {0};
    if(findKey(key, arr))
    {
      int idx = arr[0];
      m_data[idx].status = Empty;
      m_data[idx].key = null;
      m_data[idx].value = 0;
      return true;
    }
    return false;
  }

  // Retrieve element with key (set value). Returns true if element found,
  // otherwise false.
  public boolean retrieve(String key, int[] value)
  {
    int[] arr = {0};
    if(findKey(key, arr))
    {
      int idx = arr[0];
      value[0] = m_data[idx].value;
      return true;
    }
    return false;
  }

  // Collects n "first" elements in table into arrays key[] and value[]. Returns
  // how many elements are collected (can be less than n). Note that the collected
  // elements are not necessarily sorted.
  public int collect(int n, String key[], int value[])
  {
    int collected = 0;
    for(int idx = 0; idx < m_capacity; ++idx)
    {
      if(m_data[idx].status == Occupied)
      {
        if(collected < n)
        {
          key[collected] = m_data[idx].key;
          value[collected] = m_data[idx].value;
          collected++;
        }
        else
          return collected;
      }
    }
    return collected;
  }

  public static class TableEntry
  {
    int status;
    String key;
    int value;
  }
}

Код


import java.io.*;
import java.nio.charset.Charset;
import java.util.Scanner;

public class SpellCheck
{
  public static final double AVG_BYTES_PER_WORD = 5.0;
  public static final int ITERATIONS = 10;

  private static String fileEncoding;

  public static void main(String[] args)
  {
    if(args.length < 1)
    {
      printUsage();
      System.exit(1);
    }

    initCharset(args);

    for(int i = 0; i < ITERATIONS; i++)
    {
      testHashMap(args[0]);
      testTable(args[0]);
    }

    long time = System.currentTimeMillis();
    for(int i = 0; i < ITERATIONS; i++)
      testHashMap(args[0]);
    time = System.currentTimeMillis() - time;
    System.out.println("HashMap time = " + time / ITERATIONS + " ms");

    time = System.currentTimeMillis();
    for(int i = 0; i < ITERATIONS; i++)
      testTable(args[0]);
    time = System.currentTimeMillis() - time;
    System.out.println("Table time = " + time / ITERATIONS + " ms");
  }

  private static void initCharset(String[] args)
  {
    if(args.length > 2 && Charset.isSupported(args[2]))
      fileEncoding = args[2];
    else
      fileEncoding = Charset.defaultCharset().name();
  }

  private static void printUsage()
  {
    System.out.println("Usage: java SpellCheck <text_file> [<encoding>]");
  }

  private static HashMap testHashMap(String fileName)
  {
    try
    {
      File file = new File(fileName);
      HashMap hashMap = new HashMap((int) (file.length() / AVG_BYTES_PER_WORD));
      Scanner scanner = new Scanner(new FileInputStream(fileName), fileEncoding);
      while(scanner.hasNext())
      {
        String s = scanner.next();
        if(hashMap.contains(s))
        {
          hashMap.put(s, hashMap.find(s) + 1);
        }
        else
        {
          hashMap.put(s, 1);
        }
      }
      scanner.close();
      return hashMap;
    }
    catch(IOException e)
    {
      System.err.println("Error reading input file: " + e.getMessage());
      System.exit(2);
      return null;
    }
  }

  private static Table testTable(String fileName)
  {
    try
    {
      File file = new File(fileName);
      Table table = new Table((int) (file.length() / AVG_BYTES_PER_WORD));
      Scanner scanner = new Scanner(new FileInputStream(fileName), fileEncoding);
      int[] idx = new int[1];
      while(scanner.hasNext())
      {
        String s = scanner.next();
        if(table.findKey(s, idx))
        {
          table.insert(s, idx[0] + 1);
        }
        else
        {
          table.insert(s, 1);
        }
      }
      scanner.close();
      return table;
    }
    catch(IOException e)
    {
      System.err.println("Error reading input file: " + e.getMessage());
      System.exit(2);
      return null;
    }
  }
}

--------------------

KatrinIceLand

Дата 11.11.2007, 13:51 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 166
Регистрация: 16.3.2006

Репутация: нет
Всего: нет

LSD, спасибо большое за помощь!

Твой вариант решения я сдала преподователю. Результат сообщю smile

--------------------

[... кто изобрел математику? А зачем?...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »