VB6: Best way to find all permutations of a given string in a file - Contest

smUX,

You have to read...

Writing should not be include in the time. You should be placing your data in arrays and when done the timing stops. Then you sort and write the data to the file.

I will make this as simple as I can for code submission that will conform to the testing standards. I will deliver a skeleton of the program that I am using to test results. All you need to do is to fit your code into it AS A CALLED MODULE ONLY with the associated code used in the module for the testing purposes which will already be coded for you.

I'm with Logophobic and Smux, 162906 permutations.

randem: I haven't submitted anything yet. Expect to by end of week.

Merri: If your are finding 1,533,257 permutations, then you obviously aren't searching the same file. I reconfirmed the 162906 count by counting each of the 24 permutations using repeated InStr calls on the entire file as one long string.

smUX: 0.6s isn't much, but simply finding and counting the permutations might take considerably less time. The method I just mentioned above takes about 0.6s on my pc.

Here is the code I am using to test with. Please view and reconstruct your code to fit so that I won't have to reconstruct it with the many re-submissions that I am getting.

Merri, A tip for you...post the output so you can prove these permutations and can be proven right or wrong...2 of us have the same results *exactly* (me and logo) and they disagree with yours. The way my code works, there's *no* way my results could miss out any possibilities and it checks all 24 possible permutations (run Randem's program if you need to know what the permutations are)

First comfirm that both you are running on the same file by comparing the checksums...

Quote:

---

Originally Posted by Logophobic

Merri: If your are finding 1,533,257 permutations, then you obviously aren't searching the same file.

---

I'm not finding that many, that's how many randem's program reports as known permutations in it's output file.

As it seems everyone missed it, smUX was talking about generating a 100MB file in the post above where I originally mentioned how many I found (1 628 577). Same settings than with 10MB file, just bigger.

Quote:

---

Originally Posted by Merri

As it seems everyone missed it, smUX was talking about generating a 100MB file in the post above where I originally mentioned how many I found (1 628 577). Same settings than with 10MB file, just bigger.

---

Ah, that explains it a little...assuming 100MB file with the exact same settings you should have approximately 10x as many because of the way Randem's written the injection code which injects the permutations into the random file :-)

That would be correct. That is why I gave the checksum so that you could verify that you were using the same file as everyone else... It's all there in writing...

Quote:

---

Originally Posted by randem

That would be correct. That is why I gave the checksum so that you could verify that you were using the same file as everyone else... It's all there in writing...

---

I'm not going to generate the file again only to find out it's checksum; it's too slow to be bothered :) Using a standard checksum like CRC32 might make things easier as there are optimized programs that can do the calculation very fast.

That is ok. But that is why the info was given in the first place so that when a person generated the file all they had to do was to check the checksum on the screen with what was to be expected to avoid those sorts of issues. Simple enough... no?

Randem, am I right in saying the file generator makes files in the same block sizes as we're working in (64k) or something? Because I think that for a fair test of 100% reliable code that it should actually have been done using a different block size. In the real world, my bit of code that checks for the possibility of an instance that spans 2 blocks would have caught at least a couple that other people's code missed :-)

Now, who said this was the final file... The procedure is in the original post...

No, I know that...partly why I am mentioning it to you now so other people have to hurriedly rush and add in protection like that themselves :-P

[spoiler]
My code doesn't make any separate checks between two blocks. It processes linearly what it gets. It also doesn't know that there are 24 different permutations and it doesn't calculate/figure out what they are.
[/spoiler]

Merri,

Did you get the email and attachment I sent you?

Yeah, I got it. Just don't have the time to mess with it atm.

Just remember Merri...100% or nothing, black or white, there is no grey :-)

It is entirely possible that the cross-block thing does not happen...just as possible that it does happen though :-P

Trust me smUX he doesn't need to worry about such things...

Merri,

When you get a chance just add the module to the skeleton and uncomment the code with your name in it in the form. It will be simple.

smUX,

You have a module also...

I'd change how the functions must be contructed. Outputting a Long array would be much better than adding in code that expects something certain to be given. Current output added to the function code totally kills all the performance (LogArray and JoinArray).

So do you mind if I rewrite the testing phase to something faster when I have the time?

No, Have a go at it.

Using the skeleton code, my own method is worse than the instr by a long shot, although it takes half the time of the brute force replace method.

For me, the results with the 10MB file are:

Brute force replace: 2812ms
Brute force instr/rev: 968/984ms
My method: 1359ms

This is in real-time with the skeleton program compiled for fast code and *my* code using 16k blocks rather than 64k blocks (as I've mentioned before, I seem to get better times with that specific block size...don't know why, and once my method's public I am sure someone can explain why :-))

I don't see any reason for working any further on this. Looks like if I can't beat the basic instr methods, what I *thought* was good results isn't going to win me anything :-)

I'll do a little clean-up and commenting so people at least know what the code does and I'll send it to Randem. I might even adapt it a little so it can be used with an array of words to generate offset values of the words requested, which might be of use to me in future...I don't see any point in trying to win though :-)

Also, I quickly chucked together a bit of code that literally just runs through the file and doesn't make notes about the offsets or anything...instr took 700ms for the whole 10MB file...I'd be surprised if anyone *can* do faster than instr, although I thought instr would be slower :-)

I'm using my own benchmarker (skeleton) program as randem's required extra functions cause a major slowdown with bigger files (100 MB files run practically forever). That's where I ended with limited time... instead of fixing randem's program I wrote my own. Although now I have some time as I'm having my first weekend in a while when I don't have any work to do, but I have other things to do as well.

I made my own InStr and Replace functions to provide comparison. Here is what I get when I run it with a 10 MB file:

Code:

---

FindUsingReplace_Merri finished in 1751 ms, found 162906 permutations
FindUsingInStr_Merri finished in 551 ms, found 162906 permutations
FindUsingBitCompare_Merri finished in 144 ms, found 162906 permutations
FindUsingReplace_Merri finished in 1775 ms, found 162906 permutations
FindUsingInStr_Merri finished in 563 ms, found 162906 permutations
FindUsingBitCompare_Merri finished in 157 ms, found 162906 permutations
Current file is 10485760 bytes

---

Running on AMD Turion64 MT-32 @ 1800 MHz laptop.

Project without my own competition code attached.

If you're getting results that are 1/4 of the time of the instr, I've got no chance of winning :-)

Posting results actually invalidates the whole contest...

Hey, as randem said from the start, speed isn't the only factor. Who knows how bad the other factors of my code are... ^_^ I might have it uncommented, it might be very unoriginal and plain and unclear and complex and...

If this was a serious competition with huge prizes, I'd agree that we should be hush-hush...we're mostly doing this for fun and practice though, aren't we? We're learning from each other about different ways to achieve the same results and which ones work better and why (well, hopefully why...I'm sure Merri will have something to say about other people's choices of method, he knows all about how effective different functions are :-))

I guess it is now...

You got $10,000 for first prize winner lined up? :-P

No, but why would you want to decide what other would like to do or compete for? I did say that I would see about getting a prize for the winner in the original post...

Yeah, but I don't think we were actually taking part for the prize...well, I wasn't, I wouldn't even dare with people like Merri taking part, I've no chance :-)

I guess I'm mostly talking about myself, but is anyone doing this for fame and fortune?

Possibly, But now with results posted Who is going to submit there code if they can't beat the speed. Even though that's not the only category that is what everyones sees first...

Fame and fortune no but if we were doing it for the prior reason you mentions I would have just left this as part of the original thread... This thread had OTHER Meanings...

Quote:

---

Originally Posted by randem

Possibly, But now with results posted Who is going to submit there code if they can't beat the speed. Even though that's not the only category that is what everyone sees first...

---

If people weren't going to post results because they can't win, I think you'll find the only person sending you code would be Merri...don't assume that we're not going to bother because we're going to fail :-P

Winning isn't everything, but not taking part is *nothing*...even taking the time to have a go shows that you are interested, and we'll still have a go.

As I said before, winning *isn't* my intention and I am sure most other people don't even think they're going to win...it's fun to program and see if they can find new ways of doing stuff...look at what I've learned in this project:

• Smaller block sizes in my method results in faster results
• Merging sorted lists into one big sorted list can be a very simple and fast process...even with long lists
• No matter how fast my code, there's faster code out there always...and tinkering with how the code works can give unexpected results :-)

It winning wasn't the goal why did you mention

Quote:

---

Originally Posted by smUX

If you're getting results that are 1/4 of the time of the instr, I've got no chance of winning :-)

---

Unfortunately this will be the attitude of anyone else who was going to submit... Now if they did not know exactly what they had to beat they would submit...

Note the :-)...it means I am joking around...smilies (or emoticons) are a long-standing mainstay of the internet, surely you understand how they work?

Personally I don't think people will just give up on their attempts because they can't win...I haven't, because I've already done work on it and I've had fun.

IMO people who were doing this to try to win won't even have started unless they had a good chance of doing so, so I don't see it as an issue :-P

Then tell me why others have taken part in contests before even when they've known the speed of my code beforehand?

And I don't care about the prize actually... so if I'd win, it could go to the next one.

But that is what invalidates the whole thing. I am not only looking for speed but that is what everyone is focused on... We will see how it goes from here.