9 Replies - 1160 Views - Last Post: 07 July 2018 - 02:36 PM

#1 tony_tony   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 07-July 18

Lnked Lists: how to minimize time/space complexity in a concrete case

Posted 07 July 2018 - 06:00 AM

I'll try to describe briefly the project I'm working on and then I'll pose my question.

Project:

Suppose you are running an online shop that connects buyers to sellers. So there is a list of ITEMS and a list of BUYERS. When the buyer is satisfied with a product he puts it in the basket and the item is removed from the available items shown to other users.

What can happen: the buyer can quit without going through the checkout so the items he selected (if any) should be available again for other users or the sell can be called off from the seller so the item is not available no more even if it was in someone's basket. Plus I could be asked to print a report of the current situation at a certain time describing for each buyer its basket.

Question: I have a list of actions that take place like "BUYER1 logs-in", "ITEM11 is for sale" or "BUYER13 puts ITEM1 in the basket" (we neglect the checkout) and I was wondering which data structure is more appropriate to handle this specific case, in particular which solution is the best in terms of time and space complexity.

I came up with two possible solutions: I could store items data in a linked list of structures (with fields like Id, price etc.) named "available items" and store buyers data in a linked list of structures that contains a field named let's say "basket" which is a linked list of items and when a buyers puts a product in the basket the item is removed from the "available items" and appended to the "basket". The issue could be that when a sell is called off I don't know who put the item in the basket so I should go through the list of buyers and for each of them through their basket to delete the product. Or I could add a field to the items struct named let's say "buyerID" where I could change the value from 0 (the item is available) to the ID of the buyer that put the item in the basket but when I have to print a report for each buyer I have to go through the list of items to know what he is buying.

Don't know if the solutions I came up with are efficient both from the time and space complexity. Could you suggest me a better solution? Thanks a lot in advance to everybody! Any help is appreciated.

Is This A Good Question/Topic? 0
  • +

Replies To: Lnked Lists: how to minimize time/space complexity in a concrete case

#2 jimblumberg   User is offline

  • member icon

Reputation: 5537
  • View blog
  • Posts: 17,143
  • Joined: 25-December 09

Re: Lnked Lists: how to minimize time/space complexity in a concrete case

Posted 07 July 2018 - 06:52 AM

Have you considered a couple of counters in your inventory list? One counter to indicate how many of each item you have in inventory, and one counter to indicate how many pending orders you have for that item? If the the two counters are equal then that item is not available. This would involve two "lists"1 one a "list" of your inventory and a second a "list" of your customers. The customer "list" would hold the items in their "basket", this "list" would only need the quantity and the id number of the inventory item.

Note 1. The actual data structure used for these "lists" could be almost any data structure, not necessarily a list data structure. And IMO a list data structure may not be the best data structure for this method.

Jim
Was This Post Helpful? 1
  • +
  • -

#3 tony_tony   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 07-July 18

Re: Lnked Lists: how to minimize time/space complexity in a concrete case

Posted 07 July 2018 - 08:44 AM

Hi Jim, thanks for your answer! The fact is that it's a shop where a seller can sell a single item (more like eBay than Amazon), so you don't need counters... I was considering linked lists because I don't know in advance how many items and/or buyers there will be!

This post has been edited by Skydiver: 07 July 2018 - 01:31 PM
Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg   User is offline

  • member icon

Reputation: 5537
  • View blog
  • Posts: 17,143
  • Joined: 25-December 09

Re: Lnked Lists: how to minimize time/space complexity in a concrete case

Posted 07 July 2018 - 09:03 AM

Quote

I was considering linked lists because I don't know in advance how many items and/or buyers there will be!

So what benefits do you think you will have using a linked list over a vector or any other container?

Quote

So there is a list of ITEMS and a list of BUYERS. When the buyer is satisfied with a product he puts it in the basket and the item is removed from the available items shown to other users.

So if a seller can only sell one item at a time then perhaps a simple "sold" flag is all you need.

Jim
Was This Post Helpful? 0
  • +
  • -

#5 tony_tony   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 07-July 18

Re: Lnked Lists: how to minimize time/space complexity in a concrete case

Posted 07 July 2018 - 09:24 AM

The advantage of lists would be that adding a new element is really easy, since you don't have to dynamically reallocate vectors or other structures. For the sold flag the thing is: it's really useful but my problem was about how to avoid to go through lists every time a buyer refuses to purchase an item in the basket or the sale is called off by the seller. Thanks for your answer!

This post has been edited by Skydiver: 07 July 2018 - 01:32 PM
Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

Was This Post Helpful? 0
  • +
  • -

#6 Salem_c   User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 2185
  • View blog
  • Posts: 4,248
  • Joined: 30-May 10

Re: Lnked Lists: how to minimize time/space complexity in a concrete case

Posted 07 July 2018 - 10:26 AM

I would suggest you start with a physical model - say a pack of cards.

Create say 10 post-it notes with names for sellers, and randomly distribute the cards amongst the sellers.

Create say 20 post-it notes with names for buyers.

Now model all the behaviours such as
- searching for a specific item, say 3 of clubs.
- searching for a kind of item, say all the 7's.
- moving an item from a seller to a buyer shopping basket.
- etc
- etc

> Don't know if the solutions I came up with are efficient both from the time and space complexity.
This is premature optimisation disease.
Efficiency comes in many flavours (one of which is how long it takes to design and debug).

A multiplicity of use-cases means you're likely to be making compromise choices between simple data structures, or building complicated blended data structures which attempt to optimise your common use-cases.

If you focus too much on making one use-case super-efficient, then you're likely to neglect other use-cases which are perhaps more frequent, examine more data, and take longer to execute.

If you create suitable abstractions for 'Seller', 'Buyer', 'Basket', 'Shelf' etc, then should you find your first implementation choice isn't so good, you minimise the amount of disturbance to the rest of the code. If you're successful in hiding your data structures behind an abstraction, then you can prototype now to get something working, then measure, analyse and improve later (knowing you have a working reference to guide you).

FWIW, by the time you scale this to millions of items, the searching time that allows your buyers to quickly locate what interests them will be your key metric.
Was This Post Helpful? 1
  • +
  • -

#7 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6333
  • View blog
  • Posts: 21,743
  • Joined: 05-May 12

Re: Lnked Lists: how to minimize time/space complexity in a concrete case

Posted 07 July 2018 - 01:34 PM

tony_tony: There is no need to quote the post above yours. Just use the big Reply button or the Fast Reply area. If there is a specific thing you want to address (like jimblumberg has done above), then just quote that section.
Was This Post Helpful? 0
  • +
  • -

#8 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6333
  • View blog
  • Posts: 21,743
  • Joined: 05-May 12

Re: Lnked Lists: how to minimize time/space complexity in a concrete case

Posted 07 July 2018 - 01:41 PM

So far I'm not seeing anything C or C++ specific in this question so I'll be moving this into the Software Development section. I'm choosing Software Development over the more specific Computer Science which the title of this topic suggests because of Salem_c's very cogent comment in post #6 which identifies that not only is there a pure computer science problem of least time/space complexity aspect, but also the software development time/architecture complexity involved.
Was This Post Helpful? 0
  • +
  • -

#9 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 6333
  • View blog
  • Posts: 21,743
  • Joined: 05-May 12

Re: Lnked Lists: how to minimize time/space complexity in a concrete case

Posted 07 July 2018 - 01:49 PM

Tangent to this discussion: Since we are talking about concrete cases, you may want to watch this video:
Bjarne Stroustrup: Why you should avoid Linked Lists
since it feels like you already have a preconceived idea that the linked list will give you good time/space complexity.

Yes, if you do the big O analysis, the linked list looks very attractive, but if you do real world timing, you may be disappointed.
Was This Post Helpful? 0
  • +
  • -

#10 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7205
  • View blog
  • Posts: 15,018
  • Joined: 16-October 07

Re: Lnked Lists: how to minimize time/space complexity in a concrete case

Posted 07 July 2018 - 02:36 PM

View Posttony_tony, on 07 July 2018 - 11:24 AM, said:

The advantage of lists would be

This is what we call an implementation detail.

You have functions that will login a buyer. Store and retrieve the current cart for the buyer. Retrieve available items. Add an item to a cart.

The data store for that API is irrelevant at this point. It might be entirely in memory, or in random access files, or an RDBMS, or whatever. The important part of the problem is figuring out the kind of methods you need to support for your application.

I'd start with your data model. Most programs do some level of CRUD with various data objects. Define those objects, then the operations. Then, and only them, worry about how you're going to store and retrieve those objects.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1