Is the approach of 'just try it and if it goes badly fix it' doable?
mid = (lo + hi) / 2;
if ((mid <= lo) || (mid >= hi)) {
Fix it
}
John Hascall
IT Services
Iowa State Univ.
> On Sep 24, 2014, at 11:49 AM, RSmith <[email protected]> wrote:
>
> I'm trying to find what the limit is for dividing in terms of accuracy.
>
> Basically I have one program that inserts values to a table and determine
> sort order using one standard trick that has a REAL column named "SortOrder"
> which gets the value Highest_previous_value+1 if an insert happens with
> something that needs to be sorted at the end of the table.
>
> For any other position, the SortOrder gets assigned the value:
> ((Prev.Sortorder + Next.Sortorder) / 2)
>
> So to be clear (in case anyone is not familiar with this method), let's start
> with a small table with 1 item added like this:
>
> ID | SortOrder | Data
> 1 | 1 | 'First Row'
>
> Adding two new rows to the end every time will use previous highest
> SortOrder+1 so that the result is:
>
> ID | SortOrder | Data
> 1 | 1 | 'First Row'
> 2 | 2 | 'Eventual Fourth Row'
> 3 | 3 | 'Last Row'
>
> Adding a new row that should Sort in between IDs 1 and 2 above will take
> those SortOrders and find a new Order value by dividing the total for IDs 1
> and 2 (=3) by 2 (=1.5):
>
> ID | SortOrder | Data
> 1 | 1 | 'First Row'
> 2 | 2 | 'Eventual Fourth Row'
> 3 | 3 | 'Last Row'
> 4 | 1.5 | 'New Second Row'
>
> Adding another row that should Sort in between IDs 2 and 4 will again total
> and divide by 2 (=(2+1.5)/2):
>
> ID | SortOrder | Data
> 1 | 1 | 'First Row'
> 2 | 2 | 'Eventual Fourth Row'
> 3 | 3 | 'Last Row'
> 4 | 1.5 | 'New Second Row'
> 5 | 1.75| 'New Third Row'
>
> So that if the Query 'SELECT Data FROM t ORDER BY SortOrder' executes it goes
> like this:
>
> Data
> 'First Row'
> 'New Second Row'
> 'New Third Row'
> 'Eventual Fourth Row'
> 'Last Row'
>
>
> This seems like a clever method and I've seen it used a few times, but it
> really can break easily if you keep dividing by two, there is a very quick
> limit in accuracy where one value can no longer be divided by two
> meanigfully. In 64-bit Floating point Math that limit is very far away, quite
> a few iterations (assuming normal floating point mantissa accuracy - the
> exponent size does not matter since any two such values will be adjacent in
> the same realm of magnitude and only the available real numbers in between
> them counts), but if inserts happen 2 to 3 times a second, and imagining for
> a moment that the sort might hit the same spot every time, many consecutive
> divs might be exhausted quick.
>
> The question is - how can I accurately establish how many
> total-then-divide-by-2's a set of co-values in 64-bit FP guise can withstand
> before the difference is too small to make sense to the sorter in SQLite?
>
> Reason: The fix is easy but costly on a large DB, sort and reassign
> SortOrders simply in Integer steps: 1, 2, 3 etc., but I want to establish how
> often this should be done, as little as possible preferred, but not so little
> as to allow the order to break or div0 errors or such.
>
>
>
> _______________________________________________
> sqlite-users mailing list
> [email protected]
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
