Monthly Archives: January 2020

Time and Space Efficiency

There are lots of reasons for choosing one sorting algorithm over another. We might choose an algorithm because it is simple, fast, uses less memory, or works well on the kind of data we have. An algorithm that is easier to understand is also easier to write and debug. However, often the simplest sorts are not efficient. Efficiency is usually the first thing we look for.

We can compare algorithms in terms of time and space efficiency.

Space efficiency refers to the amount of space that an algorithm uses. An algorithm that uses less space and runs faster is more efficient.

  • We measure efficiency by the size of the input. For a sorting algorithm the input is the array of elements to be sorted, so the size of the input is the number of elements. We will use n for the number of elements being sorted.
  • We can measure the time efficiency of an algorithm by counting how many statements get executed when the algorithm runs.

We are most interested in how the running time grows as the size of the input grows, so we can ignore statements that get executed the same number of times each time the algorithm is run.

  • Instead we look at those statements that get executed a different number of times depending on the size of the input.
  • In sorting algorithms, the common operation is a comparison, so we usually count comparisons when we consider sorting algorithms.
  • As the number of elements to be sorted grows, the number of comparisons required grows as well.

We want to find the relationship between the two growth rates.

The selection sort has an outer loop that runs n-1 times, where n is the size of the input array.

The inner loop runs a variable number of times, ranging from 1 to n-1, depending on the index of the outer loop.

So, we can say that the time efficiency of the selection sort algorithm is on the order of n^2.

  • We use big-oh notation saying that selection sort is O(n^2). This means that the running time of the selection sort algorithm will be no worse than on the order of n^2 units of time, where n is the size of the input.
  • We are not interested in how long a unit of time is because we use big-oh notation only to compare algorithms to each other; we are not trying to find out how long the algorithm takes to run.
  • Note that because O(n^2) is an efficiency no worse than n^2, we could also say that selection sort is O(n^3) or O(n^4 ) or O(2n). However, we want to get as close as possible to an algorithm’s real time efficiency.
  • We can analyze insertion sort in almost the same way.
  • Its two nested loops run n times each, so the statements (comparisons) inside get executed approximately n^2 times.
  • The insertion sort algorithm is therefore also O(n^2).
  • An algorithm,  that  was  O(n) would be more efficient than one that is O(n^2 ).
  • Likewise, O(n^3 ) and O(2n) algorithms are less efficient than O(n2 ).

Table below shows various efficiency values for algorithms ranked from most efficient to least efficient. Note that for small values of n there is not much difference, but when n gets large, the efficiency of an algorithm makes a big difference.

The insertion sort has O(n^2) in the worse case. However, in an verage when the data is random, it is a more efficient sort.

These two sorts can also be implemented to work on objects.

 

Chapter 6 – ArrayLists of BankAccount objects 


import java.util.ArrayList; 

/** This bank contains a collection of bank accounts. */ 

public class Bank { 

    /** instance field(s) **/
    private ArrayList<BankAccount> accounts; 

    /** Constructs a bank with no bank accounts. */ 

    public Bank() 
    { 
        accounts = new ArrayList<BankAccount>(); 
    } 

    /** Adds an account to this bank. 
    @param a the account to add */ 

    public void addAccount(BankAccount a) 
    { 

        accounts.add(a); 
    } 

    /** Gets the sum of the balances of all accounts in this bank. @return the sum of the balances */ 

    public double getTotalBalance() 
    { 
        double total = 0; 
        for (BankAccount a : accounts) 
        { 
            total = total + a.getBalance(); 
        } 
        return total;
    } 

    /** Counts the number of bank accounts whose balance is at least a given value. 
     * @param atLeast the balance required to count an account 
     * @return the number of accounts having least the given balance */ 

    public int count(double atLeast) 
    { 
        int matches = 0; 
        for (BankAccount a : accounts) 
        { 
            if (a.getBalance() >= atLeast) 
                matches++; // Found a match 
        } 
        return matches; 
    } 

    /** Finds a bank account with a given number. 
     * @param accountNumber the number to find 
     * @return the account with the given number, or null if there is no such account */ 
    public BankAccount find(int accountNumber) 
    { 
        for (BankAccount a : accounts) 
        { 
            if (a.getAccountNumber() == accountNumber) // Found a match 
                return a; 
        } 
        return null; // No match in the entire array list 
    } 

    /** Gets the bank account with the largest balance. 
     * @return the account with the largest balance, or null if the bank has no accounts */ 
    public BankAccount getMaximum() 
    { 
        if (accounts.size() == 0) return null; 
        BankAccount largestYet = accounts.get(0); 
        for (int i = 1; i < accounts.size(); i++) 
        { 
            BankAccount a = accounts.get(i); 
            if (a.getBalance() > largestYet.getBalance()) largestYet = a; 
        } 
        return largestYet; 
    } 

}




//********************************************************************
//  Account.java now called BankAccount.java       Author: Lewis/Loftus/Cocking
//
//  Represents a bank account with basic services such as deposit
//  and withdraw.
//********************************************************************

import java.text.NumberFormat;

public class BankAccount /** formerly called Account **/
{
   private NumberFormat fmt = NumberFormat.getCurrencyInstance();

   private final double RATE = 0.035;  // interest rate of 3.5%

   private int acctNumber;
   private double balance;
   private String name;

   //-----------------------------------------------------------------
   //  Sets up the account by defining its owner, account number,
   //  and initial balance.
   //-----------------------------------------------------------------
   public BankAccount (String owner, int account, double initial)
   {
      name = owner;
      acctNumber = account;
      balance = initial;
   }

   //-----------------------------------------------------------------
   //  Validates the transaction, then deposits the specified amount
   //  into the account. Returns the new balance.
   //-----------------------------------------------------------------
   public double deposit (double amount)
   {
      if (amount < 0)  // deposit value is negative
      {
         System.out.println ();
         System.out.println ("Error: Deposit amount is invalid.");
         System.out.println (acctNumber + "  " + fmt.format(amount));
      }
      else
         balance = balance + amount;
      return balance;
   }

   //-----------------------------------------------------------------
   //  Validates the transaction, then withdraws the specified amount
   //  from the account. Returns the new balance.
   //-----------------------------------------------------------------
   public double withdraw (double amount, double fee)
   {
      amount += fee;

      if (amount < 0)  // withdraw value is negative
      {
         System.out.println ();
         System.out.println ("Error: Withdraw amount is invalid.");
         System.out.println ("Account: " + acctNumber);
         System.out.println ("Requested: " + fmt.format(amount));
      }
      else
         if (amount > balance)  // withdraw value exceeds balance
         {
            System.out.println ();
            System.out.println ("Error: Insufficient funds.");
            System.out.println ("Account: " + acctNumber);
            System.out.println ("Requested: " + fmt.format(amount));
            System.out.println ("Available: " + fmt.format(balance));
         }
         else
            balance = balance - amount;

      return balance;
   }

   //-----------------------------------------------------------------
   //  Adds interest to the account and returns the new balance.
   //-----------------------------------------------------------------
   public double addInterest ()
   {
      balance += (balance * RATE);
      return balance;
   }

   //-----------------------------------------------------------------
   //  Returns the current balance of the account.
   //-----------------------------------------------------------------
   public double getBalance ()
   {
      return balance;
   }

   //-----------------------------------------------------------------
   //  Returns the account number.
   //-----------------------------------------------------------------
   public int getAccountNumber ()
   {
      return acctNumber;
   }

   //-----------------------------------------------------------------
   //  Returns a one-line description of the account as a string.
   //-----------------------------------------------------------------
   public String toString ()
   {
      return (acctNumber + "\t" + name + "\t" + fmt.format(balance));
   }
}

The whole Bank ADT is visible:

import java.util.ArrayList;

/**
   This bank contains a collection of bank accounts.
*/
public class Bank
{   
   /**
      Constructs a bank with no bank accounts.
   */
   public Bank()
   {
      accounts = new ArrayList<BankAnccount>();
   }

   /**
      Adds an account to this bank.
      @param a the account to add
   */
   public void addAccount(BankAccount a)
   {
      accounts.add(a);
   }
   
   /**
      Gets the sum of the balances of all accounts in this bank.
      @return the sum of the balances
   */
   public double getTotalBalance()
   {
      double total = 0;
      for (BankAccount a : accounts)
      {
         total = total + a.getBalance();
      }
      return total;
   }

   /**
      Counts the number of bank accounts whose balance is at
      least a given value.
      @param atLeast the balance required to count an account
      @return the number of accounts having least the given balance
   */
   public int count(double atLeast)
   {
      int matches = 0;
      for (BankAccount a : accounts)
      {
         if (a.getBalance() >= atLeast) matches++; // Found a match
      }
      return matches;
   }

   /**
      Finds a bank account with a given number.
      @param accountNumber the number to find
      @return the account with the given number, or null if there
      is no such account
   */
   public BankAccount find(int accountNumber)
   {
      for (BankAccount a : accounts)
      {
         if (a.getAccountNumber() == accountNumber) // Found a match
            return a;
      } 
      return null; // No match in the entire array list
   }

   /**
      Gets the bank account with the largest balance.
      @return the account with the largest balance, or null if the
      bank has no accounts
   */
   public BankAccount getMaximum()
   {
      if (accounts.size() == 0) return null;
      BankAccount largestYet = accounts.get(0);
      for (int i = 1; i < accounts.size(); i++) 
      {
         BankAccount a = accounts.get(i);
         if (a.getBalance() < largestYet.getBalance())
            largestYet = a;
      }
      return largestYet;
   }
   /** NOTICE THE INSTANCE FIELD AT THE END OF THE FILE **/
   private ArrayList<BankAccount> accounts;
}

The whole BankAccount ADT (formerly Account) is visible:

//********************************************************************
//  Account.java now called BankAccount.java       Author: Lewis/Loftus/Cocking
//
//  Represents a bank account with basic services such as deposit
//  and withdraw.
//********************************************************************

import java.text.NumberFormat;

public class BankAccount
{
   private NumberFormat fmt = NumberFormat.getCurrencyInstance();

   private final double RATE = 0.035;  // interest rate of 3.5%

   private int acctNumber;
   private double balance;
   private String name;

   //-----------------------------------------------------------------
   //  Sets up the account by defining its owner, account number,
   //  and initial balance.
   //-----------------------------------------------------------------
   public BankAccount (String owner, int account, double initial)
   {
      name = owner;
      acctNumber = account;
      balance = initial;
   }

   //-----------------------------------------------------------------
   //  Validates the transaction, then deposits the specified amount
   //  into the account. Returns the new balance.
   //-----------------------------------------------------------------
   public double deposit (double amount)
   {
      if (amount < 0)  // deposit value is negative
      {
         System.out.println ();
         System.out.println ("Error: Deposit amount is invalid.");
         System.out.println (acctNumber + "  " + fmt.format(amount));
      }
      else
         balance = balance + amount;
      return balance;
   }

   //-----------------------------------------------------------------
   //  Validates the transaction, then withdraws the specified amount
   //  from the account. Returns the new balance.
   //-----------------------------------------------------------------
   public double withdraw (double amount, double fee)
   {
      amount += fee;

      if (amount < 0)  // withdraw value is negative
      {
         System.out.println ();
         System.out.println ("Error: Withdraw amount is invalid.");
         System.out.println ("Account: " + acctNumber);
         System.out.println ("Requested: " + fmt.format(amount));
      }
      else
         if (amount > balance)  // withdraw value exceeds balance
         {
            System.out.println ();
            System.out.println ("Error: Insufficient funds.");
            System.out.println ("Account: " + acctNumber);
            System.out.println ("Requested: " + fmt.format(amount));
            System.out.println ("Available: " + fmt.format(balance));
         }
         else
            balance = balance - amount;

      return balance;
   }

   //-----------------------------------------------------------------
   //  Adds interest to the account and returns the new balance.
   //-----------------------------------------------------------------
   public double addInterest ()
   {
      balance += (balance * RATE);
      return balance;
   }

   //-----------------------------------------------------------------
   //  Returns the current balance of the account.
   //-----------------------------------------------------------------
   public double getBalance ()
   {
      return balance;
   }

   //-----------------------------------------------------------------
   //  Returns the account number.
   //-----------------------------------------------------------------
   public int getAccountNumber ()
   {
      return acctNumber;
   }

   //-----------------------------------------------------------------
   //  Returns a one-line description of the account as a string.
   //-----------------------------------------------------------------
   public String toString ()
   {
      return (acctNumber + "\t" + name + "\t" + fmt.format(balance));
   }
}

You may use a ListIterator which has support for a remove/add method during the iteration itself.

stackoverflow 

ListIterator<Book> iter = books.listIterator();
while(iter.hasNext()){
    if(iter.next().getIsbn().equals(isbn)){
        iter.add(new Book(...));
    }
}