2020-09-22
Sep 23 In-Class Exercise Thread.
Post your solution here for the Sep 23 In-class Exercise.
Best,
Chris
Post your solution here for the Sep 23 In-class Exercise.
Best,
Chris
2020-09-23
The four points on the circle:
0, 0.25, 0.5, 0.75
10 random numbers:
[0.16, 0.67, 0.66, 0.03, 0.84, 0.39, 0.7, 0.25, 0.44, 0.36]
Mapping:
0: [0.03] 0.25: [0.36, 0.25] 0.5: [0.39, 0.44] 0.75: [0.66, 0.67, 0.7, 0.84]
New node: 0.65
(Edited: 2020-09-23) Values remapped: [0.66, 0.67]
The four points on the circle:
0, 0.25, 0.5, 0.75
10 random numbers:
[0.16, 0.67, 0.66, 0.03, 0.84, 0.39, 0.7, 0.25, 0.44, 0.36]
Mapping:
0: [0.03]
0.25: [0.36, 0.25]
0.5: [0.39, 0.44]
0.75: [0.66, 0.67, 0.7, 0.84]
New node: 0.65
Values remapped: [0.66, 0.67]
N, E, S, W
- In general Real numbers could be n*1, 0.25 + n*1, 0.5 + n*1, 0.75 + n*1; where n is an any number. For now, we can put n = 0 to get 0, 0.25, 0.5, 0.75
- 10 random numbers :: 0.1, 0.2, 0.28, 0.45, 0.55, 0.68, 0.79, 0.85, 0.94, 0.98;;
Mapping -
N - 0.1, 0.94, 0.98 E - 0.2, 0.28 S - 0.45, 0.55 W - 0.68, 0.79, 0.85
- New node M - 0.42;;
New Mapping -
N - 0.1, 0.94, 0.98 E - 0.2, 0.28 M - 0.45 - The key that gets remapped! S - 0.55 W - 0.68, 0.79, 0.85
N, E, S, W
*In general Real numbers could be n*1, 0.25 + n*1, 0.5 + n*1, 0.75 + n*1; where n is an any number.
For now, we can put n = 0 to get 0, 0.25, 0.5, 0.75
*10 random numbers :: 0.1, 0.2, 0.28, 0.45, 0.55, 0.68, 0.79, 0.85, 0.94, 0.98;;
Mapping -
N - 0.1, 0.94, 0.98
E - 0.2, 0.28
S - 0.45, 0.55
W - 0.68, 0.79, 0.85
*New node M - 0.42;;
New Mapping -
N - 0.1, 0.94, 0.98
E - 0.2, 0.28
M - 0.45 - The key that gets remapped!
S - 0.55
W - 0.68, 0.79, 0.85
1. 0, 1/4, 1/2, 3/4
2. If a new node is added, we expect k/(n+1) will need to change
So, say the 10 keys are 0.1, 0.2, 0.3, 0.4, 0.8, 0.7, 0.3, 0.2, 0.9, 0.6. The stored keys will look as follows:
0: {0.1, 0.9}
1/4: {0.2, 0.3, 0.2}
1/2: {0.4, 0.6}
3/4: {0.8, 0.7}
Say another new node location, 0.29 is added.
Our new server layout will look like this:
0: {0.1, 0.9}
1/4: {0.2, 0.2}
0.29: {0.3}
1/2: {0.4, 0.6}
3/4: {0.8, 0.7}
(Edited: 2020-09-23) 1.
0, 1/4, 1/2, 3/4
2.
If a new node is added, we expect k/(n+1) will need to change
So, say the 10 keys are 0.1, 0.2, 0.3, 0.4, 0.8, 0.7, 0.3, 0.2, 0.9, 0.6.
The stored keys will look as follows:
0: {0.1, 0.9}
1/4: {0.2, 0.3, 0.2}
1/2: {0.4, 0.6}
3/4: {0.8, 0.7}
Say another new node location, 0.29 is added.
Our new server layout will look like this:
0: {0.1, 0.9}
1/4: {0.2, 0.2}
0.29: {0.3}
1/2: {0.4, 0.6}
3/4: {0.8, 0.7}
1) Locations: 0.0, 0.25. 0.50, 0.75
Random numbers are
0.13 0.28
0.41 0.94
0.85 0.30
0.46 0.43
0.73 0.04
2) Keys stored 0.0 are {0.04,0.94}
Keys stored 0.25 are {0.28,0.13,0.30}
Keys stored 0.50 are {0.43,0.46,0.41}
Keys stored 0.75 are {0.85,0.73}
3) Random Node location Generated : 0.80
Keys remapped : 0.85
(Edited: 2020-09-23) 1) Locations: 0.0, 0.25. 0.50, 0.75
Random numbers are
0.13 0.28
0.41 0.94
0.85 0.30
0.46 0.43
0.73 0.04
2) Keys stored 0.0 are {0.04,0.94}
Keys stored 0.25 are {0.28,0.13,0.30}
Keys stored 0.50 are {0.43,0.46,0.41}
Keys stored 0.75 are {0.85,0.73}
3) Random Node location Generated : 0.80
Keys remapped : 0.85
1. N:0 E:0.25 S:0.5 W:0.75
2. N: 0.096, 0.08, 0.03 E: 0.34, 0.18 S: 0.48, 0.52 W: 0.81, 0.83, 0.76 3. New location SW: 0.53 0.52 is remapped to SW
1. N:0 E:0.25 S:0.5 W:0.75
2.
N: 0.096, 0.08, 0.03
E: 0.34, 0.18
S: 0.48, 0.52
W: 0.81, 0.83, 0.76
3.
New location SW: 0.53
0.52 is remapped to SW
4 nodes -> 0, 0.25, 0.5, 0.75
node-Key -> 0: 0.03
distribution 0.25: 0.30, 0.20, 0.21
0.50: 0.62, 0.52, 0.39
0.75: 0.63, 0.73, 0.81
New Node -> 0.16
Keys remapped -> 0.16: 0.20(Edited: 2020-09-23)
4 nodes -> 0, 0.25, 0.5, 0.75
node-Key -> 0: 0.03
distribution 0.25: 0.30, 0.20, 0.21
0.50: 0.62, 0.52, 0.39
0.75: 0.63, 0.73, 0.81
New Node -> 0.16
Keys remapped -> 0.16: 0.20
//Place four nodes at the N,S,E,W points of a circle. 0.0 0.25 0.50 0.75 //generate random 10 keys 0.1 0.2 0.3 0.4 0.5 0.55 0.6 0.7 0.8 0.9 //put the keys into the circle 0.0 => [0.1,0.9] 0.25 => [0.2,0.3] 0.50 => [0.4,0.5,0.55,0.6] 0.75 => [0.7,0.8]
//Pick a random new node location and add it to the ring. 0.0 => [0.1,0.9] 0.25 => [0.2,0.3] 0.50 => [0.4,0.5] 0.60 => [0.55,0.6] 0.75 => [0.7,0.8]
//new keys remapped [0.55,0.6] (k/n+1) = 10/(4+1) = 2 = count([0.55,0.6]) < 4 = (k-n)
conclusion: remapped keys much smaller than (k-n)(Edited: 2020-09-23)
//Place four nodes at the N,S,E,W points of a circle.
0.0
0.25
0.50
0.75
//generate random 10 keys
0.1
0.2
0.3
0.4
0.5
0.55
0.6
0.7
0.8
0.9
//put the keys into the circle
0.0 => [0.1,0.9]
0.25 => [0.2,0.3]
0.50 => [0.4,0.5,0.55,0.6]
0.75 => [0.7,0.8]
//Pick a random new node location and add it to the ring.
0.0 => [0.1,0.9]
0.25 => [0.2,0.3]
0.50 => [0.4,0.5]
<u>0.60 => [0.55,0.6]</u>
0.75 => [0.7,0.8]
//new keys remapped
[0.55,0.6]
(k/n+1) = 10/(4+1) = 2 = count([0.55,0.6]) < 4 = (k-n)
conclusion: remapped keys much smaller than (k-n)
Four nodes -> 0, 0.25, 0.50, 0.75
(Edited: 2020-09-23) Random keys -> 0.1, 0.15, 0.30, 0.45, 0.55, 0.65, 0.70, 0.80, 0.94, 0.99 0 => 0.1, 0.94, 0.99 0.25 => 0.15, 0.30 0.50 => 0.45, 0.55 0.75 => 0.65, 0.70, 0.80
a new node is added at 0.90 0 => 0.1, 0.99 0.25 => 0.15, 0.30 0.50 => 0.45, 0.55 0.75 => 0.65, 0.70, 0.80 0.90 => 0.94
0.94 was remapped from 0 to 0.90
Four nodes -> 0, 0.25, 0.50, 0.75
Random keys -> 0.1, 0.15, 0.30, 0.45, 0.55, 0.65, 0.70, 0.80, 0.94, 0.99
0 => 0.1, 0.94, 0.99
0.25 => 0.15, 0.30
0.50 => 0.45, 0.55
0.75 => 0.65, 0.70, 0.80
a new node is added at 0.90
0 => 0.1, 0.99
0.25 => 0.15, 0.30
0.50 => 0.45, 0.55
0.75 => 0.65, 0.70, 0.80
0.90 => 0.94
0.94 was remapped from 0 to 0.90
2020-09-26
0, 0.25, 0.5, 0.75
Generating 10 random numbers (using online random numbers generator): 0.23 0.87 0.50 0.49 0.85 0.72 0.53 0.66 0.04 0.05
Mapping [0] => 0.04, 0.05 [0.25] => 0.23 [0.5] => 0.50, 0.49, 0.53 [0.75] => 0.87, 0.85, 0.72, 0.66
New node at 0.86 0.87 and 0.85 will be remapped(Edited: 2020-09-26)
0, 0.25, 0.5, 0.75
Generating 10 random numbers (using online random numbers generator):
0.23
0.87
0.50
0.49
0.85
0.72
0.53
0.66
0.04
0.05
Mapping
[0] => 0.04, 0.05
[0.25] => 0.23
[0.5] => 0.50, 0.49, 0.53
[0.75] => 0.87, 0.85, 0.72, 0.66
New node at 0.86
0.87 and 0.85 will be remapped
(c) 2025 Yioop - PHP Search Engine