Algorithm To Process Purchases Efficiently and Apply Constraint I am working on a problem where I have to completely scan a large unordered log file which contains purchasing details of customers. The file structure is as follows:

customerId  itemId  cost


The customer could have purchased the same item more than once in a day and at different times so there will be multiple entries for a customer and item combination. At the end of the processing, the program should print the customerId and the total cost of all their purchases, but with a discount applied so that the cost of the most expensive item is removed.

My algorithm is as follows:


Create a map, call it M-1, with the customerId as key and a running total cost as the value i.e. customerid -> running_total_cost.
Create another map, call it M-2, with the key as (customerId and itemId) and for the value the running subtotal. That is, it keeps a tab on how much of this item this customer has bought.
For each line in the file, upsert into M-1 the customerId and add the cost of this item to the running total. Also upsert an entry in M-2 containing the running total of this customer and item purchased. So M-1 has this structure:


customerId  RunningTotal


And M-2 has this structure

customerId ItemId RunningTotal



After the file has been completely processed in step 3, for each entry in M-1, get the customerId and look-up the customer in M-2. In M-2, run a loop so that it finds the most expensive purchase this customer made. This can be done by creating a temporary variable and looping through the purchases the customer made and comparing the current value of this variable with the next value. Replace the value of the variable with the new highest total At the end, the highest value will remain.
Print table


My question is whether this can be processed any faster than this?

UPDATE

I believe I have an optimal solution for this now. The algorithm is as follows:


Make one pass through the file. For each line, create a map with the following structure


Map[CustomerId, Map[ItemId, subtotal]]



After processing the file completely and making the above map, then do the following loop


for each customerId
  count = 0
  total = 0
  highestSubtotal = 0
  for each itemId
     total += subtotal
     highestSubtotal = max(highestSubtotal, subtotal)
     count += 1
print CustomerId, if count &gt; 1 then total - highestSubtotal else total


I don't think I can optimise that anymore unless anybody can think of something else.
The algorithm I posted above doesn't work. It's the same as trying to load all the file upfront which blows up as the heap memory is exhausted.

Another solution would be to sort the file before processing it. The UNIX sort command is able to sort files much bigger than the RAM available on the machine. It does this using external sort I believe.

So my new solution is to sort the file first on the customerId. This ways a one pass can be done on the file and the data for each customer calculated on the fly. As each customer is encountered in order, before computing the next customer's data the memory consumed for the previous customer is freed.