|
Now the task is clear; unfortunately I have no good idea (in fact no idea at all) about
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
CPallini wrote: Now the task is clear; unfortunately I have no good idea (in fact no idea at all) about
That's ok... thanks for your time.
|
|
|
|
|
I think Pallini actually has your answer. Think of it on a smaller scale at first...
With the numbers you gave, you just satisfied the first condition (Set of 10, ending in each digit from 0 to 9). Of course, just the numbers 0 to 9 would satisfy that condition.
Now move to the 100s... You basically need 100 numbers that end in 00-99, and 00, 01, 02, ... 98, 99 satisfies that condition. Move to the thousands, and the ten thousands, and there you are.
So technically, a set of 00000-99999 in order satisfies every condition except the randomness. If you want bigger numbers, you can just prepend a few random digits to each, the same way you use "21890" instead of just "0" in your example. Since the last N digits are unique, the number as a whole is unique.
So if I'm right so far, I have your answer.
Create an array of numbers from 0 to 99999 (Maximum - 1) such that Array[N] = N. Just to start off.
Start by randomly sorting each block of 10. First randomize elements 0-9, them 10-19, and so on.
Then sort the blocks themselves. Treat 0-9 as a cohesive unit, 10-19 as a unit, and so on. Sort each block of 100 as if it was comprised of ten blocks.
As you can probably see by now, you just move up one power of ten at a time. Next you sort each block of 1000, treating it as 10 blocks of 100 each, then the whole array as 10 blocks of 1000 each.
You could even do this backwards, first sorting the big blocks, then the little blocks.
At this point, the entire array is randomized, yet will still satisfy your conditions.
This will of course take quite a while if you use a larger set, but there are ways around that too. Use a tree instead. Build a tree where each node has ten children (Except the leaf nodes). These children start out as "0", "1", ..., "8", "9". Traverse the whole tree, level by level, and shuffle the children of each node. Then just traverse the tree to grab all of the shuffled numbers in order, and pipe them into an array. Someone elsewhere in the thread showed you how to quickly search for them.
Ok, this post is way longer than I intended, and I was going to leave the office over a half hour ago, so good luck
|
|
|
|
|
Hi
I think the tree is a really good idea...
As I said before, I have already written the bruteforce method that CPallini was talking about earlier.
I will try out the tree algorithm as it seems a more elegant solution to my problem.
Thank you for taking the time to look through this
Regards
Chandra
|
|
|
|
|
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 ..
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
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 ..
Thank you... I shall try and post back... I am already doing the brute force method, but the first one seems quite interesting.
Meanwhile, is it possible, given a number, to say exactly where in the list it is? Speed is of essence - I will need to give out the answers within a 20 second framework, considering that I will have close to 2 million numbers that will form the base list. I cannot use any database engine...
The reason in my original post to ask for any algorithm for the generation was to see if I could utilize the reverse of that to find the position of numbers too...
|
|
|
|
|
ChandraRam wrote: considering that I will have close to 2 million numbers that will form the base list. I cannot use any database engine
If you need 2 million numbers such that each number only occurs once, then it may be best to precompute as any calculation process has state information that includes all previous numbers (of the 2 million) that have been issued. Unless you can come up with an algorithm that uses less state information, you may need to store up to 2 million numbers - so precomputation may be attractive.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
The speed of the generation is not so much an issue (as in hours, is also OK) as the ability to instantly retrieve any number's position in the list...
|
|
|
|
|
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
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
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
Great!... Now, why didn't I think of that? :->
Language suggestions to hold 2.6 million array items?
|
|
|
|
|
What is the application for this? It's not going to come out very random with these constraints
I'd do something like this:
Its not going to win any awards for neatness, but I think it uses fairly minimal memory. Also its generating the numbers on the fly, rather than using a pre-sorted array, which is kindof cheating
IEnumerable< int > ChandrasCrazyNumbers()
{
use the hash-backed index to do removes. The bool is always true - its
a placeholder.
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 =
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];
yield return int.Parse(string.Concat(...., randomTen, randomOne));
}
}
}}}}}
|
|
|
|
|
Hi Mark
Thank you for looking through this...
This is for a lottery number generator application, which is not actually _random_ in the true sense; there has to be a method in the madness My client is actually guaranteeing that each block of 10 will fetch 1 prize, each block of 100 - 10 prizes, and so on...
I don't quite get the logic, though - my requirement is to generate 26 million numbers, distributed as described above. I am always looking for different ways to implement this.
I would welcome any explanation that you can give on your logic.
Thank you in advance
Chandra
|
|
|
|
|
Dear everyone,
I am facing a problem about my AI assignment. It is to implement Expectation Maximization(EM) for learning a simple naive Bayes model. Who has programming experience about using this algorithm? I don't know where to begin? Thanks if you will give me some help.
|
|
|
|
|
There are several articles on artificial intelligence and neural networks here on CodeProject.
I suggest you use the search facilities on the top of most CP pages. That's where I
would begin.
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
yanhe0116 wrote: I don't know where to begin
I googled and came up with thesis, descriptions, hybrid improvements and even java code for a basic example. If it were me, I would start there.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
I am trying to write some graphics code using the web-development tool Adobe ActionScript (version 3). AS3 has many sophisticated graphics capabilities, but what it does not have apparently, is any sort of BitBlt capability with raster operation (ROP) codes. This may have something to do with it being based on 'Sprites' which from my brief persual of some wikipedia info, is a different philosophy altogether from BitBlt.
I was trying to emulate BitBlt from scratch in ActionScript, by merely dumping three bitmaps into arrays, and then going through them pixel by pixel doing the logical ops on each pixel. As could probably be expected, this is way too slow. It was taking a full second to do ROP bitmap combinations that BitBlt would do instantaneously. (This has nothing to do with any inherent limitation in Actionscript, which does plenty of things graphical instantaneously.)
So I need to find out the algorithms that BitBlt is employing to do what it does and if its possible for me to emulate that (assuming that BitBlt isn't relying primarily on graphics hardware that can't be accessed from a web application.)
Important point:
There is only one ROP code I need to use, so possibly it could be optimized on that basis. (Its one of the more complex ROP codes involving XOR and AND of three different bitmaps).
-- modified at 14:44 Thursday 15th November, 2007
|
|
|
|
|
Hi, image operations in professional packages are implemented using highly optimized code,
typically a combination of C and assembly code; where possible SIMD techniques are applied
(that's MMX/SSE on Intel Pentium). It is the result of extensive research, so you won't
match its performance easily.
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
"Hi, image operations in professional packages are implemented using highly optimized code, typically a combination of C and assembly code; where possible SIMD techniques are applied (that's MMX/SSE on Intel Pentium). It is the result of extensive research, so you won'tmatch its performance easily."
If it were documented anywhere, of course I would be able to emulate it (w/ exception of hardware capabilities). There's no apparent performance hit merely from using ActionScript either, which does some things much faster (e.g. antialiasing) than can be done with Windows code, although I have no idea how its done.
|
|
|
|
|
Windows apps can call on the built-in BitBlt functions[^].
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 [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Luc Pattyn wrote: Windows apps can call on the built-in BitBlt functions[^].
The Windows BitBlt was the one I was referring to, and I am familiar with the documented interface for it.
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
You could save yourself some typing by just responding to every post with "Google it". (Incidentally why does this forum even exist when a link to google is all that's needed.)
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.
As far as my problem, I have three bitmaps - two of them never change position in relation to the client area, and the third scrolls up and down. With each scroll the BitBlt w/ ROP code has to be done. I'm thinking now since the first two bitmaps don't move, I can precalclulate values for them and store them in another table maybe 10-15 megs in size. So, part of the ROP calculation could be replaced by an indexed table look-up, though given the ROP code, I don't know how to do this yet, and furthermore don't know if there's any time saving with this method.
|
|
|
|
|
Most of the people active on this forum use Windows; when they would need BitBlt, they
would call the function, without worrying too much how it is implemented (that was
Microsoft's job).
If you want to implement your own BitBlt function, you will run into performance issues;
the general lines to maximize performance on pixel operations are: avoid testing
and branching, avoid function calls, avoid unnecessary moves, and try to handle as
many pixels as possible in a single operation. The details of all this are way beyond the
scope of a forum such as this, as I already indicated.
With the partial description you provided, I would judge your table look-up is unlikely
to provide any speed-up unless it replaces two of the three images, which probably it isn't.
A Pentium-class CPU is better at reading a couple of pixel streams (which is a very
predictable process, and a prefetch can be organized), than at looking up tables;
and it is unlikely the table replaces more than a couple of (fast) instructions anyway.
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
<blockquote class="FQ"><div class="FQA">Luc Pattyn wrote:</div>With the partial description you provided, I would judge your table look-up is unlikely
to provide any speed-up unless it replaces two of the three images, which probably it isn't.</blockquote>
Something just occurred to me:
BYTE and[256][256]
BYTE or[256][256]
BYTE not[256];
That's less than 150K.
The question is, could and[x][y] be retrieved quicker than x&y is calculated. I suppose some table like this might already be used behind the scenes if it is actually quicker though.
------
Sorry, that was stupid.
But here's what I might try:
BYTE ROP[256][256][256];
This would store every possible byte value for the Raster Op I'm doing. I think one table look up would be quicker than three bitwise logical ops. But how much quicker, and is it worth a 16MB table. Guess I'll find out.
-- modified at 17:21 Thursday 15th November, 2007
|
|
|
|
|
Hi,
The optimization of image processing code is handled at the cycle level, that is why
C/assembly/MMX/SSE are required here. If you want to explain an approach in a higher level,
that is fine to express the concept, but for performance you must visualize the basic CPU
operations that will correspond.
if BYTE ROP[x][y][z] contains a random value, of course you need a table look-up.
At best, these are the basic operations that would occur (assume x,y,z in CPU registers):
copy x, shift it by 8 positions, add y to it, shift it by 8 positions, add z to it,
add the address of ROP[0][0][0] to it, do an indirect load; so that amounts to 6 simple
arithmetic operations and a load.
as long as the value of BYTE ROP[x][y][z] can be expressed as a function of x,y,z containing
less than say 6 logical operators the direct code would be faster, since it does not need
the load at all.
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)
From what you have shown so far, I can only conclude that you are a novice in
optimization stuff.
If you want to continue in this field, I recommend you study some code outside
the .NET Framework, and look at assemly code generated (a) by compilers, (b) by
manual optimization (e.g. look at the disassembled code of the strlen function, you
will find over 100 lines for something that most people would do, somewhat slower,
in less than 10 lines! The difference is not much, but that's mainly because strlen
is hard to parallellize, although there are MMX versions of it too).
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Luc Pattyn wrote: From what you have shown so far, I can only conclude that you are a novice in
optimization stuff.
For the record, I've had two courses in digital logic at the graduate level, (pursuant to my master's degree) but that type of optimization isn't really an option for me here, is it? I certainly know assembler as well. Remember my original problem, however: I am trying to emulate BitBlt with in the actionscript/flash environment which doesn't have it. My goal is to eak out as much speed for the operation in that environment, and see what I come up with. In my previous post I was thinking out loud, essentially in an attempt to get some meaningful feedback for my desired goal, which BTW, I have yet to recieve. Essentially what you're implying is that there is NO WAY to achieve a faster emulation of BitBlt in a flash environment other than a pixel by pixel operation. I appreciate your explanation as to why a table lookup would not be faster than the bitwise logical operation, but once again how have you helped me towards solving my original problem at all?
Respectfully,
Force Code
----------------------------
"if BYTE ROP[x][y][z] contains a random value, of course you need a table look-up. At best, these are the basic operations that would occur (assume x,y,z in CPU registers): copy x, shift it by 8 positions, add y to it, shift it by 8 positions, add z to it,
add the address of ROP[0][0][0] to it, do an indirect load; so that amounts to 6 simplearithmetic operations and a load."
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:
My thinking first of all that a compiler would convert x,y,z into a single value and store it in one register and use it as an offset from a base address - there go your litany of copies and such.
(But you said it with such authority - I almost assumed for a minute you knew what you were talking about.)
-- modified at 19:39 Thursday 15th November, 2007
|
|
|
|
|
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
well that too proves my point. how do you think a CPU gets to an element of a three-
dimensional array?
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
that's not what I said; to the contrary, I told you looking for parallellism
is a major way to speed up image processing. To what degree it is possible in your case
I can't tell.
I am not going to spend the time and solve your problem, I don't even plan on
investigating it any further. I have told you how complex your goal may be and what
is important to image processing performance.
I think you are looking at a major undertaking and probably will be disappointed by
the results that you will obtain, but hey don't let anyone discourage you...
Luc Pattyn [Forum Guidelines] [My Articles]
this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|