Welcome, guest! Please login or register.

    * Shoutbox

    RefreshHistory
    • puta loca: or what section can i ask this
      Today at 05:45:08 AM
    • puta loca: does someoen has platinum ps v2 files?
      Today at 05:44:59 AM
    • w azza 3: server down??
      Today at 05:07:47 AM
    • charmie: rippppppppppppppppppppppppppppppppppppppppppppppp
      May 20, 2018, 09:03:41 PM
    • Tesco Value: eco reset? :o
      May 20, 2018, 08:54:27 PM
    • Tesco Value: aw is server down? :P
      May 20, 2018, 08:54:03 PM
    • mandmgalaxy: is the game down?
      May 20, 2018, 08:05:07 PM
    • bliss death: i believe 95% of the community disliked this change heavily as it came out of nowhere. and the fact you clear ironmen banks as well. terrible change. disappointed.
      May 20, 2018, 06:08:36 PM
    • bliss death: just wondering when the server is gonna be fixed and reverted
      May 20, 2018, 06:07:36 PM
    • Saltyspade10: I'll be back ;)
      May 15, 2018, 04:43:53 PM
    • Nunubuffs:[link]
      May 15, 2018, 12:06:25 PM
    • Nunubuffs: .info god
      May 15, 2018, 12:05:40 PM
    • Nunubuffs: Www.scaperune
      May 15, 2018, 12:05:25 PM
    • Nunubuffs: Www.scaperune
      May 15, 2018, 12:05:18 PM
    • Wilkooo: Meep meep
      May 15, 2018, 04:49:58 AM
    • FoHammer: Checkout my thread here we're now live: [link]
      May 14, 2018, 08:26:59 PM
    • FoHammer: Beemonumerouno
      May 14, 2018, 08:26:25 PM
    • DeathsChaos9::|
      May 14, 2018, 07:46:09 PM
    • Service.Man: Hi guys. I've just made a new account and downloaded the server - Still can't log in. Any tips?
      May 14, 2018, 01:37:43 AM
    • beemonumerouno: where can i ask if someone has a good custom server for free?
      May 11, 2018, 04:00:25 PM

    Author Topic: Parallel Execution of Mutators on Abstract Data Structures  (Read 741 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