Given an array of pointers to ordinary C NUL-terminated (and typically very long) strings, how can we best find the smallest and the largest strings?
views:
215answers:
6+1 simplest is the easiest :)
Necrolis
2010-09-10 08:06:57
i've posted code for that idea ;]
Tomasz Kowalczyk
2010-09-10 08:07:45
+3
A:
Maybe for looping through them will help? - Ok, you don't want C++ idea, let's see:
Ok, again:
char **strings; // initialized
int stringsNumber = 500; // number of string in first dimension
int longestLen = 0;
int shortestLen = MAX_INT; // or other REALLY BIG number ;]
char *longest = NULL;
char *shortest = NULL;
int current = 0;
for(int i =0; i < stringsNumber; i++)
{
current = strlen(strings[i]);
if(current > longestLen) { longestLen = current; longest = strings[i]; }
if(current < shortestLen) { shortestLen = current; shortest = strings[i]; }
}
Tomasz Kowalczyk
2010-09-10 07:45:09
The question is about an array of pointers, not a vector of strings.
Guillaume Lebourgeois
2010-09-10 07:51:59
where do you find difference in idea? it could be array of strings in php, way would be the same.
Tomasz Kowalczyk
2010-09-10 07:53:01
Your code finds largest and smallest length of strings, not strings. And, don't use stringsNumber if you have std::vector.
W55tKQbuRu28Q4xv
2010-09-10 07:53:36
again, i'm showing the IDEA, not the target implementation. if you can't upvote, please at least not downvote. i've edited my comment to reflect your requests.
Tomasz Kowalczyk
2010-09-10 07:57:21
Also, initialize longest and shortest - if all strings is empty longest and shortest will be uninitialized.
W55tKQbuRu28Q4xv
2010-09-10 08:01:50
`int shortestLen` shouldn't be initialized to MAX_INT or you won't find anything shorter than that. Actually the lengths should be `size_t`, so you should use SSIZE_MAX.
nategoose
2010-09-10 17:59:48
max_int edited, for the size_t i would argue, but you are right.
Tomasz Kowalczyk
2010-09-10 18:10:44
+1
A:
You can have another array of char pointers of size n, with its ith pointer pointing to the start of the ith string.
Increment each pointer till it reaches the end.
The first one to reach the end was the pointer to the shortest string.
The last one to reach the end was the pointer to the longest string.
codaddict
2010-09-10 07:47:30
This is clever, but it still looks at every character of every string, so it doesn't beat the naïve approach of calling `strlen` once per string.
Matthew Flaschen
2010-09-10 07:55:53
A:
If it's given to you and you don't manage it - iteration over array and strlen.
If you manage it - consider using std::string or pair<char *, int>(string,length) to optimize your code as well as replacing array of pointers with some ordered container.
XAder
2010-09-10 08:14:28
+1. Detail of language choice aside, this answer makes a valid point. Often the best optimization is to find another way to do it entirely. Here, the suggestion is to use a slightly more complicated string representation that retains length as well as the characters themselves. That makes the cost O(n) where n is the size of the array, instead of O(n*m) where m is the average length of the string.
RBerteig
2010-09-10 09:35:43
A:
I repeat my question.
What do you mean array of pointer to strings?
Do you mean what you say?
typedef char *string; /* excuse the reserved identifier */
typedef string *pointer_to_string;
pointer_to_string ARRAY_OF_POINTER_TO_STRING[3];
string *ss = malloc(3 * sizeof *ss);
ss[0] = "one"; ss[1] = "two"; ss[2] = "three";
ARRAY_OF_POINTER_TO_STRING[0] = ss;
/* first attempt at demonstrating `array of pointer to string` was invalid *
ARRAY_OF_POINTER_TO_STRING[1] = {"um", "dois", "tres"};
ARRAY_OF_POINTER_TO_STRING[2] = {"un", "deux", "trois"};
*/
free(ss);
Or simply array of char *?
typedef char *string; /* excuse the reserved identifier */
string ARRAY_OF_CHAR_STAR[3];
ARRAY_OF_CHAR_STAR[0] = "one";
ARRAY_OF_CHAR_STAR[1] = "two";
ARRAY_OF_CHAR_STAR[2] = "three";
pmg
2010-09-10 09:48:24
+1
A:
If the strings are really really long, you should consider saving them with a length attribute, which is computed already during entering the strings.
nob
2010-09-10 09:54:04