|
The idea of step 2 is this:
assuming you have two arrays with N and M elements, respectively, where N < M. Now extend that array by attaching M-N additional numbers. Then you have two arrays of the same size and can use step 1 to solve the problem.
That said, you should not actually extend the smaller array, as that would be O(N). You only have to modify the algorithm to behave as if it were extended. Also the description isn't quite correct as it fails to mention that you have to attach a like number of smaller and bigger elements to make sure the median isn't moved: so add (M-N)/2 elements that are smaller than the smallest element of both arrays at the start of the smaller array, and then (M-N)/2 elements at the end that are bigger than the biggest number in both arrays. (As I said, you don't actually add these values, you only do this virtually).
Example:
arr1 = { 6, 11, 18 } (length 3)
arr2 = { 4, 5, 8, 9, 10, 12, 15 } (length 7)
step 2 (adding 2 values at both the start and the end):
arr1a = { 1, 2, 6, 11, 18, 19, 20 } (length 7)
Actually "step 2" is a misnomer as it is supposed to be executed before step 1 in case the precondition (same array size) isn't met.
|
|
|
|
|
What do two arrays have to do with the problem? Put them together into a single array, which need not be sorted. There are no fewer than five such algorithms available online (e.g., Dromey, Knuth, Floyd). This very subject was my thesis paper in graduate school.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Show me a community that obeys the Ten Commandments and I'll show you a less crowded prison system." - Anonymous
|
|
|
|
|
if i Put them together into a single array ,it's not o(logn)
|
|
|
|
|
If you merged one sorted array into the other, the cost would simply be O(N log(N)). The cost for picking the element at position N/2 would then be O(1).
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Show me a community that obeys the Ten Commandments and I'll show you a less crowded prison system." - Anonymous
|
|
|
|
|
|
a1_shay wrote:
nlogn it"s not logn
 Whatever you are attempting to convey here did not work.
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Show me a community that obeys the Ten Commandments and I'll show you a less crowded prison system." - Anonymous
|
|
|
|
|
He said that O(N log(N)) is not O(log(N)), and he has a point 
|
|
|
|
|
Hello everybody,
This will take a little while to describe the problem I'm facing, and I will appreciate your patience.
I'm creating a pretty large SDI MFC application, with a lot of options and controls. Most of the application screens are list based. If that matters, imagine MS Word 2007 with editable list instead editable document.
Some of the controls activate a pretty lengthy operations that do work on the list, and update its entries. These operations use worker threads to do their work.
Now, the problem. I want to update the list on the go while disabling all the controls, except one - the "cancel" button.
A simple EnableWindow(FALSE) wouldn't work, as the application is Ribbon based. I.e. to make the buttons look disabled I must handle ON_UPDATE_COMMAND_UI.
Simple message pump wouldn't work as well, because of MFC message routing.
Can anybody suggest a proper approach for such an application? That is both relative simple and general (I have many different operations that activate worker threads).
|
|
|
|
|
I do not understand this statement:
>> Simple message pump wouldn't work as well, because of MFC message routing.
Are you referring to a local message loop?
Of course EnableWindow won’t work, since ribbon Windows controls, all controls with are derived from CObject and are represented by just image drawn by the ribbon control. Few of them are actually hosting Windows control (like CMFCRibbonEdit for example).
Anyway, if you update some data in the background using worker thread, use a variable that would tell update command handler to toggle enabled state: disable when thread is still running, and enable when thread is done, using CCMdUI.
You can also consider using
ON_UPDATE_COMMAND_UI_RANGE, for the range of the ribbon’s panel controls.
JohnCz
|
|
|
|
|
You can post a message from your thread to the view that contains your list. Your view can then add the data to the list (or modify it as needed) and then call UpdateWindow() fot the list.
UpdateWindow bypasses the normal winproc and is handled immediately by the window.
Hope this helps.
Karl - WK5M
PP-ASEL-IA (N43CS)
PGP Key: 0xDB02E193
PGP Key Fingerprint: 8F06 5A2E 2735 892B 821C 871A 0411 94EA DB02 E193
|
|
|
|
|
I do not think that UpdateWindow addresses the original problem. UpdateWindow triggers system to sends (not posts) WM_PAINT message, therefore message is not placed in the queue. SendMessage causes system to call windows procedure directly, therefore this s a blocking call.
Anyway, original problem is to update UI controls on the ribbon, not list control.
Setting variable using proper synchronization is I think less expensive than posting the custom message from the worker thread; however I think the difference is negligible.
If PostMessage is used, the handler can set variable to be used in Update UI handlers.
JohnCz
|
|
|
|
|
Here's an excellent article on worker threads: WorkerThreads[^]
"Real men drive manual transmission" - Rajesh.
|
|
|
|
|
Why not worker threads with PostMessage combo? it works.
Starting to think people post kid pics in their profiles because that was the last time they were cute - Jeremy.
|
|
|
|
|
I am implementing RSA in C++ and here's my design(code structure).
keygen.h
namespace rsa{
class keygen{
public:
keygen(size);
void generate();
string gete(){ return xyz; }
..
..
..
private:
void initall();
keygen(){}
}
}
prime.h
namespace rsa{
unsigned int primes[]={2,3,5,7,11.....541};
bool isPrime(mpz_t, unsigned short);
void getPrime(mpz_t, mpz_t)
}
endec.h
namespace rsa{
string encryption(string text, const string& n, const string& e);
string decryption(string cipher, const string& n, const string& d);
}
Is this a good design? How can I make it better? I want to improve the structure or the overall design, that's why dint post any implementation specific code. Things like naming standards, using classes wherever applicable, standard function signature and similar is what I'm looking for.
|
|
|
|
|
Hi,
I'd get rid of the private member functions and use a PIMPL [1] for your key generator class. It clears a lot of stuff out of the header file and makes that a bit easier to use. If you can end up with something minimal it doesn't help people using your code. Perhaps something like:
class key_generator_data;
class key_generator
{
public:
key_generator( const unsigned key_size );
key_pair create_new_key() const;
private:
std::unique_ptr<key_generator_data> data_;
};
And that's it with key_pair, public_key and private_key being classes.
The only other thing I'd comment on would be what your encryption and decryption functions are called and the parameters they take. Perhaps consider having a stream interface as well?
bool encrypt( std::istream &plain_text, std::ostream &cypher_text, const std::string &n, const std::string &e );
bool decrypt( std::istream &cypher_text, std::ostream &plain_text, const std::string &n, const std::string &d );
Perhaps have better naming for the public and private keys as well.
I know that you don't generally encode much with RSA but stream interfaces make it a lot easier to encrypt and decrypt stuff. You can test stuff by entering plain text at the console, reading it from a file or even over a socket without the caller having to buffer anything.
One final point... If you intend doing anything else it might be worth making an abstract base encryptor class and implementing your code in terms of that. Then if you ever decide to use a different asymmetric encryption algorithm or want to unit test client code you can just in a replacement.
Cheers,
Ash
[1] Herb Sutter describes what a PIMPL is in "Exceptional C++". They're a great way of avoiding all the nightmares that come with cluttered interfaces.
|
|
|
|
|
Aescleal wrote:
I'd get rid of the private member functions and use a PIMPL [1] for your key generator class. It clears a lot of stuff out of the header file and makes that a bit easier to use. If you can end up with something minimal it doesn't help people using your code. Perhaps something like:
class key_generator_data;
class key_generator
{
public:
key_generator( const unsigned key_size );
key_pair create_new_key() const;
private:
std::unique_ptr<key_generator_data> data_;
};
And that's it with key_pair, public_key and private_key being classes.
That's an interesting concept, PimpL.. I'll try implementing it. But why having so many classes for keys(key_pair, public_key and private_key) instead of a single key class will be better?
Aescleal wrote: The only other thing I'd comment on would be what your encryption and decryption functions are called and the parameters they take. Perhaps consider having a stream interface as well?
bool encrypt( std::istream &plain_text, std::ostream &cypher_text, const std::string &n, const std::string &e );
bool decrypt( std::istream &cypher_text, std::ostream &plain_text, const std::string &n, const std::string &d );
Perhaps have better naming for the public and private keys as well.
I know that you don't generally encode much with RSA but stream interfaces make it a lot easier to encrypt and decrypt stuff. You can test stuff by entering plain text at the console, reading it from a file or even over a socket without the caller having to buffer anything.
Ahh that's another great idea.. it will surely come handy. Also, I realized that encryption and decryption are exactly similar(except the parameters ofcourse), a single function will suffice
bool crypt( std::istream &in, std::ostream &out, const std::string &n, const std::string &e );
Aescleal wrote: One final point... If you intend doing anything else it might be worth making an abstract base encryptor class and implementing your code in terms of that. Then if you ever decide to use a different asymmetric encryption algorithm or want to unit test client code you can just in a replacement.
Base class encryptor? Can you please throw some more light on this?
Thanks Ash 
|
|
|
|
|
A single key class would work as well. I've usually used one for the private key and one for the public key but thats probably just a matter of taste.
The abstract base class thing...
What I was suggesting was defining an interface class:
class encryptor
{
public:
virtual bool encrypt( ... ) = 0;
virtual bool decrypt( ... ) = 0;
};
and you'll have an implementation like:
class RSA_encryptor : public encryptor
{
public:
virtual bool encrypt( ... );
virtual bool decrypt( ... );
};
then when you write your client code it uses the encryptor interace, creating an RSA_encryptor to do your stuff. It's be something like:
void do_something( encryptor *enc )
{
}
int main()
{
key k(...);
RSA_encryptor rsa( &key );
do_something( &rsa );
}
This means that do_something can be unit tested by chucking in a mock encryptor and if you ever need to change algorithm you can just change the top level declaration and it all works swimmingly.
Hope that helps,
Cheers,
Ash
|
|
|
|
|
Wow.. I understand now and can see the benefits of using that too. I often miss using this OOP features. Can you please suggest me some good book for learning the usage of OOP features in C++(advanced C++)?
Thanks again Ash
|
|
|
|
|
I don't know of any C++ text that does a good job at OO design.
I'd have a look at "Design Patterns: Elements of Reusable Object-Oriented Software" by Gamma, Helm, Johnson and Vlissides. It's nearly 20 years old but goes over some common design templates (for the want of a better word) that you can integrate into your code. The C++ implementations are complete rubbish but the underlying principles are well worth a look. Incidentally when you read articles/other books/forums about OO design and implementation this book is called the GoF (Gang Of Four).
Other more advanced books that are worth a read are "Exceptional C++" by Herb Sutter - it's got a lot about how to implement classes to break dependencies but less about how to actually do OO stuff. Still worth a read.
"Agile Software Development, Principles, Patterns, and Practices" by Robert C. Martin. It's got a rehash of some of the GoF patterns which is more accessible. It's mostly about how to develop software but there's a fair amount of material on OO desing and programming. Unfortunately the examples are in Java but the text surrounding it is well worth a read.
If you have access to a good public or academic library then it might be worth getting a loan off them first before going bananas and spending loads of cash.
Ash
|
|
|
|
|
Hello Friends
I am creating a dialog based Application in which I am creating several Tabs.I am adding seven button to this Dialog also.
Now,I want to set the some color on Button. And,On Tab change ,I want to change the colors of button too.
Any Ideas?
Thanks & regards
Yogesh
|
|
|
|
|
By: I want to set the some color on Button
Do you mean set some bitmap and change it to indicate button state or change the color of the whole button?
JohnCz
|
|
|
|
|
I set the Button WS_DISABLED and i want to change the Whole Color Of Button.
Yogesh
|
|
|
|
|
yogeshs wrote: Now,I want to set the some color on Button.
Are you handling the WM_CTLCOLORBTN message?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Show me a community that obeys the Ten Commandments and I'll show you a less crowded prison system." - Anonymous
|
|
|
|
|
No, I am not handling this Message .But i tried to inherit Class from CButton and tried to set color.
But no use.
And i want to change the color at runtime also.So,for that Do I need to Override Drawitem? What its Actual Working ?
Some Ideas ??
Regards
Yogesh
|
|
|
|
|
yogeshs wrote: No, I am not handling this Message .But i tried to inherit Class from CButton and tried to set color.
But no use.
I think you have to use ON_NOTIFY_REFLECT() in the button's message map, or ON_NOTIFY() in the parent (i.e., dialog).
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"Show me a community that obeys the Ten Commandments and I'll show you a less crowded prison system." - Anonymous
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
