|
Is your list already (partially) sorted? What element are you using for the pivot? Does your list have a lot of repeated elements?
As for the data structures themselves, both take O(n log n) comparisons in the average case. In the worst case, quicksort takes O(n^2) comparisons, whereas mergesort takes O(n log n) comparisons.
"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
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
|
|
|
|
|
My list is not sorted at all :
void *ft_init_array_int(int len)
{
int *tab;
srand(time(NULL));
if (!(tab = (int*)malloc(len * sizeof(int))))
return (NULL);
while (len--)
tab[len] = rand();
return ((void*)tab);
}
I have noticed that if I my list has a lot of duplicate keys ("tab[len] = rand()%10" instead of "tab[len] = rand()"), my quicksort is much faster than my mergesort.
I use the first element for the pivot. I wanted to have consistent result first and then improve my mergesort.
For instance, it takes 7 seconds or so for my mergesort to sort 10.000.000 integers and around 13sec for my quicksort (qsort from stdlib.h takes 4sec). Does that mean that my algo (without improvement) does not work well enough ?
|
|
|
|
|
If your implementation "only" takes about 3 times as long as the stdlib qsort, then you can be reasonably sure that, technically, you did it correctly.
As for why your program takes longer, there are quite a number of things that can go wrong in performance optimization. A good start would be avoiding shortcuts and explicit optimization, even if it may sound counter-intuitive. The compiler is exceptionally good at optimizing code without your help, but to do this efficiently, it needs to see the "real" code, not some byte manipulation that it can't make heads or tails of.
One example is your #define: all it does is accessing array members, but all the compiler sees is some weird pointer arithmetic. Do leave the compiler arithmetic to the compiler, and you'll find that at the very least you'll get more readable code at no performance loss, and maybe you'll even see an improvement. I think I understand what you use this define for, but if I'm right, all you really need is a typecast from void* to int* (or pointer to whatever element type you're using)
Another issue may be the various helper functions you're calling: without the actual type information, these functions may be very inefficient. E. g. a function to swap two ints only requires a handful of assembler instructions. A function to swap two arrays of n bytes, where n is a run time variable, requires about three to five times as much.
You could check your compiler's aqssembler output to see what it makes of your code. Try different variants to find out what the compiler makes of it. Maybe that can give you some insight into what is causing the performance issue.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)
|
|
|
|
|
Thank you for your exhaustive response, your answer has risen a few more interrogations. I will work on the subject and I will come back to you as soon as possible.
|
|
|
|
|
Problem: This is our first programming assignment. This assignment has two parts:
• Part 1: I ask you to write a program to build a decision tree using Gini impurity measurement to guide tree generation. The data set is the poker hand data set archived at UCI Machine Learning Repository: Poker Hand Data Set
Data Set
Characteristics: Multivariate Number of Instances: 1025010 Area: Game
Attribute
Characteristics: Categorical, Integer Number of Attributes: 11 Date Donated 2007-01-
01
Associated Tasks: Classification Missing Values? No Number of Web
Hits: 212827
You shall use the training data set to build your decision tree and then use the testing data set to evaluate your decision tree. You need to report classification accuracy using a bar chart and compare it with the distance based classification which is given in Part II.
• Part II: For this part, I ask you to use the same training data set in Part I to build a distance-based classification model. Here, you need to find a good distance metric and a parameter k that serves as the threshold to bound the nearest neighbors for any given data item (or point). Then, you need to apply your model to the testing data set to evaluate your classification model. You shall record the classification accuracy and compare it in a
bar chart with that of the decision tree model built in Part I.
Programming Language:
C++ or Java, but C++ is preferred.
|
|
|
|
|
Your first decision should be to read this[^]. Your homework won't be done here.
"the debugger doesn't tell me anything because this code compiles just fine" - random QA comment
"Facebook is where you tell lies to your friends. Twitter is where you tell the truth to strangers." - chriselst
|
|
|
|
|
Was this handed out in the 10am or 11am CS class with Professor Lewis?
"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
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
|
|
|
|
|
I have a question that is think should be rather simple, I also feel it is not a copy of a question from years back.
I am new to programing in general and I have only been doing it on and off for a few years. I use the VS2012 compiler & GNU GCC with C & C++.
My question is really simple and I will try to explain this so everyone can understand.
I want to make two functions that can encrypt or decrypt strings using AES or rinjdael.
http://pastebin.com/Gw0RLBNR[^]
The paste above is what I am talking about, it uses two functions one teaEncode and one teaDecode. I want to figure out how to make an equivalent to the tea system above but with AES.
https://github.com/seonggwang/miniature-AES[^]
Now I understand some of you would link me to like the one below.
WinAES: A C++ AES Class[^]
I'll be blunt I have been trying to make a function to encrypt/decrypt data in C++ under VS2012 using many different page on git. But the problem is few of them want to compile and I really don't know how to fix many of the issue they bring up.
So I really am just asking for a AES string encryption/decryption that works under VS2012 or GCC.
|
|
|
|
|
If you can't use one of the few that compile, try listing the specific compilation errors for one that does not. People here are willing to help with specific issues.
"the debugger doesn't tell me anything because this code compiles just fine" - random QA comment
"Facebook is where you tell lies to your friends. Twitter is where you tell the truth to strangers." - chriselst
|
|
|
|
|
|
The error messages tell you what to do. What are you having trouble with?
None of your 3 invocations of cl include the switch specified in the error messages (/EHsc)
Likewise, did you make the suggested change to line 28 of aes.cpp?
"When I was 5 years old, my mother always told me that happiness was the key to life. When I went to school, they asked me what I wanted to be when I grew up. I wrote down 'happy'. They told me I didn't understand the assignment, and I told them they didn't understand life." - John Lennon
|
|
|
|
|
I am having problems with fixing the errors.
|
|
|
|
|
Er, yes. You ah, you already made that clear in your first post.
What specifically is giving you a problem?
"When I was 5 years old, my mother always told me that happiness was the key to life. When I went to school, they asked me what I wanted to be when I grew up. I wrote down 'happy'. They told me I didn't understand the assignment, and I told them they didn't understand life." - John Lennon
|
|
|
|
|
That error I am not sure how to fix it and I am pretty sure more errors will come up after it.
I did attach a file with the error log in it.
|
|
|
|
|
There is one error and one warning shown there. The solution to each are in the messages!
1. Warning - arising from one of the VS supplied files.
2. Error - the compiler isn't prepared to treat a const char* as a const byte*
To solve, follow the directions.
I.e
1. Add the /EHsc switch to the command line. - "cl /EHsc aes.cpp"
2. Goto line 29 of aes.cpp and cast the first parameter of DefaultEncryptorWithMAC to be a const byte*
Something like: DefaultEncryptorWithMAC( (const byte*)firstParam, secondParam, thirdParam);
"When I was 5 years old, my mother always told me that happiness was the key to life. When I went to school, they asked me what I wanted to be when I grew up. I wrote down 'happy'. They told me I didn't understand the assignment, and I told them they didn't understand life." - John Lennon
|
|
|
|
|
|
Bother. 
I'd actually downloaded the project yesterday that you shared at MediaFire or wherever it was. I've just tried the page you linked to here, but only saw the ability to browse 10 sample projects. Going back to the article's main page also only gives the ability to download any one of the 10 samples.
So, I gave it a go and carried-on anyway - loading the SLN file in your zip.I converted it to one that VS2010 was happy with and hit build. Great, no problem - it builds just fine.
--
Next, I created a new win32, console project in the solution.(called Member10657083) I copied the contents of your aes.cpp file and replaced the contents of "Member10657083.cpp" with it. I also uncommented the #include stdafx.h line.
Upon trying to build, I didn't get that warning you had, but still got the same error.
Mistakenly, I changed
new DefaultEncryptorWithMAC(
password.c_str(),
into
new DefaultEncryptorWithMAC(
(const char*)password.c_str(),
Of course, the error was exactly the same. Realizing my mistake, I then changed it to:
new DefaultEncryptorWithMAC(
(const byte*)password.c_str(),
and tried again. Bingo! The project compiled. While the project didn't successfully build, it was only linker errors, since I didn't add any to the new project. I'm tired and very rarely use VS, so I'm not going to tackle that tonight.
Hope this helps.  Let me know how you get on.
"When I was 5 years old, my mother always told me that happiness was the key to life. When I went to school, they asked me what I wanted to be when I grew up. I wrote down 'happy'. They told me I didn't understand the assignment, and I told them they didn't understand life." - John Lennon
|
|
|
|
|
That did change things but it seems to have created quite a few linker errors on my end as well.
|
|
|
|
|
Hi,
I am making a gui for an application, which requires me to invoke a windows command prompt inside a MFC gui window.I am very new to MFC, I will highly appreciate, if somebody can give an idea, how to invoke a windows command prompt inside a MFC window.
|
|
|
|
|
Opening a command prompt window is not related to MFC. It can be performed by any Windows application using ShellExecute[^]:
ShellExecute(NULL, _T("open"), _T("cmd.exe"), _T("/k"), NULL, SW_SHOW);
ShellExecute starts cmd.exe here which opens the shell. The /k parameter specifies that the shell is not closed immediately but requires closing the window or typing 'exit' (type 'help cmd' in a shell to list available options). The fifth parameter can be used to specify a directory.
|
|
|
|
|
Hi,
I want to embedd the command prompt inside a mfc window, can u suggest some template and how to do this.
Thanks,
Kamlendra
|
|
|
|
|
|
Why do you need a command prompt? Much better to use a label for the question, and an edit control (CEdit) for the response.
|
|
|
|
|
I have some structures in my application (which is pretty big). To test certain error conditions, I have to input wrong values to these variables and send across another system (using udp sockets). How can I use the treeview to populate all the structures and upon user selection of one of the node (the struct variable), i wants to input error values and update the same structure variable in my app. Here is the sample
Quote: hRoot = m_TreeView.InsertItem(_T("Messages"), 0, 1);
hMainMsg = m_TreeView.InsertItem("XXXXX", 0, 1, hRoot);
hSubMsg = m_TreeView.InsertItem("MsgHdr", 2, 3, hMainMsg);
m_TreeView.InsertItem(_T("msgId"), 4, 5, hSubMsg);
m_TreeView.InsertItem(_T("InfId"), 4, 5, hSubMsg);
m_TreeView.InsertItem(_T("Seq No"), 4, 5, hSubMsg);
m_TreeView.InsertItem(_T("msgLen"), 4, 5, hSubMsg);
m_TreeView.InsertItem(_T("timeStamp"), 4, 5, hSubMsg);
in double click event,
HTREEITEM nodSelected = m_TreeView.GetSelectedItem();
CString strSelected = m_TreeView.GetItemText(nodSelected);
HTREEITEM hParent = nodSelected;
while (hParent = m_TreeView.GetParentItem(hParent))
{
CString strParent = m_TreeView.GetItemText(hParent);
if (strcmp(strParent,"Messages")==0)
break;
m_TreeView.SetItemState(hParent, TVIS_BOLD, TVIS_BOLD);
strSelected = strParent + "." + strSelected;
}
m_txtMsg = strSelected + "=";
for ex. m_txtMsg will be now "XXXXX.msgHdr.msgId=<some value="">"
Is there any way to use this text data to assign as my variable
Please help.
|
|
|
|
|
You can only set the content of a structure by referring to it by address (aka pointer/reference). So rather than adding the item as text to each tree node, you should create a structure item, populate it with the data, and save its address in the node.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
