Algorithms

CPallini wrote:

Now the task is clear; unfortunately I have no good idea (in fact no idea at all) about

cp9876 wrote:

There is a brute force way to arrange these, but it is easier to describe a randomiser:

1. Start with the set of 10,000 numbers in order.
2. Generate a set of swap commands, swap the ith element with one n places away, i in [0,10000) n in [1,10000) with circular referencing. If the swap is within 10 places it always happens, if 10 - 99 places then it swaps with the nearest element in the range 10 - 99 with the same LSB, if 100 - 999 then to the nearest element with the same 2 LSB etc...
continue random swaps until the set is randomised.


To arrange by brute force:

1. generate 10000 random LSB so that each group of 10 contains {0,..,9}
2. for each group of 100 LSB's generate a random group of 100 next LSB's (i.e. 10 '0's, 10'1's etc) call these {Ai}. Assign these Ai as follows - Assign Ao to the first number. Then assign Ai with the lowest i such that the number formed by the two LSBs is not already in this group.
3. Do the same for the next LSB assigning 1000 numbers etc ..

ChandraRam wrote:

considering that I will have close to 2 million numbers that will form the base list. I cannot use any database engine

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