Best way to make Telephone Directory program
-
Here is the question.. There are 10,000 entries in text file which has following format
"name:telephone number:address"
We need to make a program that will read that file and look up the name, telephone number or address from any one of them in O(log n) complexity. So obviously, I'm gonna store each entry in array and sort them and do binary search to look up a particular variable, as it needed to O(logn) in complexity. Now, my question is should I copy the array to another three arrays, each of them sorted according to three parameters(telephone numbers, names, address) and then perform look up search. Is there any better way of doing it without taking so much space because basically to make program in O(logn) complexity, you are taking 3 times the space as compared to original linear search. Suggest the best way of doing it. Any help will be appreciated. Shivam
-
Here is the question.. There are 10,000 entries in text file which has following format
"name:telephone number:address"
We need to make a program that will read that file and look up the name, telephone number or address from any one of them in O(log n) complexity. So obviously, I'm gonna store each entry in array and sort them and do binary search to look up a particular variable, as it needed to O(logn) in complexity. Now, my question is should I copy the array to another three arrays, each of them sorted according to three parameters(telephone numbers, names, address) and then perform look up search. Is there any better way of doing it without taking so much space because basically to make program in O(logn) complexity, you are taking 3 times the space as compared to original linear search. Suggest the best way of doing it. Any help will be appreciated. Shivam
as name, number, and address are strings, they wouldn't need to get stored multiple times; all you need to duplicate is pointers/references to them. And with say 250 chars per telephone, you would need less than 10 MB of memory anyway. :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
as name, number, and address are strings, they wouldn't need to get stored multiple times; all you need to duplicate is pointers/references to them. And with say 250 chars per telephone, you would need less than 10 MB of memory anyway. :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
Thank you for the response but this not what I'm trying to ask. So far, I've made a class called telephone with three member variables of String type, those are names, address and telephone number. Then I made array of telephone class of size 10,000. Now this array has randomly distributed telephone entries but I need arrange sorted order according to each three variable, i.e. telephone, name and address so that I could perform binary search. Let say user enter telephone number then my program will perform binary search on list sorted according to telephone numbers. If user enter name then my program will perform search on the list which is started according to name and similarly it will do same procedure for address. So basically you need three list, but can you think of any other method of doing this? Thank you Shivam
-
Thank you for the response but this not what I'm trying to ask. So far, I've made a class called telephone with three member variables of String type, those are names, address and telephone number. Then I made array of telephone class of size 10,000. Now this array has randomly distributed telephone entries but I need arrange sorted order according to each three variable, i.e. telephone, name and address so that I could perform binary search. Let say user enter telephone number then my program will perform binary search on list sorted according to telephone numbers. If user enter name then my program will perform search on the list which is started according to name and similarly it will do same procedure for address. So basically you need three list, but can you think of any other method of doing this? Thank you Shivam
what I said is this, using your terminology: you make 10,000 Telephone instances, and store each of them in three different arrays, then sort each of these arrays. That is still only 10,0000 Telephones, not 30,000. as for sorting stuff, there are smarter ways to represent data. Either come up with something yourself, or make use of existing ones, see e.g. the .NET collections. Finally, as this is homework, you're supposed to do the work yourself. :|
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
Here is the question.. There are 10,000 entries in text file which has following format
"name:telephone number:address"
We need to make a program that will read that file and look up the name, telephone number or address from any one of them in O(log n) complexity. So obviously, I'm gonna store each entry in array and sort them and do binary search to look up a particular variable, as it needed to O(logn) in complexity. Now, my question is should I copy the array to another three arrays, each of them sorted according to three parameters(telephone numbers, names, address) and then perform look up search. Is there any better way of doing it without taking so much space because basically to make program in O(logn) complexity, you are taking 3 times the space as compared to original linear search. Suggest the best way of doing it. Any help will be appreciated. Shivam
How about three of Dictionary<string,Telephone> ? Or a spell check tree? Or this thing[^], whatever it is.
-
what I said is this, using your terminology: you make 10,000 Telephone instances, and store each of them in three different arrays, then sort each of these arrays. That is still only 10,0000 Telephones, not 30,000. as for sorting stuff, there are smarter ways to represent data. Either come up with something yourself, or make use of existing ones, see e.g. the .NET collections. Finally, as this is homework, you're supposed to do the work yourself. :|
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
Oh, I got it. Thank you very much. :) Shivam
-
How about three of Dictionary<string,Telephone> ? Or a spell check tree? Or this thing[^], whatever it is.
Ok, its a homework of data structure course, so u can't expect us to use pre-written classes of .NET. We have to write complete program on our own :((. But the suggestions you gave are really good, I'll definitely look into them. Thank you Shivam
-
Oh, I got it. Thank you very much. :) Shivam
You're welcome. :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.