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

BTW: Some code submitted is basically uncommented and hard to read. Those are area of the contest as well...

FYI

Yeah, I was banned for "insulting another member"...and to make matters worse they were posting game code in the classic VB forum and the mods *allowed* it saying it's VB code so it's allowed. Trust me, this is the last time I (1) report incorrectly posted posts, (2) actually reply to a post unless I have good reason to do so

I informed the person politely that talking about a tic-tac-toe game in "classic VB" should have been done in the games programming forum and he apologised the first time then did it again, so I wasn't as polite

So, after this contest, don't expect me around here much :-P

I have a question/comment. According to the totals you provided with the sample file there should be 8070 permutations found, but my app is finding more than that. So I compared the result files and mine is counting something like "Dsafd" as 2 where your results is only count it as 1. So I guess the question would be, should this search be case sensitive?

It is case sensitive. Thanks for the idea, I'll make my code have a feature for case insensitivity ^_^

It is case sensitive, but you do have an idea there...

LOL... Let us add more flexibility to our utterly useless function. :D

It's only useless because you haven't thought of a reason to use it.:p

As soon as I think of a reason I let you know ;)

Ok, Time for the second file. For this test I have included a program that will create the exact same file for each of you to test with. I have included the parameters that you will use in the downloaded zip file. There is a verification checksum to insure that you are testing with the same file everyone else is testing with.

Contents of the ReadMe.txt file:

Supplied is a program that will create a permutation file for you to test with
For this test we will use a file with the following parameters:

Permutation String: asdf
Filesize 10mb
Seed: 9756
Permutations Per Buffer: 1000
Verification Checksum: 46774
Blocks 160


Create Permutation File

Good luck. I have already tested this file on some of the current entries and although most of the submissions pass on the 5mb file they severely bomb :eek2: on the 10mb file.

Atleast that file is big enough to cause that most of the time goes to writing the output file :P


Err... did I just blow off my cover?

Actually, No. The way I have it organized it that all the output it to arrays then after that finishes the output goes to the file. That is not to be included in the timing.

Yeah, my prog failed dismally with the new file but that's because it was all variations of asdf and I hadn't set the upper bound for a variable array high enough (was trying to safeguard against memory errors from using too much :-))

However, I adjusted (and way way way overshot) the new setting and ran the test and on my PC with other programs running and not setting priority to realtime I got just under 2.1s...1.25s with priority set. Add another .6s for saving the file :-)

In the case of my program, it works with such small blocks (16k to 64k, settable) that the array in question (which is used for sorting the output later when saving) doesn't need to be excessively large, so I am confident that future "bugs" like this won't be an issue....and I've tested it with all blocksizes on the new file. Randem, expect the new file to be sent to you once I've done a test with a random 100MB file I make with your prog.

And BTW, nice prog...it's a lot simpler than the prog I sent you, and has more features (I didn't think of adding a validation system although I am pretty sure I was considering something similar at one point :-P)

randem: Humm, are you using the flexible function that can take any permutation string (which I have understood means that every character must be different) up to 30 characters or the fixed one in the button that can only do asdf and that's it?


Edit!
Found 1628577 permutations of "adsf" in 1400 (or 1320 in realtime).

Merri: 1.62m results returned? You sure? Randem's own generator program calculates 153k of them, although interestingly enough *my* program calculates 162.9k of them. If I were to explain why mine gives a higher number than Randems, I would say it's because mine allows for one thing most people probably haven't considered (although Merri definitely is smart enough to have :-P)...mine allows for a 4 byte "overhang" between each block in case the string in question happens between the end of one block and the start of another (although I realised a minor bug with this possibly, it *might* have double-counted a result if it occurred at the very end of a block...which I fixed by modifying the overhead length and it doesn't seem to have actually made an effect at all, so it wasn't an issue)

However, I don't think this was the issue because I did a test without using the "overhang" and it returned 162,889 rather than 162,906 (only a difference of 17) using a 16k block and the full 162,906 using a 64k block (which I am assuming Randem used) and I have also written in double and order checking to my own checker built into my prog and the order is fine and there are *no* doubles so Randem's count is wrong (or calculated differently to how we've been told to calculate it...please elucidate :-P) anyway :-)

Edit: BTW I actually added a "double checker" into the main search code, I was sure I had done but couldn't remember...this code checks to see if the next result matches the previously added result and only writes it if it is different to last one...that's why the bug didn't make any difference, because it was double-checking results before writing them :-)

You assume WRONG!!! You must read all that is written. What the program does is to insert KNOWN permutations into the file. Of course as we all know when you generate random data anything can be in there. I only give the count of what I place into the file as a reference. I do state that there could be more...

That is actually the purpose of YOUR program to find them all, No?

True I guess...I had a feeling that you faked the randomness in the file by forcing in instances, although personally I think it should have been 100% random like the random file maker I sent you :-P

Oh, and I might have thought of a use for this method. It could be useful for dictionary compression methods and working out which strings would return the best compression ratios...maybe only useful for word-or-text-based dictionary compression rather than for anything though. I'll probably adapt it to be usable for this sometime. If my code takes 2 seconds to do 24 checks in a 5MB file, imagine how quickly it could scan a 100k file for a max of 10k words and work out which ones are going to give the best compression ratio :-)

Well, I needed some verification that the sequences would actually appear in the file and know exactly where they were so that I could do a quick check to see if any submissions were worth a further look for if they could not find all the known ones they rest would be moot!

Quote:

---

Originally Posted by Merri

Atleast that file is big enough to cause that most of the time goes to writing the output file :P


Err... did I just blow off my cover?

---

You're not alone, Merri. With this newly generated file, my code runs four times as long while outputting data than it does while only counting the permutations. I am also wondering about your 1628577 permutations, because I concur with smUX that there are 162,906 of them. I'm rather curious about your speed, too... I think mine is faster :)

logophobic,

I don't have a submission from you, eh?

Personally I don't think writing to the HD should be included in the time...my prog gives stats both with and without the HD writing, just in case.

However, with the 10MB file, writing it only takes about 0.6s...doesn't add too much to the time :-P

smUX: 1 533 257 known permutations in the file. And I'm very sure the result is correct.

Writing isn't included in timing as randem stated a few posts above. (I have four different versions in my submitted program.)

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.