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:
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?
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 > 1 then total - highestSubtotal else total
I don't think I can optimise that anymore unless anybody can think of something else.