# 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:

1. 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.
2. 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.
3. 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

1. 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.
2. 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:

1. Make one pass through the file. For each line, create a map with the following structure
Map[CustomerId, Map[ItemId, subtotal]]

1. 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.

• I suppose that when inserting into M-2 I could use an efficient data structure that will maintain some order. This will eliminate the need to loop through M-2 in step 4. What would be the best data structure to do this in? What I would need to do is just pop the highest value element and discard the rest of the values. – C.S May 4 at 20:06

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.

• I cannot see why "making one pass through the file" should load all the file upfront. You can read the file line by line or datum by datum. – Apass.Jack May 5 at 16:40
• The end effect is the same. If I load up all the data in the file upfront it will blow up because it exhausts the heap. If you pass line by line, because of the need to hold each customer's data until all the file has processed, it blows the memory. Any calculation to calculate the total cost cannot be done until all the data for that customer has been read and that can't be done until the file has been completely read. So you end up holding all the data in memory anyway – C.S May 5 at 17:29
• @Apass.Jack would love to see a clever algorithm for this but I don't think it can be done without compromising on increasing heap memory size. For example, when I increased the heap size to 2GB I was able to process 10million lines with the original algorithm. But when I bumped it to 400million lines and up'd the heap to 10GB, it blew up with OOM. – C.S May 5 at 17:32
• The best solution is not having to keep playing with heap size, especially since the file could grow over time. The ideal solution will be memory resource savy and this answer I posted does that but it involves sorting the file first with an external sort algorithm like UNIX's sort command. Then the memory consumption is minimal. – C.S May 5 at 17:34
• How many customerIds are there? If it is less than a few million or even hundreds of millions, then reading the file line by line should be fine. – Apass.Jack May 5 at 18:14