How do I improve my performance with this singly linked list struct within my program?
- by Jesus
Hey guys, I have a program that does operations of sets of strings. We have to implement functions such as addition and subtraction of two sets of strings. We are suppose to get it down to the point where performance if of O(N+M), where N,M are sets of strings. Right now, I believe my performance is at O(N*M), since I for each element of N, I go through every element of M. I'm particularly focused on getting the subtraction to the proper performance, as if I can get that down to proper performance, I believe I can carry that knowledge over to the rest of things I have to implement.
The '-' operator is suppose to work like this, for example.
Declare set1 to be an empty set.
Declare set2 to be a set with { a b c } elements
Declare set3 to be a set with ( b c d } elements
set1 = set2 - set3
And now set1 is suppose to equal { a }. So basically, just remove any element from set3, that is also in set2.
For the addition implementation (overloaded '+' operator), I also do the sorting of the strings (since we have to).
All the functions work right now btw.
So I was wondering if anyone could
a) Confirm that currently I'm doing O(N*M) performance
b) Give me some ideas/implementations on how to improve the performance to O(N+M)
Note: I cannot add any member variables or functions to the class strSet or to the node structure.
The implementation of the main program isn't very important, but I will post the code for my class definition and the implementation of the member functions:
strSet2.h (Implementation of my class and struct)
// Class to implement sets of strings
// Implements operators for union, intersection, subtraction,
// etc. for sets of strings
// V1.1 15 Feb 2011 Added guard (#ifndef), deleted using namespace RCH
#ifndef _STRSET_
#define _STRSET_
#include <iostream>
#include <vector>
#include <string>
// Deleted: using namespace std; 15 Feb 2011 RCH
struct node {
std::string s1;
node * next;
};
class strSet {
private:
node * first;
public:
strSet (); // Create empty set
strSet (std::string s); // Create singleton set
strSet (const strSet ©); // Copy constructor
~strSet (); // Destructor
int SIZE() const;
bool isMember (std::string s) const;
strSet operator + (const strSet& rtSide); // Union
strSet operator - (const strSet& rtSide); // Set subtraction
strSet& operator = (const strSet& rtSide); // Assignment
}; // End of strSet class
#endif // _STRSET_
strSet2.cpp (implementation of member functions)
#include <iostream>
#include <vector>
#include <string>
#include "strset2.h"
using namespace std;
strSet::strSet() {
first = NULL;
}
strSet::strSet(string s) {
node *temp;
temp = new node;
temp->s1 = s;
temp->next = NULL;
first = temp;
}
strSet::strSet(const strSet& copy) {
if(copy.first == NULL) {
first = NULL;
}
else {
node *n = copy.first;
node *prev = NULL;
while (n) {
node *newNode = new node;
newNode->s1 = n->s1;
newNode->next = NULL;
if (prev) {
prev->next = newNode;
}
else {
first = newNode;
}
prev = newNode;
n = n->next;
}
}
}
strSet::~strSet() {
if(first != NULL) {
while(first->next != NULL) {
node *nextNode = first->next;
first->next = nextNode->next;
delete nextNode;
}
}
}
int strSet::SIZE() const {
int size = 0;
node *temp = first;
while(temp!=NULL) {
size++;
temp=temp->next;
}
return size;
}
bool strSet::isMember(string s) const {
node *temp = first;
while(temp != NULL) {
if(temp->s1 == s) {
return true;
}
temp = temp->next;
}
return false;
}
strSet strSet::operator + (const strSet& rtSide) {
strSet newSet;
newSet = *this;
node *temp = rtSide.first;
while(temp != NULL) {
string newEle = temp->s1;
if(!isMember(newEle)) {
if(newSet.first==NULL) {
node *newNode;
newNode = new node;
newNode->s1 = newEle;
newNode->next = NULL;
newSet.first = newNode;
}
else if(newSet.SIZE() == 1) {
if(newEle < newSet.first->s1) {
node *tempNext = newSet.first;
node *newNode;
newNode = new node;
newNode->s1 = newEle;
newNode->next = tempNext;
newSet.first = newNode;
}
else {
node *newNode;
newNode = new node;
newNode->s1 = newEle;
newNode->next = NULL;
newSet.first->next = newNode;
}
}
else {
node *prev = NULL;
node *curr = newSet.first;
while(curr != NULL) {
if(newEle < curr->s1) {
if(prev == NULL) {
node *newNode;
newNode = new node;
newNode->s1 = newEle;
newNode->next = curr;
newSet.first = newNode;
break;
}
else {
node *newNode;
newNode = new node;
newNode->s1 = newEle;
newNode->next = curr;
prev->next = newNode;
break;
}
}
if(curr->next == NULL) {
node *newNode;
newNode = new node;
newNode->s1 = newEle;
newNode->next = NULL;
curr->next = newNode;
break;
}
prev = curr;
curr = curr->next;
}
}
}
temp = temp->next;
}
return newSet;
}
strSet strSet::operator - (const strSet& rtSide) {
strSet newSet;
newSet = *this;
node *temp = rtSide.first;
while(temp != NULL) {
string element = temp->s1;
node *prev = NULL;
node *curr = newSet.first;
while(curr != NULL) {
if( element < curr->s1 ) break;
if( curr->s1 == element ) {
if( prev == NULL) {
node *duplicate = curr;
newSet.first = newSet.first->next;
delete duplicate;
break;
}
else {
node *duplicate = curr;
prev->next = curr->next;
delete duplicate;
break;
}
}
prev = curr;
curr = curr->next;
}
temp = temp->next;
}
return newSet;
}
strSet& strSet::operator = (const strSet& rtSide) {
if(this != &rtSide) {
if(first != NULL) {
while(first->next != NULL) {
node *nextNode = first->next;
first->next = nextNode->next;
delete nextNode;
}
}
if(rtSide.first == NULL) {
first = NULL;
}
else {
node *n = rtSide.first;
node *prev = NULL;
while (n) {
node *newNode = new node;
newNode->s1 = n->s1;
newNode->next = NULL;
if (prev) {
prev->next = newNode;
}
else {
first = newNode;
}
prev = newNode;
n = n->next;
}
}
}
return *this;
}
