Algorithms

cp9876 wrote:

Unless you have RAM issues, generate two arrays each of 2 million integers:

a[i] being the randomised numbers
b[j] such that b[a[i]] = i

IEnumerable< int > ChandrasCrazyNumbers()
{
   // We use dictionarys like lists (string, bool) because this lets us
 use the hash-backed index to do removes. The bool is always true - its 
a placeholder.

   // I've kinda expanded this out into ones, tens, hundreds because 
when its more generalised it gets harder to follow.

   Dictionary< string, bool> ones = 
   Dictionary< string, Dictionary< string, bool>> tens =
   Dictionary< string, List< string >> hundreds =
   Dictionary< string, List< string >> thousands =


   // now we will first pick the rightmost random digit from the ones list
   // and remove it from the avaliable ones... say "4"
   // then pick an avaliable tens that corresponds to the ones, say "24"
   // etc etc

while(true)
{
initialise thousands like so: iterate 0-9999, for say 5983, file that under
"983", {... {"5983", true} .... } 
while(thousands.Count > 0)
{
initialise hundreds like so: iterate 0-999, for say 583, file that under
"83", {... {"583", true} .... } 
while(hundreds.Count >0)
{
 initialise tens like so: iterate 0-99, for say 58, file that under
      "8", {... {"58", true} .... }
   while(tens.Count > 0)
   {      
       init ones like so: {"0", "1"... "9"} all true;
       while(ones.Count > 0)
       {
          string randomOne = ones.Keys[random between 0 and ones.Count)];
          ones.Remove[randomOne];

          string randomTen = tens[randomOne].Keys[random between 0 and tens.Count)];
          tens.Remove[randomTen];

          // ditto for hundreds and thousands

          yield return int.Parse(string.Concat(...., randomTen, randomOne));
       }
   }
}}}}}

yanhe0116 wrote:

I don't know where to begin

Luc Pattyn wrote:

Windows apps can call on the built-in BitBlt functions[^].

Luc Pattyn wrote:

Google (BilBlt, rasterop, theory, internals, ...) will lead you to some junk and some
code snippets; there must be some C/C++/Java implementations around. But again, performance
wise none of those will match specialized products

Luc Pattyn wrote:

From what you have shown so far, I can only conclude that you are a novice in
optimization stuff.

Force Code wrote:

I am not at all convinced that all that copying and shifting and adding you describe is in fact the operations involved in a table lookup

Force Code wrote:

that there is NO WAY to achieve a faster emulation of BitBlt in a flash environment other than a pixel by pixel operation

Force Code wrote:

There are several people in this forum with "Microsoft MVP" in their signature. Don't know if that's literal or some code unique to this forum, but maybe I was thinking someone like that might run across this thread.

Luc Pattyn wrote:

So what I am saying is this: on modern CPUs (Pentium class, RISC, and many others)
u= x&y | x^z | !y&z would be faster than u=ROP[x][y][z]
without any doubt, (say by a factor of 1.33 to 2)

#include < iostream >
#include < windows.h >

using namespace std;

BYTE ROP[256][256][256];

int main(int argc, char *argv[])
{
  DWORD time = GetCurrentTime();
  for (int x=0; x<256; x++)
    for (int y=0; y<256; y++)
      for (int z=0; z<256; z++)
        ROP[x][y][z] = (x&y) | (x^z) | (!y&z);
  cout << "test 1: " << GetCurrentTime()-time << endl;
        
  BYTE n;
  time = GetCurrentTime();
  for (int x=0; x<256; x++)
    for (int y=0; y<256; y++)
      for (int z=0; z<256; z++)  
        n = ROP[x][y][z];      
  cout << "test 2: " << GetCurrentTime()-time << endl;
}

Force Code wrote:

test 1: 240
test 2: 60