Click here to Skip to main content
15,887,175 members
Home / Discussions / Algorithms
   

Algorithms

 
GeneralRe: Association Rule Algorithm:dynamic god capabilities. Pin
shuga28-Nov-15 17:57
shuga28-Nov-15 17:57 
GeneralRe: Association Rule Algorithm:dynamic god capabilities. Pin
shuga28-Nov-15 17:57
shuga28-Nov-15 17:57 
QuestionHow do I solve the recurrence T(n) = T (n - 1) + c substitution method? Pin
axeemg17-Nov-15 4:12
axeemg17-Nov-15 4:12 
AnswerRe: How do I solve the recurrence T(n) = T (n - 1) + c substitution method? Pin
Patrice T17-Nov-15 17:53
mvePatrice T17-Nov-15 17:53 
QuestionAlgorithm query + request Pin
Member 1214387716-Nov-15 6:53
Member 1214387716-Nov-15 6:53 
AnswerRe: Algorithm query + request Pin
Chris Losinger16-Nov-15 7:01
professionalChris Losinger16-Nov-15 7:01 
AnswerRe: Algorithm query + request Pin
Patrice T17-Nov-15 18:00
mvePatrice T17-Nov-15 18:00 
GeneralHash table load factor Pin
Member 1180386012-Nov-15 13:04
Member 1180386012-Nov-15 13:04 
Hi.

I was recently interested in literature regarding what a good hash table load factor is for rehashing. Wikipedia mentions 0,7, 0,75 and 2/3, but with no explanation as to why performance degrades at these numbers.

The problem intrigued me, and I came to the conclusion that, mathematically speaking, the load factor threshold is at exactly log 2 (~0,7), which I found rather beautiful in it's own way.

I am posting this in case somebody else finds it interesting as I could not find any reference to a similar solution. Please also reply if you find any errors.

---------------------------------------

Chaining can be avoided and branch prediction exploited by predicting if a bucket is empty or not. A bucket is probably empty if the probability of it being empty exceeds 0,5.

Let s represent the size and n the number of keys added. Using the binomial theorem, the probability of a bucket being empty is:

P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0).

Thus, a bucket is probably empty if there are less than

log(2)/log(s/(s - 1)) keys.

As s reaches infinity and if the number of keys added is such that P(0) = 0,5, then n/s approaches log(2) rapidly:

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0,7.
QuestionAlgorithm needed to find a point on A4 size plane Pin
Member 1213438812-Nov-15 3:45
Member 1213438812-Nov-15 3:45 
AnswerRe: Algorithm needed to find a point on A4 size plane Pin
Richard Deeming12-Nov-15 4:05
mveRichard Deeming12-Nov-15 4:05 
AnswerRe: Algorithm needed to find a point on A4 size plane Pin
Chris Maunder12-Nov-15 4:15
cofounderChris Maunder12-Nov-15 4:15 
QuestionFastest way to count nested loops Pin
Member 113783027-Nov-15 2:32
Member 113783027-Nov-15 2:32 
AnswerRe: Fastest way to count nested loops Pin
Patrice T7-Nov-15 4:57
mvePatrice T7-Nov-15 4:57 
GeneralRe: Fastest way to count nested loops Pin
Member 113783027-Nov-15 5:02
Member 113783027-Nov-15 5:02 
GeneralRe: Fastest way to count nested loops Pin
PIEBALDconsult7-Nov-15 5:18
mvePIEBALDconsult7-Nov-15 5:18 
GeneralRe: Fastest way to count nested loops Pin
Member 113783027-Nov-15 5:36
Member 113783027-Nov-15 5:36 
GeneralRe: Fastest way to count nested loops Pin
Patrice T7-Nov-15 7:51
mvePatrice T7-Nov-15 7:51 
GeneralRe: Fastest way to count nested loops Pin
Patrice T7-Nov-15 8:16
mvePatrice T7-Nov-15 8:16 
GeneralRe: Fastest way to count nested loops Pin
Member 113783027-Nov-15 8:27
Member 113783027-Nov-15 8:27 
GeneralRe: Fastest way to count nested loops Pin
Patrice T7-Nov-15 8:52
mvePatrice T7-Nov-15 8:52 
GeneralRe: Fastest way to count nested loops Pin
Member 113783027-Nov-15 9:08
Member 113783027-Nov-15 9:08 
GeneralRe: Fastest way to count nested loops Pin
Patrice T7-Nov-15 9:19
mvePatrice T7-Nov-15 9:19 
GeneralRe: Fastest way to count nested loops Pin
harold aptroot7-Nov-15 5:20
harold aptroot7-Nov-15 5:20 
AnswerRe: Fastest way to count nested loops Pin
Luc Pattyn3-Jan-16 6:37
sitebuilderLuc Pattyn3-Jan-16 6:37 
Questionhow do you calculate a primitive operation in algorithm analysis Pin
Member 118975665-Nov-15 21:15
Member 118975665-Nov-15 21:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.