|
When you refer to a local copy of the list, do you mean a copy local to each worker thread, or local to the worker module, (all worker threads can access)?
If you mean local to each worker thread, then that becomes expensive creating a deep copy of the list every time a worker needs to reference it.
Do I misunderstand?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
A shallow copy does the trick. jschell doesn't want to call this a shallow copy, whatever. What I meant, and what the whole thread has always been about, is assigning the list to a local variable, and never editing its contents, only replacing the whole thing. The list which a reader is iterating over does not change since it has an .. even shallower f***ing copy, whatever the f*** you want to call it. Copy of the pointer. They can update that when they're ready for it to change.
The list is never modified anyway, only replaced. At least that was the premise of this sub-thread stared by jschell
modified 29-Dec-23 11:32am.
|
|
|
|
|
Shallow copy of the list?
No rebuild the entire list brand new.
|
|
|
|
|
Threads take a copy of the reference to the list. Making a new list builds it brand new. There is no reason for threads to make a deep copy since the list, once made, never changes (only replaced as a whole).
E: why are you making me re-explain your own idea back to you anyway? You know how this works, you suggested it.
modified 29-Dec-23 11:19am.
|
|
|
|
|
|
Fine. You're not wrong, but you didn't have to be an ass about it. But that's nothing new for you.
|
|
|
|
|
Not sure how I am being an ass.
You brought up shallow copy which was not in any way relevant. I can only respond to what you posted.
Best I could guess was that you were using a different definition of shallow copy than I was. So I defined the term.
|
|
|
|
|
Richard Andrew x64 wrote: so that would lead to exceptions caused by changing the list out from under them.
That cannot happen.
Per your original description the worker threads do not modify it.
The management thread creates a new list. The worker threads never use that list until it is done and the management thread is done with it.
Richard Andrew x64 wrote: seeing the new version of the list while other threads are still working with data from the old version of the list.
I think that requirement is going to end up requiring additional locking.
Say you look up prices in a list. Then an execution flow looks like this
Worker1: Gets price X (v1) from list. Continues work
Management: rebuild list (simple lock)
Worker2: Starts (simple lock gone) and gets price X (v2) from list.
Worker1: Finishes work with v1
Worker2: Finishes work with v2
|
|
|
|
|
jschell wrote: That cannot happen.
Not even if the worker thread is in the middle of enumerating the list?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Richard Andrew x64 wrote: enumerating the list?
Correct.
The Management thread creates a new list. Completely new. It does not modify nor touch the old list in any way.
The worker threads, are using the old list. Because they copied the pointer, the old list is the only one that they can use. The old list is not modified.
The pointer copy is the key to this behavior.
|
|
|
|
|
Yes, you're right, by George.
So that implies that the reference assignment itself is atomic?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Richard Andrew x64 wrote: So that implies that the reference assignment itself is atomic?
Yes that must be the case.
For java and C# it is.
Best I can tell in C++ the answer is sort of. Apparently it depends on the execution environment. But there is std:atomic.
I wondered, when this thread started, if it was possible to have a language that supports threads where assignment was not atomic. (C++ the language does not support threads.)
|
|
|
|
|
Without knowing frequencies, the size of the "work unit", the implications of returning a "busy" signal versus "locking", it's hard to make a thoughtful recommendation.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
Appreciate you chiming in anyway. The Slim Reader/Writer lock provides for that by offering methods that acquire locks with timeout values.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
So far, I see no evidence that the list has to be "protected" at all. If it's "updates"; they should be atomic. If it's inserts, the caller picks it up in the next "list query". If you're not using lists as lists, maybe you should be using a concurrent dictionary. If you don't like dictionaries, wrap it to make it look like a list (keys, values or key value pairs).
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
T(n)=c if n=1
=2T(n-1)+d if n>1
Find the value of T(n) and thus the time complexity.
My attempt at it got stuck.
T(n)=4T(n-2)+3d
T(n)=8T(n-3)+7d
..
..
..
T(n)=8T(n-k)+7d
It can't be solved further.
|
|
|
|
|
Quote: It can't be solved further
This does not help us in any way or format, why can it not be solved further, did it freeze, were there an error etc. etc.
|
|
|
|
|
Start writing things out more fully then look for the pattern in terms of n .
T(1) = c
T(2) = 2T(1) + d
T(2) = 2c + d -------- take this
|
T(3) = 2T(2) + d |
|
____________| and put it here
|
/------\
T(3) = 2(2c + d) + d
T(3) = 4c + 2d + d
T(3) = 4c + 3d
T(4) = 2T(3) + d
T(4) = 2(4c + 3d) + d
T(4) = 8c + 6d + d
T(4) = 8c + 7d
T(5) = 2T(4) + d
T(5) = 2(8c + 7d) + d
T(5) = 16c + 14d + d
T(5) = 16c + 15d
"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
"I don't drink any more... then again, I don't drink any less." - Mike Mullikins uncle
|
|
|
|
|
Googling suggests that time complexity requires 'code'. So as a starting point doesn't one need to write the recursive function first?
|
|
|
|
|
A colleague has asked for assistance with the problem stated below. I have searched and tried to create a solution without success. Another colleague suggested I post on this forum. The preferred approach would be in msAccess/vba, but any advice appreciated.
The problem:
Given a set of N participants, divide the participants into teams of m members. There are a number of Activities that take place in Sessions. Assign Teams to each session*activity such that no participant/member is assigned more than once in session, and no participant/member is in same activity more than once. Each team can only participate in 1 activity.
For testing suppose there a 4 activities that occur in 4 sessions, and 8 participants in teams of 2.Is there an algorithmic solution for 4x4 and 2. The underlying question is--is there a scalable solution beyond 4x4 and 2?
Manually, with 8 participants A,B,C,D,E,F,G,H - there is a solution
......... Activities
......... 1 2 3 4
Session 1 AE-CF-DG-BH
Session 2 CG-AH-BE-DF
Session 3 DH-BG-AF-CE
Session 4 BF-DE-CH-AG
modified 3-Nov-23 11:34am.
|
|
|
|
|
Reminds of some companies: send you on courses you don't need to fulfill the "educational quota". May as well be talking colored marbles.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
So, you want us to do your homework for you; sorry, that's not what this site is for. And looking at your profile you have been a member long enough to know that.
|
|
|
|
|
I'm not asking for you or anyone to do homework. My interest is really whether this is a problem that fits a "family of problem types with an algorithmic solution". I have seen picking marbles etc and how many ways can you do X, but I found this particular problem more complex. Any advice as to how to approach the problem would be helpful.
I do recognize there are 16 teams (4x4) in a solution and that with 8 participants, there are 28 unique teams. But it's not just selecting 16 out of 28.
|
|
|
|
|
You have all the information you need in the question. It even provides you with sample data to work out first (4x4 and 2). S otry to draw some diagrams to see how you can fit the respective teams into the different activitie, and if there is a common thread to get to the answer.
|
|
|
|
|
Hello!
I need to implement an algorithm to create round-robin tournament schedules, but with the constraint that up to 2 teams – that may play in different leagues – might share the same field on the same time slot of the week, so they must be never be scheduled to play at their home field in the same round of their league schedule.
Simple example:
leagueA = [
TeamA(plays at FieldA on Sunday),
TeamB(plays at FieldB on Sunday),
TeamC(plays at FieldA on Saturday),
TeamD(plays at FieldD on Saturday)
]
leagueB = [
TeamE(plays at FieldA on Sunday),
TeamF(plays at FieldF on Sunday),
TeamG(plays at FieldG on Saturday),
TeamH(plays at FieldF on Saturday)
]
I was thinking of generating the schedule for leagueA with the circle algorithm alternating home and away at each round as described in the linked article, and then to approach the scheduling for leagueB by prefilling the slots for the teams that share the field with teams in the other league somehow, but I'm not sure whether it's the right approach and how to actually implement it in a way that is guaranteed to produce schedules do not produce conflicts.
Any help would be highly appreciated!
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
