Processing buy and sell orders

Question

My code is too slow, it does the desired, but not in \$O(\log n)\$ or faster.

Explanation of the auction system:

For simplicity we will assume that all orders are for a single unit of the traded item. The double action system operates as follows. When a new buy order of $x arrives it is simply stored for future use if none of the stored sell orders has an asking price lower than or equal to $x. Otherwise, the new buying bid is matched with the sell order with lowest asking price (earliest such order if there are ties). The two matched orders are removed from the system, and the buyer receives the item in exchange for paying a clearing price equal to the matched sell order asking price, i.e., the lowest asking price available at the time the new buy order was received.

It's supposed to be a simple program that takes orders per line and sells or buys. The program must read from the standard input a list of buy and sell orders in the format given in the samples below, with one order per line. The program must print to the standard output the number of units exchanged and the total clearing price, using the format given in the examples below, and printing a new line at the end. Note that after processing the input there can be orders left uncleared.

Sample Input

order 1 sell at 30 
order 2 buy at 20

Output for Sample Input

units exchanged 0 total clearing price 0

public static void main(String args[]) { 
  // Create an array list for order to read data from the file 
  ArrayList<String> orders = new ArrayList<String>();

  // Create sell and buys array list to get the list of 
  // buyers and sellers 
  ArrayList<String> sells = new ArrayList<String>(); 
  ArrayList<String> buys = new ArrayList<String>();

  // declare the required variables 
  int price = 0; 
  int exchange = 0;

  // since we are using files put the execution code in try..catch 
  // block 
  try { 
      // create a file object by passing it to scanner class 
      // to read the file data 
      Scanner input = new Scanner(System.in);

      // read the lines from the text file 
      while (input.hasNextLine()) { 
           orders.add(input.nextLine()); 
      } 

      // separate the orders 
      for (int i = 0; i < orders.size(); i++) { 
           System.out.println("" + orders.get(i));

           if (orders.get(i).contains("sell")) { 
                sells.add(orders.get(i)); 
           }

           if (orders.get(i).contains("buy")) { 
                buys.add(orders.get(i)); 
           }

      }

      // now get the price values from each line from the 
      // respective orders and compare the values 
      int buy = 0; 
      int sell = 0;

      for (int i = 0; i < buys.size(); i++) { 
           buy = getPrice(buys.get(i)); 
           for (int j = 0; j < sells.size(); j++) { 
                sell = getPrice(sells.get(j));

                // if the values are same, then compute the clear price 
                // values 
                // and increment the exchange value 
                if (buy == sell) { 
                     price += 2 * buy; 
                     exchange += 2; 
                } 
           } 
      }

      // print the final statement. 
      System.out.println("\nUnits of exchanged " + exchange + " total clearing price "+ price);
  } catch (Exception e) { 
      e.printStackTrace(); 
  } 
}

// getPrice method that retrieves the integer values from 
// each line 
 public static int getPrice(String s) { 
  // use the scanner object to access the line values 
  Scanner in = new Scanner(s).useDelimiter("[^0-9]+");

  int i = 0; 
  int j = 0;

  // get the integer values 
  while (in.hasNext()) { 
      i = in.nextInt(); 
      j = in.nextInt(); 
  }

  // return the required price value 
  return j; 
}

Answer 1

You should always convert the input data in something sane ASAP. Dealing with string can get inefficient and unreadable pretty soon. Something like

enum Type {SELL, BUY}

@RequiredArgsConstructor
@Getter
@ToString
class Order {
    private final Type type;
    private final int id;
    private final int price;
}

sounds good. The above annotations are from Lombok, but you can write the boilerplate manually if you really want to.

By using a class instead of extracting the information from the string again and again, you'll surely gain a factor of 10+. That's good, but the more important part is the quadratic complexity.

---

Otherwise, the new buying bid is matched with the sell order with lowest asking price (earliest such order if there are ties).

This sounds like a Comparator: Order by price and then by id. I'd probably go for Guava's ComparisonChain, but it's simple enough:

class OrderComparator implements Comparator<Order> {
    public int compare(Order o1, Order o2) {
        int result = Integer.compare(o1.price, o2.price);
        if (result != 0) {
            return result;
        }
        return Integer.compare(o1.id, o2.id);
}

In theory, we could create an array of all sells and use Arrays.sort with our OrderComparator on it. However, when a new sell comes in, we'd need to insert it in the appropriate position or sort the array again. Too bad.

But we need no sorted array. All we need is

• to get the least element
• remove it if it's good enough
• add a new element

Fortunately, there's a PriorityQueue, which provides these operations efficiently (O(log n)). So we're nearly done.

---

A piece of code could look like

private void processNextBuy(Order buy) {
    assert buy.type == Type.BUY;
    // just look at it, but don't remove yet
    Order sell = sellQueue.peek();
    if (sell!=null && sell.price <= buy.price) {
        sellQueue.poll(); // paired, so remove it
        price += 2 * buy;
        exchange += 2;
    } else {
        buyQueue.add(buy); // unpaired, so process later
    }
}

From the description, I'm unsure if a new sell should be processed the same way. The boring parts around are left as an exercise for the reader. ;)

Answer 2

Well, let's see, code style.

ArrayList<String> orders = new ArrayList<String>();

Always try to use the lowest interface, for ArrayList that would be List:

List<String> orders = new ArrayList<String>();

That allows to easier swap it for a another List implementation later if necessary. This is especially important if you have a function returning the ArrayList, the function should always be declared with List so that you can easily change the returned List implementation later, without breaking everyones code.

---

int price = 0; 
int exchange = 0;

Declare variables when you need them, that is to limit their scope.

---

// create a file object by passing it to scanner class 
// to read the file data 
Scanner input = new Scanner(System.in);

This is a prime example for confusing commentary, which does say something different then the code does.

---

for (int i = 0; i < orders.size(); i++) {

There is the for-each loop which makes this a lot easier to read:

for (String order : orders) {

---

System.out.println("" + orders.get(i));

What is that supposed to accomplish? Please stop immediately using the "concatenate it with an empty string to cast it to a string" idiom. It's stupid, and it possibly hides mistakes. Like in this case, the order you get is a string, there's no need to concatenate it with a string to make it a string. Also System.out.println does have multiple overloads that accept pretty much all types.

---

int buy = 0; 
int sell = 0;

for (int i = 0; i < buys.size(); i++) { 
    buy = getPrice(buys.get(i)); 
    for (int j = 0; j < sells.size(); j++) { 
        sell = getPrice(sells.get(j));

Again, declare variables where they are needed, and limit their scope to the smallest possible.

for (String buy : buys) { 
    int buy = getPrice(buy); 
    for (String sell : sells) { 
        int sell = getPrice(sell);

---

price += 2 * buy; 
exchange += 2;

Just so that you are aware of it, this is not shorthand for

price = price + 2 * buy;

It is short hand for:

price = (int) (price 2 * buy)

In this case it doesn't really matter, but you should be aware that here is a cast.

---

} catch (Exception e) {

Only try to catch only the exception that are actually thrown. Makes the code easier to read and does "swallow" exceptions which you might not wanted to handle.

---

// getPrice method that retrieves the integer values from // each line public static int getPrice(String s) {

There is JavaDoc for documentating your code.

---

public static int getPrice(String s) {
    // use the scanner object to access the line values 
    Scanner in = new Scanner(s).useDelimiter("[^0-9]+");

    int i = 0; 
    int j = 0;

    // get the integer values 
    while (in.hasNext()) { 
        i = in.nextInt(); 
        j = in.nextInt(); 
    }

    // return the required price value 
    return j;
}

This function is seems extremely complicated for a rather simple task. Try if String.split(String) and Integer.parseInt(String) might be better suited for this task:

public static int getPrice(String line) {
    String[] splittedLine = line.split("[^0-9]");
    String lastItem = splittedLine[splittedLine.length - 1];
    return Integer.parseInt(lastItem);
}

---

Also I'd like to note that your code is neatly formatted and also has comments, thumbs up for that.

---

What could you do to make it faster? Depending on the amount of data, it might be interesting to sort the list of buys and sells, and then perform a binary search on it instead of looping through all elements all the time.