1.

Solve : Alpha Odometer - Time Waster Curiosity Program?

Answer»

Just sharing a program I was messing with to generate all combinations of A thru Z for 26 character length only.

With winter storm here and an IDEA on my mind to toy with, I decided to build upon someone elses project out of curiosity as to how quickly a modern computer could process to generate all combinations of A thru Z with all letters A thru Z involved without repeat letters as for you can only have 1 of each letter type in the shuffle.

I expected it to process 26 to the power of 26 quicker for all combinations of same case A to Z, but then I realized that its single-threaded execution and so only 1/4th of my Athlon II x4 2612Mhz quadcore was being used.

So I do come here with a question though which is..... is it the IDE that compiled the source code that basically governs whether its a single-threaded execution or is it in your source code that you need to add to specify to tap into the use of all cores to get full 100% CPU utilization?

As for with the current code to get 100% utilization the trick would be to create 4 programs with 4 blocks of the alphabet range to work WITHIN and then set core affinity so that each program when executed runs on its own core.

Here is a link to see it running without having to compile and run yourself. I shared it on youtube to share with some other friends and anyone else interested in it: https://www.youtube.com/watch?v=8YrhqAhNJEc&feature=youtu.be

Here is the section that I tweaked to how I wanted it to process. If you go to the original source at the site I got this from you will see it processing far fewer letters and not logging the start and stop time with use of a system batch type execution within the program.

Quote

{
system("@echo. Started %date% at %time% >>ABC.log");
char str[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int n = strlen(str);
permute(str, 0, n-1);
system("@echo. End %date% at %time% >>ABC.log");
system("PAUSE");
return 0;
}


Code: [Select]// http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

#INCLUDE <stdio.h>
#include <string.h>
#include <cstdlib>
#include <iostream>

/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}

/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting INDEX of the string
3. Ending index of the string. */
void permute(char *a, int l, int r)
{
int i;
if (l == r)
printf("%s\n", a);
// write to file here current string
else
{
for (i = l; i <= r; i++)
{
swap((a+l), (a+i));
permute(a, l+1, r);
swap((a+l), (a+i)); //backtrack
}
}
}

/* Driver program to test above functions */
int main()
{
system("@echo. Started %date% at %time% >>ABC.log");
char str[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int n = strlen(str);
permute(str, 0, n-1);
system("@echo. End %date% at %time% >>ABC.log");
system("PAUSE");
return 0;
}That code determines permutations, not combinations, does it not?
Quote from: DaveLembke on December 29, 2015, 11:43:31 AM
So I do come here with a question though which is..... is it the IDE that compiled the source code that basically governs whether its a single-threaded execution or is it in your source code that you need to add to specify to tap into the use of all cores to get full 100% CPU utilization?
You have to write code that uses threads- at least in the case of C. Other languages might work with coroutines or other parallelization options.

In a case such as this, it would make sense to have a thread pool. For example, let's say we want to have 4 threads running. In this case the best approach, at least in terms of simplicity to implement, would be to have a rather simplistic thread pool. The top-level call to permute could run four iterations of it's loop as separate threads, wait for them to complete, then run the next four. The primary disadvantage is that the generated sequence wouldn't have a predictable sequence, and it would require some additional synchronization on the output to prevent multiple threads from attempting to print to the standard output simultaneously.

While it wasn't with permutations, I took this approach with a File Search class I (re)designed a while ago. Mind you, it's a bit more complicated since it doesn't merely intend to print output, but rather make it available to other pieces of code, but it effectively follows the approach of having multiple HIGHER level Search actions be run via separate threads. (An earlier version made the mistake of spinning a new thread for every single subdirectory search which made things far, far slower)

Here's a C# version using Linq, though it is still only runs on a single thread. It's also generic so it works on sequences of any type. Strings are simply a sequence of char (IEnumerable in .NET's case):

Code: [Select]class Program
{
static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> list, int length=-1)
{
if(length==-1) length = list.Count(); //ignore that this is multiple enumeration...
if (length == 1) return list.Select(t => new T[] { t });

return Permutations(list, length - 1)
.SelectMany(element => list.Where(e => !element.Contains(e)),
(item1, item2) => item1.Concat(new T[] { item2 }));
}
static void Main(string[] args)
{
int totalcount = 0;
String Alphabet = "ABCDEFGHJKLMNOPQRSTUVWXYZ";

foreach(var loopalphabet in Permutations(Alphabet))
{
String buildresult = new String(loopalphabet.ToArray());
Console.WriteLine(buildresult);
totalcount++;
}
Console.WriteLine("Count:" + totalcount);
Console.ReadKey();
}
}
Thanks BC for the info

also..

Quote
(An earlier version made the mistake of spinning a new thread for every single subdirectory search which made things far, far slower)

Wow.... sounds like if run in a location targeting a large number of subdirectories could bring the system to its knees depending on if the routine for that thread executed and ended or stayed active and grew larger and larger until all subdirectories are targeted.

Interesting thread pool .... so you could create 4 threads and set an core affinity to each thread so that it makes use of the entire CPU, and the top level call that is running manages the 4 threads on what is processed next and plays traffic cop with it all.


Discussion

No Comment Found

Related InterviewSolutions