Revision as of 03:46, 19 April 2019 edit TruthBuster21223 (talk \| contribs) 159 edits Pointed out that alias structure is not unique ← Previous edit		Revision as of 20:00, 26 September 2019 edit undo Tamfang (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 59,063 edits →Table generation Next edit →
Line 36: The Alias structure is not unique. As the lookup procedure is slightly faster if {{math\|''y'' < ''U<sub>i</sub>''}} (because {{mvar\|K<sub>i</sub>}} does not need to be consulted), one goal during table generation is to maximize the sum of the {{mvar\|U<sub>i</sub>}}. Doing this optimally turns out to be [[NP hard]],<ref name=marsaglia/>{{Rp\|6}} but a “[[~~Robin~~greedy ~~Hood]]” [[heuristic~~algorithm]] comes reasonably close: rob from the richest and give to the poorest. That is, at each step choose the largest {{mvar\|U<sub>i</sub>}} and the smallest {{mvar\|U<sub>j</sub>}}. Because this requires sorting the {{mvar\|U<sub>i</sub>}}, it requires {{math\|''O''(''n'' log ''n'')}} time. ==Efficiency==

Alias method: Difference between revisions