This is the 11th day of my participation in the August Wenwen Challenge.More challenges in August

About the author: Wu Kong, 8 years of experience in Internet development and architecture, explains distributed, architecture design, Java core technology with stories. Author of “JVM Performance Optimization Practice” column, open source “Spring Cloud Practice PassJava” project, public account: Wukong chat architecture. This article is available at www.passjava.cn

Today I met a problem of equal distribution, and I would like to share my solution.

Example: 5 apples: a1, B1, C1, D1, E1, assigned to 3 warriors: ABC, the number is ABC, to achieve random and equal distribution. Expected result: A=[A1,d1], B=[B1, E1], C=[C1].

Thinking: the thinking of using the hash algorithm, give warriors and apple number, traverse the apple, and then use the serial number of the apple % 3, the remainder came in the form of serial number of the mighty, and then put the apple assigned to the warriors. This is the idea of a sub-database. The current code has been implemented.

for (i = 0; I < total number of apples; I++) {mapping table = [The word "apple"=> Apple array [I],"Warriors"=> Array of warriors [I % total warriors],];// Store the mapping in the arrayArray_push (list of mappings, mappings); }returnMapping table;Copy the code

Results:

Mapping table = [[The word "apple" => a1,
         "Warriors" => A,
	],
	[
         The word "apple" => b1,
          "Warriors" => B,
	],
	[
         The word "apple" => c1,
         "Warriors" => C,
	],
	[
         The word "apple" => d1,
         "Warriors" => A,
	],
	[
         The word "apple" => e1,
         "Warriors" => B,
	],
]
Copy the code

Then you go through the map, and you give the warriors apples. It’s not what you’d expect from an array, but it’s enough for your work.

Disadvantages:

  • Detail 1: If there are two apples numbered F1, G1, and the array of apples is [f1, G1], the result is: A=[A1,d1,f1], B=[b1, E1, G1], C=[c1], the result is not uniform.
  • Detail 2: If ABC is assigned A maximum of 4, and A has already been assigned 4, the redistribution to him will exceed the limit.
  • Detail 3: If 5 apples are good or bad, the good apples are preferentially assigned, and the apples need to be sorted first.
  • Detail 4: There is no randomness, it is sorted according to the order of apples.

The following solutions are only in the scheme level, not coding, just for reference:

  • 答 案 : We can redistribute ABC by reversing the order of ABC.
  • Answer: is to add a layer of judgment, when full, the warrior is excluded, the dividend -1, take the remainder, the apple number % 2.
  • Answer: It is to rank apples in order of good and bad.
  • 解 析 : Shuffle the apple array.

In addition, I looked at the ordered set zset of Redis, and found that it can also be realized, but it is not the idea of redundancy. The score of the ordered set is used to sort the warriors. After allocating an apple, the score is added by one and then allocated to the warriors with the lowest score. Because the redis mirror used in the work is 2.8, and the highest score and the lowest score of Zset need more than 5.0, after the interview with the local redis abstract algorithm to solve this problem.