Welcome, guest! Please login or register.

    * Shoutbox

    RefreshHistory
    • wjfgg321: 사설토토사이트추천 첫충20프로%s t - 2 2 5 5. c o m%가입코드 s  t  8  8안전사설토토사이트추천 토토추천 사설토토추천사이트 토토사이트주소 해외토토사이트추천 스포츠토토사이트추천 사설토토추천 안전메이저토토사이트추천 안전사설토토추천
      Today at 07:55:33 PM
    • stCky:[link]
      Today at 07:15:22 PM
    • gordy9596: similar to this [link]
      Today at 05:58:11 PM
    • gordy9596: I'm looking for someone, who would like to make a 2006 remake like this?
      Today at 05:57:41 PM
    • gordy9596: Hi
      Today at 05:57:12 PM
    • `Discardedx2`: k
      Today at 03:47:14 AM
    • Travas: the 'ol welfare bear
      December 09, 2017, 11:51:16 PM
    • Travas: ah, grizzly
      December 09, 2017, 11:51:10 PM
    • Cole1497: im bout to pack me a can of grizzly and go ham on a bitch
      December 09, 2017, 11:14:20 PM
    • wailsalih: It's my day off I'm just smoke and pk please any staff look at my ip ban situation please
      December 09, 2017, 12:24:37 PM
    • wailsalih: Anyone staff here?
      December 09, 2017, 10:11:30 AM
    • wailsalih: I got banned one year ago cause I did something dumb pkags banned me he's still holding the grudge can someone help?
      December 09, 2017, 10:02:50 AM
    • juhta6: oi. where's the download link for rs2 317 client
      December 09, 2017, 08:15:45 AM
    • Striker Fox2: Yes Welcome
      December 09, 2017, 07:50:13 AM
    • Amcora: Welcome soulcist
      December 09, 2017, 06:50:08 AM
    • Daveite: Is there anyway to download this
      December 08, 2017, 08:53:47 PM
    • Daveite: I'm looking for a the runescape chicken model
      December 08, 2017, 08:53:28 PM
    • Daveite: I have a noob question
      December 08, 2017, 08:53:02 PM
    • Daveite: Hey guys
      December 08, 2017, 08:52:53 PM
    • DeathsChaos9: *sigh*
      December 08, 2017, 04:21:46 PM

    Author Topic: Parallel Execution of Mutators on Abstract Data Structures  (Read 706 times)

    0 Members and 1 Guest are viewing this topic.

    Offline_nova

    • Member
    • **
    • Posts: 31
    • Thanks: +10/-10
      • View Profile
    The jist:

    This algorithm is meant to calculate the order that mutators, or functions that modify data containers, must be executed in parallel without any race conditions. This assumes that all of the mutators being called are instantaneous and without step. Further expansion on that would require that mutators indicate an argument for their presidence. I have not worked on exactly how that would function but I imagine it wouldn't take too much thought.

    The concept for gaming in this algorithm works as follows:

    A). You have a mutator that moves a player north one tile.
    B). You have a mutator that changes the text a player has over their head to 'hello'.
    C). You have a mutator that moves a player south one tile.

    These mutators explicitly state their dependencies of an abstract data container. These dependencies are components. Components are logical organizations of data.

    A). Location
    B). HeadText
    C). Location

    A dependency is described as a pointer to these components which have a universal identifier. This algorithm only works if abstract data containers do not share components. You can describe these components as pointers then create a list of what dependencies a mutator operating on a data container will access and use the following code to calculate the order in which they have to be executed in parallel. If A, B, C are each mutator different data containers then they can be executed in parallel because they will have access to different data.

    However a generalization can be made. This generalization can be made at a macro level for the logical organization of data. This is possible because components of data containers do not have access to any other data container. If it is possible, it makes calculating the dependencies slightly more complex so this rule is employed to simplify the process. We can assume that mutator A and B would not share dependencies to data, and mutator B and C would not as well. However A and C would and therefore could not be ran in parallel in any case.

    O(N**2/2) (I believe, correct me if I'm wrong my math is terrible)

    The code

    Code: Java
    1.  
    2. importjava.util.ArrayDeque;
    3. importjava.util.ArrayList;
    4. importjava.util.HashSet;
    5. importjava.util.List;
    6. importjava.util.Queue;
    7. importjava.util.Random;
    8. importjava.util.Set;
    9.  
    10. /**
    11.  * @author hadyn
    12.  */
    13. publicclass Runner {
    14.  
    15.   privatestaticfinalint STATE_COUNT =5000;
    16.   privatestaticfinalint MUTATOR_COUNT =5000;
    17.   privatestaticfinalint MAXIMUM_DEPS =8;
    18.  
    19.   publicstaticvoid main(String... args){
    20.     State[] states =new State[STATE_COUNT];
    21.     for(int i =0; i < STATE_COUNT; i++){
    22.       states[i]=new State(i);
    23.     }
    24.  
    25.     Mutator[] mutators =new Mutator[MUTATOR_COUNT];
    26.     for(int i =0; i < MUTATOR_COUNT; i++){
    27.       mutators[i]=new Mutator(i);
    28.     }
    29.  
    30.     // Set up the dependencies.
    31.     Random random =newRandom();
    32.     for(int i =0; i < MUTATOR_COUNT; i++){
    33.       int count = random.nextInt(MAXIMUM_DEPS -1)+1;
    34.       for(int j =0; j < count; j++){
    35.         mutators[i].addDependency(states[random.nextInt(STATE_COUNT)]);
    36.       }
    37.     }
    38.  
    39.     // Start the process of determining which mutators to execute.
    40.     Queue<Mutator> queue =new ArrayDeque<>();
    41.     for(Mutator mutator : mutators){
    42.       queue.add(mutator);
    43.     }
    44.  
    45.     System.out.println("Starting...");
    46.     long startTime =System.currentTimeMillis();
    47.  
    48.     List<ExecutionSet> executionSets =new ArrayList<>();
    49.     int maximumSize =0;
    50.     while(!queue.isEmpty()){
    51.       ExecutionSet executionSet =new ExecutionSet();
    52.       executionSets.add(executionSet);
    53.  
    54.       Mutator start = queue.poll();
    55.       executionSet.addMutator(start.getId());
    56.       queue.add(start);                             // Append it back to the queue as a stopper.
    57.  
    58.       Set<Mutator> except =new HashSet<>();
    59.       except.addAll(start.getExcept());
    60.       int width =1;
    61.  
    62.       Mutator next;
    63.       while(!start.equals(next = queue.poll())){
    64.         if(except.contains(next)){
    65.           queue.add(next);
    66.           continue;
    67.         }
    68.         executionSet.addMutator(next.getId());
    69.         except.addAll(next.getExcept());
    70.         width++;
    71.       }
    72.       maximumSize =Math.max(width, maximumSize);
    73.     }
    74.  
    75.     long elapsed =System.currentTimeMillis()- startTime;
    76.     System.out.println("Elapsed (ms): "+ elapsed);
    77.     System.out.println("State count: "+ STATE_COUNT);
    78.     System.out.println("Mutator count: "+ MUTATOR_COUNT);
    79.     System.out.println("Maximum width: "+ maximumSize);
    80.     System.out.println("Maximum dependencies: "+ MAXIMUM_DEPS);
    81.  
    82.     System.out.println();
    83.  
    84.     System.out.println("Mutators");
    85.     System.out.println("--------");
    86.  
    87.     for(Mutator mutator : mutators){
    88.       System.out.println(mutator);
    89.     }
    90.  
    91.     System.out.println();
    92.  
    93.     System.out.println("Execution steps");
    94.     System.out.println("---------------");
    95.  
    96.     int step =0;
    97.     for(ExecutionSet executionSet : executionSets){
    98.       System.out.println("Step "+ step+++" | "+ executionSet);
    99.  
    100.     }
    101.   }
    102.  
    103.   privatestaticclass State {
    104.     int id;
    105.     Set<Mutator> mutators =new HashSet<>();
    106.  
    107.     State(int id){
    108.       this.id= id;
    109.     }
    110.  
    111.     publicvoid addRelationship(Mutator mutator){
    112.       mutators.add(mutator);
    113.     }
    114.  
    115.     public Set<Mutator> getMutators(){
    116.       return mutators;
    117.     }
    118.  
    119.     @Override publicint hashCode(){
    120.       int hashCode =1;
    121.       hashCode = hashCode *31+ id;
    122.       return hashCode;
    123.     }
    124.  
    125.     @Override publicboolean equals(Object obj){
    126.       if(obj ==null){
    127.         returnfalse;
    128.       }
    129.  
    130.       if(!(obj instanceof State)){
    131.         returnfalse;
    132.       }
    133.  
    134.       State state =(State) obj;
    135.       return id == state.id;
    136.     }
    137.  
    138.     @Override publicString toString(){
    139.       StringBuilder builder =new StringBuilder();
    140.       builder.append("State")
    141.         .append(' ')
    142.         .append(id);
    143.       return builder.toString();
    144.     }
    145.  
    146.     publicint getId(){
    147.       return id;
    148.     }
    149.   }
    150.  
    151.   privatestaticclass Mutator {
    152.     int id;
    153.     Set<State> states =new HashSet<>();
    154.     Set<Mutator> except;
    155.  
    156.     Mutator(int id){
    157.       this.id= id;
    158.     }
    159.  
    160.     publicint getId(){
    161.       return id;
    162.     }
    163.  
    164.     publicvoid addDependency(State state){
    165.       states.add(state);
    166.       state.addRelationship(this);
    167.     }
    168.  
    169.     public Set<Mutator> getExcept(){
    170.       if(except !=null){
    171.         return except;
    172.       }
    173.       Set<Mutator> results =new HashSet<>();
    174.       for(State state : states){
    175.         Set<Mutator> mutators = state.getMutators();
    176.         results.addAll(mutators);
    177.       }
    178.       results.remove(this);
    179.       except = results;
    180.       return results;
    181.     }
    182.  
    183.     @Override publicint hashCode(){
    184.       int hashCode =1;
    185.       hashCode = hashCode *31+ id;
    186.       return hashCode;
    187.     }
    188.  
    189.     @Override publicboolean equals(Object obj){
    190.       if(obj ==null){
    191.         returnfalse;
    192.       }
    193.  
    194.       if(!(obj instanceof Mutator)){
    195.         returnfalse;
    196.       }
    197.  
    198.       Mutator mutator =(Mutator) obj;
    199.       return id == mutator.id;
    200.     }
    201.  
    202.     @Override publicString toString(){
    203.       StringBuilder builder =new StringBuilder();
    204.       builder.append("Mutator ").append(id).append(" | ");
    205.  
    206.       boolean first =true;
    207.       for(State state : states){
    208.         if(!first){
    209.           builder.append(", ");
    210.         }
    211.         builder.append(state.getId());
    212.         first =false;
    213.       }
    214.  
    215.       return builder.toString();
    216.     }
    217.   }
    218.  
    219.   privatestaticclass ExecutionSet {
    220.     Set<Integer> mutatorIds =new HashSet<>();
    221.  
    222.     publicvoid addMutator(int id){
    223.       mutatorIds.add(id);
    224.     }
    225.  
    226.     @Override publicString toString(){
    227.       StringBuilder builder =new StringBuilder();
    228.       builder.append('{');
    229.       boolean first =true;
    230.       for(int mutatorId : mutatorIds){
    231.         if(!first){
    232.           builder.append(", ");
    233.         }
    234.         builder.append(mutatorId);
    235.         first =false;
    236.       }
    237.       builder.append('}');
    238.       return builder.toString();
    239.     }
    240.   }
    241. }
    242.  
    243.  
    « Last Edit: May 20, 2016, 08:54:49 PM by _nova »
    RS2Ad banner

     

    Copyright © 2017 MoparScape. All rights reserved.
    Powered by SMFPacks SEO Pro Mod |
    SimplePortal 2.3.5 © 2008-2012, SimplePortal