Code Efficiency help!!! Please!!

[kimss90]

I want my code to perform O(N), where N is the length of the longer string.

Can you help me out?

#include <iostream>
#include <string>
#include <vector>

using std::string;
using std::vector;
using std::cout;
using std::endl;

bool ed1(const std::string& s1, const std::string& s2)
{	
	
	size_t s1length = s1.length(); // length of s1
	size_t s2length = s2.length(); // length of s2

	if (s1length < s2length){ // For the case s2 is longer than s1
		return ed1(s2, s1);
	}

	vector<int> ins(s2length + 1);
	vector<int> del(s2length + 1);
	vector<int> sub(s2length + 1);
	vector<int> p(s2length + 1);
	vector<int> q(s2length + 1);
	vector<int> r;
	vector<int> s(s1length);
	vector<int>::iterator pos;
	
	
	
	p.at(0) = 0;
	/*for (size_t i = 1; i <= s2length; i++)
		p.at(i) = p.at(i - 1) + 1;
		*/
	for (pos = p.begin()+1; pos != p.end(); pos++){
		*pos = *(pos-1) + 1;
	}
	for (size_t i = 1; i <= s1length; i++)
	{
		q.at(0) = p.at(0) + 1;
		for (size_t k = 1; k <= s2length; k++)
		{
			int d_del = p.at(k) + 1;
			int d_ins = q.at(k - 1) + 1;
			int d_sub = p.at(k - 1) + (s1.at(i - 1) == s2.at(k - 1) ? 0 : 1);
			q.at(k) = fmin(fmin(d_del, d_ins), d_sub); // Just for the edit distance.
			del.at(k) = d_del; // To find if any character is deleted.
			ins.at(k) = d_ins; // To find if any character is inserted.
			sub.at(k) = d_sub; // To find if any character is changed.
			//cout <<"k = "<<k<<" d_del = "<<d_del << " d_ins = " <<d_ins << " d_sub = " << d_sub << endl;
		}
		r = p;
		p = q;
		q = r;
	}

	//cout << "p[s2length] = " << p[s2length] << " del[s2length] = " << del[s2length] << " ins[s2length] = " << ins[s2length] << " sub[s2length] = " << sub[s2length] << endl;


	int result = p[s2length]; // result of the edit distance.

	if (result <= 1 || ((del[s2length] == 2 || sub[s2length] == 2) && result == 2)){ // Return true if the edit distance is less than one, or the edit distance is 1.5.
		return true;
	}
	else{
		return false;
	}
	/*
	p.at(0) = 0;
	for (size_t i = 1; i <= s2length; i++)
		p.at(i) = p.at(i - 1) + 1;

	for (size_t i = 1; i <= s1length; i++)
	{
		q.at(0) = p.at(0) + 1;
		for (size_t k = 1; k <= s2length; k++)
		{
			int d_del = p.at(k) + 1;
			int d_ins = q.at(k - 1) + 1;
			int d_sub = p.at(k - 1) + (s1.at(i - 1) == s2.at(k - 1) ? 0 : 1);
			q.at(k) = fmin(fmin(d_del, d_ins), d_sub); // Just for the edit distance.
			del.at(k) = d_del;
			ins.at(k) = d_ins;
			sub.at(k) = d_sub;
			//cout <<"k = "<<k<<" d_del = "<<d_del << " d_ins = " <<d_ins << " d_sub = " << d_sub << endl;
		}
		r = p;
		p = q;
		q = r;
	}

		cout << "p[s2length] = " << p[s2length] << " del[s2length] = " << del[s2length] << " ins[s2length] = " << ins[s2length] << " sub[s2length] = " << sub[s2length] << endl;
	
		
	int result = p[s2length];

	if (result <= 1 || ((del[s2length] == 2 || sub[s2length] ==2)&&result ==2)){
		return true;
	}
	else{
		return false;
	}
	*/
}


int main(){
	if (ed1("exist", "list")){
		cout << "true" << endl;
	}
	else{
		cout << "false" << endl;
	}
}

[Lachlan Easton]

What in the world is this code even meant to do?

[kimss90]

This method is for finding the edit distance of two strings.

[iwhaley]

where is using namespace you have four errors

[giblit]

You don't need using namespace xxxxx; and you should generally avoid it as that defeats the purpose of avoiding naming collisions. He has a better way by only including the specific ones used which is fine.

Though I agree with Lachlan you should tell us what it does. Examples: Remove the unnecessary code (the random commented out stuff). Then provide useful comments and tell us more information on what you are trying to do.

[kimss90]

This is a method to find the edit distance of two strings.
Also, I wanted to make it perform O(N), but I couldn't find out how...

[kimss90]

I changed the code to make you guys easier to understand.

[ne555]

> This method is for finding the edit distance of two strings.
> bool ed1(const std::string& s1, const std::string& s2)
...


¿what part of `Remove the unnecessary code' did you not understand?

[kimss90]

what part of `I couldn't find out how' did you not understand?

[ne555]

you couldn't find a O(N) algorithm, (¿time or space?)
¿what does line 57 have to do with that?
¿what's the difference between 68-103 and 31-67?
¿why do I need to bother with 68-103?

[kimss90]

You don't need to bother with 68-103.
All you need is 1-67.

[kimss90]

line 57 was written to check if the method was working properly

[ne555]

> You don't need to bother with 68-103.
then don't post it.


So, looking at the return type of your function, it should be obvious that you are not really interest in calculating the edit distance, but to know if such distance is 1 or 1.5 (¿?)
Considering the recursive approach, once that you have surpassed the maximum distance you could stop and return infinity.

[kimss90]

if you are not busy, would you show me how to do so?

[ne555]

//if their distance is at most `max_distance'
bool edit_distance( string a, string b, int max_distance ){
   if( max_distance == 0 ) return a==b;
   if( a.empty() ) return b.size() <= max_distance;
   if( b.empty() ) return a.size() <= max_distance;

   return
      ((a.last == b.last)?
         edit_distance(a(0:size-1), b(0:size-1), max_distance) //same, keep going
         : edit_distance(a(0:size-1), b(0:size-1), max_distance-1) //replace
      )
      or edit_distance(a, b(0:size-1), max_distance-1) //insert in `a'
      or edit_distance(a(0:size-1), b, max_distance-1);  //delete in `a'
}

As the max_distance is smaller, you cannot go too far from the diagonal of the matrix, so it'll end being O(n)

[kimss90]

how can I use 'last' or a(0:size-1)?

[kimss90]

Can you make this code runnable? Because, I'm a beginner of c++ yet...