Thank you for that report, Domenico. Those generation speeds are so fast, it raises another question. Based on my previous, brute force, inefficient, initial shot on Base 10, I figured I’d write the results out to a file, then just access the file with Reads when I needed the numbers - about once every two months.
For comparison, can you read 9! records faster than 68 seconds?
In the olden days, those times were more impacting. FurtureBase/ZBasic gave comparative times for their compiler’s operations. For example, it was less (time) costly, to use Z = Y * Y than to use the exponent operator, Z = Y^2. But that’s when computer speeds were measured in MHz, not GHz.
You pay the slow-speed operation price once to generate a file you wanted to use, then, in the future, you’d just read the file. Nowadays, especially with a non-SSD drive, it might be slower to do the reads. What is your experience?
I love to spend my time on that… Progress bar: I think that Xojo made updates to the UI while running a thread or loop unnecessary complex.
Hi Everyone! I took a few minutes to look at the code and make some changes you might like 
**Changes:
- threaded permutations
- paginated data-viewing in ListBox
- optimized code and added compiler pragmas to further increase speed
- added ProgressBar
can be further optimized in a few places.
**Demo runs 4-5x faster when actually compiled vs running in Xojo IDE.
Code can be found at:
I find times interesting. On my 3.6 GHz, 8GB, i3, Mac Mini, for 9! the time was 13 seconds.
On my older 3 GHz, 16GB, AMD Phenom 16, the same run took 40 seconds.
I understand the overhead of the list and progress bar - but each machine has the same overhead. I wonder how the same test would fair on an M1?
This is fun. Thank you for all your contributions to my questions.
1 Like
Thanks Matthew, interesting!
Thanks Matthew, great work. Thanks for sharing the code. Your program deserves to be added to the examples distributed with Xojo, it offers several cues for those who want to learn the language, plus it has a fun aspect of being able to be used to generate anagrams.
In order to complete the Paul’s app, can you please add a button to save the results obtained in a TXT (or CSV) file?
I’m attaching a code of a method used in a previous work that saves the contents of a ListBox in a CSV file. I think it might come in handy for someone.
Thank you very much for your time and greetings to everyone.
Public Sub esportaCSV(pList As DesktopListBox)
// (API 2)
// Esporta i dati presenti nella ListBox in un file CSV
// Export the data present in the DesktopListBox in a csv file
//
if pList.RowCount = 0 Then
MessageBox("No data to export.")
Return
end if
var aHeadings(-1) as String = pList.HeaderAt(-1).Split(chr(9))
var strDelim as String = ";"
var intRow, intColumn as Integer = 0
'var strKey, strValue as String = ""
var f as FolderItem
var t as TextOutputStream
// --- Definisce il FileType ---
// --- Define FileType ---
Var csvType As New FileType
csvType.Name = "csv"
csvType.Extensions = "csv"
f = FolderItem.ShowSaveFileDialog(csvType, "exportFile")
if f = Nil then
Return
end if
try
t = TextOutputStream.Create(f)
// --- Esporta i dati di intestazione delle colonne ---
// --- Exporting column headers ---
If pList.HasHeader = True Then
for intColumn = 0 to aHeadings.LastRowIndex
t.Write(ConvertEncoding(chr(34)+aHeadings(intColumn)+chr(34),Encodings.UTF8))
if intColumn < pList.ColumnCount Then t.Write(ConvertEncoding(strDelim, Encodings.UTF8))
next
End If
// --- Inizia la scrittura del file ---
// --- Start writing export file ---
t.Write(ConvertEncoding(Chr(13),Encodings.UTF8))
// --- Cicla sulle righe ---
// --- Loop rows ---
for intRow = 0 to pList.RowCount-1
// --- Cicla sulle colonne ---
// --- Loop columns ---
for intColumn = 0 to pList.ColumnCount-1
t.Write(ConvertEncoding(chr(34),Encodings.UTF8))
t.Write(ConvertEncoding(pList.CellTextAt(intRow,intColumn),Encodings.UTF8))
t.Write(ConvertEncoding(chr(34),Encodings.UTF8))
if intColumn < pList.ColumnCount-1 then t.Write(ConvertEncoding(strDelim,Encodings.UTF8))
next
t.Write(ConvertEncoding(Chr(13),Encodings.UTF8))
next
t.Close
catch err As IOException
MessageBox("Error: " + err.Message)
end try
End Sub
If someone were interested in Anagrams, I could see BOTH the list (multipage - nice touch) and a CSV file would be desirable.
However, for generating the numbers of a particular number Base, the list would be unnecessary overhead. It’s useful at the start - to verify the generator is working by testing a smaller run. But for the final, on a large set (1 million+), just the timer, maybe progress bar, and output file would be of interest. So an added option choice of the just file, without the list box update, would be nice.
The world has gotten so complicated. A line (a record) can be delimited by a carriage return, or a linefeed, or a linefeed + carriage return. I’ve lost track of what compilers are looking for now. In decades past, one was looking for an EOF (end of file) status. Now, in SimpleFortran anyway, the EOF is signaled by triggering and i/o error flag. Which in my mind is not an “error” at all; it’s just the EOF.
My brute force method wrote the number (0123456789) or string (0123456789AB) out without delimiters between the characters. I figured it was already going to be a large file and I didn’t need the comma separators because I could separate the elements in the subsequent Read format.
If you were looking for words (single word) in an Anagram of characters, by matching the result with a dictionary lookup (actual dictionary file, not a programming construct) you also would not want the individual elements separated because you’d be picking up the full word.
See updated example at same download link - I cut the CSV save method down to 7 lines of code
Normally, for multicolumn listboxes, you can also load listbox.contents as a string…and save directly to file. The contents are fully CSV format with no modification needed
Matthew, Thank you for the modification. Note that when working with a number base - rather than anagrams from a text string - the number of records can get quite large (about 480 million for 12!).
When I ran your modified routine, I didn’t see anything to bypass the list feature so I just hit the Save button - thinking that after I designated the output file it would take the input string and run with it. The message came up that the file was successfully saved (too fast for 0-B) and it had a size of 0 bytes.
So it appears that it successfully saved the list result, and as the list was empty, it saved an empty file.
I thought of going into your code and just bypassing adding to the listbox, but you may be building the CSV file from the listbox contents. In that case, I’d comment out the listbox add and put “Write” statements there instead.
A nice feature would be two checkboxes, One for Build List, another for Create File, so the user could choose one or the other or both. If it were me, I’d ascertain the potential number for records by the size of the input string and issue a warning if the number of lines generated would be outrageous for even a multi-page list box - should that option be selected.
Although I’m working with unique digits, I can imagine someone dealing with characters would want to allow duplicate characters so a string like HERTE could produce THERE. So there is no need to check for duplicates in the input.
Please know I am not asking you to do “work”. If this is a fun project for you, I am happy and appreciate what you have given us. And if it were me, I’d like a suggestion to change the Save Button to maybe “SaveTo” so the user designates the destination, then issue the “Success” message after there is actual output (at least flag it so it doesn’t come up if Start hasn’t been pushed).
Thank you Matthew, for the new program posted. There is always something to learn from your code. There are some great people in the Xojo community.
Hi Paoul, analyzing the code kindly posted by Matthew, we observe that:
- The generation of the various elements occurs in a separate thread, so it proceeds in parallel with other functions of the program;
- the generated elements are saved in the string array Permutations();
- the only purpose of the listbox is to view the elements of the Permutations() array by scrolling through the btnBack and btnForward buttons;
- the presence of the listbox does not influence in anyway the elaboration speed since it is not updated with the generated elements;
- the btnSave button exports on the file the result of the processing, i.e. the elements of the Permutations() array - it does not take into account the listbox;
- it is obvious that in order to export data on the file, the elaboration must be finished; therefore the correct way to proceed is:
(a) insert the string to be processed
(b) start the processing and wait for it to finish
(c) visualize the results obtained through the listbox or save them on the file
- in order to avoid clicking accidentally on the save button, during the elaboration, you can deactivate it before starting the elaboration and activate it when the elaboration is finished, this is obtained by adding the two lines of code as shown in the figure
- if you prefer a txt file instead of a csv file just modify the first line of the code in the pressed event of the btnSave replacing “csv” with “txt” - … ShowSaveFileDialog(“txt”, “permutations.txt”)
It is obvious that, depending on the characteristics of your PC (amount of RAM, CPU speed, etc…) you will have to wait some time for the generation of 12! permutations and then you will still have to wait some more time to save the file that could reach a considerable size.
Best regards and good work
1 Like
Domenico, thank you for the snippet. If I understand, your points 2, 3, 4, the list box is not filled during the generation, it only displays (starting with page 1) the elements of the resulting array - and only fills a page at a time as you move forward or back.
So there is no worry about “filling up” a Listbox WHILE the permutations are generated.
But because all the permutations are generated first, and held in an array, rather than written out as they are generated, one needs enough RAM to hold the results prior to writing them out.
And because there is nothing to Save, until the Start button is pushed, it’s a nice gesture to disable Save until after the Start is activated.
Do I understand that correctly?
1 Like
Perfect Paul, that’s right
The list only loads the first 200 permutations, unless you venture to another page while the demo is running. Otherwise it’s pure array based and the listbox plays no role in speed nor load time. The save button will only work once permutations have been run. If you run much above 10!, You’ll need to split the results (process array in chunks vs as a whole or line by line) as the demo currently is taking an array, converting it to a string delimited by EndOfLines which creates the CSV single column format, and is saving it all-at-once to file. Depending on system resources, this save method may fail for extremely large batches of data if not processed in chunks, since memory may not be able to hold the “whole string.” The listbox, since it only ever holds 200 records, uses ‘pages’ (almost like pointers) to point to parts of the array, loading only the ‘buffered’ portion of the array.
A good modification to the save method would be to loop thru in chunks of say…1000 indexes of the array at a time, writing each to file. For large saves, this is also preferable to add a “saved progress” indicator so a user knows the app isn’t hanging and actually processing data… With even a “time remaining” indicator for really long processes. Would Be glad to add a saved progress modification… Would only take maybe 5-10 minutes I love sharing code and reviewing other code… There’s a million ways to code, and everyone creates uniquely. I’ve been developing for nearly 30 years and always learning something new and love sharing what I’ve learned along the way.
Matthew, English is so much fun. Take the word “work” as in, “The save button will only work once permutations have been run.” As the Save Button is enabled, it “works” in that it brings up a dialog allowing you to name a file and designate its location. It even gives you and “Success” message. But it doesn’t “work” until the permutations have been run in the sense that there is nothing to save. It creates an empty file.
Though I can see the usefulness of the Runner for someone ferreting out anagrams, in my situation, I was looking for a more elegant way to generate the numbers in Base10, Base11, and Base12 that had no repeating digits. I started it on its Base12 journey and it’s been running FOR A WHILE now (over an hour)
In fact, a little more than halfway through, this “Non Fatal Error” message popped up.
It’s might be the problem you were referring to:
Sub mostraElemento()
#Pragma NilObjectChecking False
#Pragma StackOverflowChecking False
#Pragma DisableBoundsChecking True
Var k As integer
var element As String = “”
// Crea l’elemento della permutazione
for k = 0 to p.Count-1
element=element+p(k)
next
// Visualizza la permutazione nella ListBox
// (è possibile salvarla in un database oppure in un file di testo)
'total=total+1
'Listbox1.AddRow(total.ToString, element)
Permutations.Add(element)
End Sub
Hi Paul,
sorry for my English, I used an automatic translator.
I tried to run the program with 10 elements, in a few seconds it finished execution and generated the txt file.
I tried with 11 elements, it took a few minutes and worked correctly.The file with 11! elements (almost 40 million) is almost 0.5 GB in size.
Trying with 12 elements after a while crashed.
Considering that 12The file with 11! elements (almost 40 million) is almost 0.5 GB in size.
Trying with 12 elements after a while crashed.
Considering that 12! = 12*11! we should expect a file size of almost 6 GB!!! The array can’t hold that amount of data, we are talking about almost 480 million elements.
Taking Matthew’s suggestion, I set a maximum number of elements for the array (MAX_ELEMENTS=10 million) and every time I add an element to the array I check if this limit has been reached, in this case I save the content in a file_001, I empty the array and continue the processing until I reach another 10 million elements, I save them in a file_002 and so on.
At the end I save the last remaining elements in the last file_00N. It slows down a bit the execution but it works correctly. However, consider that the sum of all files generated will always be about 6 GB.
I wrote a few lines of code on the fly that I now share with you.
Add two properties to the main window:
1)
MAX_ELEMENTS As Integer = 10000000 // 10 million seems reasonable to me but you can use whatever value you like.
-
NumFile As Integer = 0
At the end of the “mostraElemento” method add the following code:
k = Permutations.Count
If k >= MAX_ELEMENTS Then
// --- Save file ---
NumFile=NumFile+1
Var fSave As FolderItem = SpecialFolder.Desktop.Child("File_"+NumFile.ToString+".txt")
Var output as String = String.FromArray(Permutations, EndOfLine)
Var tOutput as TextOutputStream
tOutput = TextOutputStream.Create(fSave)
tOutput.Write output
tOutput.Close()
//======================================
Permutations.RemoveAll
End if
At the end of the code in the UserInterfaceUpdate event, comment out or delete the last line btnSave.Enabled = True (the save button is no longer useful) and add the following code:
'======================
'btnSave.Enabled = True
'======================
// --- Save last file ---
NumFile=NumFile+1
Var fSave As FolderItem = SpecialFolder.Desktop.Child("File_"+NumFile.ToString+".txt")
Var output as String = String.FromArray(Permutations, EndOfLine)
Var tOutput as TextOutputStream
tOutput = TextOutputStream.Create(fSave)
tOutput.Write output
tOutput.Close()
//======================================
MessageBox("work completed")
The code can surely be improved (for example by choosing a folder where to save the files, which are now saved on the desktop), but it gives the results you are looking for.
Regards.
1 Like
Good Morning - Please see the attached v3
**This version implements automatic saving for permutations over 10! - to prevent memory issues when generating large sets of permutations.
**You’ll note that in the current example, the save method will take much longer to generate and save the permutations than the previous methods. This is the “looping thru each item” method I described yesterday, leading to “slow” saving of large data-sets & demonstrates why looping one-by-one is a bad idea (would take forever to generate the permutations).
**Later this afternoon, I’ll add the last few lines that will tremendously increase the generation and save method for large permutations sets. I wanted to provide both versions for benchmarking purposes & to demonstrate why it’s better to save “chunks” of data vs looping over the permutations one-by-one. The updated demo has a new name, to keep the previous benchmarking example available.
It took less than 2 minutes to add the “save by chunk” method so I figured I’d go ahead and share it now so you can compare/benchmark both saving methods. Note in V4 of the demo, it now automatically saves large permutation sets directly to file, just as quickly as the original method of paging to a listbox. Enjoy!
1 Like
Thanks so much Matthew. Great work. Thanks for sharing.
