|
I did the same using set command string (passed as param to mcisendstring function). But I am getting "value out of range exception..", what to do with this ?
thank u,
kiran.
|
|
|
|
|
kadkir wrote: I am trying to record a wave file using "winmm.dll"
So you're using the waveIn___() APIs?
If so, you can specify the format you want to record in your
call to waveInOpen() (see the WAVEFORMATEX struct parameter).
Mark
Mark Salsbery
Microsoft MVP - Visual C++
![Java | [Coffee]](https://codeproject.global.ssl.fastly.net/script/Forums/Images/coffee.gif)
|
|
|
|
|
Hello everyone,
I have a large data set of integers (about several Million), all of them are positive integers from experiment. They are stored on a file on local machine. I want to select the largest 1000 values then make analysis based on the 1000 values.
Could anyone suggest some efficient solutions? I think sorting the several M data in memory is not feasible.
thanks in advance,
George
|
|
|
|
|
use map for initially storing the integers
use this map to write integers to file
Using map will unsure that integers are sorted even when written to file
read first 1000 values from file ....now you will get them as storted
|
|
|
|
|
Hi ccpptrain,
What do you mean map?
regards,
George
|
|
|
|
|
|
Thanks abhijit,
I think you mean put all several hundred Million data samples into a memory based data structure Map. I think the memory will be used out. 
Do you have any other ideas?
regards,
George
|
|
|
|
|
It is a generalization of your hand-crafted container. There are several C++ classes implementing it, see, for instance:
std::map [^]
and
MFC CMap [^.]
Hope that helps.
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.
|
|
|
|
|
Thanks CPallini,
I have read through the MSDN reference. I think the memory will be used out if I choose to make all data in pure memory based data structure Map. If I have only several hundred or several thousand of data samples to select, it will be ok to use Map. But now I have several Million data samples.
Any ideas to save memory and do not degrade performance too much? (I think using Map could have very good performance if the total memory is enough.)
regards,
George
|
|
|
|
|
George_George wrote: What do you mean map?
learn C++ containers 
but, hey !!!! where's my answer bloody lamer ?
|
|
|
|
|
why map ?
map forbids to have 2 keys identical, and FWI understand, there no need for a pair of (key; value).
vector is good enough then...
|
|
|
|
|
You don't need to sort the values, you have just to pick the 1000 largest ones, hence only a traversal of the whole set is needed.
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.
|
|
|
|
|
Hi CPallini,
I think you mean I use sorted Map right? I have used Map before for small amount of data, e.g. several hundred or something like this. But in current situation, I have several Million data samples and I will have more in the future.
I am afraid that we can not put all the data (such a big volumn) into memory based data structure Map.
Any comments or ideas? I am looking for some other ways which consume less memory (maybe we only store a part of the data set into Map?), and which also does not degrade performance too much.
regards,
George
|
|
|
|
|
is processing time a constraint for you?
means, if the logic takes suficient time, then, is it ok?
|
|
|
|
|
Thanks chandu004,
I want to find a balanced solution between memory footprint and processing time. To tell the truth, the memory can not hold all the data, maybe only 2% of the data. Any ideas?
regards,
George
|
|
|
|
|
here i have an idea. but not sure about the processing time complexities. we have to work them out practically and see.
George_George wrote: memory can not hold all the data
thats true.
but i think that, memory can very well hold 1000 structures of the following type.
struct linkedlist
{
linkedlist * prev;
ULONG value;
linkedlist *next;
};
//the size comes here to be 4*3*1000(max)bytes.
1.define a linked list.
2.take care such that, when ever, any item is added into the linked list, and the count is >1000, delete the last one.
3.now, read each value from the list and insert it just in between the two values, of which, one is greater and the other is smaller.
4.in this case, at any point of time, the largest 1000 values will be handled by the linked list.
i hope, this algorithm is suitable for your application.
or if you fell that, iam wrong, please try to correct me.
thank you.
|
|
|
|
|
Thanks chandu004,
I can understand that your solution could work and does not consumes too much memory. And I want to confirm that you need to sort the linked list by the value element, right?
But I doubt the performance of your algorithm, because I think we could save time to do a sorting (I want to largest 1000 values, and they do not need to be sorted). But I do not have smart ideas about how to optimize the performance of your algorithm. I hope you or other people could provide better ideas to make enhancement.
regards,
George
|
|
|
|
|
George_George wrote: I want to largest 1000 values, and they do not need to be sorted
thats fine, but unless we have the latest 1000 elements sorted, we cannot insert 1001 st element at the appropriate place.
any way, here i could workout a rough algorithm. please go through it.
1.maintain the head and tail of the linked list in some global variables.
2.say we already have some values in the list as
207,30,29,21,......,5.
3.now in this case, we know that, the max element is 207(HEAD) and min element is 5 (TAIL).
4.now, in this case, if we get an element smaller than 5, we can directly discard it because, it is nomore eligible to fit into the top 1000.
5.if we get an element say, 25,
while(linklist->value>element)
linklist=linklist->next;
6.now insert it there, and delete the link to the last element, thereby maintaining the list size to 1000.
7.in general, whenever any element is inserted into the list, then delete the last node and make its previous as the last.
thanks for such an interesting post and if it is possible to send the file(the million values file) then i shall try to implement this algorithm.
otherwise, i shall generate one such file with random numbers and see.
BTW, can you tell me the size of your file in GB or TB
|
|
|
|
|
Thanks chandu004,
The size of data is tens of G.
Your solution should work. Thanks. I am thinking whehter your method could be improved by reading more data into memory? Like, maintain 10000 data in the linked list? Is it better? I do not know whether you have better ways to improve it (I mean performance).
regards,
George
|
|
|
|
|
If anything, I think maintaining 10000 values would be worse, as the average and worst-case insertion times would increase, while I can see no real tangible benefit.
|
|
|
|
|
Thanks Cyrilix,
I also agree.
regards,
George
|
|
|
|
|
no using 10000 nodes would in no way increase hte performance, but increases the complexity, because, insertions and traversal depth will be more.
any way, give me three days time and i shall get back to you with my algorithm, which we can post here and discuss on improvising it.
or if you have already sketched the algorithm, then please post it to me i shall give my ideas on it.
|
|
|
|
|
Thanks chandu004,
I have a new idea. I want to use STL nth_element to select the largest 1000 elements from N elements. And I will divide the several G elements into tens of groups and each group has N elements. How do you think of this solution.
I heard the time complexity of nth_element is O(n), but actually I do not believe it. Do you know how nth_element could be implemented in O(n)?
regards,
George
|
|
|
|
|
George_George wrote: I think sorting the several M data in memory is not feasible.
Sure it is, and in only a few seconds. For example, using qsort() I sorted an array of 1,000,000 integers in ~2 seconds, and 2,000,000 integers took ~4 seconds.
So, by "not feasible", did you mean "not possible," or "not in an efficient manner?"
"Normal is getting dressed in clothes that you buy for work and driving through traffic in a car that you are still paying for, in order to get to the job you need to pay for the clothes and the car and the house you leave vacant all day so you can afford to live in it." - Ellen Goodman
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
|
|
|
|
|
It seems to me like it is very feasible as well. Say, you have 10 million integers, that's 10 000 000 * 4 bytes, so 40 MB in an array. That's nothing!
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
