So ive got 3 assignments. Ive completed the first one which is to write a program that will take in a text file and spit out a reverse of it. example: "i like dogs" would have an output "sgod ekil i"
my 2nd assignment is to find the last occurrence of a letter in a text file. Since i have a program that reverses a whole file, could i simply implement that and search for the first occurrence? Instead of finding all occurrences and storing the buffer location of each and finding the largest?

I also already have a program that finds the first occurrence, so im really thinking it would just be some copy/paste and rewrite a few lines.

you could, but it won't perform as well. you dont need to store all occurrences. just the last one. as soon as you find a new one, you replace the last one. when you reach the end, your last one is the answer.

why wouldn't it perform as well? (assuming he saves the result of the reversal in a text file and isn't reversing again)

Because it is much faster to use fseek() than to load an entire file and reverse it just to find the last character.

my high school physics teacher taught us a little trick that i've always remembered. we were learning newtonian mechanics (forces, velocity, etc) and when a block is at an angle, students were constantly confused whether they should use sine or cosine. when the angle was 40 degrees, sine and cosine were similar enough that you can't tell which to use based on the number you get from the formula. so his advice: use your model, but stretch the data to the extreme. sin 40 and cos 40 are close enough that can't figure out which is correct by looking at it, but if you stretched that angle to 0.01 degrees and 89.99 degrees, then sin and cos are very different, and it becomes clear which one to use.

in this context, instead of a text file that's 3 words long, consider a text file that's 20 gigs. OP's method is to first reverse the string, then find the first occurrence. how will he reverse the string? either 1) he'll keep the whole thing in memory (good luck), or 2) he'll keep part of it in memory and write to another file when he's low in memory. then repeat until the whole thing is in the new file. now he's doing a find on the new file.

option 1) clearly eats up tremendous memory, and 2) writes a huge file to disk. neither are preferred.

consider the alternative. read the file in chunks, keeping a pointer to the last occurrence. then release your memory and read more. repeat until you reach the end. this won't eat up as much memory, and it won't write a huge file to disk.

does that make sense?


maybe you were confused with your assumption. nobody said it's the same file. input is the character and a file, output is the last occurrence.
if his assignment was literally to write down the last occurrence (eg: write down "position 15"), then sure you can just find the first occurrence in the reversed file. but his assignment is to write the program which will do it for any given file.

This post was edited by carteblanche on Oct 1 2014 08:13pm

Right, I understand the time and space complexities. i guess I was under the assumption that it was the same file

If it was a lazy reverse operation, it would be totally fine. Since it's greedy (you always reverse the whole file, instead of what your program actually needs), it's not. Just do the backwards search, it's simple enough.

No matter what you will have to look at each character in the string once.

I would loop through every character and then just update the index when you find the letter occur. Then you will have the last occurrence when you are done.

That is O(n) asymptotic time, which is linear.



Didn't see it was C, but however you can use the above to get inspiration.

If you are to perform other tasks with the same file in the same problem, you will have to study if preprocessing the string would benefit.

This post was edited by Utunity on Oct 26 2014 09:52am

Sorry for double posting but I figured out my answer was quite wrong.

I have managed to do it in almost constant time best case and O(n) worst case



With the above code I found a "`" which was at the end of a 500mb file in constant time. However if it was the last occurrence in the beginning of the file it would have taken much longer.

Good job on answering a question that is a month old...