loicfevrier
Re:Ask HN: Fast sampling and update of weighted items? (data structure...
on Wednesday March 25, 2009 @04:45PM (#532404)
Which language are you using ? Matlab, C/C++ ?
What would be an estimate of N : 10^3, 10^6, 10^9 ?
Re:Ask HN: Fast sampling and update of weighted items? (data structure...
on Wednesday March 25, 2009 @04:44PM (#532401)
Exact, I forgot that point.
Re:Ask HN: Fast sampling and update of weighted items? (data structure...
on Wednesday March 25, 2009 @03:32PM (#532305)
It means that K is much smaller that N.
Because if K is a O(N) then doing an update in O(log n) is not good, it is better to rebuild the whole strcuture in O(n).
Re:Ask HN: Fast sampling and update of weighted items? (data structure...
on Wednesday March 25, 2009 @03:30PM (#532299)
Red-black trees are far too complex for this simple task :
just use any binary balanced tree so that the maximum height is O(log n). (red-black trees will work but take any one you want, red-black tree are slow)
On each node you store two numbers :
- sum of the weights at the left
- sum of the weights at the right
Want you want to choose an item just explore the tree and for each node choose left or right according to the two weights.
==> O(log n)
If you update an item you'll need to update all the weight up to the root of the tree.
==> O(log n) for each update
Re:Ask HN: Fast sampling and update of weighted items? (data structure...
on Wednesday March 25, 2009 @03:29PM (#532296)
But you will need to re-compute the sum each time you are doing an update wich takes O(n).
You can use Binary Indexed Trees to do that efficiently : http://www.topcoder.com/tc?module=Static&d1=tutorials...