k-Nearest Neighbors Search

ultrAslan · #1 11-Mar-2009, 13:26

Your program must observe the following requirements:

1. Maintain the following constant:
MAX SIZE = 1000
You must not ask the user to input this value. Recall that to declare a constant integer,
you can use: const int MAX SIZE = 1000;

2. User Input | Your program must ask for the following:
An integer space size where 0 < space size MAX SIZE, which denotes the
\actual" data set size.
An integer k where 0 < k space space
An integer key of arbitrary range, for which your program will use as the search
query (to be described later).
If the value entered for k and space size are not within their respective range, then your
program must output an error and repeat this process until the condition is satised.

3. The Search Space|Create an array of integers of size MAX SIZE, but only populate
the rst space size elements of this array using the pseudo-random number generator,
rand(). All numbers that are generated must be normalized to the range of [0; 5000].
Repetitions are permitted. This list must then be sorted in nondecreasing order (see
below).

4. The Result Set | Create an array of integers of size MAX SIZE, populating no elements.
This array will eventually contain the k nearest neighbors once your algorithm
is nished running.

5. You can write any number of functions that might be of use to you. However, the
following two are mandatory:
2
void p r i n tLi s t ( cons t i n t l i s t [ ] , cons t i n t l i s t s i z e )
| Returns nothing and outputs the rst list size elements from the list[] array.
void query ( cons t i n t key , cons t i n t l i s t [ ] , cons t i n t l i s t s i z e ,
i n t r e s u l t [ ] , cons t i n t r e s u l t s i z e )
| This function returns nothing, but places the result size integers from list[]
that are closest to key into the result[] array. This function may not perform any
of the following:
(a) Create arrays of arbitrary size. You may only create arrays of constant size
like 4, 13, 100, etc. Only constant sized arrays can be created (remember
that MAX SIZE is a constant)
(b) Print out anything or ask for user input
(c) Alter any of the parameters except for the results[] array

6. After each search, use the printList() function on the array holding your result set to
print out the k-NN results. Then ask the user if they would like to continue searching
for another key, and repeat the search on the SAME space if armative. That is, do
not regenerate the random list after each query.

7. Once the user wants to stop running searches, use the printList() function to print
out the search space.

I don't know how to start could anyone help me with that code?
Thanks...

davekw7x · #2 11-Mar-2009, 14:08

Quote:

Originally Posted by ultrAslan

...
I don't know how to start...

1. Read the complete assignment. Don't worry about how you are going to code it. For goodness sake don't actually start writing code until you understand exactly what the program is required to do.

2. Visualize how you are going to test the program. You can even use pencil and paper (gasp) or a text editor to transcribe a "practice session." That is, think about what you, the user, will give the program to work with and exactly what the program will give you in return.

3. Don't skip step 1 or step 2. This is very important.

4. Be sure that step 3 is complete. This is even more important.

5. You can just implement the requirements of the assignment one step at a time in a top-down fashion. Get inputs and make sure they are correct. Then write whatever functionality that you need for the rest of program (the "Good Stuff"). Do it one step at a time. Compile after every few additional input lines. Don't write tens or hundreds of lines of code before trying to compile.

Assuming you have done steps 1, 2, 3, 4, you might do something like:

CPP / C++ / C Code:

#include <iostream>

using namespace std;

int main()
{
    const int MAX_SIZE = 1000;
    int space_size;
    int k;
    int key;
    cout << "Enter an integer that is > 0  and is < " << MAX_SIZE << ": ";
    cin >> space_size;
    //
    // You will be required  to put some code that lets the user try again if
    // there was an invalid entry, but for now, just bail out.
    // 
    if (!cin || space_size < 0 || space_size >= MAX_SIZE) {
        cout << "Invalid entry." << endl;
        exit(EXIT_FAILURE);
    }
    //
    // I always make sure that I know what the program is going to be working with.
    // Sometimes steps like the following don't need to be in the final program,
    // but it's nice to know what has happened so far.
    cout << "You entered " << space_size << endl;

    //
    // Now prompt for and obtain the value for k
    //
    cout << "Enter an integer that is > 0  and is < " << space_size << ": ";
    cin >> k;
    if (!cin || k < 0 || k >= space_size) {
        cout << "Invalid entry." << endl;
        exit(EXIT_FAILURE);
    }
    cout << "You entered " << k << endl;
    //
    // Now prompt for and obtain the value for the key
    //
    cout << "Enter an integer to be used as a key: ";
    cin >> key;
    //
    // etc.


    return 0;
}

Now might be a good time to implement the part that requires the program to give the user a chance to try another input if an invalid entry is made. Make sure each step that you have implemented here works exactly as it should. Then go on to the "Good Stuff."

Regards,

Dave

ultrAslan · #3 11-Mar-2009, 14:15

CPP / C++ / C Code:

//the main function 
int main() 
{ 
	//variables and constants 
	int space_size, key, k;
	
	//initialize search space of an array of 1000 integers 
		
		//get the space_size in range of [0,1000]
	do { 
		cout << "Enter the size of your search size (1 - 1000): ";
		cin >> space_size;
		
		if (!(space_size>0 && space_size<1000))
		{
			cout <<"Error!"
			<< endl;
		}
	} while(!(space_size>0 && space_size<1000));
	
		
		//get number of nearest neighbors
	do {
		cout <<"Number of nearest neighbors to include: ";
		cin >> k;
	} while (!(k>0 && k<1000));
	
		//get the search key
	cout <<"Please enter a search key: ";
	cin >> key;
	
		//the search space
	vector<int> search_space(MAX_SIZE);
	
	
	
	//end of program 
	return 0; 
}

I have something like that. As you see I created the vector and I need to fill it with random numbers so I added something like that; however, I always get 0000s when I compile

CPP / C++ / C Code:

for (int i=0; i<space_size; i++) {
		search_space.push_back(rand_range(0, 5000));
			cout << search_space[i];
	}

Is there anything wrong with it?

By the way I defined the random number as

CPP / C++ / C Code:

/**
 * Random number
 *
 * @param const int start	Starting point
 * @param const int end		End point
 *
 */

int rand_range(const int start, const int end)
{
	return (rand() % (end - start + 1)) + start;
}

davekw7x · #4 11-Mar-2009, 15:35

Quote:

Originally Posted by ultrAslan

As you see I created the vector

You create a vector with size = MAX_SIZE. The vector contains that many elements. All of their values are zeros.

Then you push more elements into the vector. The first MAX_SIZE elements are still equal to zero.

So you can do the following:

1. Declare the vector with nothing in it and then use push_back to fill it up.

CPP / C++ / C Code:

    const int MAX_SIZE = 5000;
    int space_size = 10; // You get this from the user, but for testing I just use a value
    vector<int> x;// An "empty" vector
    cout << "Before the push_back loop: x.size() = " << x.size() << endl;
    for (int i = 0; i < space_size; i++) {
        x.push_back(rand_range(1, 20));
    }
    cout << "After  the push_back loop: x.size() = " << x.size() << endl;
    // now print out the space_size elements

or

Declare a vector with as many elements that you need. Then use an iterator or assignment to store values.

CPP / C++ / C Code:

    vector<int> x(5000); // A vector filled with zeros
    int space_size = 10;
    cout << "Before the assignment loop: x.size() = " << x.size() << endl;
    for (int i = 0; i < space_size; i++) {
        x[i] = rand_range(1, 20);
    }
    cout << "After  the push_back loop: x.size() = " << x.size() << endl;
    // now print out the space_size elements

N.B. I don't see where your assignment even mentions vectors. I mean, experienced C++ programmers might use vectors instead of arrays, but how important is it for you to follow the directions exactly? If I were an instructor (I'm not), I would insist on exact implementation of my detailed program specification. Period. If some on-line guru suggests that "vectors are better than arrays," I couldn't argue with that, but I would still insist that people follow instructions. (From my experience I would assert that this is at least as likely to happen outside the classroom as in, so is an important part of the learning process. But maybe that's just me.)

I mean, if you declare an array (as the assignment stated), then use the loop like the one in my second example to store the values, wouldn't it do what you need?

Regards,

Dave

ultrAslan · #5 11-Mar-2009, 15:42

If I did it with vectors, I can get extra point

and the code you wrote...

CPP / C++ / C Code:

cout << "After the push_back loop: x.size() = " << x.size() << endl;

the value will be always same because the size is 1000; however, i need to see the values inside the vector? How can I do that?

CPP / C++ / C Code:

		//the search space
	vector<int> search_space(MAX_SIZE);
	
	for (int i=0; i < space_size; i++) {
		search_space[i] = rand_range(0, 5000);
		cout <<search_space[i]<< "\n";
	}

now that works... What should I do next?

davekw7x · #6 11-Mar-2009, 15:51

Quote:

Originally Posted by ultrAslan

If I did it with vectors, I can get extra point

and the code you wrote...

CPP / C++ / C Code:

cout << "After the push_back loop: x.size() = " << x.size() << endl;

the value will be always same because the size is 1000; however, i need to see the values inside the vector? How can I do that?

Yes it will, with my code, but not with yours. That was kind of my point.

You can look at values of the elements by using an iterator or by indexed notation. Here's an example based on your (broken) code.

CPP / C++ / C Code:

int main()
{
    const int MAX_SIZE = 10;
    vector<int> x(MAX_SIZE); // A vector filled with zeros
    int space_size = 5;

    cout << "Before the push_back loop: x.size() = " << x.size() << endl;

    for (size_t i = 0; i < x.size(); i++) {
        cout << "x[" << i << "] = " << x[i] << endl;
    }
    for (int i = 0; i < space_size; i++) {
        x.push_back(rand_range(1, 20));
    }
    cout << "After  the push_back loop: x.size() = " << x.size() << endl;

    for (size_t i = 0; i < x.size(); i++) {
        cout << "x[" << i << "] = " << x[i] << endl;
    }
    
    return 0;
}

Output:

Code:

Before the push_back loop: x.size() = 10
x[0] = 0
x[1] = 0
x[2] = 0
x[3] = 0
x[4] = 0
x[5] = 0
x[6] = 0
x[7] = 0
x[8] = 0
x[9] = 0
After  the push_back loop: x.size() = 15
x[0] = 0
x[1] = 0
x[2] = 0
x[3] = 0
x[4] = 0
x[5] = 0
x[6] = 0
x[7] = 0
x[8] = 0
x[9] = 0
x[10] = 4
x[11] = 7
x[12] = 18
x[13] = 16
x[14] = 14

Regards,

Dave

ultrAslan · #7 11-Mar-2009, 16:08

Now, I am really confused :S

I need to push random number in the vector, so shouldn't I need to use

CPP / C++ / C Code:

vector<int> search_space(MAX_SIZE);
	

for (int i=0; i < space_size; i++) {
		search_space.push_back(rand_range(0, 5000));
	}

Then I wan to see what is in it?? How can I do that?

davekw7x · #8 11-Mar-2009, 16:26

Quote:

Originally Posted by ultrAslan

Now, I am really confused

:

CPP / C++ / C Code:

vector<int> search_space(MAX_SIZE);

If MAX_SIZE is equal to 5000, the vector has 5000 elements. Index values go from zero up to and including 4999. All element values are initialized to zero.

CPP / C++ / C Code:

    search_space.push_back(rand_range(what, whatever));

Now the vector has 5001 elements. Elements with index values 0 through 4999 have value zero. The element with index number 5000 (the 5001th element) has whatever value you pushed.

Please run the example in my most recent post. New stuff was pushed onto the vector. The initial stuff was unchanged by the push.

If you want to create a vector of a particular size and then store stuff without creating new elements, then just store values using indexed notation of the second example of my post number 4. No pushing, please.

Bottom line: push_back() creates a new place for the value and stores it there. That is, the size of the vector is increased by one, and previous values are unchanged.

Look in your text or look for an on-line reference. For example, http://www.cplusplus.com/reference/stl/vector/

Regards,

Dave

"Over and out."

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Unable to search for the nearest value	Yvonne	C Programming Language	4	07-Oct-2005 10:40
Linear Search	eccoflame	C Programming Language	3	19-Apr-2005 09:36
GIDForums Search w/ Google	BobbyDouglas	GIDForums™	1	09-Feb-2004 17:05
Search Engine Positioning 101 and 201 "How To" Tips...	000	Search Engine Optimization Forum	0	29-May-2003 11:34

k-Nearest Neighbors Search

Re: k-Nearest Neighbors Search

Re: k-Nearest Neighbors Search

Re: k-Nearest Neighbors Search

Re: k-Nearest Neighbors Search

Re: k-Nearest Neighbors Search

Re: k-Nearest Neighbors Search

Re: k-Nearest Neighbors Search