How to improve my list's speed

Question

I'm wondering how I could improve my list's element-adding speed or just the whole list implementation.

The adding function first checks if the object is unique. If not, it will just check if the new data is better (the lower the value, the better) than the old one, then swap the values or just skip adding an element.

I have no idea how to make it work faster, but I know that something here is probably done terribly wrong. I need to use that list to add about 3 million elements in less than 4 seconds.

Note: Using std::string in my project is unfortunately forbidden.

#include <iostream>
struct node
{
 long shortestRoute;
 char* name;
 node *next;
 node()
 {
 next = 0;
 }
};
class List {
public:
 node *first;
 List() { first = 0 ;} 
 void add(long shortestRoute, char* name)
 {
 node *node = new node;
 node->name = name;
 node->shortestRoute = shortestRoute;
 if(first == 0)
 first = node;
 else
 {
 node *temp = first;
 while(temp)
 {
 if(!strcmp(temp->name, name) && temp->shortestRoute > shortestRoute)
 {
 temp->shortestRoute = shortestRoute;
 return;
 }
 else if (!strcmp(temp->name, name))
 return;
 else if(temp->next)
 temp = temp->next;
 else
 break;
 }
 temp->next = node;
 node->next = 0;
 }
 } 
 int size()
 {
 node *temp = first;
 int size;
 if(!first)
 size = 0;
 else
 size = 1;
 while(temp->next)
 {
 ++size;
 temp = temp->next;
 }
 return size;
 }
};
struct City
{
 City() { fastConnection = true; }
 int shortestRoute;
 char* name;
 Vector<char*> citiesSoFar; 
 bool fastConnection;
};

• Jamal: If this is C++ and not C, shouldn't you be using std::string instead of char*?
• Cheslav: Using std::string in my project is unfortunately forbidden.
• Jamal: Ah. That's unfortunate. On another note: struct node should be within List as private. The nodes belong to the list and shouldn't be exposed to the public.
• Loki Astari: Are you trying to implement Dijkstra's algorithm with your own classes?
• Loki Astari: It would be much easier to implement with standard containers (and probably more efficient). The priority queue provided by the standard can maintain an ordered container with only O(ln(n)) insert complexity (much better than you would do manually (unless you are very good) and using a list the best you can do is O(n)).

Answer 1

If I understand correctly, you wish to maintain a list of places, and record only the shortest route to each place. This means that each time you need to find any duplicate entry, and choose which to keep.

For this task, an unordered list is pretty much the worst choice you could use. Your algorithm is O(n²) (that is, O(n) for adding each of n elements), and while that isn't important for 10 destinations, it's pretty critical for 3 million!

Given that ordering is not critical here, a hash table is really the correct implementation to use. This will get you O(1) insert and lookup, and the added programming complexity and memory use is appropriate for that number of elements. If that's not possible somehow, then second best would be some kind of self-balancing tree.

Finally, it makes no sense to count the length of a large list by iterating the elements. Just increment a counter every time you add an element. A reduction from O(n) to O(1). (In theory, if you add and destroy a lot of elements very frequently, but only query the size once in a blue moon, then my statement is untrue, but I doubt that's the case here.)

As far as your existing implementation goes, it's a bad plan to create the new node and then not use it. Maybe in your implementation a garbage collector will sort it out, but otherwise it'll be a huge memory leak, not to mention wasted effort.

Answer 2

One small suggestion in your size() function.:

int size()
{
 node *temp = first;
 // Initialize size so you don't have to worry about first == 0
 int size = 0;
 // Makes no sense to execute while if (first == 0)
 // so move it inside the if condition
 if(first)
 {
 size = 1;
 while(temp->next)
 {
 ++size;
 temp = temp->next;
 }
 }
 return size;
}

---

Also, you may choose to have different names for the size() function and the local variable size, just to avoid confusion.

• Jamal: I'd also make size and size()'s types std::size_t.

Answer 3

• Are you suppose to add elements to an empty list? If you are adding to an empty list, then you can add them in ascending order or descending order.
• The problem you have is that you will be adding unknown element to the list i.e it could be < or == or> than this element. In this case, even if you order the list, you just cannot add a new element to the end of list or at the head. You will have to traverse the list to see if this element is greater the ith element.
• So adding would take O(n) as the worst case. Because you are adding the element to the end of the list. If ordering matters.

• The larger the list, the more time it will take to add an element.

• I suggest adding elements to the list in an order. Example, add 1 first, then add 2, then add 3, then add 4 etc. If you can add them in that order, you will only be adding elements to the end of the list which takes O(1).

Answer 4

1. Maintain an inner hash table to look up name duplicates. O(1)

   a. char *name => long shortestRoute

2. Don't instantiate (new *node) until absolutely necessary.

Should be all that is needed.