|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
@Morfildur:
(Note: I don't feel I know how C++ works really, completely out of the loop for years and years.)
How about wrapping your events into a new type that has everything needed inside so that you can write a comparison between two of those new types, then using std::priority_queue? Basically, you don't have that key that you set to the time in std::map to get stuff into an order, instead, because those new events can be compared themselves, the std::priority_queue stuff does the ordering. It hopefully does something super smart with trees so that things run nice on average. If you look at the top element, you'll go to sleep for a bit if it's not yet time to start that job.
Downside is that you can only use this if the rule about what's higher priority between two elements doesn't change with the current time. You can also only ever look at the top element.
|
So i'm trying to figure out d-heaps but I've been stuck on the same stupid problem
for two days. This is supposed to be how you get the parent node:
parent (i) = (i-1)/d, using truncating division
Either I am extremely stupid or it doesn't work, but when I try to
get the parent (in a 4heap) for index 8, which is 2 I get: (8-1)/4 = 1.75
What is up?
I've found several formulas to find the parent in dheaps, but none of them seem to work for 2-, 3- and 4-heaps. Is it even possible to have one formula that works for all of them?
|
sigh
Apparently if you use RegisterWindowMessage with PostMessage, it doesn't get passed through WndProc to a WindowsHook, but if you switch PostMessage with SendNotifyMessage, it does. I don't even....
|
On February 13 2015 08:36 Animzor wrote:
So i'm trying to figure out d-heaps but I've been stuck on the same stupid problem
for two days. This is supposed to be how you get the parent node:
parent (i) = (i-1)/d, using truncating division
Either I am extremely stupid or it doesn't work, but when I try to
get the parent (in a 4heap) for index 8, which is 2 I get: (8-1)/4 = 1.75
What is up?
I've found several formulas to find the parent in dheaps, but none of them seem to work for 2-, 3- and 4-heaps. Is it even possible to have one formula that works for all of them?
The first index is zero. Not one. Also the index is the floor() of that result if it wasn't clear.
|
On February 13 2015 08:48 zzdd wrote:Show nested quote +On February 13 2015 08:36 Animzor wrote:
So i'm trying to figure out d-heaps but I've been stuck on the same stupid problem
for two days. This is supposed to be how you get the parent node:
parent (i) = (i-1)/d, using truncating division
Either I am extremely stupid or it doesn't work, but when I try to
get the parent (in a 4heap) for index 8, which is 2 I get: (8-1)/4 = 1.75
What is up?
I've found several formulas to find the parent in dheaps, but none of them seem to work for 2-, 3- and 4-heaps. Is it even possible to have one formula that works for all of them? The first index is zero. Not one. Also the index is the floor() of that result if it wasn't clear.
oh fuck, I got things mixed up because the implementation in my assignment has to start with index 1.
Thanks!
|
Follow up question: If I change the formula to take into account the index starting at 1 I should get:
(i+1)/d
It seems to work for any index except 2. Since (2+1)/4 = 0.75 which is 0.
Any thoughts on how to fix this?
Edit: it doesn't work for any leftmost child. It's always .75
|
On February 12 2015 21:58 Morfildur wrote:
I have an interesting problem that I'm trying to think through:
At work we need a realtime scheduling system where events can be scheduled to happen e.g. 5 seconds from now or theoretically 5 month, 4 days, 3 hours, 2 minutes and 1 second from now, though most events are scheduled for at most a week in the future. The number of scheduled events potentially numbers in the 1000s for every single second, i.e. a span of 10 seconds can have a total of 50000+ scheduled events. Past events have to be processed as long as they aren't past their TTL, i.e. when the schedule misses 10s due to a restart or hiccup, all those events still have to get processed.
Until recently we used a database with a "update X set processed=workerid where processed is null" statement that the ~100 worker processes executed whenever they ran out of jobs. It was far too slow eventhough a garbage collector held the table as small as possible by removing all finished events. We then switched to a Redis based solution, which can handle it but occasionally runs into performance issues as well.
I've now decided that it would be a nice problem to use to get back into C++, so I've started developing a C++ service that takes care of the scheduling. I'm just thinking about how to store the data internally so it is efficient for those large numbers of events. The service just has 2 functions: ScheduleEvent and GetNextEvent. ScheduleEvent adds an event at any point in time, GetNextEvent returns the next scheduled event based on time, variable time-to-live and event priority
I'm currently using a std::map<int, std::vector<Item>*> with the map key being the timestamp and the vector containing the items, but I'm having trouble with the time it takes to seek through the vectors, especially after the workers stopped processing for a few seconds and many events went past their TTL.
How does that problem make you feel like it's a good idea to get into c++? I'm feeling like in some weird way that it's almost like a scale up vs a scale out solution in some way. Are you hoping that faster speed will somehow mean that you'll be able to keep up? What happens when the number of events double? Are you going to switch to assembly to make it even faster? If you are really trying to process that many events I'm thinking its time to start looking into ways to seriously scale out.
|
United States13132 Posts
On February 13 2015 09:22 Animzor wrote:
Follow up question: If I change the formula to take into account the index starting at 1 I should get:
(i+1)/d
It seems to work for any index except 2. Since (2+1)/4 = 0.75 which is 0.
Any thoughts on how to fix this?
Edit: it doesn't work for any leftmost child. It's always .75
If your index is shifted one to the right of normal then you want to add one after you divide.
|
On February 13 2015 10:05 Blitzkrieg0 wrote:Show nested quote +On February 13 2015 09:22 Animzor wrote:
Follow up question: If I change the formula to take into account the index starting at 1 I should get:
(i+1)/d
It seems to work for any index except 2. Since (2+1)/4 = 0.75 which is 0.
Any thoughts on how to fix this?
Edit: it doesn't work for any leftmost child. It's always .75 If your index is shifted one to the right of normal then you want to add one after you divide.
That works for the leftmost child, but the rest:
(2/4)+1 = 1.5
(3/4)+1 = 1.75
(4/4)+1 = 2
(5/4)+1 = 2.25
|
United States13132 Posts
On February 13 2015 10:28 Animzor wrote:Show nested quote +On February 13 2015 10:05 Blitzkrieg0 wrote:On February 13 2015 09:22 Animzor wrote:
Follow up question: If I change the formula to take into account the index starting at 1 I should get:
(i+1)/d
It seems to work for any index except 2. Since (2+1)/4 = 0.75 which is 0.
Any thoughts on how to fix this?
Edit: it doesn't work for any leftmost child. It's always .75 If your index is shifted one to the right of normal then you want to add one after you divide. That works for the leftmost child, but the rest: (2/4)+1 = 1.5 (3/4)+1 = 1.75 (4/4)+1 = 2 (5/4)+1 = 2.25
Are you not doing integer division? If you aren't you can just floor it before you add the one.
You have an algorithm that solves your problem for the index starting at 0. Do the algorithm and then add one to the result so that your index starts at 1 instead of 0 is the logic here. If it doesn't work then the algorithm doesn't work for starting at index 0.
|
On February 13 2015 10:31 Blitzkrieg0 wrote:Show nested quote +On February 13 2015 10:28 Animzor wrote:On February 13 2015 10:05 Blitzkrieg0 wrote:On February 13 2015 09:22 Animzor wrote:
Follow up question: If I change the formula to take into account the index starting at 1 I should get:
(i+1)/d
It seems to work for any index except 2. Since (2+1)/4 = 0.75 which is 0.
Any thoughts on how to fix this?
Edit: it doesn't work for any leftmost child. It's always .75 If your index is shifted one to the right of normal then you want to add one after you divide. That works for the leftmost child, but the rest: (2/4)+1 = 1.5 (3/4)+1 = 1.75 (4/4)+1 = 2 (5/4)+1 = 2.25 Are you not doing integer division? If you aren't you can just floor it before you add the one. You have an algorithm that solves your problem for the index starting at 0. Do the algorithm and then add one to the result so that your index starts at 1 instead of 0 is the logic here. If it doesn't work then the algorithm doesn't work for starting at index 0.
That's it! Thanks a lot.
Edit: there were some test cases where it didn't work. But I tried changing it to (i-2)/d and it worked.
|
Bisutopia19297 Posts
I need RHEL7 password help please!
First I edit pwquality.conf because its updated values should affect /etc/pam.d/system-auth. Next I'm running authconfig --updateall
The update call is not reading from pwquality.conf and is setting system-auth to different values. Any help on this would be amazing. Thank you!
|
|
|
Bisutopia19297 Posts
On February 13 2015 22:33 Manit0u wrote:Show nested quote +On February 13 2015 22:29 BisuDagger wrote:I need RHEL7 password help please! First I edit pwquality.conf because its updated values should affect /etc/pam.d/system-auth. Next I'm running authconfig --updateall The update call is not reading from pwquality.conf and is setting system-auth to different values. Any help on this would be amazing. Thank you! Could it be related to this? https://github.com/OpenSCAP/scap-security-guide/issues/282
It would be, but I concluded from that discussion the issue had been fixed and as long as I update pwquality.conf I would be fine.
|
|
|
Bisutopia19297 Posts
From what I gather, athconfig --updateall doesn't write the files but resets them instead... Odd.
It resets the pam files which is fine. They are all auto-generated and pwquality.conf remains untouched.
|
Bisutopia19297 Posts
Unfortunately that's not the fix. No editing in system-auth-ac is allowed since it will be overwritten.
|
Bisutopia19297 Posts
Problem Resolved. SCAP scanner just runs errors atm.
|
anyone linux users that are believers in vim here? I'm too used to using windows text based editors -_-
|
|
|
|
|
|
|
|
EPT
